6 papers
Colour-balanced subgraphs
Emma Hogan, Alex Scott, Dmitry Tsarev
A -edge-coloured graph is colour-balanced if each colour appears equally often. Resolving a conjecture of Pardey and Rautenbach, we show that any colour-balanced -edge-colour…
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…
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…
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…