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.
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.
H is called a k-uniform hypergraph if every edge in E consists of exactly k vertices.
is the number of edges that contain both 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.
There are two famous algorithms for asymptotic packing of k-uniform hypergraphs: the random greedy algorithm via branching process, and the Rödl nibble.
is independently and uniformly assigned a distinct real "birthtime"
To show that, let stop the process of adding new edges at time
surviving is modeled by a continuous branching process.
Assume time goes backward so Eve gives birth in the interval of
A rooted tree with the notions of parent, child, root, birthorder and wombmate shall be called a broodtree.
denote the probability that Eve survives in the broodtree
all of whose children survive while Eve has no births in
, consider a procedure we call History which either aborts or produces a broodtree.
denote the probability that the branching process yields broodtree
Rödl's result can be formulated in form of either packing or covering problem.
This conjecture roughly means that a tactical configuration is asymptotically achievable.
In 1997, Noga Alon, Jeong Han Kim, and Joel Spencer also supply a good bound for
under the stronger codegree condition that every distinct pair
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.