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

Structure and randomness in extremal combinatorics

Roberts, Barnaby (2017) Structure and randomness in extremal combinatorics. PhD thesis, The London School of Economics and Political Science (LSE).

[img]
Preview
Text - Submitted Version
Download (827kB) | Preview
Identification Number: 10.21953/lse.5uqfgbh7m14x

Abstract

In this thesis we prove several results in extremal combinatorics from areas including Ramsey theory, random graphs and graph saturation. We give a random graph analogue of the classical Andr´asfai, Erd˝os and S´os theorem showing that in some ways subgraphs of sparse random graphs typically behave in a somewhat similar way to dense graphs. In graph saturation we explore a ‘partite’ version of the standard graph saturation question, determining the minimum number of edges in H-saturated graphs that in some way resemble H themselves. We determine these values for K4, paths, and stars and determine the order of magnitude for all graphs. In Ramsey theory we give a construction from a modified random graph to solve a question of Conlon, determining the order of magnitude of the size-Ramsey numbers of powers of paths. We show that these numbers are linear. Using models from statistical physics we study the expected size of random matchings and independent sets in d-regular graphs. From this we give a new proof of a result of Kahn determining which d-regular graphs have the most independent sets. We also give the equivalent result for matchings which was previously unknown and use this to prove the Asymptotic Upper Matching Conjecture of Friedland, Krop, Lundow and Markstrom. Using these methods we give an alternative proof of Shearer’s upper bound on off-diagonal Ramsey numbers.

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

Actions (login required)

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

Downloads

Downloads per month over past year

View more statistics