3 papers
math.CO2018
Lower bounds on the chromatic number of random graphs
Peter Ayre, Amin Coja-Oghlan, Catherine Greenhill
We prove that a formula predicted on the basis of non-rigorous physics arguments [Zdeborova and Krzakala: Phys. Rev. E (2007)] provides a lower bound on the chromatic number of spa…
math.CO2017
The satisfiability threshold for random linear equations
Peter Ayre, Amin Coja-Oghlan, Pu Gao +1
Let be a random matrix over the finite field with precisely non-zero entries per row and let be a random vector chosen independently of .…
cs.DM2015
Hypergraph coloring up to condensation
Peter Ayre, Amin Coja-Oghlan, Catherine Greenhill
Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the -colorability threshold in random -uniform hypergraphs up…