Search

Let T be an oriented tree on n vertices with maximum degree at most e o (log ⁡ n). If G is a digraph on n vertices with minimum semidegree δ 0 (G) ≥ (1 2 + o (1)) n , then G contains T as a spanning tree, as recently shown by Kathapurkar and Montgomery (in fact, they only require maximum degree o (n / log ⁡ n)). This generalizes the corresponding result by Komlós, Sárközy and Szemerédi for graphs. We investigate the natural question how many copies of T the digraph G contains. Our main result states that every such G contains at least | Aut (T) | − 1 (1 2 − o (1)) n n ! copies of T , which is optimal. This implies the analogous result in the undirected case. [ABSTRACT FROM AUTHOR]

A famous result by Rödl, Ruciński, and Szemerédi guarantees a (tight) Hamilton cycle in k -uniform hypergraphs H on n vertices with minimum (k − 1) -degree δ k − 1 (H) ⩾ (1 / 2 + o (1)) n , thereby extending Dirac's result from graphs to hypergraphs. For graphs, much more is known; each graph on n vertices with δ (G) ⩾ (1 / 2 + o (1)) n contains (1 − o (1)) r edge-disjoint Hamilton cycles where r is the largest integer such that G contains a spanning 2 r -regular subgraph, which is clearly asymptotically optimal. This was proved by Ferber, Krivelevich, and Sudakov answering a question raised by Kühn, Lapinskas, and Osthus. We extend this result to hypergraphs; every k -uniform hypergraph H on n vertices with δ k − 1 (H) ⩾ (1 / 2 + o (1)) n contains (1 − o (1)) r edge-disjoint (tight) Hamilton cycles where r is the largest integer such that H contains a spanning subgraph with each vertex belonging to kr edges. In particular, this yields an asymptotic solution to a question of Glock, Kühn, and Osthus. In fact, our main result applies to approximately vertex-regular k -uniform hypergraphs with a weak quasirandom property and provides approximate decompositions into cycle factors without too short cycles. [ABSTRACT FROM AUTHOR]