Content deleted Content added
clean up; add reflist |
Added illustration and description. |
||
Line 1:
[[File:Hypergraph packing.svg|thumb|The red subset of edges of the graph and the blue subset are each '''packings''' in the given hypergraph. The red subset is an [[optimal packing]], as its edges contain the highest number of vertices possible for this graph (all 9 in this case).]]
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.
| |||