Search

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [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]

We prove that any quasirandom uniform hypergraph H can be approximately decomposed into any collection of bounded degree hypergraphs with almost as many edges. In fact, our results also apply to multipartite hypergraphs and even to the sparse setting when the density of H quickly tends to 0 in terms of the number of vertices of H. Our results answer and address questions of Kim, Kühn, Osthus and Tyomkyn; and Glock, Kühn and Osthus as well as Keevash. The provided approximate decompositions exhibit strong quasirandom properties which are very useful for forthcoming applications. Our results also imply approximate solutions to natural hypergraph versions of long-standing graph decomposition problems, as well as several decomposition results for (quasi)random simplicial complexes into various more elementary simplicial complexes such as triangulations of spheres and other manifolds. [ABSTRACT FROM AUTHOR]

We prove that for any integer k≥2$$ k\ge 2 $$ and ε>0$$ \varepsilon >0 $$, there is an integer ℓ0≥1$$ {\ell}_0\ge 1 $$ such that any k‐uniform hypergraph on n vertices with minimum codegree at least (1/2+ε)n$$ \left(1/2+\varepsilon \right)n $$ has a fractional decomposition into (tight) cycles of length ℓ$$ \ell $$ (ℓ$$ \ell $$‐cycles for short) whenever ℓ≥ℓ0$$ \ell \ge {\ell}_0 $$ and n is large in terms of ℓ$$ \ell $$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into ℓ$$ \ell $$‐cycles. Moreover, for graphs this even guarantees integral decompositions into ℓ$$ \ell $$‐cycles and solves a problem posed by Glock, Kühn, and Osthus. For our proof, we introduce a new method for finding a set of ℓ$$ \ell $$‐cycles such that every edge is contained in roughly the same number of ℓ$$ \ell $$‐cycles from this set by exploiting that certain Markov chains are rapidly mixing. [ABSTRACT FROM AUTHOR]

A tight Hamilton cycle in a k-uniform hypergraph (k-graph) G is a cyclic ordering of the vertices of G such that every set of k consecutive vertices in the ordering forms an edge. Rödl, Ruciński and Szemerédi proved that for $k\ge 3$ , every k-graph on n vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such k-graphs is ${\exp(n\ln n-\Theta(n))}$. As a corollary, we obtain a similar estimate on the number of Hamilton ${\ell}$ -cycles in such k-graphs for all ${\ell\in\{0,\ldots,k-1\}}$ , which makes progress on a question of Ferber, Krivelevich and Sudakov. [ABSTRACT FROM AUTHOR]

A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is 'pseudorandom', meaning that, for instance, the matching contains as many edges from a given set of edges as predicted by a heuristic argument. [ABSTRACT FROM AUTHOR]

We show that a quasirandom k-uniform hypergraph G has a tight Euler tour subject to the necessary condition that k divides all vertex degrees. The case when G is complete confirms a conjecture of Chung, Diaconis and Graham from 1989 on the existence of universal cycles for the k-subsets of an n-set. [ABSTRACT FROM AUTHOR]

Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. We develop an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov, and Vu for graphs. From our results we deduce several corollaries on subgraph counts in random d-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruciński, and Šileikis on the threshold for the existence of an '-overlapping Hamilton cycle in a random d-regular r-graph. Moreover, we apply our results to prove bounds on the query complexity of testing subgraph-freeness. The problem of testing subgraph-freeness in the general graphs model was first studied by Alon, Kaufman, Krivelevich, and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting. [ABSTRACT FROM AUTHOR]