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.
Definition and terminology
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.
is a (,)-good hypergraph if there exists a such that for all and and both of the following conditions hold.
where the degree deg(x) of a vertex x is the number of edges that contain x and the codegree codeg(x, y) of two distinct vertices x and y is the number of edges that contain both vertices.
There exists an asymptotic packing P of size at least for a -uniform hypergraph under the following two conditions,
- All vertices have the degree of in which tends to infinity.
- For every pair of vertices shares only common edges.
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 hypergraphs: the random greedy algorithm via branching process, and the Rödl nibble.
Random greedy algorithm via branching process
Every edge is independently and uniformly assigned a distinct real "birthtime" . The edges are taken one by one in the order of their birthtimes. The edge is accepted and included in if it does not overlap any previously accepted edges. Obviously, the subset is a packing and it can be shown that its size is almost surely. To show that, let stop the process of adding new edges at time . For an arbitrary , pick such that for any -good hypergraph where denotes the probability of vertex survival (a vertex survives if it is not in any edges in ) until time . Obviously, in such a situation the expected number of surviving at time is less than . As a result, the probability of surviving being less than is higher than . In other words, must include at least vertices which means that .
To complete the proof, it must be shown that . For that, the asymptotic behavior of surviving is modeled by a continuous branching process. Fix and begin with Eve with the birthdate of . Assume time goes backward so Eve gives birth in the interval of with a unit density Poisson distribution. The probability of Eve having birth is . By conditioning on the birthtimes are independently and uniformly distributed on . Every birth given by Eve consists of offspring all with the same birth time say . The process is iterated for each offspring. It can be shown that for all there exists a so that with a probability higher than , Eve has at most descendants.
A rooted tree with the notions of parent, child, root, birthorder and wombmate shall be called a broodtree. Given a finite broodtree 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 denote the probability that Eve survives in the broodtree given by the above process. The objective is to show and then for any fixed , it can be shown that . These two relations complete our argument.
To show , let . For small, as, roughly, an Eve starting at time might have a birth in time interval all of whose children survive while Eve has no births in all of whose children survive. Letting yields the differential equation . The initial value gives a unique solution . Note that indeed .
To prove , consider a proceture we call History which either aborts or produces a broodtree. History contains a set of vertices, initially . will have a broodtree structure with the root. The are either processed or unprocessed, is initially unprocessed. To each is assigned a birthtime , we initialize . History is to take an unprocessed and process it as follows. For the value of all with but with no that has already been processed, if either some has and with or some have with and , then History is aborted. Otherwise for each with add all to as wombmates with parent and common birthdate . Now is considered processed. History halts, if not aborted, when all are processed. If History does not abort then root survives broodtree if and only if survives at time . For a fixed broodtree, let denote the probability that the branching process yields broodtree . Then the probability that History does not abort is . By the finiteness of the branching process, , the summation over all broodtrees and History does not abort. The distribution of its broodtree approaches the branching process distribution. Thus .
The Rödl nibble
In 1985, Rödl proved Paul Erdős’s conjecture by a method called the Rödl nibble. Rödl's result can be formulated in form of either packing or covering problem. For the covering number denoted by shows the minimal size of a family of k-element subsets of which have the property that every l-element set is contained in at least one . Paul Erdős et al. conjecture was
where . This conjecture roughly means that a tactical configuration is asymptotically achievable. One may similarly define the packing number as the maximal size of a family of k-element subsets of having the property that every l-element set is contained in at most one .
Packing under the stronger condition
For a k-uniform, D-regular hypergraph on n vertices, if k > 3, there exists a packing P covering all vertices but at most . If k = 3 there exists a packing P covering all vertices but at most .
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 .
- Branching process
- Independent set
- Graph coloring
- Covering number
- Set packing
- Ramsey's theorem
- Set cover problem
- Sphere packing
- Steiner system
- Erdős, P.; Hanani, H. (1963), "On a limit theorem in combinatorial analysis" (PDF), Publ. Math. Debrecen, 10: 10–13.
- Spencer, J. (1995), "Asymptotic packing via a branching process", Random Structures and Algorithms, 7 (2): 167–172, doi:10.1002/rsa.3240070206.
- Alon, N.; Spencer, J. (2008), The Probabilistic Method (3rd ed.), Wiley-Interscience, New York, ISBN 978-0-470-17020-5.
- Rödl, V.; Thoma, L. (1996), "Asymptotic packing and the random greedy algorithm", Random Structures and Algorithms, 8 (3): 161–177, doi:10.1002/(SICI)1098-2418(199605)8:3<161::AID-RSA1>3.0.CO;2-W.
- Spencer, J.; Pippenger, N. (1989), "Asymptotic Behavior of the Chromatic", Journal of Combinatorial Theory, Series A, 51 (1): 24–42, doi:10.1016/0097-3165(89)90074-5.
- Alon, N.; Kim, J.; Spencer, J. (1997), "Nearly perfect matchings in regular simple hypergraphs", Israel Journal of Mathematics, 100 (1): 171–187, doi:10.1007/BF02773639.