7 papers
Anticoncentration of random spanning trees in graphs with large minimum degree
Veronica Bitonti, Lukas Michel, Alex Scott
A classical result by Otter shows that the complete graph has an exponential number of non-isomorphic spanning trees. This was recently extended by Lee to every almost regular grap…
Improved exploration of temporal graphs
Paul Bastide, Carla Groenland, Lukas Michel +2
A temporal graph is a sequence of graphs on the same vertex set of size . The \emph{temporal exploration problem} asks for the length of the shortest seque…
Infinite Schnyder Woods
Louigi Addario-Berry, Emma Hogan, Lukas Michel +1
It is well-known that any finite triangulation possesses a unique maximal Schnyder wood. We introduce Schnyder woods of infinite triangulations, and prove there exists a unique max…
An improved upper bound for the multicolour Ramsey number of odd cycles
Maria Axenovich, Wouter Cames van Batenburg, Oliver Janzer +2
We show that the -colour Ramsey number of an odd cycle of length is at most . This proves a conjecture of Fox and is the first improvem…
Tight Bounds for Hypercube Minor-Universality
Emma Hogan, Lukas Michel, Alex Scott +3
Benjamini, Kalifa and Tzalik recently proved that there is an absolute constant such that any graph with at most edges and no isolated vertices is a minor of th…
Lower bounds for graph reconstruction with maximal independent set queries
Lukas Michel, Alex Scott
We investigate the number of maximal independent set queries required to reconstruct the edges of a hidden graph. We show that randomised adaptive algorithms need at least $Ω(Δ^2 \…
Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
Lukas Michel, Alex Scott
Local search algorithms for NP-hard problems such as Max-Cut frequently perform much better in practice than worst-case analysis suggests. Smoothed analysis has proved an effective…