Integer and fractional packing of families of graphs

Let F be a family of graphs. For a graph G, the F-packing number, denoted νF(G), is the maximum number of pairwise edge-disjoint elements of F in G. A function ψ from the set of elements of F in G to [0, 1] is a fractional F-packing of G if ? e∈H∈F ψ(

3

2

l

Ju

7

2

]

O

C

.

th

a

m

[

4

v

5

3

5

3

/

tha

m

:v

i

Xr

aIntegerandfractionalpackingoffamiliesofgraphsRaphaelYuster DepartmentofMathematicsUniversityofHaifaatOranimTivon36006,IsraelAbstractLetFbeafamilyofgraphs.ForagraphG,theF-packingnumber,denotedνF(G),isthemaximumnumberofpairwiseedge-disjointelementsofFinG.AfunctionψfromthesetofelementsofFinGto[0,1]isafractionalF-packingofGif e∈H∈Fψ(H)≤1foreache∈E(G).ThefractionalF-packingnumber,denotedν F(G),isde nedtobethemaximumvalueof H∈(GF)ψ(H)overallfractionalF-packingsψ.OurmainresultisthatνF(G) νF(G)=o(|V(G)|2).Furthermore,asetofνF(G) o(|V(G)|2)edge-disjointelementsofFinGcanbefoundinrandomizedpolynomialtime.ForthespecialcaseF={H0asigni cantlysimplerproofofarecentdi cultresultofHaxellandR¨odl[8]that}weν obtainH0(G) νH0(G)=o(|V(G)|2).1IntroductionAllgraphsconsideredhereare niteandhavenoloops,multipleedgesorisolatedvertices.Forthestandardterminologyusedthereaderisreferredto[3].LetFbeany xed niteorin nitefamilyofgraphs.ForagraphG,theF-packingnumber,denotedνF(G),isthemaximumnumberofpairwiseedge-disjointcopiesofelementsofFinG.AfunctionψfromthesetofcopiesofofFinGto[0,1]isafractionalF-packingofGif elements

e∈H∈Fψ(H)≤1foreache∈E(G).For

afractionalF-packingψ,letw(ψ)=

νF (G),isde nedtobethemaximum H∈(G

valueFof)ψ(H).ThefractionalF-packingnumber,denoted

w(ψ)overallfractionalpackingsψ.Noticethat,

trivially,νF (G)≥νF(G).IfFconsistsofasinglegraphH0weshalldenotetheparametersabovebyνHH

0(G)andν0(G).

SincecomputingνF (G)amountstosolvingalinearprogram,itcanbecomputedinpolynomialtimeforevery niteF.Ontheotherhand,itwasprovedbyDorandTarsiin[4]thatcomputingνH0(G)isNP-HardforeveryH0withacomponenthavingatleastthreeedges.Thus,itisinteresting

Let F be a family of graphs. For a graph G, the F-packing number, denoted νF(G), is the maximum number of pairwise edge-disjoint elements of F in G. A function ψ from the set of elements of F in G to [0, 1] is a fractional F-packing of G if ? e∈H∈F ψ(

todeterminewhenνF (G)andνF(G)are“close”,therebygettingapolynomialtimeapproximatingalgorithmforanNP-Hardproblem.ThefollowingresultwasprovedbyHaxellandR¨odlin[8].Theorem1.1IfH0isa xedgraphandGisagraphwithnvertices,thenνH

0(G) νH0(G)=

o(n2).

The25pageproofofTheorem1.1presentedin[8]isverydi cult.Themajordi cultyliesinthefactthattheirmethodrequiresprovingthatthereisafractionalpackingwhichisonlyslightlylessthanoptimal,andwhichassignstoeverycopyofH0either0oravaluegreaterthanτforsomeτ>0whichisonlyafunctionofH0.

Inthispaperwepresentasigni cantlysimplerproofofTheorem1.1.OurproofmethodenablesustogeneralizeTheorem1.1tothe“family”case.Theredoesnotseemtobeaneasywaytogeneralizetheproofin[8]tothefamilycase.

Theorem1.2IfFisa xedfamilyofgraphsandGisagraphwithnvertices,thenνF (G) νF(G)=o(n2).

NoticethatTheorem1.2immediatelyyieldsapolynomialtimealgorithmforapproximatingνF(G)towithinanadditivetermof n2forevery >0.Furthermore,ifFis nite,thedegreeofthepolynomialdependsonlyonF,andnoton1/ .Ourproofalsosuppliesarandomizedpolynomialtimealgorithmthat ndsasetofνF(G) o(n2)edge-disjointcopiesofelementsofFinG.2Toolsusedinthemainresult

Asin[8],acentralingredientinourproofofthemainresultisSzemer´edi’sregularitylemma[9].LetG=(V,E)beagraph,andletAandBbetwodisjointsubsetsofV(G).IfAandBarenon-empty,letE(A,B)denotesetofedgesbetweenthem,andpute(A,B)=|E(A,B)|.ThedensityofedgesbetweenAandBisde nedas

d(A,B)=e(A,B)

Let F be a family of graphs. For a graph G, the F-packing number, denoted νF(G), is the maximum number of pairwise edge-disjoint elements of F in G. A function ψ from the set of elements of F in G to [0, 1] is a fractional F-packing of G if ? e∈H∈F ψ(

Lemma2.1Foreveryγ>0,thereisanintegerM(γ)>0suchthatforeverygraphGofordern>Mthereisaγ-regularpartitionofthevertexsetofGintomclasses,forsome1/γ<m<M.

d(i,j) <ζtk 2.

3Proofofthemainresult

LetFbeafamilyofgraphs,andlet >0.ToavoidthetrivialcaseweassumeK2∈/F.WeshallprovethereexistsN=N(F, )suchthatforalln>N,ifGisann-vertexgraphthen (G) ν(G)< n2.

νFF

3

Let F be a family of graphs. For a graph G, the F-packing number, denoted νF(G), is the maximum number of pairwise edge-disjoint elements of F in G. A function ψ from the set of elements of F in G to [0, 1] is a fractional F-packing of G if ? e∈H∈F ψ(

Letk∞denotethemaximalorderofagraphinF.Letk0=min{k∞, 20/ }.Letδ=β= /4.2k0Forallr=2,...,k02,letµr=µ(β,r)beasinLemma2.3,andputµ=minr=2{µr}.Let2ζ=µδk0/2.Fork=3,...,k0,letγk=γ(δ,ζ,k)andTk=T(δ,ζ,k)beasinLemma2.2.Let

20γ=minkk=3{γk}.LetM=M(γ /(25k0))beasinLemma2.1.Finally,weshallde neNto

beasu cientlylargeconstant,dependingontheabovechosenparameters,andforwhichvariousconditionsstatedintheproofbelowhold(itwillbeobviousintheproofthatalltheseconditionsindeedholdforNsu cientlylarge).Thus,indeed,N=N(F, ).

(G).Fixann-vertexgraphGwithn>Nvertices.FixafractionalF-packingψwithw(ψ)=νF

WemayassumethatψassignsavaluetoeachlabeledcopyofanelementofFsimplybypidingthevalueofψoneachnonlabeledcopybythesizeoftheautomorphismgroupofthatelement.If (G)< n2wearedone.Hence,weassumeν (G)=αn2≥ n2.νFF

′WeapplyLemma2.1toGandobtainaγ-regularpartitionwithm′parts,whereγ′=γ /(25k02)

and1/γ′<m′<M(γ′).DenotethepartsbyU1,...,Um …… 此处隐藏：12333字，全部文档内容请下载后查看。喜欢就下载吧 ……