The penultimate rate of growth for graph properties

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPH

PROPERTIES

´´´ANDDAVIDWEINREICHJOZSEFBALOGH,BELABOLLOBAS,

Abstract.GivenapropertyPofgraphs,writePnforthesetofgraphswith

vertexset[n]havingpropertyP.Wecall|Pn|thespeedofP.Recentresearch

hasshownthatthespeedofamonotoneorhereditarypropertyPcanbea

constant,polynomial,orexponentialfunctionofn,andthestructureofthe

graphsinPcanthenbewelldescribed.Similarly,|Pn|canbeoftheform2(1 1/k+o(1))n(1 1/k+o(1))n/2or2forsomek>1andthepropertiescanben

describedandhavewellbehavedspeeds.Inthispaper,wediscussthebehavior

ofpropertieswithspeedsbetweentheselatterbounds,i.e.betweenn(1+o(1))n

2and2(1/2+o(1))n/2.

1.Introduction

Agraphpropertyisa(in nite)collectionof(labeled)graphsclosedunderiso-morphism.Thepropertyconsistingofall nitegraphsiscalledthetrivialproperty.Apropertyishereditaryifitisclosedundertakinginducedsubgraphs,anditismonotoneifitisclosedundertakingsubgraphs.Forexample,beingacyclic,planar,orperfectarehereditaryproperties,whileonlythe rsttwoaremonotone.Rathertrivially,everyhereditarypropertycanbede nedintermsofforbiddeninducedsubgraphs,andeverymonotonepropertycanbede nedintermsofforbiddensub-graphs.

GivenapropertyP,writePnforthesetofallgraphsinPwithnvertices.Wecallthisthen-levelofP.Thenumberofgraphsinthen-level,|Pn|,iscalledthespeedofaproperty.Inrecentyears,therehasbeenmuchresearchintothesequence(|Pn|)∞n=1forhereditaryproperties(see,forexample,[13],[5],[1])andformonotoneproperties(see,forexample,[2],[6]).Themostnaturalquestionsaboutthespeedofahereditaryproperty,which rstappearedin[13],areasfollows.

1.Doeslimn→∞

2.Doeslimn→∞

3.Doeslog|Pn|nexistforallhereditarypropertiesP?log|P|existforallhereditarypropertiesP?

log|Pn|limn→∞log

existforallhereditarypropertiesP?n|P|limn→∞log

existforallhereditarypropertiesP?4.Does

The rstquestionwasanswereda rmativelybyScheinermanandZitoin[13],andtheotherswereleftbythemasopenquestions.Thefourthquestionwasanswereda rmativelybyBollob´asandThomasonin[5].However,thesecondandthirdquestionsremainedopen.Inthispaperweanswerbothnegatively,evenunderastrongconditiononthestructureoftheproperty.Indoingso,weshedsomelightonagapintheexistingresearchonspeeds.

Whileinvestigatingthequestionsabove,ScheinermanandZito[13]discoveredthatthespeedsequenceoftenhasawell-de nedbehavior.Theypresentedaroughhierarchyofspeedsforhereditaryproperties,showingthatthespeedofapropertymustfallintocertainrangesofgrowth.EarlierresultsbyBollob´asandThomasonResearchpartiallysupportedbyOTKAgrantF026049.

ResearchpartiallysupportedbyNSFGrantDMS9971788.

1

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

2´´´JOZSEFBALOGH,BELABOLLOBAS,ANDDAVIDWEINREICH

[5]hadshownthatthehighestspeedofgrowthishighlyconstrainedaswell.Thepresentauthorsprovidedamoredetailedpictureofthehierarchyofspeedsforhereditarypropertiesin[1]andfurthermoredescribedthestructureofpropertiesfallingintoeachrangeofspeed.Similarresultsformonotonepropertieswereshownin[2].

Theseresultscanbebrie ysummarizedinthefollowingtheorem,whichpresentsfourfunctionalrangesintowhichthespeedofahereditarypropertymayfall.The rstlevelofgrowthcanbedividedintothreepartsdependingonwhetheri=0,i=1,ori>1.

Theorem1.LetPbeahereditarypropertyofgraphs.Thenoneofthefollowingistrue:

1.thereexistsN,k∈Nandacollection{pi(n)}ki=0ofpolynomialssuchthatfor kalln>N,|Pn|=i=0pi(n)in,

2.thereexistsk∈N,k>1suchthat|Pn|=n(1 1/k+o(1))n,

23.n(1+o(1))n≤|Pn|≤no(n),

24.thereexistsk∈N,k>1suchthat|Pn|=2(1 1/k+o(1))n/2.

The rsttwocasesandajumptothethirdaredescribedandprovenbytheauthorsin[1,3].Thelastcaseandthegapbetweencase3and4areshownbyBollob´asandThomassonin[5,6].Speci cally,Theorem1andtheresultsof[1]implythatifthespeedofapropertyfallsintoeitherthe rsttwoorthe nalrange,thespeedactuallyapproachesalimitingfunctionandthestructureofgraphsinthepropertycanbedescribed.EvenfromtheformofthestatementofTheorem1,however,itisclearthattheexactbehaviorofpropertieswithspeedsfallingintothethirdrangeisnotwellunderstood.

Forthisrange,eventheboundshavenotbeenfullydescribed,althoughthelowerboundisunderstoodandcanbeapproximatedusingresultsfrom[2].InSection2ofthispaper,weexploretheupperboundofthisrangeandshow,asintheotherranges(includingwithinthe rstrange),thatthereisadiscontinuousjumpintherangesofspeedsallowed.

InSection3wedescribeatypeofproperty,aselectivelyrestrictedproperty,whichexistsinthepenultimaterangeofgrowth.Weshowthatsomeselectivelyrestrictedpropertieshavespeedstowardsthebottomofthethirdrangeofgrowth,whileothershavehighspeeds.

