6 citations · 17 across the 6 of their papers we have counts for
4 papers · 1 filter
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…