Eoin Hurley

FOCS Conference 2025 Conference Paper

Cycle-factors of regular graphs via entropy

• Micha Christoph
• Nemanja Draganic
• António Girão
• Eoin Hurley
• Lukas Michel
• Alp Müyesser

It is a classical result that a random permutation of n elements has, on average, about log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt {\log d} )$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1 + {\mathcal{O}}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

STOC Conference 2023 Conference Paper

Uniformly Random Colourings of Sparse Graphs

• Eoin Hurley
• François Pirot

SODA Conference 2021 Conference Paper

An improved procedure for colouring graphs of bounded local density

• Eoin Hurley
• Rémi de Joannis de Verclos
• Ross J. Kang

We develop an improved bound for the chromatic number of graphs of maximum degree Δ under the assumption that the number of edges spanning any neighbourhood is at most for some fixed 0 < σ < 1. The leading term in the reduction of colours achieved through this bound is best possible as σ → 0. As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erdős-Nešetřil conjecture and Reed's conjecture. We prove that the strong chromatic index is at most 1. 772Δ 2 for any graph G with sufficiently large maximum degree Δ. We prove that the chromatic number is at most ⌈0. 881(Δ + 1) + 0. 119 ω ⌉ for any graph G with clique number ω and sufficiently large maximum degree Δ. Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most (1 – σ) Δ, and establish what may be considered first progress towards a conjecture of Vu.