Back to Search
Start Over
Extremal combinatorics, graph limits and computational complexity
- Publication Year :
- 2016
- Publisher :
- University of Oxford, 2016.
-
Abstract
- This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}<superscript>d</superscript> where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q<subscript>m</subscript> in Q<subscript>d</subscript>. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Q<subscript>d</subscript> of bounded average degree such that G does not contain a copy of Q<subscript>m</subscript> but, for every G' such that G &subne; G' ⊆ Q<subscript>d</subscript>, the graph G' contains a copy of Q<subscript>m</subscript>. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2<superscript>(1-ε)k</superscript> subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2<superscript>(1+o(1))<superscript>ck</superscript> </superscript> for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q<subscript>m</subscript> in Q<subscript>d</subscript>. That is, we determine the minimum number of edges in a spanning subgraph G of Q<subscript>d</subscript> such that the edges of E(Q<subscript>d</subscript>)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q<subscript>m</subscript>. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A<subscript>0</subscript> of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A<subscript>0</subscript> percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Q<subscript>d</subscript> has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset &Vscr;(q,n) consisting of all subspaces of &Fopf;<subscript>q</subscript><superscript>n</superscript>ordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in &Vscr;(q,n) and a bound on the size of the largest antichain in a p-random subset of &Vscr;(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (ε<subscript>i</subscript>)<superscript>∞</superscript><subscript>i=1</subscript> tending to zero such that, for all i ≥ 1, every weak ε<subscript>i</subscript>-regular partition of W has at least exp(ε<subscript>i</subscript><superscript>-2</superscript>/2<superscript>5log∗ε<subscript>i</subscript><superscript>-2</superscript></superscript>) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q &VerticalSeparator;≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → &Zopf;<subscript>p</subscript> such that any two adjacent vertices are mapped to elements of &Zopf;<subscript>p</subscript> at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q &LT; 4 and is PSPACE-complete for p/q ≥ 4.
- Subjects :
- 511
Combinatorial analysis
Computational complexity
Graph coloring
Graph theory
Combinatorial probabilities
Percolation (Statistical physics)--Mathematical models
Extremal problems (Mathematics)
Mathematics
Saturation Problems
Weak Saturation
Circular Colouring
Antichains in Random Posets
Sperner Theory
Bootstrap Percolation
Combinatorial Reconfiguration
Counting Antichains
Weak Regularity
Supersaturation in Posets
Graph Limits
Subjects
Details
- Language :
- English
- Database :
- British Library EThOS
- Publication Type :
- Dissertation/ Thesis
- Accession number :
- edsble.728769
- Document Type :
- Electronic Thesis or Dissertation