Continuous optimisation in extremal combinatorics

Jenssen, Matthew (2017) Continuous optimisation in extremal combinatorics. PhD thesis, London School of Economics and Political Science.

Preview

Text - Submitted Version Download (721kB) | Preview

Abstract

In this thesis we explore instances in which tools from continuous optimisation can be used to solve problems in extremal graph and hypergraph theory. We begin by introducing a generalised notion of hypergraph Lagrangian and use tools from the theory of nonlinear optimisation to explore some of its properties. As an application we find the Tur´an density of a small family of hypergraphs. We determine the exact k-colour Ramsey number of an odd cycle on n vertices when n is large. This resolves a conjecture of Bondy and Erd˝os for large n. The first step of our proof is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. We establish a correspondence between extremal constructions in the Ramsey setting and optimal points in the continuous setting. We thereby uncover a correspondence between extremal constructions and perfect matchings in the k-dimensional hypercube. This allows us to prove a stability type result around these extremal constructions. We consider two models from statistical physics, the hard-core model and the monomer-dimer model. Using tools from linear programming we give tight upper bounds on the logarithmic derivative of the independence and matching polynomials of a d-regular graph. For independent sets, this is a strengthening of a sequence of results of Kahn, Galvin and Tetali, and Zhao that a disjoint union of Kd,d’s maximises the independence polynomial and total number of independent sets among all d-regular graphs on the same number of vertices. For matchings, the result implies that disjoint unions of Kd,d’s also maximise the matching polynomial and total number of matchings. Moreover we prove the Asymptotic Upper Matching Conjecture of Friedland, Krop, Lundow, and Markstr¨om. Through our study of the hard-core model, we also prove lower bounds on the average size and the number of independent sets in a triangle-free graph of maximum degree d. As a consequence we obtain a new proof of Shearer’s celebrated upper bound on the Ramsey number R(3, k).

Item Type:	Thesis (PhD)
Additional Information:	© 2017 Matthew Jenssen
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	Skokan, Jozef and Böttcher, Julia
URI:	http://etheses.lse.ac.uk/id/eprint/3572

Actions (login required)

Record administration - authorised staff only