Content deleted Content added
m Open access bot: hdl updated in citation with #oabot. |
Added "Matching in hypergraphs" to "See also" |
||
| (4 intermediate revisions by 2 users not shown) | |||
Line 1:
[[File:Hypergraph packing.svg|thumb|The partitioning of edges into these two subsets is called a '''packing''', as each edge in each subset has vertices not contained in any other edge within the same subset. The packing is [[optimal packing|optimal]], as there are 2 subsets, and there is no way to make a packing with 1 subset 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 34 ⟶ 36:
Every edge <math>E \in H</math> is independently and uniformly assigned a distinct real "birthtime" <math>t_E \in [0,D
]</math>. The edges are taken one by one in the order of their birthtimes. The edge <math>E</math> is accepted and included in <math>P</math> if it does not overlap any previously accepted edges. Obviously, the subset <math>P</math> is a packing and it can be shown that its size is <math>|P|=\frac{n}{K+1}</math> almost surely. To show that, let stop the process of adding new edges at time <math>c</math>. For an arbitrary <math>\gamma >0</math>, pick <math>c, D_0, \epsilon</math> such that for any <math>(D_0,\epsilon)</math>-good hypergraph <math>f_{x,H}(c)<\gamma^2</math> where <math>f_{x,H}(c)</math> denotes the probability of vertex <math>x</math> survival (a vertex survives if it is not in any edges in <math>P</math>) until time <math>c</math>. Obviously, in such a situation the expected number of <math>x</math> surviving at time <math>c</math> is less than <math>\gamma^2 n</math>. As a result, the probability of <math>x</math> surviving being less than <math>\gamma n</math> is higher than <math>1-\gamma</math>. In other words, <math>P_c</math> must include at least <math>(1-\gamma)n</math> vertices which means that <math>|P|\geq (1-\gamma)\frac{n}{K+1}</math>.
To complete the proof, it must be shown that <math>\lim_{c\rightarrow \infty} \lim_{x,H} f_{x,H}(c)=0</math>. For that, the asymptotic behavior of <math>x</math> surviving is modeled by a continuous branching process. Fix <math>c>0</math> and begin with Eve with the birthdate of <math>c</math>. Assume time goes backward so Eve gives birth in the interval of <math>[0,c)</math> with a unit density [[Poisson distribution]]. The probability of Eve having <math>k</math> birth is <math>\frac{e^{-c}c^k}{k!}</math>. By conditioning on <math>k</math> the birthtimes <math>x_1,...,x_k</math> are independently and uniformly distributed on <math>[0,c)</math>. Every birth given by Eve consists of <math>Q</math> offspring all with the same birth time say <math>a</math>. The process is iterated for each offspring. It can be shown that for all <math>\epsilon >0</math> there exists a <math>K</math> so that with a probability higher than <math>(1-\epsilon)</math>, Eve has at most <math>K</math> descendants.
Line 46 ⟶ 48:
==The Rödl nibble==
In 1985, Rödl proved [[Paul Erdős]]’s conjecture by a method called the Rödl nibble. Rödl's result can be formulated in form of either packing or covering problem. For <math>2\leq l<k<n</math> the covering number denoted by <math>M(n,k,l)</math> shows the minimal size of a family <math>\kappa</math> of <math>k</math>-element subsets of <math>\{1,...,n\}</math> which have the property that every <math>l</math>-element set is contained in at least one <math>A \in \kappa</math>. [[Paul Erdős]] et al. conjecture was
:<math>\lim_{n\rightarrow \infty} \frac{M(n,k,l)}{{n \choose l}/{k \choose l}}=1</math>.
Line 53 ⟶ 55:
==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 codegree condition that every distinct pair <math>v, v'\in V</math> has at most one edge in common.
For a ''k''-uniform, ''D''-regular hypergraph on ''n'' vertices, if ''k'' > 3, there exists a packing ''P'' covering all vertices but at most <math>O(nD^{-1/(k-1)})</math>. If ''k'' = 3 there exists a packing ''P'' covering all vertices but at most <math>O(nD^{-1/2}\ln^{3/2}D)</math>.
Line 75 ⟶ 77:
* [[Sphere packing]]
* [[Steiner system]]
* [[Matching in hypergraphs]]
==References==
{{Reflist}}
{{refbegin|2}}
| |||