Packing in a hypergraph: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 15:08, 12 May 2009 edit Ntsimp (talk \| contribs) Autopatrolled, Extended confirmed users, Pending changes reviewers, Rollbackers 34,639 edits Mathematics ← Previous edit		Latest revision as of 22:51, 11 March 2025 edit undo BagLuke (talk \| contribs) Extended confirmed users 578 edits Added "Matching in hypergraphs" to "See also"
(40 intermediate revisions by 27 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 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.▼ ▲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 [[~~Vojtech~~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=▼ ▲==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. ▼ ▲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~~Vojtě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=▼ ▲==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.▼ ▲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 ''~~deg~~degree'' <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 ''~~codeg~~codegree'' <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 ~~degre~~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 ~~hypegraphs~~hypergraphs: ~~which are~~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 ~~proceture~~procedure 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 ~~braching~~branching 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. ~~Rodl~~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 ~~<math>~~codegree~~</math>~~ condition that every distinct pair <math>v, v'\in V</math> ~~have~~has at most one ~~dege~~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=▼ ▲==See ~~Also~~also== * [[Branching process]] * [[Independent set (graph theory)\|Independent set]] * [[Graph coloring]] * [[Covering number]] 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 = ~~1963~~2022 \| issue = 1–4 \| pages = ~~10-13~~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~~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~~161–177 \| citeseerx = 10.1.1.4.1394}}. }} * {{Citation \| doi = 10.1016/0097-3165(89)90074-5 ~~\| last1 = Spencer\| first1 = J.~~ \| ~~last2~~last1 = ~~Pippenger~~Spencer\| first1 = NJ. \| 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~~24–42 \| doi-access = free }} }}. * {{Citation \| ~~last1~~doi = ~~Alon~~10.1007/BF02773639 \| ~~first1~~ doi-access= N. \| ~~last2~~last1 = ~~Kim~~Alon\| ~~first2~~first1 = J.Noga \| author1-link = Noga Alon \| ~~last3~~last2 = ~~Spencer~~Kim\| ~~first3~~first2 = 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 \| ~~pages~~issue = ~~171-187~~1 \| pages = 171–187 }} \| citeseerx = 10.1.1.483.6704}}. {{refend}} [[Category:Hypergraphs]] ~~=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'']