InSection4,wedemonstrateparticularselectivelyrestrictedpropertieswhichprovideanin nitecollectionofnegativeexamplesforthesecondandthirdquestionsofScheinermanandZito.Speci cally,wedescribeamonotone(andhenceheredi-tary)propertywithspeedthatoscillatesin nitelyoftenbetweentwofunctionsneartheupperandlowerboundsonthepenultimaterange.

Inthetwosubsequentsections,wediscussimprovementsontheconstructiongiveninSection4.Weclosewithaconjecturethattheresultspresentedherearenearlythebestonecouldobtain.

2.Boundsonthefactorialrange

Whataretheactualupperandlowerlimitsonthepenultimaterangeofgrowth?Theorem1impliesthatifPishereditaryandforsome >0wehave|Pn|<n(1 )nforin nitelymanyvaluesofn,thenthepropertywillfallintoranges1or2.Thesameistrueformonotoneproperties,asisshownin[2].Thetheoremalsosuggests

2thatifthereisacsuchthat|Pn|>2cnforin nitelymanyvaluesofn,thenthe

speedofthepropertyfallsintorange4.

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPHPROPERTIES3

Infact,itisshownin[3]thatthesmallestpropertyinthepenultimaterangeisthepropertyPclique={G:everycomponentofGiscomplete}orthecom-

nplementaryproperty.Thesepropertieshavespeed|Pclique|=b(n),whereb(n)

isthenthBellnumber.Hencethelowerboundonthisspeedrangeisb(n)～ 1 1/lognnnn(logn) n.

Withthelowerboundknown,webeginourinvestigationofthepenultimate2rangeatitsupperbound.Whatspeedsofthetype2o(n)arepossibleforgraphproperties?Thisquestionmaybeansweredmoreeasilyformonotonethanforhereditaryproperties;infactthequestionisopenforthelatterclass.Weshallshow2 thatgivenanymonotonepropertyP,eitherthereisan suchthat|Pn|<2nor

(1/4+o(1))n2elsethespeedisatleast2.

Notationandde nitions:ForagraphG,wewritev(G)=|V(G)|ande(G)=|E(G)|.Further,wecallagraphGann-graphifv(G)=n,andH Gak-subgraphifv(H)=k.Thecollectionoflabeledn-graphs(on[n])isdenotedGn.

Thefollowinglemmaisasimpleobservationwhichnonethelessprovidesstronginformationaboutlargegraphproperties.

Lemma2.Let >0and0<c≤2.ThereisanNsuchthatforalln>N,ifS2 c+ isasetofgraphsonnverticesand|S|>2n,thenthereisagraphG∈Swithe(G)>n2 c.

Proof.Letfc(n)bethenumberofgraphsonnverticeswithatmostn2 cedges.Then,

fc(n)≤2 cn n

j

=2 ≤n2 cj=0en22n2 c2 c n2 c e n2 c

n2 cncn=2n2 c(lg(e/2)+clgn)+(2 c)lgn=2n2 c+o(1).

Henceforall thereisanNsuchthatforalln>N,fc(n)<2n.Thusif

2 c+ n>NandthereisacollectionSofn-graphswith|S|>2n,thenthereisa

2 cgraphG∈Swithe(G)>n.

Wearenowreadytoprovethemainresultofthissection.NotethatapropertyPismonotoneifandonlyifthereisa(possiblyin nite)collectionHofgraphssuchthatP=Mon(H),whereMon(H)isthesetofallgraphsGsuchthatnosubgraphofGisisomorphictoanyH∈H.Wealsode neHer(H)asthesetofallgraphsGsuchthatnoinducedsubgraphofGisisomorphictoanyH∈H.

Theorem3.LetPbeamonotoneproperty.If|Pn|=2o(n),thenthereisat≥1

2 1/t+o(1)suchthat|Pn|≤2n.

Proof.LetP=Mon(H)beamonotonepropertywithspeed|Pn|=2o(n).IfeverygraphH∈Hhaschromaticnumberatleast3,then{G:Gisbipartite}

1nMon(H)=P,inwhichcase|Pn|≥2(2).HenceHcontainsabipartitegraph

H.LettbetheorderofthelargersetinthebipartitionofH.Assumeforthe

2 1/t+o(1)sakeofcontradictionthat|Pn|>2n.ByLemma2,thereisthenaG∈P

ov´ari,S´os,andTur´an[8]saysthatGsuchthate(G)>n2 1/t.AresultofK

containsthegraphKt,tasasubgraph.ThusGcontainsHasasubgraph,whichisacontradiction.222 c+

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

4´´´JOZSEFBALOGH,BELABOLLOBAS,ANDDAVIDWEINREICH

2Theresultaboveisnearlythebestresultpossibleaboutthegapbelow2cn.In

theproof,weshowedthatlargepropertiesmustcontainlargecompletebipartitegraphs.Ontheotherhand,wecanconstructpropertiesthatnearlyreachtheupperboundgivenforwhichalargecompletebipartitegraphisforbidden.Todoso,weusethewell-knownfactthatforanytthereexistsabipartitegraphwithatleastn2 2/tedgesthatcontainsnosubgraphisomorphictoKt,t(see,i.e.,[4],p.316,

2Thm.VI.2.10).Hence,forexample,ifP=Mon({Kt,t,K3}),then|Pn|=2o(n)

2 2/t2 2/tand|Pn|≥2n.ThusTheorem3infactguaranteesatsuchthat2n≤2 1/t|Pn|<2n.Weconjecturethatthesameistrueforhereditaryproperties,and

2 2/tagainthiswouldbethebestpossible,as|Pn|≥2nforP=Her({Kt,t,K3}).Theconjecturebelowdi ersfromTheorem3onlyinconsideringhereditaryrather

thanmonotoneproperties.

Conjecture4.LetPbeahereditaryproperty.If|Pn|=2o(n),thenthereisa

2 1/tt≥1suchthat|Pn|≤2n.

