Packing in a hypergraph
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 the Rödl nibble and was proposed by Vojtěch Rödl et al. They showed that the achievable packing by the Rödl nibble is in some sense close to that of the random greedy algorithm.
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.
In the following definitions, the hypergraph is denoted by H=(V,E). H is called a k-uniform hypergraph if every edge in E consists of exactly k vertices.
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.
...
Wikipedia