In 1976, Alspach, Mason, and Pullman conjectured that any tournament $T$ of even order can be decomposed into exactly ${rm ex}(T)$ paths, where ${rm ex}(T):= frac{1}{2}sum_{vin V(T)}|d_T^+(v)-d_T^-(v)|$. We prove this conjecture for all sufficiently
large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.
Kostochka and Thomason independently showed that any graph with average degree $Omega(rsqrt{log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $Omega(rsqrt{log r})$ contains a $K_r$ minor, a partial result towards Hadwige
rs famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong $overrightarrow{K}_r$ minor is a digraph whose vertex set is partitioned into $r$ parts such that each part induces a strongly-connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong $overrightarrow{K}_r$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least $2r$ contains a strong $overrightarrow{K}_r$ minor, and any tournament with minimum out-degree $Omega(rsqrt{log r})$ also contains a strong $overrightarrow{K}_r$ minor. The latter result is tight up to the implied constant, and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function $f: mathbb{N} rightarrow mathbb{N}$ such that any digraph with minimum out-degree at least $f(r)$ contains a strong $overrightarrow{K}_r$ minor, but such a function exists when considering dichromatic number.
We study Hamiltonicity in random subgraphs of the hypercube $mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $mathcal{Q}^n$ according to a uniformly chosen random orderi
ng. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. Secondly, we obtain a perturbation result: if $Hsubseteqmathcal{Q}^n$ satisfies $delta(H)geqalpha n$ with $alpha>0$ fixed and we consider a random binomial subgraph $mathcal{Q}^n_p$ of $mathcal{Q}^n$ with $pin(0,1]$ fixed, then with high probability $Hcupmathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollobas, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $pin(0,1]$ the graph $mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the Rodl nibble, and absorption.
We prove a canonical polynomial Van der Waerdens Theorem. More precisely, we show the following. Let ${p_1(x),ldots,p_k(x)}$ be a set of polynomials such that $p_i(x)in mathbb{Z}[x]$ and $p_i(0)=0$, for every $iin {1,ldots,k}$. Then, in any colouring
of $mathbb{Z}$, there exist $a,din mathbb{Z}$ such that ${a+p_1(d),ldots,a+p_{k}(d)}$ forms either a monochromatic or a rainbow set.
Resolving a problem raised by Norin, we show that for each $k in mathbb{N}$, there exists an $f(k) le 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $
k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k) = O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k) = O(k^2)$. Our methods are robust enough to handle list colouring as well: we also show that for each $k in mathbb{N}$, there exists an $f_ell(k) le 4k$ such that every graph $G$ with list chromatic number at least $f_ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$. This result is again best-possible up to multiplicative constants; here, unlike with $f(cdot)$, even the existence of $f_ell(cdot)$ appears to have been previously unknown.
We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular we show that in every cover of a Young diagram with $binom{2k}{k}$ steps with generalized rectangles there is a row or
a column in the diagram that is used by at least $k+1$ rectangles, and prove that this is best-possible. This answers two questions by Kim, Martin, Masa{v{r}}{i}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim emph{et al.}, we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height~2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))log_2log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.
We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $leftlceil frac{n}{2}rightrceil$ paths, while
a conjecture of Haj{o}s states that any Eulerian graph on $n$ vertices can be decomposed into at most $leftlfloor frac{n-1}{2}rightrfloor$ cycles. The ErdH{o}s-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $frac{n}{2}+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $frac{n}{2}+o(n)$ cycles. (iii) $G$ can be decomposed into at most $frac{3 n}{2}+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$. (iv) $G$ can be decomposed into $max left{frac{odd(G)}{2},frac{Delta(G)}{2}right}+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$. (v) If $G$ is Eulerian, then it can be decomposed into $frac{Delta(G)}{2}+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.
We prove a `resilience version of Diracs theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $varepsilon>0$, a.a.s. the following holds: let $G$ be any subgraph of the random $
n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+varepsilon)d$. Then $G$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that $d$ is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.
