Jenssen, Matthew
(2017)
Continuous optimisation in extremal combinatorics.
PhD thesis, The London School of Economics and Political Science (LSE).
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 kcolour 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 kdimensional hypercube. This allows us to prove a stability type result around these extremal constructions.
We consider two models from statistical physics, the hardcore model and the monomerdimer model. Using tools from linear programming we give tight upper bounds on the logarithmic derivative of the independence and matching polynomials of a dregular 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 dregular 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 hardcore model, we also prove lower bounds on the average size and the number of independent sets in a trianglefree 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).
Actions (login required)

Record administration  authorised staff only 