Daniela Kühn

For all integers $n \geq k > d \geq 1$, let $m_{d}(k,n)$ be the minimum integer $D \geq 0$ such that every $k$-uniform $n$-vertex hypergraph $\mathcal H$ with minimum $d$-degree $\delta_{d}(\mathcal H)$ at least $D$ has an optimal matching. For every fixed integer $k \geq 3$, we show that for $n \in k \mathbb{N}$ and $p = \Omega(n^{-k+1} \log n)$, if $\mathcal H$ is an $n$-vertex $k$-uniform hypergraph with $\delta_{k-1}(\mathcal H) \geq m_{k-1}(k,n)$, then a.a.s.\ its $p$-random subhypergraph $\mathcal H_p$ contains a perfect matching. Moreover, for every fixed integer $d < k$ and $\gamma > 0$, we show that the same conclusion holds if $\mathcal H$ is an $n$-vertex $k$-uniform hypergraph with $\delta_d(\mathcal H) \geq m_{d}(k,n) + \gamma\binom{n - d}{k - d}$. Both of these results strengthen Johansson, Kahn, and Vu's seminal solution to Shamir's problem and can be viewed as ``robust'' versions of hypergraph Dirac-type results. In addition, we also show that in both cases above, $\mathcal H$ has at least $\exp((1-1/k)n \log n - \Theta (n))$ many perfect matchings, which is best possible up to an $\exp(\Theta(n))$ factor.

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_{v\in 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.

We provide a combinatorial characterization of all testable properties of $k$-uniform hypergraphs ($k$-graphs for short). Here, a $k$-graph property $P$ is testable if there is a randomized algorithm which makes a bounded number of edge queries and distinguishes with probability $2/3$ between $k$-graphs that satisfy $P$ and those that are far from satisfying $P$. For the $2$-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. Our results for the $k$-graph setting are in contrast to those of Austin and Tao, who showed that for the somewhat stronger concept of local repairability, the testability results for graphs do not extend to the $3$-graph setting. Our proof relies on a random subhypergraph sampling result proved in a companion paper.

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 $\left\lceil \frac{n}{2}\right\rceil$ paths, while a conjecture of Haj\'{o}s states that any Eulerian graph on $n$ vertices can be decomposed into at most $\left\lfloor \frac{n-1}{2}\right\rfloor$ cycles. The Erd\H{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.

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given $2$-factor. We show that this can be achieved for all large $n$. We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large $n$.

We prove a `resilience' version of Dirac's 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.