A new asymptotic enumeration technique

A new asymptotic enumeration technique

ID:40243873

大小:277.47 KB

页数:25页

时间:2019-07-28

A new asymptotic enumeration technique_第1页
A new asymptotic enumeration technique_第2页
A new asymptotic enumeration technique_第3页
A new asymptotic enumeration technique_第4页
A new asymptotic enumeration technique_第5页
资源描述:

《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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。