Topics in extremal graph theory and probabilistic combinatorics - Roberts, A (2018)
This thesis considers a variety of problems in Extremal Graph Theory and Probabilistic Combinatorics. Most of these problems are structural in nature, but some concern random reconstruction and parking problems. A matching in a bipartite graph G = (U, V, E) is a subset of the edges where no two edges meet, and each vertex from U is in an edge. A classical result is Hall’s Theorem [30] which gives necessary and sucient conditions for the existence of a matching. In Chapter 2 we give a generalisation of Hall’s Theorem: an (s, t)-matching in a bipartite graph G = (U, V, E) is a subset of the edges F such that each component of H = (U, V, F) is a tree with at most t edges and each vertex in U has s neighbours in H. We give sharp sucient neighbourhood-conditions for a bipartite graph to contain an (s, t)-matching. As a special case, we prove a conjecture of Bennett, Bonacina, Galesi, Huynh, Molloy and Wollan [6]. The classical stability theorem of Erdős and Simonovits [19] states that, for any fixed graph with chromatic number k+1 ≥ 3, the following holds: every n-vertex graph that is H-free and has within o(n2) of the maximal possible number of edges can be made into the k-partite Turán graph by adding and deleting o(n2) edges. In Chapter 3 we prove sharper quantitative results for graphs H with a critical edge, showing how the o(n2) terms depend on each other. In many cases, these results are optimal to within a constant factor. Tur´an’s Theorem [66] states that the Kk+1-free graph on n vertices with the most edges is the complete k-partite graph with balanced class sizes Tk(n), called the ‘Turán graph’. In Chapter 4 we consider a cycleequivalent result: Fix k 2 and let H be a graph with (H) = k + 1 containing a critical edge. For n suciently large, we show that the unique n-vertex H-free graph containing the maximum number of cycles is Tk(n). This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian [2]. The hypercube Qn = (V,E) is the graph with vertices V = {0, 1}n where vertices u, v are adjacent if they differ in exactly one co-ordinate (so Q2 is the square and Q3 is the cube). Harper’s Theorem [33] states that in a hypercube the Hamming balls have minimal vertex boundaries with respect to set size. In Chapter 5 we prove a stability-like result for Harper’s Theorem: if the vertex boundary of a set is close to minimal in the hypercube, then the set must be very close to a Hamming ball around some vertex. A common class of problem in Graph Theory is to attempt to reconstruct a graph from some collection of its subgraphs. In shotgun assembly we are given local information, in the form of the r-balls around vertices of a graph, or coloured r-balls if the graph has a colouring. In Chapter 6 we consider shotgun assembly of the hypercube - given the r-balls of a random q colouring of the vertices, can we reconstruct the colouring up to an automorphism with high probability? We show that for q ≥ 2, a colouring can be reconstructed with high probability from the 2-balls, and for q ≥ n 2+Θ(log -1 /2 n) , a colouring can be reconstructed with high probability from the 1-balls. In Chapter 7 we consider a parking problem. Independently at each point in Z, randomly place a car with probability p and otherwise place an empty parking space. Then let the cars drive around randomly until they find an empty parking space in which to park. How long does a car expect to drive before parking? Answering a question of Damron, Gravner, Junge, Lyu, and Sivakoff [12], we show that for p < 1/2 the expected journey length of a car is finite, and for p = 1/2 the expected journey length of a car by time t grows like t 3/4 up to polylogarithmic factors.