Packing in a hypergraph

<p>In mathematics, a packing in a hypergraph is a <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> of the set of the <a href="/facts/Hypergraph/qIR2o2I3">hypergraph</a>'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 <a href="/facts/Optimal_packing/nQtnMb6Y">optimal packing</a> in <i>k</i>-uniform hypergraphs. One of them is a random <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a> which was proposed by <a href="/facts/Joel_Spencer/dhg8jEo4">Joel Spencer</a>. He used a <a href="/facts/Branching_process/JzdGdWrQ">branching process</a> to formally prove the optimal achievable bound under some side conditions. The other algorithm is called the Rödl nibble and was proposed by <a href="/facts/Vojt%C4%9Bch_R%C3%B6dl/8h2dy5dU">Vojtěch Rödl</a> 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.
</p>

Packing in a hypergraph open-in-new

Packing in a hypergraph