Fractional Decompositions of Dense Hypergraphs

A seminal result of Rodl (the Rodl nibble) asserts that the edges of the complete r-uniform hypergraph K$_{n}^{r}$ can be packed, almost completely, with copies of K$_{k}^{r}$, where k is fixed. This result is considered one of the most fruitful applications of the probabilistic method. It was not known whether the same result also holds in a dense hypergraph setting. In this paper we prove that it does. We prove that for every r-uniform hypergraph H0, there exists a constant α=α(H0) r > 2. We prove that there exists a constant α=α(k,r) < 1 such that every r-uniform hypergraph with n (sufficiently large) vertices in which every (r–1)-set is contained in at least αn edges has a fractional K$_{k}^{r}$-decomposition. We then apply a recent result of Rodl, Schacht, Siggers and Tokushige to obtain our integral packing result. The proof makes extensive use of probabilistic arguments and additional combinatorial ideas.