| Institution | London School of Economics and Political Science |
|---|---|
| Status | PhD Student since September 2013 |
| Advisors | Jozef Skokan and Peter Allen |
| maths@ewandavies.org, E.S.Davies@lse.ac.uk | |
| CV | |
| Links | arXiv, Google Scholar, ORCID, Research Gate |
We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all $q \ge 2$. This immediately 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 prove an asymptotically tight lower bound on the expected size of an independent set in a triangle-free graph on $n$ vertices with maximum degree $d$ drawn uniformly at random, showing the average is at least $(1+o_d(1)) \frac{\log d}{d}n$. This gives an alternative proof of Shearer's upper bound on the Ramsey number $R(3,k)$.
We then prove a lower bound on the total number of independent sets in such a graph which is asymptotically tight in the exponent. In both cases, tightness is exhibited by a random $d$-regular graph.
Our results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $\lambda^{|I|}$, for a fugacity parameter $\lambda>0$. We prove a general lower bound on the occupancy fraction of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $\lambda =O_d(1)$.
We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
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)$. The upper bound was recently improved by Sárközy who gave a stability version of the classical theorem of Erdős and Gallai on graphs containing no long cycles. 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 any $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.
For matchings, the result implies that disjoint unions of $K_{d,d}$'s maximize the matching polynomial and total number of matchings, as well as proving 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}$.
A new approach to the counting lemma in 3-uniform hypergraphs. We develop a theory of regularity inheritance and use it to prove a slight strengthening of the counting lemma of Frankl and Rödl. Full paper to follow.