Packing in a hypergraph: Difference between revisions

Revision as of 15:10, 11 February 2014

Latest revision as of 22:51, 11 March 2025

(21 intermediate revisions by 15 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.

==History==

Line 16 ⟶ 18:

:<math> \text{codeg}(x,y)\leq \epsilon D </math>

where the ''degree'' <math>\text{deg} (''x'')</math> of a vertex ''<math>x''</math> is the number of edges that contain ''<math>x''</math> and the ''codegree'' <math>\text{codeg} (''x'', ''y'')</math> of two distinct vertices ''<math>x''</math> and ''<math>y''</math> is 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>(kK+1)</math>-uniform hypergraph under the following two conditions,

#All vertices have the degree of <math>D(1+o(1))</math> in which <math>D</math> tends to infinity.

#For every pair of vertices shares only <math>o(D)</math> common edges.

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 hypegraphshypergraphs: the random greedy algorithm via branching process, and the 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

]</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 42 ⟶ 44:

To show <math>f(c)=0</math>, let <math>c\geq 0, \Delta c>0</math>. For <math>\Delta c</math> small, <math>f(c+\Delta c)-f(c) \approx -(\Delta c)f(c)^{Q+1} </math> as, roughly, an Eve starting at time <math> c+\Delta c</math> might have a birth in time interval <math>[c, c+\Delta c)</math> all of whose children survive while Eve has no births in <math>[0, c)</math> all of whose children survive. Letting <math>\Delta c\rightarrow 0 </math> yields the differential equation <math>f'(c)=-f(c)^{Q+1}</math>. The initial value <math>f(0)=1</math> gives a unique solution <math>f(c)=(1+Qc)^{-1/Q}</math>. Note that indeed <math>\lim_{c\rightarrow \infty} f(c)=0</math>.

To prove <math>\lim^* f_{x,H}(c)=f(c)</math>, consider a procetureprocedure we call History which either aborts or produces a broodtree. History contains a set <math>T</math> of vertices, initially <math>T=\{x\}</math>. <math>T</math> will have a broodtree structure with <math>x</math> the root. The <math>y\in T</math> are either processed or unprocessed, <math>x</math> is initially unprocessed. To each <math>y\in T</math> is assigned a birthtime <math>t_y</math>, we initialize <math>t_x=c</math>. History is to take an unprocessed <math>y\in T</math> and process it as follows. For the value of all <math>t_E</math> with <math>y\in E</math> but with no <math>x\in E</math> that has already been processed, if either some <math>E</math> has <math>t_E<t_y</math> and <math>y,z\in E</math> with <math>z\in T</math> or some <math>E, E'</math> have <math>t_E,t_{E'}<t_y</math> with <math>y\in E,E'</math> and <math>|E\cup E'|>1</math>, then History is aborted. Otherwise for each <math>E</math> with <math>t_E<t_y</math> add all <math>z\in E-\{y\}</math> to <math>T</math> as wombmates with parent <math>y</math> and common birthdate <math>t_E</math>. Now <math>y</math> is considered processed. History halts, if not aborted, when all <math>y\in T</math> are processed. If History does not abort then root <math>x</math> survives broodtree <math>T</math> if and only if <math>x</math> survives at time <math>c</math>. For a fixed broodtree, let <math>f(T,c)</math> denote the probability that the branching process yields broodtree <math>T</math>. Then the probability that History does not abort is <math>f(T,c)</math>. By the finiteness of the branching process, <math>\sum f(T,c)=1</math>, the summation over all broodtrees <math>T</math> and History does not abort. The <math>lim^*</math> distribution of its broodtree approaches the branching process distribution. Thus <math>\lim^* f_{x,H}(c)=f(c)</math>.

==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>.

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 <math>k</math>-element subsets of <math>\{1,...,n\}</math> having the property that every <math>l</math>-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 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 61 ⟶ 63:

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

This has subsequently improved to <math>n/3-O(\frac{\log n}{\log \log n})</math><ref>{{Cite journal |last1=Keevash |first1=Peter |authorlink1=Peter Keevash |last2=Pokrovskiy |first2=Alexey |last3=Sudakov |first3=Benny |authorlink3=Benny Sudakov |last4=Yepremyan |first4=Liana |date=2022-04-15 |title=New bounds for Ryser's conjecture and related problems |journal=Transactions of the American Mathematical Society, Series B |language=en |volume=9 |issue=8 |pages=288–321 |doi=10.1090/btran/92 |doi-access=free |issn=2330-0000|hdl=20.500.11850/592212 |hdl-access=free }}</ref> and <math>\frac{n-4}{3}</math><ref>{{Cite arXiv |last=Montgomery |first=Richard |date=2023 |title=A proof of the Ryser-Brualdi-Stein conjecture for large even ''n'' |class=math.CO |eprint=2310.19779}}</ref>

==See also==

Line 73 ⟶ 77:

* [[Sphere packing]]

* [[Steiner system]]

* [[Matching in hypergraphs]]

==References==

{{Reflist}}

{{refbegin|2}}

Line 83 ⟶ 89:

| journal = Publ. Math. Debrecen

| volume = 10

| year = 19632022

| issue = 1–4 | pages = 10–13

| doi = 10.5486/PMD.1963.10.1-4.02 | url = http://www.renyi.hu/~p_erdos/1963-07.pdf

}}.

* {{Citation

Line 116 ⟶ 122:

| year = 1996

| pages = 161–177

| citeseerx = 10.1.1.4.1394}}.

}}.

* {{Citation

| doi = 10.1016/0097-3165(89)90074-5

| last1 = Spencer| first1 = J. | author1-link = Joel Spencer

| last2 = Pippenger| first2 = N. | author2-link = Nick Pippenger

| title = Asymptotic Behavior of the Chromatic Index for Hypergraphs

| journal = [[Journal of Combinatorial Theory]] | series = Series A

| volume = 51

Line 127 ⟶ 133:

| year = 1989

| pages = 24–42

| doi-access = free

}}.

}}.

* {{Citation

| doi = 10.1007/BF02773639 | doi-access=

| last1 = Alon| first1 = N.Noga | author1-link = Noga Alon

| last2 = Kim| first2 = J.Jeong-Han

| last3 = Spencer| first3 = J.Joel | author3-link = Joel Spencer

| title = Nearly perfect matchings in regular simple hypergraphs

| journal = [[Israel Journal of Mathematics]]

Line 139 ⟶ 146:

| issue = 1

| pages = 171–187

| citeseerx = 10.1.1.483.6704}}.

}}.

{{refend}}