Thisconjectureisfarfromproven,however.Whileitwouldbesurprising,itisnotinconceivablethattherecouldbepropertieswithotherspeeds.AresultofRuzsaandSzemer´ediabouthypergraphssuggeststhatpropertiesofhypergraphsdonotbehavesonicely,butthecalculationsandconsiderationsarecompletelydi erent.

3.Somespecialpropertiesandtheirgrowth

TheresultsoftheprevioussectionimplythatifthespeedofPisinthepenul-

2 1/ttimaterange,thereisanintegert≥1suchthatn(1+o(1))n<|Pn|<2n.This

isprovenformonotonePbutonlyconjecturedforhereditaryP.Wenowturnourattentiontothequestionofwhatspeedsareactuallyachievedinthisrangeforgraphproperties,eithermonotoneorhereditary.Wepresentacollectionofpropertieswithspeedslyingintherange.

Our rstpropertyisde nedintermsofthedensityofsubgraphs.Wede nethec-densepropertyQcbyQc={G:e(H)≤cv(H)forallH G}.ThefollowingassertionwasprovedbyScheinermanandZito[13].

(c+o(1))nTheorem5.Foranyc>1,|Qn.c|=n2

ThepropertyQcisamonotoneproperty,andthisresultshowsthatanyspeedofthetypencn,c>1isachievable.Thenextpropertywedescribeisnotmonotoneorhereditary,butitsn-levelcontainsthen-levelofQc.Itwillbeusefulinfurther

n={G∈Gn:e(G)≤cn}.proofsinthissection.Thec-densen-levelissimplyScThefollowinglemmagivesaboundonitssize.

nLemma6.Ifc>1,then|Sc|<f(n)ncn,withf(n)=O(1.5n).

Proof.Notesimplythat

cn n cn j 2n2|Sc|≤≤en/2jjj=0j=0

where,easily,f(n)=O(1.5n). cncn<cnen2/2cn=cn(en/2)=f(n)ncn,

Weshowedintheprevioussectionthattherearepropertieswithspeedsatthe

2 2/t2 1/t≤|Pn|<2n.Hence,therearetopofthethirdrange,thatis,with2n

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPHPROPERTIES5

propertieswithspeedsthroughouttherangeofthethirdcaseofTheorem1.Thisdoesnotnecessarilymeanthatanyspeedcanbeachieved,however.Weexamineconstraintsondemonstrablyachievablefunctionslaterinthispaper.

Asmentionedintheintroduction,ifthespeedofapropertyfallsintoanybutthethirdrange,|Pn|canbedescribedwitha“nice”function.However,weshallshowthatthisisnotthecaseforthethirdrange.Inthisrange,itispossibleforthespeedtooscillatebetweentwodi erentfunctionsin nitelyoften.

Moreprecisely,thequestionweexamineisasfollows.IsthereapropertyPsothatforfunctionsf(n)<g(n),|Pn|oscillatesin nitelyoftenbetweenthem?Clearlytherearechoicesoff(n)andg(n)forwhichitisnotpossibletocon-structsuchahereditaryproperty.Inparticular,Theorem1impliesthatifg(n)≤

2n(1 1/k+o(1))nforsomekorf(n)≥n(1 1/k+o(1))n/2forsomek,then|Pn|cannotoscillate.

However,weshallshowthatformanychoicesoff(n)andg(n)inasubrangeofthethirdrangeofTheorem1,wecanconstructsuchaproperty.Furthermore,thispropertyismonotone(andthereforealsohereditary).Ourmethodsareprobabilisticinnature,andweproceedinsteps, rstdemonstratingapropertywith xedupperandlowerboundsontheoscillationofitsspeed,andthenbyadjustingtheupperandlowerbounds.

WebeginwithatechnicalprobabilisticlemmaregardingsetsofgraphsandGn,p(i.e.arandomgraphoforderninwhichedgesareselectedindependentlyatrandomwithprobabilityp).

Lemma7.Let >0be xedandletp=p(n)≤1/2.Ifnissu cientlylargeandN √nasetofgraphsT Gsatis esP(Gn,p∈T)≥1/2+2 ,then|T|≥ pN, whereN=n

2andq=1 p.

Proof.Ifnissu cientlylarge,P(e(Gn,p)≤pN)≤1/2+ .HenceP(Gn,p∈Tande(Gn,p)>pN)≥1/2+2 (1/2+ )= .NotethatforanyH∈GntheprobabilityP(Gn,p=H)dependsonlyonthenumberofedgesinH.Hence,ifH0,H1∈Gnwithe(H0)<e(H1),thenP(Gn,p=H0)≥P(Gn,p=H1).Thus,ife(H)>pN,thenforanyH withe(H )=pN,wehave 1 N P(Gn,p=H)<P(Gn,p=H)<pqN.pN

Then

P(Gn,p∈Tande(Gn,p)>pN)≤|{H∈T,e(H)>pN}|

N √so|T|≥ pN. NpqNpN 1,

Wewillbeapplyingthislemmainaspeci cform,expressedinthefollowingcorollary. Corollary8.Supposep=p(n)<1/2,pn

2→∞.Ifnissu cientlylargeandnthesetT Gsatis esP(Gn,p∈T)≥2/3,then n

p(n2 2). |T|≥(1)≥(1/p)np2

Thiscorollarywillbeappliedtoshowthattheoscillatingpropertiesweconstructgrowasdesired.Thefollowingbasicconstructionwillbeusedasastartingpointineachofthetheoremsthataretocome.Letc>1andν=(ν1,ν2,...)bean

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

6´´´JOZSEFBALOGH,BELABOLLOBAS,ANDDAVIDWEINREICH

increasing(possibly nite)sequenceofnaturalnumbers.Wede neaselectivelyrestrictedpropertyPν,cas{G:ifH Gandv(H)=νiforsomei,thene(H)≤cνi}.NotethatPν,cismonotoneandthereforealsohereditary.

ThepropertyPν,chasaspeedwhichgrowsinapredictableway.

