In submission
- Statistical physics approaches to Unique GamesM. Coulson, E. Davies, A. Kolla, V. Patel, G. Regts
@article{coulson2019statistical, title = {Statistical physics approaches to Unique Games}, author = {Coulson, Matthew and Davies, Ewan and Kolla, Alexandra and Patel, Viresh and Regts, Guus}, year = {2019}, eprinttype = {arxiv}, eprint = {1911.01504} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture.
- Regularity inheritance in hypergraphsP. Allen, E. Davies, J. Skokan
@article{allen2019regularity, title = {Regularity inheritance in hypergraphs}, author = {Allen, Peter and Davies, Ewan and Skokan, Jozef}, year = {2019}, eprinttype = {arxiv}, eprint = {1901.05955} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We give a new approach to handling hypergraph regularity. This approach allows for vertex-by-vertex embedding into regular partitions of hypergraphs, and generalises to regular partitions of sparse hypergraphs. We also prove a corresponding sparse hypergraph regularity lemma.
- Occupancy fraction, fractional colouring, and triangle fractionE. Davies, R. de Joannis de Verclos, R.J. Kang, F. Pirot
@article{davies2018occupancy, title = {Occupancy fraction, fractional colouring, and triangle fraction}, author = {Davies, Ewan and de Joannis de Verclos, Rémi and Kang, Ross J. and Pirot, Fran\c{c}ois}, year = {2018}, eprinttype = {arxiv}, eprint = {1812.11152} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
Given , there exists such that, if , then for any graph on vertices of maximum degree in which the neighbourhood of every vertex in spans at most edges, we have (i) an independent set drawn uniformly at random from has expected size at least ; and (ii) the fractional chromatic number of is at most .
The asymptotic factors cannot in general be improved by more than a factor of . One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi (1981) and Shearer (1983) on the independence number. The proofs of both use a tight analysis of the hard-core model.
- On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphsF. Bencs, E. Davies, V. Patel, G. Regts
@article{davies2018onzero, title = {On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs}, author = {Bencs, Ferenc and Davies, Ewan and Patel, Viresh and Regts, Guus}, year = {2018}, eprinttype = {arxiv}, eprint = {1812.07532} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any and any , there exists an open set in the complex plane that contains the interval such that for any and any graph of maximum degree at most . For small values of we are able to give better results. As an application of our results we obtain improved bounds on for the existence of deterministic approximation algorithms for counting the number of proper -colourings of graphs of small maximum degree.
- Colouring triangle-free graphs with local list sizesE. Davies, R. de Joannis de Verclos, R.J. Kang, F. Pirot
@article{davies2018colouring, title = {Colouring triangle-free graphs with local list sizes}, author = {Davies, Ewan and de Joannis de Verclos, Rémi and Kang, Ross J. and Pirot, François}, year = {2018}, eprinttype = {arxiv}, eprint = {1812.01534} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.
Journal publications
- Counting proper colourings in 4-regular graphs via the Potts modelE. DaviesElectronic Journal of Combinatorics 25 (2018), P4.7
@article{davies2018counting, title = {Counting proper colourings in 4-regular graphs via the Potts model}, author = {Davies, Ewan}, shortjournal = {Electron. J. Combin.}, journal = {Electronic Journal of Combinatorics}, volume = {25}, number = {4}, pages = {P4.7}, year = {2018}, eprinttype = {arxiv}, eprint = {1801.07547} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We give tight upper and lower bounds on the internal energy per particle in the antiferromagnetic -state Potts model on -regular graphs, for . This proves the first case of a conjecture of the author, Perkins, Jenssen, and Roberts on extensions of their methods, and implies tight bounds on the antiferromagnetic Potts partition function.
The zero-temperature limit gives upper and lower bounds on the number of proper -colourings of -regular graphs, which almost proves the case of a conjecture of Galvin and Tetali. For any we prove that the number of proper -colourings of a -regular graph is maximised by a union of ’s.
- Tight bounds on the coefficients of partition functions via stabilityE. Davies, M. Jenssen, W. Perkins, B. RobertsJournal of Combinatorial Theory Series A 160 (2018), 1–30
@article{davies2017tight, title = {Tight bounds on the coefficients of partition functions via stability}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {J. Combin. Theory Ser. A}, journal = {Journal of Combinatorial Theory Series A}, volume = {160}, pages = {1--30}, year = {2018}, doi = {10.1016/j.jcta.2018.06.005}, eprinttype = {arxiv}, eprint = {1704.07784} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
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 -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 .
- Extremes of the internal energy of the Potts model on cubic graphsE. Davies, M. Jenssen, W. Perkins, B. RobertsRandom Structures & Algorithms 53 (2018), 59–75
@article{davies2016extremes, title = {Extremes of the internal energy of the {P}otts model on cubic graphs}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {Random Structures Algorithms}, journal = {Random Structures \& Algorithms}, volume = {53}, number = {1}, pages = {59-75}, year = {2018}, doi = {10.1002/rsa.20767}, eprinttype = {arxiv}, eprint = {1610.08496} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
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 . 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 -colorings of a -regular graph, for any , is maximized by a union of ’s. This proves the case of a conjecture of Galvin and Tetali.
- On the average size of independent sets in triangle-free graphsE. Davies, M. Jenssen, W. Perkins, B. RobertsProceedings of the American Mathematical Society 146 (2018), 111–124
@article{davies2018average, title = {On the average size of independent sets in triangle-free graphs}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {Proc. Amer. Math. Soc.}, journal = {Proceedings of the American Mathematical Society}, volume = {146}, pages = {111--124}, year = {2018}, doi = {10.1090/proc/13728}, eprinttype = {arxiv}, eprint = {1606.01043} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on vertices with maximum degree , showing that an independent set drawn uniformly at random from such a graph has expected size at least . This gives an alternative proof of Shearer’s upper bound on the Ramsey number . We then prove that the total number of independent sets in a triangle-free graph with maximum degree is at least . The constant in the exponent is best possible. In both cases, tightness is exhibited by a random -regular graph.
Both results come from considering the hard-core model from statistical physics: a random independent set drawn from a graph with probability proportional to , for a fugacity parameter . We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree . The bound is asymptotically tight in for all .
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.
- Multicolour Ramsey numbers of paths and even cyclesE. Davies, M. Jenssen, B. RobertsEuropean Journal of Combinatorics 63 (2017), 124–133
@article{davies2016multicolour, title = {Multicolour Ramsey numbers of paths and even cycles}, author = {Davies, Ewan and Jenssen, Matthew and Roberts, Barnaby}, shortjournal = {European J. Combin.}, journal = {European Journal of Combinatorics}, volume = {63}, pages = {124--133}, year = {2017}, doi = {10.1016/j.ejc.2017.03.002}, publisher = {Elsevier}, eprinttype = {arxiv}, eprint = {1606.00762} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that . The upper bound was recently improved by Sárközy who showed that . Here we show , obtaining the first improvement to the coefficient of the linear term by an absolute constant.
- Independent Sets, Matchings, and Occupancy FractionsE. Davies, M. Jenssen, W. Perkins, B. RobertsJournal of the London Mathematical Society 96 (2017), 47–66
@article{davies2015independent, title = {{Independent Sets, Matchings, and Occupancy Fractions}}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {J. Lond. Math. Soc.}, journal = {Journal of the London Mathematical Society}, volume = {96}, pages = {47--66}, year = {2017}, doi = {10.1112/jlms.12056}, eprinttype = {arxiv}, eprint = {1508.04675} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of -regular graphs. For independent sets, this theorem is a strengthening of the results of Kahn, Galvin and Tetali, and Zhao showing that a union of copies of maximizes the number of independent sets and the independence polynomial of a -regular graph.
For matchings, this shows that the matching polynomial and the total number of matchings of a -regular graph are maximized by a union of copies of . Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markström.
In probabilistic language, our main theorems state that for all -regular graphs and all , the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity are maximized by . Our method involves constrained optimization problems over distributions of random variables and applies to all -regular graphs directly, without a reduction to the bipartite case.
Conference publications
- Tight bounds on the coefficients of partition functions via stability (extended abstract)E. Davies, M. Jenssen, W. Perkins, B. RobertsElectronic Notes in Discrete Mathematics 61 (2017), 317–321
@article{davies2017tightabs, title = {Tight bounds on the coefficients of partition functions via stability (extended abstract)}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {Electron. Notes Discrete Math.}, journal = {Electronic Notes in Discrete Mathematics}, volume = {61}, pages = {317--321}, year = {2017}, doi = {10.1016/j.endm.2017.06.054}, publisher = {Elsevier} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
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.
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 -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 .
- Counting in hypergraphs via regularity inheritance (extended abstract)E. DaviesElectronic Notes in Discrete Mathematics 49 (2015), 413–417
@article{davies2015counting, title = {Counting in hypergraphs via regularity inheritance (extended abstract)}, author = {Davies, Ewan}, shortjournal = {Electron. Notes Discrete Math.}, journal = {Electronic Notes in Discrete Mathematics}, volume = {49}, pages = {413--417}, year = {2015}, doi = {10.1016/j.endm.2015.06.058}, publisher = {Elsevier} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
We develop a theory of regularity inheritance in -uniform hypergraphs. As a simple consequence we deduce a strengthening of a counting lemma of Frankl and Rödl. We believe that the approach is sufficiently flexible and general to permit extensions of our results in the direction of a hypergraph blow-up lemma.
Other publications
- Extremal and probabilistic results for regular graphsE. DaviesPhD thesis, The London School of Economics and Political Science (2017)
@phdthesis{davies2017extremal, title = {Extremal and probabilistic results for regular graphs}, author = {Davies, Ewan}, institution = {The London School of Economics and Political Science}, year = {2017}, doi = {10.21953/lse.bijk2dsj3hlb} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
In this thesis we explore extremal graph theory, focusing on new methods which apply to different notions of regular graph. The first notion is -regularity, which means each vertex of a graph is contained in exactly edges, and the second notion is Szemerédi regularity, which is a strong, approximate version of this property that relates to pseudorandomness.
We begin with a novel method for optimising observables of Gibbs distributions in sparse graphs. The simplest application of the method is to the hard-core model, concerning independent sets in -regular graphs, where we prove a tight upper bound on an observable known as the occupancy fraction. We also cover applications to matchings and colourings, in each case proving a tight bound on an observable of a Gibbs distribution and deriving an extremal result on the number of a relevant combinatorial structure in regular graphs. The results relate to a wide range of topics including statistical physics and Ramsey theory.
We then turn to a form of Szemerédi regularity in sparse hypergraphs, and develop a method for embedding complexes that generalises a widely-applied method for counting in pseudorandom graphs. We prove an inheritance lemma which shows that the neighbourhood of a sparse, regular subgraph of a highly pseudorandom hypergraph typically inherits regularity in a natural way. This shows that we may embed complexes into suitable regular hypergraphs vertex-by-vertex, in much the same way as one can prove a counting lemma for regular graphs.
Finally, we consider the multicolour Ramsey number of paths and even cycles. A well-known density argument shows that when the edges of a complete graph on vertices are coloured with colours, one can find a monochromatic path on vertices. We give an improvement to this bound by exploiting the structure of the densest colour, and use the regularity method to extend the result to even cycles.
- Counting the number of ways a gas can fill a roomE. DaviesMaths at LSE Blog (2016)
@article{davies2016blog, title = {Counting the number of ways a gas can fill a room}, author = {Davies, Ewan}, journal = {Maths at LSE Blog}, year = {2016}, url = {http://blogs.lse.ac.uk/maths/2016/01/14/ewan-davies-counting-the-number-of-ways-a-gas-can-fill-a-room-3} }
This bib entry is for biblatex/biber, a modern, unicode-aware repacement for bibtex.
Graph theory is the study of connected systems of abstract ‘things’ which we call graphs. In this example the ‘things’ in the graph are particles of a gas or atoms in a molecule, and we describe a new method for understanding mathematical models in these graphs.
Past events
-
25 Sep 2019CS Theory Seminar, CU Boulder | Boulder, ColoradoTitle: Graph colouring and the hard-core model
-
15 Jan – 17 May 2019Simons Institute: Geometry of Polynomials | Berkeley, CaliforniaTalk: Colouring locally sparse graphs via the hard-core model (17 Apr)
-
23–24 Aug 2018Algorithmic and Combinatorial Aspects of Partition Functions | Amsterdam, NetherlandsTalk: Fractional colouring of triangle-free graphs via the hard-core model (24 Aug)
-
9–10 May 2018Two one-day Colloquia in Combinatorics | London, UK
-
1 May 2018Applied Stochastics Seminar, Radboud University | Nijmegen, NetherlandsTitle: Using Gibbs measures in extremal combinatorics
-
26–30 Mar 2018Workshop on Graph limits | Janov, CzechiaTalk: Tight bounds on the coefficients of partition functions via stability (30 Mar)
-
19 Feb – 4 Mar 2018Graphs and Randomness, IMPA | Rio de Janeiro, Brazil
-
26 Jan 2018Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: A new approach to Sidorenko's conjecture
-
18 Oct 2017Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: Shamir's problem revisited
-
28 Aug – 1 Sep 2017EUROCOMB 2017 | Vienna, AustriaTalk: Tight bounds on the coefficients of partition functions via stability (31 Aug, slides)
-
17–21 Jul 2017Novi Sad Workshop on Foundations Of Computer Science | Novi Sad, SerbiaTalk: Regularity inheritance in 3-uniform hypergraphs (20 Jul)
-
11 May 2017Two one-day Colloquia in Combinatorics (invited) | London, UKTitle: Tight bounds on the coefficients of partition functions via stability
-
21 Feb 2017Combinatorics Seminar | Oxford, UKTitle: Extremal problems on colourings in cubic graphs via the Potts model
-
3 Feb 2017Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: A probabilistic approach to bounding graph polynomials
-
27 Jan 2017PhD Seminar on Combinatorics, Games and Optimisation, LSE | London, UKTitle: A probabilistic approach to bounding graph polynomials
-
3 Aug 2016Student Combinatorics Day (invited) | Birmingham, UKTitle: On the average size of independent sets in triangle-free graphs (slides)
-
8 Apr 2016Seminário de Teoria da Computação, Combinatória e Otimização | São Paulo, BrazilTitle: Independent sets, matchings, and occupancy fractions II
-
3 Nov 2015Discrete Geometry and Combinatorics Seminar, UCL | London, UKTitle: Independent sets, matchings, and occupancy fractions
-
9 Oct 2015Mathematics Lunchtime Seminar, LSE | London, UKTitle: Independent sets, matchings, and occupancy fractions I
-
31 Aug – 4 Sep 2015EUROCOMB 2015 | Bergen, NorwayTalk: Counting in hypergraphs via regularity inheritance (31 Aug, slides)
-
15 Apr 2015Postgraduate Combinatorial Conference, QMUL | London, UKTitle: Counting in hypergraphs via regularity inheritance
-
9 Apr 2015Combinatorics Seminar, Freie Universität | Berlin, GermanyTitle: Regularity inheritance in 3-uniform hypergraphs
-
3 Jul 2014SUMMIT 190: Balogh, Csaba, Hajnal, and Pluhar are 190 (invited) | Szeged, HungaryTitle: Robustness of triangle factors
-
29 Nov 2013Mathematics Lunchtime Seminar, LSE | London, UKTitle: Cycle packing