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 ≥ 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 ⊊ G' ⊆ 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 ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2<sup>(1-ε)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á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<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 ≥ 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á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 𝒱(q,n) consisting of all subspaces of 𝔽<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 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(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 (ε<sub>i</sub>)<sup>∞</sup><sub>i=1</sub> tending to zero such that, for all i ≥ 1, every weak ε<sub>i</sub>-regular partition of W has at least exp(ε<sub>i</sub><sup>-2</sup>/2<sup>5log∗ε<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ász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤ<sub>p</sub> such that any two adjacent vertices are mapped to elements of ℤ<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 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:728769 |
| Date | January 2016 |
| Creators | Noel, Jonathan A. |
| Contributors | Scott, Alex |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b |
Page generated in 0.0155 seconds