Packing in a hypergraph: Difference between revisions

Revision as of 22:26, 11 March 2025

Latest revision as of 22:51, 11 March 2025

(2 intermediate revisions by the same user not shown)

Line 1:

[[File:Hypergraph packing.svg|thumb|The red subsetpartitioning of edges ofinto thethese graphtwo andsubsets theis bluecalled subset are eacha '''packingspacking''', as each edge in each subset has vertices not contained in any other edge within the givensame hypergraphsubset. The red subsetpacking is an [[optimal packing|optimal]], as itsthere edgesare contain2 thesubsets, highestand numberthere ofis verticesno possibleway forto thismake grapha (allpacking 9with in1 thissubset case)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==