Brunn-Minkowski Inequalities for Contingency Table

arXiv:math/0603655v1[math.CO]28Mar2006BRUNN-MINKOWSKIINEQUALITIESFORCONTINGENCYTABLESANDINTEGERFLOWSAlexanderBarvinokMarch2006Abstract.Givenanon-negativem×nmatrixW=(wij)andpositiveintegervec-torsR=(r1,...,rm)andC=(c1,...,cn),weconsiderthetotalweightT(R,C;W)ofm×nnon-negativeintegermatrices(contingencytables)Dwiththerowsumsri,thecolumnsumscj,andtheweightofD=(dij)equaltoQijwdijij.Inparticular,ifWisa0-1matrix,T(R,C;W)isthenumberofintegerfeasibleflowsinabipartitenetwork.WeproveaversionoftheBrunn-MinkowskiinequalityrelatingthenumbersT(R,C;W)andT(Rk,Ck;W),where(R,C)isaconvexcombinationof(Rk,Ck)fork=1,...,p.1.Introduction(1.1)TheBrunn-Minkowskiinequality.ThefamousBrunn-Minkowskiin-equalitystatesthatforboundedBorelsetsA,B⊂Rdandnon-negativenumbersα,βsuchthatα+β=1onehasvol(αA+βB)≥volα(A)volβ(B),wherevolistheusualvolume(Lebesguemeasure)inEuclideanspaceRdandαA+βB={αx+βy:x∈A,y∈B}.Theinequalityextendstofinitefamiliesofsetsinanobviousway:ifA1,...,Ap⊂RdareboundedBorelsetsandα1,...,αparenon-negativenumberssuchthatα1+...+αp=1then(1.1.1)vol(α1A1+...+αpAp)≥pYk=1volαk(Ak).1991MathematicsSubjectClassification.05A16,52B12,52B20,52A41.Keywordsandphrases.contingencytables,permanent,Brunn-Minkowskiinequality,flowpolytopes,integerpoints,log-concavefunctions,matrixscaling.ThisresearchwaspartiallysupportedbyNSFGrantDMS0400617.TypesetbyAMS-TEX1TheBrunn-Minkowskiinequalityplaysanimportantroleinalmostallbranchesofmathematics,see[Ga02]forasurvey.Inequality(1.1.1)wasextendedandgeneral-izedinnumerousdirection.Inparticular,weneeditsfunctionalversion,knownasthePr´ekopa-Leindlerinequality:letα1,...,αpbenon-negativenumberssuchthatα1+...+αp=1andletg,h1,...,hp:Rd−→RbeBorelmeasurablenon-negativefunctionssuchthatg(α1x1+...+αpxp)≥pYk=1hαkk(xk)forallx1,...,xk∈Rd.Then(1.1.2)ZRdg(x)dx≥pYk=1ZRdhk(x)dxαk,seeforexample,Section6.1of[Vi03]andSection2.2of[Le01].Wenotethat(1.1.1)isobtainedfrom(1.1.2)bychoosinghktobetheindicatorfunctionofAk,sothathk(x)=1ifx∈Akandhk(x)=0ifx/∈Akandgtobetheindicatorofα1A1+...+αpAp.Theinequality(1.1.2)remainsvalidifdxisreplacedbyalog-concavemeasure.Inthispaperweobtainversionsofinequality(1.1.1),respectively(1.1.2),forthenumberofintegerpoints,respectivelyforthenumberofweightedintegerpoints,insomespecialpolytopes,knownasflowpolytopes.(1.2)Contingencytables.LetR=(r1,...,rm)andC=(c1,...,cn)beposi-tiveintegervectorssuchthatmXi=1ri=nXj=1cj=N.Anm×nnon-negativeintegermatrixD=(dij)withtherowsumsr1,...,rmandthecolumnsumsc1,...,cniscalledacontingencytablewithmarginsRandC.Geometrically,onecanthinkofthesetofcontingencytableswithprescribedmarginsasofthesetofintegerpointsinthetransportationpolytopeP(R,C)ofm×nmatricesX=(xij)satisfyingtheequationsnXj=1xij=rifori=1,...,m,mXi=1xij=cjforj=1,...,nandinequalitiesxij≥0foralli,j.Thenumbersofcontingencytableswithprescribedmarginsareofinterestbe-causeoftheirapplicationsinstatistics,combinatorics,andrepresentationtheory,see[DE85],[DG95],and[DG04].Weconsiderthenumberofweightedtables,definedasfollows.2(1.3)Definition.LetW=(wij)beanm×nnon-negativematrix.ForR=(r1,...,rm)andC=(c1,...,cn),wedefineT(R,C;W)=XDYijwdijij,wherethesumistakenoverallm×ncontingencytablesD=(dij)withthemargins(R,C).Weagreethat00=1.Geometrically,T(R,C;W)isthegeneratingfunctionoverthesetofintegerpointsinatransportationpolytope.WegetthenumberofpointsifwechooseW=1,thematrixofall1s.(1.4)Integerflows.LetG=(V,E)beadirectedgraphwiththesetVofvertices,thesetEofedges,withoutmultipleedgesorloops.Supposethatanintegera(v),calledtheexcessv,isassignedtoeveryvertexv∈VsothatXv∈Va(v)=0.Acollectionx(e):e∈Eofnon-negativeintegersiscalledanintegerfeasibleflowinGifthebalanceconditionissatisfiedateveryvertexXe:head(e)=vx(e)−Xe:tail(e)=vx(e)=a(v)forallv∈V.IfGdoesnotcontaindirectedcyclesv1→v2→...→vk→v1thenthesetoffeasibleflowsiscompact,sothenumberofintegerfeasibleflowsisfinite.Someinterestingquantitiescanbedefinedasthenumberofintegerfeasibleflowsinanappropriatenetwork.Forexample,wegettheKostantpartitionfunction(fortheAn−1rootsystem)ifG=KnisacompletegraphwiththesetofverticesV={1,...,n}andedgesE={i→j:ij},cf.[B+04].Givenanintegervectora=(a1,...,an)suchthata1+...+an=0,thenumberφ(a)ofintegerfeasibleflowsinKnwiththeexcessatiequalaiisthevalueoftheKostantpartitionfunctionata.GivenadirectedgraphGon|V|=nverticesandexcessesa(v)atitsvertices,onecanconstructann×nmatrixW=(wij)withwij∈{0,1},avectorR=(r1,...,rn)ofrowsumsandavectorC=(c1,...,cn)ofcolumnsumssothatT(R,C;W)isequaltothenumberofintegerfeasibleflowsinG.Tothatend,weidentifyV={1,...,n}.GiventheexcessaiatthevertexiofG,wefindanaprioriupperboundzi≥0onthetotalincomingflowtoiandletri=zi−aiandci=zi.Finally,weletwij=1ifi=jori→jisanedgeofGandletwij=0otherwise.Withafeasibleflow{xe:e∈E}inG,weassociateacontingencytableD=(dij)asfollows:weletdij=x(e)providedi=head(e)andj=tail(e)andletdii=ri−Xe:tail(e)=ix(e)=ci−Xe:head(e)=ix(e).3Further,weletdij=0ifwij=0.OnecanobservethatthiscorrespondenceisabijectionbetweentheintegerfeasibleflowsinGandthecontingencytablesenumeratedbyT(R,C;W).Forexample,fortheKostantpartitionfunction,weletwij=1ifi≥jandwij=0otherwiseanddefiner1=