Institution: London School of Economics and Political Science
Status: PhD Student
Advisors: Jozef Skokan and Julia Böttcher
Email: m.o.jenssen@lse.ac.uk
We prove tight upper and lower bounds on the internal energy per particle in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all $q \ge 2$. This implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of $q$-colorings of a $3$-regular graph, for any $q \ge 2$, is maximized by a union of $K_{3,3}$'s. This proves the $d=3$ case of a conjecture of Galvin and Tetali.
We show that for fixed $k\geq2$ and $n$ odd and sufficiently large, $$ R_k(C_n)=2^{k-1}(n-1)+1. $$ This resolves a conjecture of Bondy and Erdős for large $n$. The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. This allows us to prove a stability-type generalisation of the above and establish a surprising correspondence between extremal $k$-colourings for this problem and perfect matchings in the $k$-dimensional hypercube $Q_k$.
We prove asymptotically tight lower bounds on the average size and the number of independent sets in a triangle-free graph of maximum degree $d$. The results come from considering the hard-core model from statistical physics. As a consequence we obtain a unified proof of two celebrated results: Shearer's upper bound on the Ramsey number $R(3,k)$ and Kahn's result that a $d$-regular graph has at most as many independent sets as a union of $K_{d,d}$'s on the same number of vertices.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that the $k$-colour Ramsey number of both an $n$-vertex path and, for even $n$, an $n$-vertex cycle is between $(k-1)n+o(n)$ and $kn+o(n)$. Here we obtain the first improvement to the coefficient of the linear term in the upper bound by an absolute constant.
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 $K_{d,d}$'s maximizes 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 $K_{d,d}$'s also maximize the matching polynomial and total number of matchings. Moreover we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markström.
The proof uses an occupancy method: we show that the occupancy fraction in the hard-core model and the edge occupancy fraction in the monomer-dimer model are maximized over all $d$-regular graphs by $K_{d,d}$.
We show that for all $k$, the $k$-colour Ramsey number of an odd cycle of length $n$ is $2^{k-1}n+o(n)$.The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation.