Content deleted Content added
Correction, the whole thing is a single packing. |
Added "Matching in hypergraphs" to "See also" |
||
| (One intermediate revision by the same user not shown) | |||
Line 1:
[[File:Hypergraph packing.svg|thumb|The partitioning of edges into these two subsets is called a '''packing''', as each edge in each subset has vertices not contained in any other edge within the same subset. The packing is [[optimal packing|optimal]], as there are 2 subsets, and there is no way to make a packing with 1 subset due to some edges covering the same vertices.]]
In mathematics, a '''packing in a hypergraph''' is a [[Partition of a set|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.
Line 77:
* [[Sphere packing]]
* [[Steiner system]]
* [[Matching in hypergraphs]]
==References==
| |||