Return to search

Extremal combinatorics, graph limits and computational complexity

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}<sup>d</sup> 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<sub>m</sub> in Q<sub>d</sub>. Specifically, we show that for m &ge; 2 fixed and d large there exists a subgraph G of Q<sub>d</sub> of bounded average degree such that G does not contain a copy of Q<sub>m</sub> but, for every G' such that G &subne; G' &sube; Q<sub>d</sub>, the graph G' contains a copy of Q<sub>m</sub>. 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 &epsilon; &gt; 0 such that for all k and for n sufficiently large there is a collection of at most 2<sup>(1-&epsilon;)k</sup> 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&aacute;lv&ouml;lgyi and Patk&oacute;s. We also prove that there exists a constant c &isin; (0,1) such that the smallest such collection is of cardinality 2<sup>(1+o(1))<sup>ck</sup> </sup> for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q<sub>m</sub> in Q<sub>d</sub>. That is, we determine the minimum number of edges in a spanning subgraph G of Q<sub>d</sub> such that the edges of E(Q<sub>d</sub>)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q<sub>m</sub>. 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<sub>0</sub> 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<sub>0</sub> percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r &ge; 2, every percolating set in Q<sub>d</sub> has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollob&aacute;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;<sub>q</sub><sup>n</sup>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 (&epsilon;<sub>i</sub>)<sup>&infin;</sup><sub>i=1</sub> tending to zero such that, for all i &ge; 1, every weak &epsilon;<sub>i</sub>-regular partition of W has at least exp(&epsilon;<sub>i</sub><sup>-2</sup>/2<sup>5log&lowast;&epsilon;<sub>i</sub><sup>-2</sup></sup>) 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&aacute;sz and Szegedy. For positive integers p,q with p/q &VerticalSeparator;&ge; 2, a circular (p,q)-colouring of a graph G is a mapping V(G) &rarr; &Zopf;<sub>p</sub> such that any two adjacent vertices are mapped to elements of &Zopf;<sub>p</sub> 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 &le; p/q &LT; 4 and is PSPACE-complete for p/q &ge; 4.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:728769
Date January 2016
CreatorsNoel, Jonathan A.
ContributorsScott, Alex
PublisherUniversity of Oxford
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Sourcehttps://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b

Page generated in 0.002 seconds