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]

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]