Lemma9.Letc>1, <1/c,ν=(νi)∞i=1beasequenceofnaturalnumbersandk=sup{νi∈ν}.Then

nn1.|Pν,c|≥n(c+o(1))nand|Pν,c|=n(c+o(1))nwhenevern=νi,

2 n2.ifk<∞andnissu cientlylarge,|Pν,c|≥2n.

Proof.Foranysequenceνandc>1,wehaveQc Pν,cand,foranyi,theνi-

νiνinνi Sc.Hencewehave|Pν,c|≥n(c+o(1))nforallnand|Pνi|≤|Sc|≤levelPν,c

iνiontheset{νi}ingTheorem5foralowerbound,wenobtain|Pν,c|=n(c+o(1))nwhenevern=νi.

Forthesecondpart,assumek<∞.ConsiderthepropertyP(k),c,where(k)is

nnthesequence(1,...,k).Wehave|P(k),c|≤|Pν,c|foralln.Hencewewouldhave(c+o(1))ν

nn.theresultif,forsu cientlylargen,|P(k),c|≥n

Chooseδsothat >δ>1/c.Letp=n δandconsiderGn,p.Weconsider

ntheprobabilitythatGn,p∈/P(k),c.ThisistheprobabilitythatGn,phasa“bad”

subgraph,thatis, nPGn,p∈/P(k),c=P(G∈Gn,p:thereisH Gwithv(H)≤kande(H)>cv(H))2

≤

≤

≤k j=1E(numberofj-subgraphsofGn,pwithmorethancjedges) j cj2k nj=1jpcj≤ j 2 cjk enej jj=1k

j=1Cjn 1 δcjn δcj ck eejj=1j2cn1 δc=,

whereCj(～jc 1)isaconstantdependingonjandc.Sinceδc>1,wehave1 δc<0,sothisprobabilitygoestozeroasngoestoin nity.Choosen0minimalsothattheprobabilitythatGn0,nδhasa“bad”subgraphislessthan1/3.Note0:Ghasthatthisprobabilityismonotonedecreasinginn.Thatis,ifP(G∈Gn0,nδ0abadsubgraph)<1/3,thenP(G∈Gn,nδ:Ghasabadsubgraph)<1/3foralln>n0.

NowwecanapplyCorollary8tothesetT=P(k),ctoobtaintheresult δn02 δ n0 δ n 0(2)>2n0/2. P(k),c ≥n0

nAlloftheinequalitiesaboveholdwheneverP(Gn,p∈T)≥2/3,sowehave|P(k),c|>

2n/2foralln>n0.Thuswecanchoosenlargeenoughtoensure2n

andobtainourresult.2 δ2 δ/2>2n2

4.Oscillatingproperties:Thesecondandthirdquestions

HavingdonethepreliminarycalculationsinSection3,wearenowreadytoprovethe rstofthreetheoremsregardingpropertiesthatoscillate.We rstconstructapropertywithalargerangeofoscillation.TheoscillationofthisspeedprovidesanegativeanswertothethirdquestionofScheinermanandZito;weshallanswerthesecondquestionwithTheorem11.

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPHPROPERTIES7

Lemma9givesapropertywiththeproperboundsonitsspeed,soallthatremainsistochooseasequencesothatthepropertygrowsasdesired.Weshallbeusingsequencesandtheirelementssigni cantlyintherestofthepaperandshallabusenotationslightly.ForasequenceN,weshallsayn∈Nifthevaluenappearssomewhereinthesequence.IfNisasubsequenceofsequenceM,weshallwriteN M.Inotherwords,weshallusesetnotationwithsequencestomeanthattherelationsholdforthesetofelementsinthesequence.

Theorem10.Letc>1and >1/c.Thereexistsequencesν=(νi)∞i=1and∞µ=(µi)i=1,whereµi=νi 1foralli,suchthat

n1.|Pν,c|=n(c+o(1))nwhenevern=νi,

2 n2.|Pν,c|≥2nwhenevern=µi,

2 n3.n(c+o(1))n≤|Pν,c|<2nifn=µi.

Proof.Wechooseν1,ν2,...,onebyone,startingwithν1=3.Havingchosen2 nν1,...,νk,wesetν=(ν1,...,νk)andnotethatbyLemma9,|Pν,c|≥2nfor

2 µk+1su cientlylargen.Chooseµk+1>νkminimalsuchthat|Pν,c|≥µk+1µk+1.

Setνk+1=µk+1+1.

Continuinginthisway,weobtainanin nitesequenceandtherequiredproperty.TheresultsinTheorems3and10suggestthatncn 2nisanaturalrangeofoscillationthatmayoccurinthepenultimaterange.However,therearemanyothertypesofoscillationpossible.We rstshowthattheupperboundoftheoscillationcanbeanyfunctionintherangethatwechoose,and,further,thattheoscillationcanbeconstrainedtoremainveryclosetotheupperbound.Choosingf(n)=n(d+o(1))nforsomed>cthengivesanegativeanswertothesecondquestionofScheinermanandZito.

WithTheorem12,weshallshowasimilar,thoughslightlyweaker,resultforthelowerbound.2 Givenafunctionf(n)≤2n,Theorem10givesasequenceνwhichguarantees

nthat|Pν,c|oscillatesbetweenn(c+o(1))nandsomevalueabovef(n)in nitelyoften.Clearly,wecanchooseνsothatthespeedonlygoesabovef(n)whenn=νi 1forsomei.However,wecandobetterthanthisbycarefullytruncatingourpropertiesatlevelµi=νi 1andshowingthatthiswillnota ectanyaspectoftheconstructionweperformsubsequently.Thisispreciselythemethodofthefollowingtheorem. Notethatweconstrainf(n)>ncn>n(c+o(1))nsothatoscillationwillactuallyoccur.

Theorem11.Letc>1,c >c,and >1/c.Letf(n)beafunctionsuchthat 2 ∞ncn<f(n)≤2nforalln.Thereexistsequencesν=(νi)∞n=1andµ=(µi)n=1andamonotonepropertyPsuchthat

