Chvátal's conjecture and correlation inequalities Ehud Friedgut.pdf

该【Chvátal's conjecture and correlation inequalities Ehud Friedgut 】是由【dt83088549】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【Chvátal's conjecture and correlation inequalities Ehud Friedgut 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..binatorialTheory,SeriesA156(2018)22–43ContentslistsavailableatScienceDirectbinatorialTheory,SeriesAate/jctaChvátal’sconjectureandcorrelationinequalitiesEhudFriedguta,1,Je?Kahnb,2,GilKalaic,3,NathanKellerd,4puterScience,WeizmannInstituteofScience,Rehovot76100,IsraelbDepartmentofMathematics,RutgersUniversity,Piscataway,NJ08854,USAcEinsteinInstituteofMathematics,HebrewUniversity,Jerusalem,IsraeldDepartmentofMathematics,BarIlanUniversity,RamatGan,IsraelarticleinfoabstractArticlehistory:Chvátal’binatoricsassertsthatReceived18September2016foranydecreasingfamilyFofsubsetsofa?nitesetS,thereAvailableonlinexxxxisalargestintersectingsubfamilyofFconsistingofallmem-Keywords:bersofFthatincludeaparticularx∈?uencesofvariablesChvátal’sconjectureonBooleanfunctionsandcorrelationinequalities,?uences??[n]={1,2,...,n}isintersectingifA∩B=?foranyA,B∈G,andincreasingifA?B∈GimpliesA∈G(andsimilarlyfordecreasing).E-mailaddresses:@(),******@(),******@(),@().1PartiallysupportedbyIsraelScienceFoundationgrant1168/-1201337andDMS-1501962andUnitedStates-,NationalScienceFoundationgrantDMS-1300120,andUnitedStates-,UnitedStates-IsraelBinationalScienceFoundationgrant2014290,:///.-3165/?.:.../binatorialTheory,SeriesA156(2018)22–4323Oneoftheseminalresults(maybetheseminalresult)binatoricsistheErd?s–Ko–Radotheorem[6],whichsaysthat,fork≤n/2,themaximumsizeofanintersectingsubfamilyofthefamilyFofallk-subsetsof[n]isn?1,thenumberofk?1k-setscontainingsome?xedx∈[n].Giventhis,itisnaturaltoaskwhethersomethingsimilarholdsforotherF’átal[4]saysthatthisistrueforeverydecreasingF:(Chvátal’sConjecture).ForanydecreasingF?2[n],somelargestinter-sectingsubfamilyhastheform{A∈F:x∈A}.Ofcourseitisnolongerthecasethatanyxwillsu?ce,andthedi?cultyofidentifyingasuitablexisacentralreasonfortheconjecture’átal’sConjecturehasbeenthesubjectofmanypapers5butprogresstodatehasbeenlimited,átal’sConjecturecanberestatedintermsofin?uences(de?nedbelow)andcorrelationinequalities,átal’sconjecturesuggestedbythesecondauthorabout25yearsago(seeSection3).We?rstrecallafewde?,weidentifysubsetsof[n]withel-ementsofthediscretecubeΩ={0,1},B?ΩisCov(A,B)=μ(A∩B)?μ(A)μ(B).Moregenerallyforf,g:Ω→RweuseCov(f,g)=Eμ[fg]?Eμ[f]Eμ[g](soCov(χA,χB)=Cov(A,B),whereweuseχforindicator).AfamilyFissaidtobeantipodalif|F∩{A,Ac}|=1foreachA?[n](plementofA).Thein?uenceofthekthvariableonA?ΩisIk(A)=2μ({x∈A|x⊕ek∈A}/),wherex⊕ekisgottenfromxbyreplacingxkby1??uenceofAisnI(A)=k=1Ik(A)andwewriteImin(A)formin1≤k≤nIk(A).RecallthatHarris’seminalcorrelationinequality[11]saysthatCov(A,B)≥0,forincreasingA,[21]initiatedthestudyof:“Howmuchareincreasingsetspositivelycorrelated?”,,Chvátal’sConjecturecanalsobeformulatedasacorrelationinequality,(both?Ω),Cov(A,B)≥1Imin(A).(1)45Alistofmorethan20papersdirectlyrelatedtotheconjectureappearsatthewebsite:.6SeanEberhardindependentlyconsideredsimilarrelations,motivatingaMathOver?owquestion[5].:.../binatorialTheory,SeriesA156(2018)22–:,B?ΩCov(A,B)≥cImin(A)μ(B)(1?μ(B)),(2)forsome?xed(positive),(2)isnottruewithc>ln2,evenifBisbalanced(.,μ(B)=1/2);inparticular,,Kahn’sstrongfromofChvátal’sconjecture()impliesthat(2)doesholdwithc=1/2,andthepossibilitythatthisrelaxationlosesonlyaconstantfactorseemstousoneofthemoreinterestingaspectsofthepresentdiscussion.(-balancedsetting.)Lowerboundsonthecorrelationsofincreasingfamiliesintermsofin?uenceswereob-tainedbyTalagrand[21](asalreadymentioned;)andbyKeller,Mossel,andSen[16]().InSection4,heseresultswithresultsaboutin?uencesofanindividualfamily(duetoKahn,Kalai,andLinial[14],andTa-lagrand[20]),(fairlystrong),forgeneralincreasingfamiliesA,B,Cov(A,B)≥cImin(A)μ(B)(1?μ(B))/log(1/Imin(A)).(3)TheseresultsmaybethoughtofasillustratingconnectionswithexistingFouriertech-(3),paredtowhatweareafter,[15]and,perhapssurprisingly,’’sconjecture.(HereweuseC?(S)fortheFouriercoe?cientχ?C(S);Fourierde?nitionsarerecalledinthenextsection.),B?Ω,n1?2Cov(A,B)≥cIk(A){B(S):Sk},(4)k=1|S|=(A,B)intermsofaweightedsumofthein?uencesofA,withthesumofweightsintheantipodalcaseequalto1/4(byParseval’sidentity;see(8)below).:.../binatorialTheory,SeriesA156(2018)22–átal’?Ωthefollowingstatementsareequivalent.(a)eTherisak∈[n]forwhichmax{|B|:B?Fintersecting}=|{A∈F:k∈A}|.e(b)Therisak∈[n]suchthatthemaximumcorrelationofFwithamaximalinter-sectingBisattainedbyB={A∈Ω:k∈A}.(c)Foranyincreasing,antipodalB?Ω,Cov(F,B)≤?1(Imin(F)).4Ofcourse(a),while(c),since,foranyA,B,Cov(A,B)=?Cov(Ac,B)(moregenerally,Cov(1?f,g)=Cov(1,g)?Cov(f,g)=?Cov(f,g)foranyf,g).(andstandard)thatthemaximumin(a)isthesameasmax{|F∩B|:Bmaximalintersecting},andthateachmaximalintersectingBisincreasingandantipodal,sohasmeasure1/2.(Fortheantipodality,notethatifB/∈BthenmaximalityimpliesthatBcontainssomeC?Bc,whenceBc∈B.)ThusformaximalintersectingBwehave|F∩B|=2n(Cov(F,B)+μ(F)/2),(5)whichimpliestheequivalenceof(a)and(b)(sincewemaximizetheleftsideof(5)bymaximizingCov(F,B)).Fortheequivalenceof(c)wejustobservethatforBasin(b)(sometimescalleda“dictatorship”)wehaveCov(F,B)=?μ({A∈F:A∪{x}∈F}/)/2=?Ik(F)/4.–WalshHarper’sclassicedge-isoperimetricinequality[10]says(thoughnotoriginallyinthislanguage)thatforallA?Ω,:.../binatorialTheory,SeriesA156(2018)22–43I(A)≥2μ(A)log2(1/μ(A)).(6)InparticularI(A)≥?:Ω→R,theFourier–Walshexpansionoffisthe(unique)representa-tionf={αSuS:S?[n]},whereuS(T)=(?1)|S∩T|forT?[n].The(Fourier)coe?cientsαSarealsodenotedf?(S).Since{uS}isanorthonormalbasisforthespaceoffunctionsf:Ω→R(relativetotheusualinnerproduct·,·withrespecttouniformmeasure),therepresentationisindeedunique,withf?(S)=f,uS,andwehaveParseval’sidentity:f,g=f?(S)?g(S)?f,g.(7)Thus(sinceμ(f)=f?(?))Cov(f,g)=f?(S)?g(S).(8)S=?Aswehavealreadydoneabove,wewillsometimesuseC?(S)forχ?C(S).Itisstandard(see?.[14])thatforanyA?Ωandi∈[n],Ii(A)=4{A(S):Si}.IfAisdecreasingthenalsoIi(f)=2A?({i})andifAisincreasingthenIi(f)=?2A?({i}).(-).,Bbeincreasingeventswithμ(B)=Cov(A,B)≥4Ik(A)Ik(B),(9)thenCov(A,B)≥1Imin(A)tlog(1/t).(10)22Inparticular,ifBisbalancedthenCov(A,B)≥1Imin(A).4:.../binatorialTheory,SeriesA156(2018)22–4327bining(9)andHarper’sinequalitygives111Cov(A,B)≥4Ik(A)Ik(B)≥4Imin(A)I(B)≥2Imin(A)tlog2(1/t).Again,;neither(9)(the“dreamrelation”)noritsconsequence(10),átal’sConjecturesug-gestedbythesecondauthorinanunpublishedmanuscriptintheearly90s[13].ThisbuiltonastrengtheningofChvátal’sConjectureproposedbyKleitman[18]?,g:Ω→R+.Wesaythatf?owstogifthereexistsv:Ω×Ω→R+suchthat:∈Ω,wehaveBv(A,B)=f(A).∈Ω,wehaveAv(A,B)=g(B).B,thenv(A,B)=0.Equivalently(viamax-?owmin-cut),f?owstogifAf(A)=Ag(A),andf(F)≥g(F)foreverydecreasingfamilyF(wheref(F)=A∈Ff(A)).(Foraprobabilistthe“?ow”visa“monotone”couplingoffandg;theequivalentconditionisstochasticdominationofgbyf(forwhichwedroptherequirementthatfandgbeprobabilitymeasures);andtheequivalenceisaninstanceofStrassen’sTheorem;.[19].)“principal”familyF=Fi={A:i∈A},wesetχF=χi(recallingthatχFistheindicatorofF).ThefollowingstrengtheningofChvátal’sconjecturewasproposedbyKleitman[18].()intersectingF?Ω,thereisaconvexncombinationi=1λiχiofχ1,...,χnthat?[7]observedthatthisisequivalenttoa“functional”formofChvátal’scon-jecture,:Ω→R+,g(F)átal’{0,1}-valuedg.:.../binatorialTheory,SeriesA156(2018)22–43Thesuggestionof[13]isaparticularsetofλi’sforKleitman’sconjecture;thesearemosteasilydescribedintermsoftheFourier–Walshcoe?:Ω→R,setf?(x)=max(f(x),0)2(thusf?(x)=f(x)2iff(x)isnonnegativeandf?(x)=0otherwise).Wecallfantipodaliff(Ac)=?f(A)foranyA?[n].Inparticular,ifFisanantipodalfamily,thenf=2·χF?([13]).Foranynondecreasing,antipodalf:Ω→R,if2λi=λi(f)={f?(S):max(S)=i}1≤i≤n,?n?thenf=i=1λiχi?,f?(?)=0,so(7)gives?2?2?n2?(n?1)?λi(f)=S=?f(S)=f,f?f(?)=2f(T)=2f(T).(11)?n?1?Thusf(T)=2λi=f(T),aprerequisitefortheconclusionofConjec-,whenf=2·χF?1withFmaximalintersecting,theλi’sareconvexcoe?cients,’’?,:Ω→Risnondecreasing,antipodalandI?Ωisdecreasing,then(withf?asabove)f?(I)≥f?(I).(12)Asnotedin[13],thefollowing,super?ciallymoregeneral,:Ω→Rbenon-?[n],letλS:[n]→R+besomefunctionsatisfyingn?2i=1λS(i)=f(S)andλS(i)=0?i/∈S,n?andsetλi=i∈SλS(i).Theni=1λiχi?(i)=f?(S)2χ.{i=maxS}Fortheequivalence:givenλS’sandλi’,f?=λiχi,andany(decreasing)I,wemayreordertheindicessothatd1(I)≥···≥dn(I),yielding??2?f(I)=Si∈SλS(i)di(I)≥idi(I){f(S):max(S)=i}≥f(I),:..