In this thesis we explore instances in which tools from continuous optimisation can be used to solve problems in extremal graph and hypergraph theory.udWe 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 ofudhypergraphs.udWe 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.udWe 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.udThrough 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’sudcelebrated upper bound on the Ramsey number R(3, k).
展开▼