1.|Pn|=n(c+o(1))nwhenevern=νi,

2.|Pn|>f(n) n!whenevern=µi,

3.|Pn|≤f(n)foralln,

4.|Pn|≥n(c+o(1))n.

Proof.ChoosesequencesνandµasinTheorem10,selectingvaluesofµiaccording2 nnto|Pν,c|≥f(n)ratherthan|Pν,c|≥2n.

µinThenthepropertyPν,chasspeed|Pν,c|≥f(µi)and|Pν,c|<f(n)forallsu -

cientlylargen=µi,sincen(c+o(1))n<f(n).

WewillusethefactthatifPismonotoneandGisann-graphinPsuchthatG HforanyothergraphonnormoreverticesinP,thenP\{H:H～=G}is2 1/c

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

8´´´JOZSEFBALOGH,BELABOLLOBAS,ANDDAVIDWEINREICH

stillamonotoneproperty.Thatis,removinggraphsfromPkhasnoe ectonPnanddoesnotdependonthegraphsinPnforanyn<k.Furthermore,removingagraphandallgraphsisomorphictoitfromapropertyreduces|Pn|byatmostn!.Ifwechoosegraphstoremovecarefully,thispropertywillremainmonotone.(N.B.:thesameistrueforhereditaryproperties.)

WeshallcallagraphG∈PeligibleinPife(G)>cv(G)andtherearenographsH∈PwithG H.ForthepropertyPν,c,ifνi 1≤v(G)<νi 1(=µi),Giseligibleifandonlyiftherearenoµi-graphsHwithG H.Ifv(G)=µi,thenweneedthefurtherconditionthatnoνi-graphscontainGasasubgraph.

Toconstructapropertysatisfyingthetheorem,weremoveµi-graphsfromPν,ctoobtainP.WeonlyneedtoshowthatthereisasetF,closedunderisomorphism,

µiµiconsistingofeligibleµi-graphsinPν,csuchthatf(n) n!<|Pν,c F|≤f(n).Bythecommentinthepreviousparagraph,changingapropertyattheµi-levela ects

otherlevelsifandonlyifita ectstheνi-level.

µiνiaresubgraphsofgraphsinPν,c?ForanymonotoneHowmanygraphsinPν,ckpropertyP,ifD={G:v(G)=k 1andthereisanH∈PksuchthatG H},

thenDk={G:G～=H v,H∈Pk,v∈V(H)}.SincePismonotonethefactthatPkisclosedundertakingsubgraphsensuresthatwegetallpossiblesubgraphs.(c+o(1))νiµiHence|Dk|≤k·|Pk|.Thus,thereareatmostνi·νigraphsinPν,cthat

iνiaresubgraphsofthoseinPν,c.Hence|Dνi|≤µiforsu cientlylargei.

Givenacollectionofgraphs{Gj}j∈A,letF({Gj}j∈A)bethesetofallgraphs

iνi 1isomorphictoGjforsomej∈AandletPk=Pν,c\F({Gj}j∈A).Wewishto

iibuildacollectionofeligiblegraphssothatPkwillbemonotoneandf(µi)≥|Pk|>f(µi) µi!.

(c+o(1))µiµiµiAs|Dνi|≤µi<f(µi)≤|Pν,c|,thereareeligiblegraphsinPν,c.LetG1

µiibeaneligiblegraphinPν,c.ThepropertyP1ismonotonesinceG1eligibleimplies

µiiiG1 HforanyH∈Pν,c G1.Further|Pν,c| |P1|≤µi!,so|P1|>f(µi) µi!.

Weproceedbypickingeligiblegraphsinorder,stoppingatthe rstpointwhen

ii|Pk|≤f(µi).Clearly,ifwehavepicked{Gi}ki=1and|Pk|>f(µi),thecounting

iargumentaboveguaranteesthatPkstillhasaneligiblegraphGk+1,sothisprocess

iicancontinue,and|Pk| |Pk+1|≤µi!.Thus,ifwhenconsideringµiwestopwitha

isetofligraphs,|Pli|≥f(µi).

nLetPn=Pν,cforalln∈/µandPµi=Pli

iforalli.Asnotedabove,Pisa

imonotoneproperty.Clearly|Pνi|=νiandf(µi)≥|Pµi|>f(µi) µi!.

/µ.Also,byourchoiceofνi,|Pn|<f(n)foralln∈(c+o(1))µ(c+o(1))ν

5.Oscillationfrombelow

CanweproduceoscillationsimilartothatinSection4,butwhichhasafunctionotherthanncnasitslowerbound?Thatis,givenafunctionf(n),isthereaproperty

2 withspeedthatoscillatesfromjustbelowf(n)tojustabove2nin nitelyoften?

Amodi cationofthepropertyinTheorem10againprovidesacandidatefortheoscillation.However,wemustrelaxtheconditionthattheoscillationstayclosetotheupperboundinordertomaketheproofworkeasily.Inparticular,thereisa2 rangeoflevelsforwhichwecannotsaywhether|Pn|<2n.

Theorem12.Letc>1and >1/c.Letf(n)beafunctionsuchthatn(c+o(1))n≤2 f(n)<2nforalln.ThereexistsapairofsequencesR=(ρi)∞i=1andM=(µi)∞i=1andamonotonepropertyPsuchthat

1.f(ρi) ρi!<|Pρi|≤f(ρi)foralli,

2 2.|Pµi|>2µiforalli,

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPHPROPERTIES9

3.|Pn|≥f(n)foralln∈/R, 2 4.|Pn|<2nforn∈i[ρi,µi+1 1].

Proof.TheprooffollowsalongthesamelinesastheproofsofTheorems10and11,onlythistimeweconstructtwosequences,Randν.We rstbuildasequenceν=(νi)∞i=1asinTheorem10.Againletµi=νi 1foralli,andconsiderPν,c.Thissatis esconditions2and4ofthetheorem(foranysequenceRwhichdoesnotintersectM=(µi)).HenceweneedtomodifyPν,ctoobtainconditions1and3.However,indoingso,weneedtobesurewedonotcreateapropertycontradictingconditions2or4.

