Institution | London School of Economics and Political Science |
---|---|
Status | PhD Student since September 2013 |
Advisors | Jozef Skokan and Peter Allen |
maths@ewandavies.org | |
CV | |
Links | arXiv, Google Scholar, ORCID |
Partition functions arise in statistical physics and probability theory as
the normalizing constant of Gibbs measures and in combinatorics and graph
theory as graph polynomials. For instance the partition functions of the
hard-core model and monomer-dimer model are the independence and matching
polynomials respectively.
We show how stability results follow naturally from the recently developed
occupancy method for maximizing and minimizing physical observables over
classes of regular graphs, and then show these stability results can be used to
obtain tight extremal bounds on the individual coefficients of the
corresponding partition functions.
As applications, we prove new bounds on the number of independent sets and
matchings of a given size in regular graphs. For large enough graphs and almost
all sizes, the bounds are tight and confirm the Upper Matching Conjecture of
Friedland, Krop, and Markström and a conjecture of Kahn on independent sets
for a wide range of parameters. Additionally we prove tight bounds on the
number of $q$-colorings of cubic graphs with a given number of monochromatic
edges, and tight bounds on the number of independent sets of a given size in
cubic graphs of girth at least $5$.
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}$.
We show how to use the recently-developed occupancy method and stability results that follow easily from the method to obtain extremal bounds on the individual coefficients of the partition functions over various classes of bounded degree graphs.
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.