In mathematics, a packing in a hypergraph is a partition of the set of the hypergraph's edges into a number of disjoint subsets such that no pair of edges in each subset share any vertex. There are two famous algorithms to achieve asymptotically optimal packing in k-uniform hypergraphs. One of them is a random greedy algorithm which was proposed by Joel Spencer. He used a branching process to formally prove the optimal achievable bound under some side conditions. The other algorithm is called Rödl nibble and was proposed by Vojtěch Rödl et al. They showed that the achievable packing by Rödl nibble is in some sense close to that of the random greedy algorithm.

## History

The problem of finding the number of such subsets in a k-uniform hypergraph was originally motivated through a conjecture by Paul Erdős and Haim Hanani in 1963. Vojtěch Rödl proved their conjecture asymptotically under certain conditions in 1985. Pippenger and Joel Spencer generalized Rödl's results using a random greedy algorithm in 1989.

## Definition and terminology

$P$ is a hypergraph packing if it is a subset of edges in H such that there is no pair of distinct edges with a common vertex.

$D(1-\epsilon )\leq deg(x)\leq D(1+\epsilon )$ $codeg(x,y)\leq \epsilon D$ where deg of a vertex denotes the number of edges that contain that vertex and codeg of two distinct vertices denotes the number of edges that contain both vertices.

## Theorem

There exists an asymptotic packing P of size at least ${\frac {n}{K+1}}(1-o(1))$ for a $(k+1)$ -uniform hypergraph under the following two conditions,

where $n$ is the total number of vertices. This result was shown by Pippenger and was later proved by Joel Spencer. To address the asymptotic hypergraph packing problem, Joel Spencer proposed a random greedy algorithm. In this algorithm, a branching process is used as the basis and it was shown that it almost always achieves an asymptotically optimal packing under the above side conditions.

## Asymptotic packing algorithms

There are two famous algorithms for asymptotic packing of k-uniform hypegraphs which are random greedy algorithm via branching process and Rödl nibble.

### Random greedy algorithm via branching process

A rooted tree with the notions of parent, child, root, birthorder and wombmate shall be called a broodtree. Given a finite broodtree $T$ we say for each vertex that it survives or dies. A childless vertex survives. A vertex dies if and only if it has at least one brood all of whom survive. Let $f(c)$ denote the probability that Eve survives in the broodtree $T$ given by the above process. The objective is to show $\lim _{c\rightarrow \infty }f(c)=0$ and then for any fixed $c$ , it can be shown that $\lim ^{*}f_{x,H}(c)=f(c)$ . These two relations complete our argument.

## Rödl nibble

In 1985, Rödl proved Paul Erdős’s conjecture by a method called Rödl nibble. Rodl's result can be formulated in form of either packing or covering problem. For $2\leq l the covering number denoted by $M(n,k,l)$ shows the minimal size of a family $\kappa$ of k-element subsets of $\{1,...,n\}$ which have the property that every l-element set is contained in at least one $A\in \kappa$ . Paul Erdős et al. conjecture was

$\lim _{n\rightarrow \infty }{\frac {M(n,k,l)}{{n \choose l}/{k \choose l}}}=1$ .

where $2\leq l . This conjecture roughly means that a tactical configuration is asymptotically achievable. One may similarly define the packing number $m(n,k,l)$ as the maximal size of a family $\kappa$ of k-element subsets of $\{1,...,n\}$ having the property that every l-element set is contained in at most one $A\in \kappa$ .

## Packing under the stronger condition

This bound is desirable in various applications, such as Steiner triple system. A Steiner Triple System is a $3-$ uniform, simple hypergraph in which every pair of vertices is contained in precisely one edge. Since a Steiner Triple System is clearly $d=(n-1)/2-$ regular, the above bound supplies the following asymptotic improvement.

Any Steiner Triple System on $n$ vertices contains a packing covering all vertices but at most $O(n^{1/2}\ln ^{3/2}n)$ .