WechoosethesequenceRasfollows.Foralli,letρibethemaximalnsuch

2 νi+1(c+o(1))νinνithatνi≤n<νi+1andPν,c≤f(n).Since|Pν,c|=νi,|Pν,c|>2n,and

2 n(c+o(1))n≤f(n)<2n,therealwayswillbesuchann.

ρisothatitsspeedisclosetof(n).WeknowthatthisWeshalladdgraphstoPν,cwillnota ectthen-levelsofourpropertyforn>ρi.Ifwecanpickthesegraphs

µisothateveryµi-subgraphisinPν,c,wewillnota ectanyn-levelforn≤σieither.

ρiwillenlargethen-levelsforµi<n<ρi.However,addingsuchagraphtoPν,cρiρiIf|Pν,c|>f(ρi) ρi!,weneednotmodify|Pν,c|.Otherwise,considerthesequenceρi ρiρiN=(ν1,...,νi).ThenPν,c PN ,c.Inparticular,Pν,c PN ,c.Since|Pν,c|<

f(ρi)<2n2 ρiρiρi<|PN ,c|,thereisagraphG∈(PN ,c Pν,c)suchthateveryH G

v(H)withv(H)≤µiisinPν,c.Wecallsuchagraphinsertable.LetG1beaninsertable

graphwithaminimalnumberofedges.Theneveryproperρi-subgraphofGisinρiρiρi,so|Pν,c∪F({G1})|≤|Pν,c|+(ρi)!.Also,ifP1isaminimalpropertycontainingPν,cρinnPν,c∪F({G1}),then|P1|=|Pν,c|forn>ρiandn<νi.Forνi≤n≤ρi,the ρi nnspeed|P1|≤|Pν,c|+(ρi)!n.Wecontinuechoosingρi-graphsinthiswayuntil

iwehaveacollection{G1,...,Gli}sothatf(ρi) ρi!<|Plρ|≤f(ρi).Astheonlyiconditionweneededtoguaranteeaninsertablegraphwasthatthepropertyhad

speedbelowf(n),itisclearthatwecanalways ndaninsertablegraphifthepropertyhasspeedbelowf(n).IfweconsidereachiinturnandconstructthepropertyP =P{lj}intheobviousway,weobtainamonotonepropertysatisfyingconditions1and2.

However,conditions3and4donotnecessarilyholdforP ontheintervals{[νi,ρi)}.Considereachvalueofiinturnandexaminetheinterval[νi,ρi)fromtheright.If,fort=ρi 1,thespeed|(P )t|<f(t),wecanproceedaswedidρifor(Pν,c):adda nitecollectiongraphsto(P )ttoobtainanewpropertywith

2 speedabovef(t).If|(P )t|>2t,wecaninsteadremovegraphs,aswedidin

2 Theorem11,untilthepropertyhasfewerthan2tt-graphs.Ineithercase,we

onlya ectthen-levelsforn∈[νi,t].Socontinuingforeachsmallervalueintheinterval,weobtainapropertyPsatisfyingalloftheconditionsofthetheorem.

Ideally,givenanytwofunctionsintheproperrangewithpositivedi erence(=o(1)),wewouldliketoconstructapropertywithspeedthatoscillatesin nitelyoftenbetweenthetwofunctions.However,thisisclearlynotpossible,asforanymonotoneorhereditaryproperty,|Pn+1|/|Pn|≤2n.Thus,forexample,choosingfunctionsthatincreasetogetherbymorethanafactorof2nwouldmakeitimpossi-bletokeepthespeedbetweenthebounds.Witharestrictionto“smooth”functionsavoidingthisproblem,itseemsthatoscillationispossible.However,aswehaveseenintheproofofTheorem12,evenwitha“smooth”functiontheproofwouldbecumbersome.Infact,evenaproperde nitionof“smooth”wouldbeunappealing.

However,anoutlineoftheapproachwewouldtaketoprovethedesiredstatementisasfollows.Giventwosuchfunctionsf(n)<g(n),wewishtoobtainaproperty

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

10´´´JOZSEFBALOGH,BELABOLLOBAS,ANDDAVIDWEINREICH

whichachievesspeedsclosef(n)forin nitelymanynandclosetog(n)forin nitelymanyn.Ratherthan ndingthesequenceνfromTheorem10,wewouldusethesequencefromTheorem11.Inthe nalstep,whenweaddorremovegraphsaccordingtowhetherthepropertyhastoohighorlowaspeed,weneedtotakecarethatinremovinggraphswedonotalterlaterproperties.Thismayrequireadjustingoursequencesothatthelevelforwhichthespeedisaboveg(n)isinthe intervalbetweenµiandρiratherthanatµi.Theconditionn(c c)nf(n)<g(n)wouldensuretheconditionsofTheorem11andthepositivedi erencebetweenthefunctions.

This,however,doesnotsolvetheproblemwehavediscussedregardingcondition4ofTheorem12.Webelievethatitisnotworththee orttodescribeinmoredetailwhatneedstobedone.Nevertheless,webelievethefollowingstatementtobetrue,andwouldbehappytoseeanelegantproof.

Letc>1,c >c,and >1/c.Letf(n),g(n)be“smooth”functionssuchthat

n(c+o(1))n≤f(n)<n(c c)nf(n)≤g(n)≤2n 2

∞foralln.ThereexistsapairofsequencesR=(ρi)∞i=1andS=(σi)i=1anda

monotonepropertyPsuchthat

1.|Pn|≥f(n)and|Pn|≤g(n)foralln∈/R∪S,ρi2.f(ρi)>|P|>f(ρi) ρi!forallρi∈R,3.g(σi)<|Pσi|<g(σi)+σi!forallσi∈S.

6.Amorenaturaloscillatingproperty

