41 citations · 175 across the 19 of their papers we have counts for
22 papers
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for…
List packing number of bounded degree graphs
Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies +1
We investigate the list packing number of a graph, the least such that there are always disjoint proper list-colourings whenever we have lists all of size associated to…
Algorithms for the ferromagnetic Potts model on expanders
Charlie Carlson, Ewan Davies, Nicolas Fraiman +3
We give algorithms for approximating the partition function of the ferromagnetic -color Potts model on graphs of maximum degree . Our primary contribution is a fully polynomi…
Computational thresholds for the fixed-magnetization Ising model
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate co…
Packing list-colourings
Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies +1
List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek m…
The -Ramsey problem for triangle-free graphs
Ewan Davies, Freddie Illingworth
In 1967, Erdős asked for the greatest chromatic number, , amongst all -vertex, triangle-free graphs. An observation of Erdős and Hajnal together with Shearer's classical u…
Approximately counting independent sets of a given size in bounded-degree graphs
Ewan Davies, Will Perkins
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density…
An algorithmic framework for colouring locally sparse graphs
Ewan Davies, Ross J. Kang, François Pirot +1
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fix…
A proof of the Upper Matching Conjecture for large graphs
Ewan Davies, Matthew Jenssen, Will Perkins
We prove that the `Upper Matching Conjecture' of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enoug…
Graph structure via local occupancy
Ewan Davies, Ross J. Kang, François Pirot +1
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of la…
Efficient algorithms for the Potts model on small-set expanders
Charles Carlson, Ewan Davies, Alexandra Kolla
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of re…
Statistical physics approaches to Unique Games
Matthew Coulson, Ewan Davies, Alexandra Kolla +2
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 Game…
Regularity inheritance in hypergraphs
Peter Allen, Ewan Davies, Jozef Skokan
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 par…
Occupancy fraction, fractional colouring, and triangle fraction
Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang +1
Given , there exists such that, if , then for any graph on vertices of maximum degree in which the neighbourhood of every vert…
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
Ferenc Bencs, Ewan Davies, Viresh Patel +1
For a graph , , and a complex number the partition function of the univariate Potts model is defined as \[ {\bf Z}(G;k,w):=\sum_{ϕ:V\to [k]}\prod_{\su…
Colouring triangle-free graphs with local list sizes
Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang +1
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.…
Counting proper colourings in 4-regular graphs via the Potts model
Ewan Davies
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 c…
Tight bounds on the coefficients of partition functions via stability
Ewan Davies, Matthew Jenssen, Will Perkins +1
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. Fo…
Extremes of the internal energy of the Potts model on cubic graphs
Ewan Davies, Matthew Jenssen, Will Perkins +1
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…
On the average size of independent sets in triangle-free graphs
Ewan Davies, Matthew Jenssen, Will Perkins +1
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 s…
Multicolour Ramsey numbers of paths and even cycles
Ewan Davies, Matthew Jenssen, Barnaby Roberts
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that . The upper bound was…
Independent Sets, Matchings, and Occupancy Fractions
Ewan Davies, Matthew Jenssen, Will Perkins +1
We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of…