5 papers · 1 filter
Cycle-factors of regular graphs via entropy
Micha Christoph, Nemanja Draganić, António Girão +3
It is a classical result that a random permutation of elements has, on average, about cycles. We generalise this fact to all directed -regular graphs on vertice…
New bounds for linear arboricity and related problems
Micha Christoph, Nemanja Draganić, António Girão +3
A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree can be decomposed into at most $\lceil(Δ+1)…
Exponential odd-distance sets under the Manhattan metric
Alberto Espuny Díaz, Emma Hogan, Freddie Illingworth +3
We construct a set of points in such that all pairwise Manhattan distances are odd integers, which improves the recent linear lower bound of Golovanov, Kupavsk…
Small families of partially shattering permutations
António Girão, Lukas Michel, Youri Tamitegama
We say that a family of permutations -shatters a set if it induces at least distinct permutations on that set. What is the minimum number of permutations of $\{1,…
Abundance: Asymmetric Graph Removal Lemmas and Integer Solutions to Linear Equations
António Girão, Eoin Hurley, Freddie Illingworth +1
We prove that a large family of pairs of graphs satisfy a polynomial dependence in asymmetric graph removal lemmas. In particular, we give an unexpected answer to a question of Gis…