Theaimofthissectionisto“sharpen”ourresultsfromadi erentpointofview.ThepropertiesgiveninTheorems10and11areusefulforourpurposes.Inparticulartheyneatlyanswerthequestionsof[13]mentionedintheintroduction.However,thepropertieswedescribeareextremelyarti cial,theiroscillationcom-ing,toalargedegree,from“unnecessary”graphs.Inparticular,therearemany(isomorphismclassesof)graphsinPν,cthatmayberemovedwithouta ectingthehereditarynatureoftheproperty.Infact,wehaveusedthisfactratherheavilyintheproofsofTheorems11and12.However,whiletheremovalofthegraphswouldnota ectthehereditarynatureofthepropertiesinquestion,itwoulda ecttheirspeed.Itwouldbenice,therefore,toknowifthereisapropertyforwhicheachisomorphismclassisnecessaryandforwhichthespeedstilloscillates.

GivenapropertyP,wede nethelimitofPasP ={G:foralln>v(G)thereisann-graphH∈PwithG≤H}.TheneverygraphinPisnecessaryifandonlyifP=P .Inthiscase,wesaythatPisalimitproperty.Notethatthelimitofapropertyisalimitproperty,thatis(P ) =P .

nIn[7],Bollob´asandThomasonshowthatif|Pn|=2(c+o(1))(2)and|P n|=n 2(c+o(1))(2),thenc=c .Henceforpropertiesinthehighestrangeofspeeds,where

c>0,apropertyanditslimithavethesamespeed.However,thisisclearlynottrue nforallproperties,asPν,c=Qcforallin niteincreasingsequencesν,while|Pν,c|nmayoscillatebut|Qc|doesnot.Hencewewouldliketodemonstrateapropertythathasalimitwhosespeedoscillates.ThefollowingtheoremprovidesalimitpropertywiththesametypeofoscillationasthatinTheorem10.

Theorem13.Letc>1, >1/c.ThereisamonotonelimitpropertyPandtwo∞sequencesR=(ρi)∞i=1andS=(σi)i=1withσi<ρi<σi+1suchthat

1.|Pn|=n(c+o(1))nwhenevern=ρiforsomei,

2 2.|Pn|=2(1+o(1))nwhenevern=σiforsomei,

2 3.n(c+o(1))n≤|Pn|≤2(1+o(1))nforalln.

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPHPROPERTIES11

Proof.FortwosequencesR,SandapropertyP,considerthepropertiesAR,SandBR,Sde nedbylevelsasfollows.AnR,S={G:v(G)=nandforalliandforall

nσi<l≤ρi,everyl-subgraphH Ghase(H)≤cl},andBR,S={G:v(G)=n

andG=H∪lwhereH∈Pσiandl=n σiforσi=max{s:n>s∈S}}.NotethatAR,SisapropertyofthetypePν,cforsomeν R.WewillconstructapropertyP AR,S∪BR,Swhichismonotone,limit,andhastheproperspeeds.

Asintheproofoftheprevioustheorems,weproceedbyconstructingsequencesRandSsothatPisasdescribed.Weshallcalculatevaluesofρi,σibasedonthoseofρi 1,σi 1,anddescribePincrementallybylevels.

2 Letρ0=2andletσ1>ρ0bethesmallestvaluesuchthat|Tσi|>2σ1,where

Tisthetrivialproperty.AsintheproofofTheorem11,wecanremovegraphsfrom2 Tσisothat|Tσi|≤2σ1+n!.LetPσibethecollectionofgraphswhichremain,andforn<σ1,letPn={G:v(G)=nandthereisH∈PσiwithG H}.

AssumewehavechosensequencesRi 1,SiwhereRi=(ρ1,...,ρi 1),Si=(σ1,...,σi)andwehavede nedthen-levelofPforn≤σi.Wewishto ndρi(c+o(1))ρiρiisothat|Aρ.ByLemma6,weknowthatforanyRi 1,Si∪BRi 1,Si|=ρi

iichoiceofρi,thespeed|Aρ.Soifwechooseρi(minimal)sothatRi 1,Si|=ρiρicρi|BRi 1,Si|<ρithedesiredrelationwillhold.Thereissuchanρi,sinceforall n σi2nσiσin>σi,|BR|P|≤|≤n2,wherethelastestimatecomesfromRi 1,Siσii 1,Siallgraphsbeingintheσi-levelofP.Henceρi=2σiwouldbemorethansu cient.

nForσi<n≤ρi,letPn=AnRi,Si∪BRi,Si.

i+1σi+1Givenρi,letσi+1>ρibethesmallestnumbersuchthat|ARi

i+1.,Si∪BRi,Si|>2TheexistenceofsuchanumberisguaranteedbyLemma9.Asintheproofof

Theorem11,wecanremoveeligiblegraphs,oneisomorphismclassatatime,from2 σσi+1σi+1ARi

i+1with|Pσi+1|<2σi+1+σi+1!.Aswewantto,Si∪BRi,SitoobtainPcreatealimitproperty,wewillthenremovegraphsfromPnforn<σi+1,keepingonlythosegraphswhichappearassubgraphsofthoseinPσi+1.However,wewanttobesurethatPremainsattheproperspeed.Inparticular,wewillremovenoσσi+1ngraphsfromBRi

i+1(notingthatQnc AR,Sforalln,SiandnographsinQc

andanysequencesR,S).Clearlythereareenougheligiblegraphsavoidingthese

σσi+1(c+o(1))σi+1collections,as|BRi

i+1|<σi+1.Notethatwiththisrestriction,we,Si|+|Qc

willnotremoveanygraphsfromPnforn≤ρi.

Inthiswayweconstructin nitesequencesRandS.ItisclearthatPisamonotoneproperty,andtheconstructionguaranteesthatPislimitproperty,sinceweremoveallgraphsthatarenotcontainedinarbitrarilylargegraphs.Thespeedsgiveninconditions1and2arecorrectontheelementsofRandS,respectively,bytheconstruction.Furthermore,Qc P,sothelowerboundgivenincondition3iscorrect.

