Packing in a hypergraph: Difference between revisions

Revision as of 20:56, 17 May 2009

Revision as of 20:43, 18 June 2009

Line 1:

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 Rödl nibble and was proposed by [[Vojtech Rödl]] et al. They showed that the achievable packing by Rödl nibble is in some sense close to that of the random greedy algorithm.

==History==

The problem of finding the number of such subsets in a k-uniform [[hypergraph]] was originally motivated through a conjecture by [[Paul Erdős]] and [[Haim Hanani]] in 1963. [[Vojtech Rödl]] proved their conjecture asymptotically under certain conditions in 1985. Pippenger and [[Joel Spencer]] generalized Rödl's results using a random [[greedy algorithm]] in 1989.

==Definition and terminology==

In the following definitions, the [[hypergraph]] is denoted by <math>H=(V,E)</math>. <math>H</math> is called '''k-uniform hypergraph''' if every edge in <math>E</math> consists of exactly <math>k</math> vertices.

Line 18:

where ''deg'' of a vertex denotes the number of edges that contain that vertex and ''codeg'' of two distinct vertices denotes the number of edges that contain both vertices.

==Theorem==

There exists an asymptotic packing P of size at least <math>\frac{n}{K+1}(1-o(1))</math> for a <math>(k+1)</math>-uniform hypergraph under the following two conditions,

Line 27:

where <math>n</math> is the total number of vertices. This result was shown by Pippenger and was later proved by Joel Spencer. To address the asymptotic hypergraph packing problem, Joel Spencer proposed a random greedy algorithm. In this algorithm, a branching process is used as the basis and it was shown that it almost always achieves an asymptotically optimal packing under the above side conditions.

==Asymptotic packing algorithms==

There are two famous algorithms for asymptotic packing of k-uniform hypegraphs which are random greedy algorithm via branching process and Rödl nibble.

===Random greedy algorithm via branching process===

Every edge <math>E \in H</math> is independently and uniformly assigned a distinct real "birthtime" <math>t_E \in [0,D

Line 52:

where <math>2\leq l<k</math>. This conjecture roughly means that a tactical configuration is asymptotically achievable. One may similarly define the packing number <math>m(n,k,l)</math> as the maximal size of a family <math>\kappa</math> of k-element subsets of <math>\{1,...,n\}</math> having the property that every l-element set is contained in at most one <math>A \in \kappa</math>.

==Packing under the stronger condition==

In 1997, [[Noga Alon]], [[Jeong Han Kim]], and [[Joel Spencer]] also supply a good bound for <math>\gamma</math> under the stronger <math>codegree</math> condition that every distinct pair <math>v, v'\in V</math> have at most one dege in common.

Line 62:

Any Steiner Triple System on <math>n</math> vertices contains a packing covering all vertices but at most <math>O(n^{1/2}\ln^{3/2}n)</math>.

==See Alsoalso==

* [[Branching process]]

Line 74:

* [[Steiner system]]

==References==

{{refbegin|2}}

Line 144:

* [http://www.mathcs.emory.edu/~rodl/''Vojtech Rödl's Homepage'']

* [http://www.cs.nyu.edu/spencer/''Joel Spencer's Homepage'']

[[Category:Hypergraphs]]