Cookies?
Library Header Image
LSE Theses Online London School of Economics web site

Extremal and probabilistic results for regular graphs

Davies, Ewan (2017) Extremal and probabilistic results for regular graphs. PhD thesis, The London School of Economics and Political Science (LSE).

[img]
Preview
Text - Submitted Version
Download (1MB) | Preview
Identification Number: 10.21953/lse.bijk2dsj3hlb

Abstract

In this thesis we explore extremal graph theory, focusing on new methods which apply to different notions of regular graph. The first notion is dregularity, which means each vertex of a graph is contained in exactly d edges, and the second notion is Szemerédi regularity, which is a strong, approximate version of this property that relates to pseudorandomness. We begin with a novel method for optimising observables of Gibbs distributions in sparse graphs. The simplest application of the method is to the hard-core model, concerning independent sets in d-regular graphs, where we prove a tight upper bound on an observable known as the occupancy fraction. We also cover applications to matchings and colourings, in each case proving a tight bound on an observable of a Gibbs distribution and deriving an extremal result on the number of a relevant combinatorial structure in regular graphs. The results relate to a wide range of topics including statistical physics and Ramsey theory. We then turn to a form of Szemerédi regularity in sparse hypergraphs, and develop a method for embedding complexes that generalises a widely-applied method for counting in pseudorandom graphs. We prove an inheritance lemma which shows that the neighbourhood of a sparse, regular subgraph of a highly pseudorandom hypergraph typically inherits regularity in a natural way. This shows that we may embed complexes into suitable regular hypergraphs vertex-by-vertex, in much the same way as one can prove a counting lemma for regular graphs. Finally, we consider the multicolour Ramsey number of paths and even cycles. A well-known density argument shows that when the edges of a complete graph on kn vertices are coloured with k colours, one can find a monochromatic path on n vertices. We give an improvement to this bound by exploiting the structure of the densest colour, and use the regularity method to extend the result to even cycles.

Item Type: Thesis (PhD)
Additional Information: © 2017 Ewan Davies
Library of Congress subject classification: Q Science > QA Mathematics
Sets: Departments > Mathematics
Supervisor: Skokan, Jozef and Allen, Peter
URI: http://etheses.lse.ac.uk/id/eprint/3615

Actions (login required)

Record administration - authorised staff only Record administration - authorised staff only

Downloads

Downloads per month over past year

View more statistics