Fortheupperbound,wesplittheinterval(σi,σi+1)intotwoparts.Ourchoiceof

2 thesequenceSguaranteesthatforρi<n<σi+1,|Pn|<2n. Forσi,we i<n≤ρ 2 σi σin + Bn .Hence|Pn|<n(c+o(1))n+n <nnote|Pn|≤ An2<P R,SR,SR.SR,Sσi(c+o(1))ρσσ2

2(1+o(1))n2 .

Thuswehavepresenteda“sensible”propertyforwhichthespeedoscillatesover2 nearlythewholeintervalfromn(1+o(1))nto2n.Thisproperty,asistrueofallofthepropertiespresentedinthepaper,hasanin niteclassofforbiddensubgraphscorrespondingtothein nitesequencesconstructed.Thatis,ifPisoneofouroscillatingpropertiesandFisaminimalclassofgraphssuchthatP=Mon(F),thenFisin nite.Isthisanecessaryconditionforoscillationtooccur?Webelieve

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

12´´´JOZSEFBALOGH,BELABOLLOBAS,ANDDAVIDWEINREICH

thatitis:ifamonotonepropertyhasa niteclassofforbiddensubgraphs,thenallofthelimitspresentedintheintroductionshouldexist.Sofar,however,aproofofsucharesultiselusive.

7.Tightboundsonthepenultimaterange

TheresultsofSections4–6demonstratethatthepenultimaterangedi erssigni cantlyfromtheotherrangesofspeed.Infact,itisunclearthatpropertiesinthisrangeneedtosatisfyanywell-de nedbehaviorbesidesthebroadboundsgiveninSection2.Nevertheless,basedonresultsinvolvingadi erentmeasureofpropertiesin[2],webelievethattherangeofoscillationdemonstratedinthepropertiespresentedhereisthemaximumpossible.Theconverseoftheconjectureistrueformonotoneproperties,asshownbyTheorem3andin[2].However,the rstpartoftheconjectureisopenevenformonotoneproperties.

Conjecture14.Forallc>1,thereexistsan >0suchthatifPisahereditary2 propertyand|Pn|≥2nholdsin nitelyoften,then|Pn|≥n(c+o(1))n.Conversely,foralld>1thereexistsaδ>0suchthatif|Pn|≤n(d+o(1))nin nitelyoften,then

2 δ+o(1)|Pn|≤2n.

ItisclearfromLemma9that,ifConjecture14istrue,δ≤1/d.PerhapsConjecture14evenholdswith =1/candδ=1/d.However,therearenoresultsofthistypeknown.Thusthepenultimateregionofspeedsremainsafertileareaforfurtherresearch.

References

[1]J.Balogh,B.Bollob´as,andD.Weinreich,Thesizeofhereditarypropertiesofgraphs,J.

Combin.TheorySer.’B’792(2000),131–156.1,2

[2]J.Balogh,B.Bollob´as,andD.Weinreich,Thesizeandspeedofmonotonepropertiesof

graphs,submittedtoDisc.Appl.Math.1,2,12

[3]J.Balogh,B.Bollob´as,andD.Weinreich,Thestructureofposetsandanapplicationto

hereditaryproperties,preprint.2,3

[4]B.Bollob´as,ExtremalGraphTheory,AcademicPress,London(1978).4

[5]B.Bollob´asandA.Thomason,Projectionsofbodiesandhereditarypropertiesofhypergraphs,

J.LondonMath.Soc.27(1995),417–424.1,2

[6]B.Bollob´asandA.Thomason,Hereditaryandmonotonepropertiesofgraphs,in“TheMath-

ematicsofPaulErd osII”(R.L.GrahamandJ.Neˇsetˇril,eds.)AlgorithmsandCombinatorics,Vol.14,Springer-Verlag(1997),70–78.1,2

[7]B.Bollob´asandA.Thomason,Thestructureofhereditarypropertiesandcolouringsof

randomgraphs,Combinatorica,toappear.10

[8]T.K ov´ari,V.T.S´os,andP.Tur´an,OnaproblemofK.Zarankiewicz.Colloq.Math.3(1954),

50-57.3

[9]H.J.Pr¨omelandA.Steger,Excludinginducedsubgraphs:quadrilaterals,RandomStructures

andAlgorithms2(1991),55–71.

[10]H.J.Pr¨omelandA.Steger,ExcludinginducedsubgraphsII:extremalgraphs,DiscreteAp-

pliedMathematics44(1993),283–294.

[11]H.J.Pr¨omelandA.Steger,ExcludinginducedsubgraphsIII:ageneralasymptotic,Random

StructuresandAlgorithms3(1992),19–31.

[12]H.J.Pr¨omelandA.Steger,TheasymptoticstructureofH-freegraphs,inGraphStructure

Theory(N.RobertsonandP.Seymour,eds),ContemporaryMathematics147,Amer.Math.Soc.,Providence,1993,pp.167-178.

[13]E.R.ScheinermanandJ.Zito,Onthesizeofhereditaryclassesofgraphs,binat.

Theory(B)61(1994),16–39.1,4,10

Abstract. Given a property P ofgraphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed ofa monotone or hereditary property P can be a constant, polynomial, or ex

THEPENULTIMATERATEOFGROWTHFORGRAPHPROPERTIES13DepartmentofMathematicalSciences,TheUniversityofMemphis,Memphis,TN38152

E-mailaddress:balogj@msci.memphis.edu

DepartmentofMathematicalSciences,TheUniversityofMemphis,Memphis,TN38152,and,TrinityCollege,CambridgeCB21TQ,England

E-mailaddress:bollobas@msci.memphis.edu

DepartmentofMathematics,UniversityofWisconsin–LaCrosse,LaCrosse,Wis-consin54601

E-mailaddress:weinreic@math.uwlax.edu

本文来源：https://www.bwwdw.com/article/cvh4.html