Packing in a hypergraph: Difference between revisions

Revision as of 22:26, 11 March 2025

Revision as of 22:44, 11 March 2025

Line 1:

[[File:Hypergraph packing.svg|thumb|The red subsetpartitioning of edges ofinto thethese graphtwo andsubsets theis bluecalled subset are eacha '''packingspacking''' in the given hypergraph. The red subset is an [[optimal packing]], as itseach edgesedge containin theeach highestsubset number ofhas vertices possiblenot forcontained thisin graphany (allother 9edge inwithin thisthe case)same subset.]]

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.