Negatively correlated random variables and Mason’s

arXiv:math/0602648v1[math.CO]28Feb2006NEGATIVELYCORRELATEDRANDOMVARIABLESANDMASON’SCONJECTUREDAVIDG.WAGNERAbstract.Mason’sConjectureassertsthatforanm–elementrankrmatroidMthesequence(Ik/mk
:0≤k≤r)islog-arithmicallyconcave,inwhichIkisthenumberofindependentk–setsofM.ArelatedconjectureinprobabilitytheoryimpliestheseinequalitiesprovidedthatthesetofindependentsetsofMsatisfiesastrongnegativecorrelationpropertywecalltheRayleighcondition.Thisconditionisknowntoholdforthesetofbasesofaregularmatroid.WeshowthatifωisaweightfunctiononasetsystemQthatsatisfiestheRayleighconditionthenQisacon-vexdelta–matroidandωislogarithmicallysubmodular.Thus,thehypothesisoftheprobabilisticconjectureleadsinevitablytoma-troidtheory.Wealsoshowthattwo–sumsofmatroidspreservetheRayleighconditioninfourdistinctsenses,andhencethatthePottsmodelofaniteratedtwo–sumofuniformmatroidssatisfiestheRayleighcondition.Numerousconjecturesandauxiliaryre-sultsareincluded.1.Introduction.Mason’sConjecture[28]isthatthesequence(Ik:0≤k≤r)ofnumbersofindependentk–setsofanm–elementrankrmatroidMislogarithmicallyconcaveinthestrongsense(I-4)that(Ik/mk
:0≤k≤r)islog–concave.Thatis,thatI2kmk
2≥Ik−1mk−1
·Ik+1mk+1
forall1≤k≤r−1.Aweakerformoftheconjectureis(I-2)thatthesequence(Ik:0≤k≤r)itselfislog–concave:I2k≥Ik−1Ik+1forall1≤k≤r−1.Mahoney[27]hasshownthat(I-2)holdsforgraphic(cycle)matroidsofouterplanargraphs.Dowling[15]hasshowntheinequalitiesI2k≥Ik−1Ik+1ingeneralfor1≤k≤7.Zhao[40]has1991MathematicsSubjectClassification.05A20;05B35,60C05,82B20.Keywordsandphrases.matroid,delta–matroid,logarithmicconcavity,Rayleighmonotonicity,Pottsmodel.ResearchsupportedbytheNaturalSciencesandEngineeringResearchCouncilofCanadaunderoperatinggrantOGP0105392.12DAVIDG.WAGNERshownthatI2k≥(1+1/k)Ik−1Ik+1ingeneralfor1≤k≤5.ThesearecurrentlythemostnotablepartialresultsonMason’sConjecture.Thereisarelatedconjectureinprobabilitytheory,butitsoriginisobscure.Pemantle[30]considersalotofconditionsofthiskind.TheBigConjecture3.4statesthatifω:B(E)→[0,∞)isanon-negativeweightfunctiononafiniteBooleanalgebraB(E),andiffk(ω):=PS⊆E:|S|=kω(S)forall0≤k≤m=|E|then(fk(ω)/mk
:0≤k≤m)islogarithmicallyconcave,providedthatωsatisfiessome-thingwecalltheRayleighcondition.Thisconditionisastrongpairwisenegativecorrelationpropertyamongrandomvariables{Xe:e∈E}correspondingtotheelementsoftheground–setE,withjointdistri-butionfunctionencodingtheweightfunctionω.TheRayleighcon-ditionisknowntoholdinitsweakestform(B–Rayleigh,forbases)forallregular(unimodular)matroids,andformanymore[13].TherearemorerefinedandinformativeversionsoftheRayleighconditionformatroids:I–Rayleigh,S–Rayleigh,andPotts–Rayleighforindependentsets,spanningsets,andthePottsmodel,respectively.ApositivesolutiontotheBigConjecturewouldbeaverygoodthing.Ifso,theneveryI–RayleighmatroidsatisfiesMason’sConjecture(I-4).InSection5weseethateveryseries–parallelmatroidisI–Rayleigh,andwehavereasontobelievethattheclassofI–Rayleighmatroidsmightcontainallgraphs,maybeallregularmatroids,perhapsevenmore.Thus,thislineofreasoninghasthepotentialforsubstantialprogressonMason’sConjecture.AlthoughtheBigConjecturehasnotbeenprovenwedohaveanewequivalentformofit,Conjecture3.11,whichstatesthatifωsatisfiestheRayleighconditionthenitssymmetrizationeωalsosatisfiestheRayleighcondition.Bytheexchangeable(symmetricfunction)caseoftheBigConjecture–thatis,Proposition3.6–thisimpliestheinequalitieson(fk(ω)).Thissuggestsanentirelydifferentapproachtowardstherequiredinequalities.InSection2webrieflyreviewsomeunimodalityconditionsfornon-negativerealsequences,somesequencesassociatedwithmatroids,andsomerelevantunimodalityconjecturesandresults.Thisismeanttoputtheresultsoflatersectionsincontext.InSection3welookatsomeexamples,statetheBigConjecture3.4,provetheexchangeablecaseProposition3.6ofit,andreviewsomesupplementaryresults.ThisisalsopartlyacapsulesummaryofsomeofSection2.4ofPemantle[30].ThenwegiveanewequivalentformoftheBigConjecture3.11,and,aftersomealgebra,thesufficientconditionsConjectures3.13and3.14.TheselattertwoconjecturesaremorelocalNEGATIVECORRELATION3than3.11,soeventhoughtheyarestrictlystrongertheymightbemoreamenabletoproof.InSection4weshowthatifωisRayleighthenSupp(ω),thesetofsetsonwhichωispositive,isaconvexdelta–matroid,andthatωislogarithmicallysubmodular.RegardingtheconjecturesofSection2thisisanegativeresult:theBigConjectureisdirectlyrelevantonlytoMason’sConjecture(I-4).Ontheotherhand,thisstructuremightbeusefulinanattempttoprovetheBigConjecture.InSection5weturntofindingexamplestopopulatethetheory.WeseethatuniformmatroidsarePotts–Rayleigh.WeshowthattheRayleighconditiononthePottsmodelpartitionfunctionispreservedbytwo–sumsofmatroids.Consequently,everyseries–parallelmatroidisPotts–Rayleigh.Analogously,two–sumspreservetheRayleighcon-ditionformatroidsinanyofthethreefrozensenses:forbases,forinde-pendentsets,orforspanningsets.ConcerningtheI–Rayleighpropertyforgraphswehaveafewsmallexamplesandtworelativelytechnicalconjectures.CJSSS[9]givesthegeneratingfunctionforthesetofspanningforestsofagraphasaGrassmann–Berezinintegral.Thisisabeautifulresult