A new asymptotic enumeration technique

《A new asymptotic enumeration technique》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Anewasymptoticenumerationtechnique:theLov´aszLocalLemmaLinyuanLu∗L´aszl´oSz´ekely†UniversityofSouthCarolina{lu,szekely}@math.sc.eduFirstDraftMay26,2009AbstractOurpreviouspaper[14]appliedageneralversionoftheLov´aszLocalLemmathatallowsnegativedependencygraphs[11]tothesp

2、aceofran-dominjectionsfromanm-elementsettoann-elementset.Equivalently,thesamestorycanbetoldaboutthespaceofrandommatchingsinKn,m.NowweshowhowthecitedversionoftheLov´aszLocalLemmaappliestothespaceofrandommatchingsinK2n.Wealsoprovetightupperboundsthatasymptoticallymatcht

3、helowerboundgivenbytheLov´aszLocalLemma.Asaconsequence,wegivenewproofstoresultsontheenumer-ationofd-regulargraphs.ThetightupperboundscanbemodifiedtothespaceofmatchingsinKn,m,wheretheyyieldasapplicationasymptoticformulasforpermutationandLatinrectangleenumerationproblems

4、.Asanotherapplication,weprovideanewprooftotheclassicalprob-abilisticresultofErd˝os[8]thatshowedtheexistenceofgraphswitharbi-trarylargegirthandchromaticnumber.Inadditiontolettingthegirthandchromaticnumberslowlygrowtoinfinityintermsofthenumberofvertices,weprovidesuchagra

5、phwithaprescribeddegreesequence,ifthedegreesequencesatisfiessomemildconditions.1Lov´aszLocalLemmawithnegativedependencygraphsarXiv:0905.3983v1[math.CO]25May2009Thisisasequeltoourpreviouspaper[14]andweusethesamenotations.LetA1,A2,...,Anbeeventsinaprobabilityspace.Anegat

6、ivedependencygraphforA1,...,Anisasimplegraphon[n]satisfyingPr(Ai

7、∧j∈SAj)≤Pr(Ai),(1)∗ThisresearcherwassupportedinpartbytheNSFDMScontract0701111.†ThisresearcherwassupportedinpartbytheNSFDMScontract0701111.1foranyindexiandanysubsetS⊆{j

8、ij6∈E(G)},iftheconditionalprobabili

9、tyPr(Ai

10、∧j∈SAj)iswell-defined,i.e.Pr(∧j∈SAj)>0.Wewillmakeuseofthefactthatinequality(1)triviallyholdswhenPr(Ai)=0,otherwisethefollowinginequalityisequivalenttoinequality(1):Pr(∧j∈SAj

11、Ai)≤Pr(∧j∈SAj).(2)ForvariantsoftheLov´aszLocalLemmawithincreasingstrength,see[10,18,11,

12、13]:Lemma1[Lov´aszLocalLemma.]LetA1,...,AnbeeventswithanegativedependencygraphG.Ifthereexistnumbersx1,...,xn∈[0,1)suchthatYP