Packing in a hypergraph: Difference between revisions

Revision as of 19:38, 28 May 2010

Latest revision as of 22:51, 11 March 2025

(33 intermediate revisions by 23 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 [[VojtechVojtě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==

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. [[VojtechVojtěch 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 a '''''k''-uniform hypergraph''' if every edge in <math>''E</math>'' consists of exactly <math>''k</math>'' vertices.

<math>P</math> is a '''hypergraph packing''' if it is a subset of edges in H such that there is no pair of distinct edges with a common vertex.

Line 13 ⟶ 15:

<math>H</math> is a '''(<math>D_0</math>,<math>\epsilon</math>)-good hypergraph''' if there exists a <math>D_0</math> such that for all <math>x,y \in V</math> and <math>D\geq D_0</math> and both of the following conditions hold.

:<math> D(1-\epsilon)\leq \text{deg}(x)\leq D(1+\epsilon)</math>

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

where the ''degdegree'' <math>\text{deg} (x)</math> of a vertex denotes<math>x</math> is the number of edges that contain that vertex<math>x</math> and the ''codegcodegree'' <math>\text{codeg} (x,y)</math> of two distinct vertices denotes<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 degredegree 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.

Line 29 ⟶ 31:

==Asymptotic packing algorithms==

There are two famous algorithms for asymptotic packing of k-uniform hypegraphshypergraphs: which arethe 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 brachingbranching process distribution. Thus <math>\lim^* f_{x,H}(c)=f(c)</math>.

==The Rödl nibble==

In 1985, Rödl proved the [[Paul Erdős]]’s conjecture by a method called the Rödl nibble. RodlRö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 <math>codegree</math> condition that every distinct pair <math>v, v'\in V</math> havehas at most one edge in common.

For a <math>''k''-</math>uniform, <math>''D''-</math>regular hypergraph on <math>''n</math>'' vertices, if <math>''k'' > 3</math>, there exists a packing <math>''P</math>'' covering all vertices but at most <math>O(nD^{-1/(k-1)})</math>. If <math>''k'' = 3</math> there exists a packing <math>''P</math>'' covering all vertices but at most <math>O(nD^{-1/2}\ln^{3/2}D)</math>.

This bound is desirable in various applications, such as [[Steiner triple system]].

A Steiner Triple System is a <math>3-</math>uniform, simple hypergraph in which every pair of vertices is contained in precisely one edge. Since a Steiner Triple System is clearly <math>''d''=(''n''-1)/2-</math>regular, the above bound supplies the following asymptotic improvement.

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

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}}

* {{Citation

| last1 = Erdős| first1 = P. | author1-link = Paul Erdős

| last2 = Hanani | first2 = H.

| title = On a limit theorem in combinatorial analysis

| 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

| doi = 10.1002/rsa.3240070206

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

| title = Asymptotic packing via a branching process

| journal = Random Structures and Algorithms

| volume = 7

| issue = 2

| year = 1995

| pages = 167–172

}} .

* {{Citation

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

| last2 = Spencer | first2= J. | author2-link = Joel Spencer

| title = The Probabilistic Method

| publisher = Wiley-Interscience, New York

Line 105 ⟶ 111:

| edition = 3rd

| isbn = 978-0-470-17020-5

}}.

* {{Citation

| doi = 10.1002/(SICI)1098-2418(199605)8:3<161::AID-RSA1>3.0.CO;2-W

| last1 = Rödl| first1 = V. | author1-link = Vojtěch Rödl

| last2 = Thoma| first2 = L.

| title = Asymptotic packing and the random greedy algorithm

| journal = Random Structures and Algorithms

| volume = 8

| issue = 3

| 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

| issue = 1

| year = 1989

| pages = 24–42

| doi-access = free

}}

}}.

* {{Citation

| last1doi = Alon10.1007/BF02773639 | first1 doi-access= N.

| last2last1 = KimAlon| first2first1 = J.Noga | author1-link = Noga Alon

| last3last2 = SpencerKim| first3first2 = J. Jeong-Han

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

| title = Nearly perfect matchings in regular simple hypergraphs

| journal = [[Israel Journal of Mathematics]]

| volume = 100

| year = 1997

| issue = 1

| pages = 171–187

| citeseerx = 10.1.1.483.6704}}.

}}

{{refend}}

=External links=

* [http://www.cs.tau.ac.il/~nogaa/''Noga Alon's Hompage'']

* [http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/''Jeong Han Kim's Homepage'']

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

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

[[Category:Hypergraphs]]