Component Games on Regular Graphs RaniHod AlonNaor† ∗ Abstract Westudythe(1:b)Maker–Breakercomponentgame,playedontheedgesetofad-regulargraph. MAKER’saim inthisgameistobuildalargeconnectedcomponent,whileBREAKER’saimistonotlethimdoso. Forallvaluesof 3 BREAKER’sbiasb,wedeterminewhetherBREAKERwins(onanyd-regulargraph)orMAKERwins(onalmostevery 1 d-regulargraph)andprovideexplicitwinningstrategiesforbothplayers. 0 Tothisend,weproveanextensionofatheorembyGallai–Hasse–Roy–Vitaveraboutgraphorientationswithout 2 longdirectedsimplepaths. n a J 1 Introduction 2 LetX beafiniteset,letF 2X beafamilyofsubsetsofX,andletm,bbetwopositiveintegers.Inthe(m:b)Maker– O] Breakergame(X,F),twop⊆layers,calledMAKERandBREAKER,taketurnsinclaimingpreviouslyunclaimedelements ofX. OnMAKER’smove,heclaimsmelementsofX,andonBREAKER’smove,heclaimsbelements.1 Thegameends C whenalloftheelementshavebeenclaimedbyeitheroftheplayers.Thedescriptionofthegameiscompletebystating . h whichoftheplayersisthefirsttomove,thoughusuallyitmakeslittledifference. MAKERwinsthegame(X,F)ifby at theendofthegamehehasclaimedalltheelementsofsomeF F;otherwiseBREAKERwins.2 Sincethesearefinite, ∈ m perfectinformationgameswithnopossibility ofdraw,foreachsetupofF,m,b andtheidentityofthefirstplayer, oneoftheplayershasastrategytowinregardlessoftheotherplayer’sstrategy. Therefore,foragivengamewemay [ saythatthegameisMAKER’swin,oralternativelythatitisBREAKER’swin.ThesetX isreferredtoastheboardofthe 1 game,andtheelementsofF arereferredtoasthewinningsets. v When m b 1, we say that the game is unbiased; otherwise it is biased, and the positive integers m and b 2 = = 8 are called the bias of MAKER and BREAKER, respectively. Maker–Breaker games are bias monotone. It means that 2 if MAKER wins some game with bias (m :b), he also wins this game with bias (m′ :b′), for every m′ m, b′ b. ≥ ≤ 0 Similarly, if BREAKER wins a game with bias (m :b), he also wins this game with bias (m′ :b′), for every m′ m, . ≤ 1 b′ b. Indeed,supposethatsomeplayerhasawinningstrategywithbiasc,andnowheplayswithbiasc′ c. He ≥ > 0 canusehisoldstrategyandinadditionclaimarbitrarilyc cextraelementspermoveandpretendhedidnotclaim ′ 3 them; whenever his strategy tells him to claim some elem−ent he has previously claimed he just claims arbitrarily 1 some unclaimed element. Similarly, if his opponent claims less elements, he can assign (in his mind) some extra : v elementstohisopponentineachmove,andcontinuewithhisstrategy. Thesamereasoningshowsthatitisnevera Xi disadvantageinaMaker–Breakergametobethefirstplayer,andawinningstrategyasasecondplayercanbeusedas awinningstrategyasafirstplayer.Thisbiasmonotonicityallowsustodefinethethresholdbias:foragivengameF, r a thethresholdbiasb∗isthevalueforwhichMAKERwinsthegameF withbias(1:b)foreveryb b∗,andBREAKER ≤ winsthegameF withbias(1:b)foreveryb b . ∗ > Inthispaper,ourattentionisdedicatedtothe(1:b)Maker–Breakers-componentgameonregulargraphs;thatis, theboardistheedgesetofsomed-regulargraphGonnverticesandthewinningsetsareconnectedcomponentsof Gwithsvertices. 1.1 Previousresults Anaturalcasetoconsideriss n;thatis,thewinningsetsarethespanningtreesofG.This(1:b)n-componentgame = isalsoknownastheconnectivitygame. TheunbiasedgamewascompletelysolvedbyLehman[13],whoshowedthatMAKERwinsthe(1:1)connectivity gameonagraphGifandonlyifGcontainstwoedgedisjointspanningtrees.Itfollowseasilyfrom[16,19]thatifGis ∗School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. E-mail: [email protected]. †SchoolofMathematicalSciences,RaymondandBeverlySacklerFacultyofExactSciences,TelAvivUniversity,TelAviv,Israel. E-mail: alon- [email protected]. 1Theplayerwhomakestheverylastmovemaynotbeabletocompletem(orb)steps,sohestopsafterclaimingallremainingelements. 2Forconvenience,wetypicallyassumethatFisclosedupwards,andspecifyonlytheinclusion-minimalelementsofF. 1 2k-edge-connectedthenitcontainskpairwiseindependentspanningtrees;thus,MAKERwinsthe(1:1)connectivity gameon4-regular4-edge-connectedgraphs,whereasBREAKERtriviallywinsthe(1:1)connectivitygameongraphs withlessthan2n 2edges,i.e.,averagedegreeunder4 O(1/n). − − Fordensergraphs,sinceMAKERwinstheunbiasedgamebysuchalargemargin,itonlyseemsfairtoevenoutthe oddsbystrengtheningBREAKER,givinghimabiasb 2.Firstandmostnaturalboardtoconsideristheedgesetofthe ≥ completegraphKn(i.e.,d=n−1).ChvátalandErdo˝s[4]showedthat 14−o(1) n/logn≤b∗(Kn)≤(1+o(1))n/logn; theupperboundwasprovedtobetightbyGebauerandSzabó[7];th¡atis,b∗¢(Kn)=(1+o(1))n/logn. Thedoubly- biased connectivity game(m:b)onKn wasconsideredbyHefetzetal.[10], wherethewinner wasdetermined for almostallvaluesofmandb. Anothernaturalboardtoconsideristheedgesetofarandomgraph. Stojakovic´ andSzabó[18]consideredthe well knownErdo˝s–Rényi random graph G , in which each of the n possible edges appears independently with n,p 2 probabilityp. Theyshowedthatalmostsurelyb∗ Gn,p =Θ np/logn¡ ¢,whereBREAKER’swinholdsforany0≤p≤1 whileMAKER’swinrequiresp≥(1+o(1))logn/nf¡orGn¢,p tob¡eforemos¢tconnected.Adifferentrandomgraphmodel, therandomd-regulargraphG onn vertices,wasconsideredbyHefetzetal.[9]. Theyshowedthatalmostsurely n,d b∗ Gn,d ≥(1−ǫ)d/log2n for d =o pn .3 Moreover, they showed that b∗(G)≤max 2,d¯/logn for a graphG of averagedegreed¯,sotheresultisasymptoticallytight. ¡ ¢ ¡ ¢ © ª BREAKER’sstrategyinpracticallyallresultsmentionedaboveistodenyconnectivitybyisolatingasinglevertex. Muchlessisknown,however,forthecases n. ItseemsthatevenifBREAKERisabletoisolateavertexinaconstant < numberofmoves,itdoeslittletopreventMAKERfromwinningthes-componentgamefors Ω(n). = 1.2 Ourresults Insteadofconsideringthethresholdbiasb∗,weshiftthefocustothemaximalcomponentsizesachievablebyMAKER inthe(1:b)game,foragivenbiasb.Letusdenotethisquantitybysb∗(G),andlet,ford≥3, sb∗(n,d)=max sb∗(G):Gisad-regulargraphonnvertices . © ª For b 2d 2, BREAKER can immediately isolate each edge claimed by MAKER in the (1:b) game, so trivially ≥ − sb∗(G)=2.Furthermore,BREAKERcandosomethingsimilarwhileb>d−2,asthefollowingpropositionshows: Proposition1. Foranypositivek,sd∗ 2 k(n,d)≤2⌈d/k⌉. − + Inthe(1:d 2)game,BREAKERcanstillrestrictthesizeofMAKER’sconnectedcomponents. − Theorem2. sd∗ 2(n,d)≤αd+βdlogn,whereαd andβd dependonlyond. − Remark. Ourproofyieldsα O d2 andβ O d/loglogd . d d = = TheproofofTheorem2relies¡ont¢hefollowing¡combinator¢iallemma,whichmaybeofindependentinterest. Lemma3. LetGbeagraphonnverticeswithminimaldegreeδ 3.Then,thereexistsanorientationDofGsuchthat ≥ everyvertexhasapositiveout-degreeandallsimpledirectedpathsinD areoflengthatmostχ(G) κ logn, where δ + κ O 1/loglogδ . δ = Remark¡. Notetha¢t sb∗(Tb+1(k))≥k, whereTr(k) isthe complete r-arytree4 withk levels, since MAKER caneasily buildapathfromtheroottosomeleaf. CompletingT (k)toad-regulargraphonn (d 1)k verticesthusshows d 1 − = − thatsd∗−2(n,d)≥logd−1n. TocomplementTheorem2,weprovethatinthe(1:d 3)gameonalmosteverygraph,MAKERcanalreadybuild − averylargeconnectedcomponent. Theorem4. LetG betherandomd-regulargraphonnvertices,whered 3.Then,s G ǫ nalmostsurely, n,d ≥ d∗ 3 n,d ≥ d whereǫd>0dependsonlyond.Inparticular,sd∗ 3(n,d)≥ǫdn. − ¡ ¢ − Remark. Aquickcalculationshowsthatǫ poly(1/d). d ≥ Whend isatmostpolylogarithmicinn,Theorems2and4showaphasetransitionphenomenonthatoccursat b d 2;insteadoftiny,polylogarithmic-sizedcomponents,MAKERissuddenlyabletobuildagiant,almostlinear- = − sizedcomponent.Whend isconstant,weevenhaveadouble-jump—fromconstant,throughlogarithmic,tolinear- sizedcomponents.ThisissummarizedinFigure1. 34BTyhactoins,ceevnetrraytnioonno-lfetahfevebritneoxmhiaaslrdicshtrilidbruetnio.n,whend=Ω pn ,Gn,disquiteclosetoGn,pforp=d/n. ¡ ¢ 2 Θ(1), b d 2; > − Θ polylogn , b d 2; sb∗(n,d)=ΘΘ¡(nlo)g,n¢, bb=dd−22;. sb∗(n,d)=(Θ¡n/polylog¢n , b≥<d−−2. < − ¡ ¢ (a)d=Θ(1) (b)d=O polylogn ¡ ¢ Figure1:Phasetransitionphenomenonatb d 2 = − Thisbehaviorissomewhatconsistentwiththeso-calledrandomgraphintuitioninpositionalgames:oftentimes, theoutcomeofagamebetweentwointelligentplayersisthesameastheoutcomeofthatgamebetweentwoplayers acting randomly. Consider the bond percolation with parameter p (i.e., each edge is deleted independently with probability1 p).Itisknown(see,e.g.,[2,15])thatforwell-expandingd-regulargraphs,whered isconstant,thesize − ofthelargestconnectedcomponenthasadouble-jumpatp=d11 —itislinearforp≥ d1+ǫ1,logarithmicforp≤ d1−ǫ1, andΘ n2/3 forp 1 . − − − =d 1 Alt¡houg¢hthesizes−ofthecomponentsaredifferent,boththebondpercolationandsb∗(n,d)haveasharpthreshold atthesamepoint,sinceinarandomplayofa(1:b)game,MAKERgetseachedgewithprobability 1 1 .5 1 b =d 1 + − 1.3 Notation WeusestandardGraphTheoryterminology,andinparticularusethefollowing: ForagivengraphG wedenotebyV(G)andE(G)thesetofitsverticesandthesetofitsedges,respectively. We oftenjustuseV andE,whenthereisnochanceofconfusion. Fortwodisjointsetsofvertices A,B V wedenoteby ⊆ E(A,B)thesetofalledges(a,b) E witha Aandb B.ForaconnectedcomponentSinMAKER’sgraph,andforan ∈ ∈ ∈ edgee E wesaythateisincidenttoSifatleastoneofitsendpointsbelongstoS;ifbothendpointsofebelongtoS, ∈ wesaythateisinsideS. WhenGisadirectedgraph,wesaythatavertexv isreachablefromavertexuifthereisadirectedpathinGfrom utov. Anunclaimededgeiscalledfree. Theactofclaimingonefreeedgebyoneoftheplayersiscalledastep. MAKER’s m (BREAKER’s b) successive steps arecalled a move. A round in the game consists of onemove of the firstplayer, followedbyonemoveofthesecondplayer. WheneverMAKERclaimsafreeedge,itbecomespartofsomeconnected componentofhis;wethensayhetouchedthatcomponent. IfaconnectedcomponentinMAKER’sgraphhasatleast onefreeedgeadjacenttoit,wesayitisalivecomponent. Asmentionedbefore,ifoneoftheplayershasawinningstrategyasasecondplayer,hecanuseittoobtainawin- ningstrategyasafirstplayer.Hence,whenwedescribeMAKER’sstrategyweassumethatheisthesecondplayer,im- plyingthatunderthedescribedconditionshecanwinaseitherafirstorasecondplayer.ThesamegoesforBREAKER’s strategy. 2 MAKER’sstrategy ThroughoutthissectionweassumethatthefirstplayerisBREAKER. InthissectionwedescribeandanalyzeaverybasicstrategyforMAKER,towhichwereferthroughoutthepaper asthe treestrategy. MAKER’s goalistobuilda component ofsize s, and hisstrategy istobuilda singleconnected componentT. Hestartsfromasinglearbitraryvertexr,andineverymoveheaddsanewvertextoT byclaiminga freeedgee E(T,V \T). IfalledgesinE(T,V \T)havealreadybeenclaimedbyBREAKER,andMAKER’scomponent ∈ isofsizestrictlylessthans,heforfeitsthegame.NotethatindeedT isatreethroughoutthegame. Definition. LetG (V,E)beagraphonnvertices.Foranintegerk 1,2,..., n/2 ,wedefine = = ⌊ ⌋ E(S,V \S) ΨE(G,k) min | |:S V,1 S k . = S ⊆ ≤| |≤ ½ | | ¾ Consideredasafunctionofk,i.e.,whenGisfixed,Ψ issometimescalledtheedgeisoperimetricprofile. E Thenext proposition showsthatifthegraphhasgoodexpanding properties, then BREAKER cannotseparate T fromV \T unlessT islargeenough. Proposition5. AssumeΨE(G,k) b.ThenMAKERisabletocarryoutthetreestrategyforatleastkroundsinthe(1:b) > gameonthegraphG. 5Thisrandomgraphintuitionisnotaformalargument,soweallowourselvestoneglectthedependenceoftheserandomchoices. 3 Proof. ConsiderthemomentbeforeMAKER’sjthmoveforsome1 j k.Wehave T j kandthus E(T,V \T) ≤ ≤ | |= ≤ | |> T b jb.Duringjmoves,BREAKERcouldhaveclaimedatmostjbedges,sosomeedgeofE(T,V \T)isstillavailable | | = forMAKERtoclaim. SinceweonlyneedMAKER’sconnectedcomponenttospanaconstantfractionofthegraph,wecanmakeuseof thefollowingresultontheedgeexpansionofsmallsetsintherandomd-regulargraph: Lemma 6 ([11], Theorem 4.16). Let d 3 be an integer and let δ 0. Then there exists ǫ ǫ(d,δ) 0 such that ≥ > = > Ψ G ,ǫn d 2 δalmostsurely. E n,d > − − ¡Takingδ¢ 1inLemma6andemployingthetreestrategyyieldsTheorem4. = Remark7. Lemma6isstrongenoughtorenderthetreestrategyeffectivealsointhedoubly-biased(m:b)game,as longasb/m d 2. TheproofiscompletelyanalogoustotheproofofProposition5whenMAKERisthefirstplayer, < − andverysimpleadjustmentsareneededwhenBREAKERstarts. 3 BREAKER’sstrategy ThroughoutthissectionweassumethatthefirstplayerisMAKER. 3.1 Reactivestrategies Definition. AstrategyofBREAKERiscalledreactiveifthefollowingholds: ineachofhissteps,iftheconnectedcom- ponentlasttouchedbyMAKERislive,BREAKERclaimsafreeedgeincidenttoit. NotethattherecanbemanyreactivestrategiesforBREAKER,varyinginthewaythathechooseswhichfreeedge to claim among those that are incident to MAKER’s last touched component. In this paper, we limit ourselves to reactiveBREAKERstrategies;thisallowsBREAKERtocontrolthenumberoffreeedgesincidenttoMAKER’sconnected components,asthefollowingclaimshows: Claim8. Letb,dbepositiveintegersandletGbead-regulargraph.If BREAKERusesareactivestrategy,thenthroughout the(1:b)Maker–BreakergameplayedontheedgesetofG,atthebeginningofeachroundeveryconnectedcomponent SinMAKER’sgraphisincidenttoatmost(d 2 b) S b 2freeedges. − − | |+ + Proof. Theclaimtriviallyholdsatthebeginningofthegame,aseveryconnectedcomponentisasinglevertex,and vertexdegreesinGareallequaltod.Ineverymove,MAKEReither: (a) claimsanedgeinsidesomecomponent;or (b) merges two connected components, i.e., claims a free edge betweentwo connected components S and S , 1 2 creatinganewconnectedcomponentSofsize S S S . 1 2 | |=| |+| | Inthefirstcase,theclaimtriviallyholdsnomatterhowBREAKERplays.Inthesecondcase,Si (fori 1,2)wasincident = beforeMAKER’smovetoatmost(d 2 b) Si b 2freeedges.AsMAKERhasjustclaimedanedgeincidenttoboth − − | |+ + S1andS2,afterMAKER’smoveatmost(d 2 b) S 2(b 2) 2freeedgesareincidenttothemergedcomponentS. − + | |+ + − BREAKER inhisnextmoveclaimsb oftheseedges(orsimplyallofthem,iftherearelessthanthat),leavingatmost (d 2 b) S 2(b 2) 2 b (d 2 b) S b 2freeedgesincidenttoS,sotheclaimstillholds. − − | |+ + − − = − − | |+ + WecannowproveProposition1. ProofofProposition1. ByClaim8wegetthatbyusinganyreactivestrategy,BREAKERcanmakesurethateverycom- ponentSinMAKER’sgraphwillhaveatmost k S k d freeedgesincidenttoit. Inparticular,k d k S forany − | |+ + + > | | livecomponent S,orequivalently S (d/k) 1. This lastinequality mayberewrittenas S d/k . Sinceevery | |< + | |≤⌈ ⌉ componentinMAKER’sgraphwascreatedbymergingtwolivecomponents,theresultfollows. Remark. Forfixeddandk,theboundofProposition1istightforlargeenoughn,viathetreestrategyonG . n,d Remark9. ReactivestrategiesareeffectiveforBREAKERalsointhedoubly-biased(m:b)game,aslongasb/m d 2. > − AproofverysimilartotheoneaboveshowsthatBREAKERcanlimitMAKERinthe(m:m(d 2) k)gametoconnected − + componentsofsizeatmost(m 1) md/k . + ⌈ ⌉ 4 3.2 Playingagainstthetreestrategy Beforepresentingafull-fledgedstrategyforBREAKERinthe(1:d 2)game,letusfirstconsiderasimplifiedversionof − it,whichremainseffectiveaslongasMAKERadherestothetreestrategyofSection2.TakingClaim8onestepfurther, BREAKER needstomakesurethat,beforeMAKER’streeT growstoomuch,theonlyfreeedgesincidenttoitwillbe edgesinsideT.Thisgivesrisetothefollowingdefinition: Definition. LetG beagraph. Asimple path p v v v inG iscalled self-colliding if v isadjacenttosome v 1 2 k k i = ··· for1 i k 2. Wecouldalsoviewp asasimplepathv v v ,whichwecallthetail,leadingtoasimplecycle 1 2 i 1 v v ≤ ≤v v−,whichwecallthebody.6 ··· − i i 1 k i + ··· WeusethefollowingvariationoftheMooreboundonthegirthofgraphswithminimumdegreek. Lemma10. LetG beagraphonn verticeswithminimumdegreeδ(G) k. Then,foreveryedge(u,v) E,thereisa ≥ ∈ self-collidingpathpstartingwith(u,v)oflengthatmost2 log n .Inparticular,g(G) 2 log n .Moreover,the distancealongpfromutoeverybodyvertexisatmost log nk−.1 ≤ k−1 k§ 1 ¨ § ¨ − Proof. Thenumberofnon-backtrackingwalksofleng§th j 1s¨tartingwiththeedge(u,v)is(k 1)j.Sincethegraph + − onlyhasnvertices,thereexisttwodistinctnon-backtrackingwalksoflengthsi 1andj 1endingatthesamevertex, + + wherei j log n . Together, thesewalksforma(notnecessarily simple) cycleoflengthatmost2 log n passingt≤hrou≤ghv.kN−o1wtakeanysimplesubcycleofittobep’sbodyandconnectitbacktouviaasimplepath.k−1 § ¨ § ¨ WenowdescribeBREAKER’sstrategy.AfterMAKER’sfirstmove,BREAKERchoosesarbitrarilyoneofthetwovertices MAKERhasjusttouchedanddenotesitbyu. BREAKERthenusesLemma10topick,foreachneighborv ofu,aself- colliding path pv oflengthatmost2 logd 1n beginningwiththeedge(u,v). Notethatthepathschosenfortwo neighborsv,v arenotnecessarilydisjoint.− ′ § ¨ NowBREAKER’sstrategyistoallowMAKERtoclaimonlyedgesfromP pv:(u,v) E ;thiswouldlimitthesize =∪ ∈ ofMAKER’sconnectedcomponenttobeatmost|P|≤2d logd−1n . © ª Proposition11. Inthe(1:d 2)gameonG,if MAKERfoll§owsthetr¨eestrategy,BREAKERisabletocarryoutthecounter- − strategy. Proof. WeshowthatBREAKERcanensurethatbeforeeverymoveofMAKER,theonlyfreeedgesinE(T,V \T)arein P;thus,MAKERmustclaimanedgeofP,advancingalongsomepv.ItistrueatthebeginningofthegameasT {u}. = AfterMAKERclaimstheedge(vi 1,vi) pv,thereareatmostd 2freeedgesincidenttovi inE(T,V \T)\P,since − ∈ − (vi 1,vi)hasjustbeenclaimedand(vi,vi 1) P. BREAKER canclaimallofthem(and,ifnecessary,somearbitrary − + ∈ extraedgesoutsideP).Thus,aftergettingaspanningtreeT P,MAKERforfeits. ⊂ Thecounter-strategyisstilleffectivewhenMAKERbuildsaforestwithmanytrees,aslongasoneoftheconnected componentsmergedisalwaysasinglevertex;nevertheless,itbreaksdownwhenMAKERbuildsupmanysmalltrees andconnectsthemonetotheother,avoidinggettingtothecollisionattheendoftheself-collidingpaths. BREAKER couldpossiblydenyamergeoftwotreesT andT byforgoingthecounter-strategyandclaimingthefreeedgebetween ′ T andT′,butthismightletMAKERescapefromtherespectiveP orP′. 3.3 Playingagainstanystrategy WenowdescribeaglobalstrategyforBREAKER,whichcopeswellwithMAKERmergingconnectedcomponentsofany size. Beforestartingthe(1:d 2)game, BREAKER usesLemma 3topickanorientationD ofthegraphG suchthat − everyvertexhasapositiveout-degreeandallsimpledirectedpathsinD areoflengthatmostd κ logn. Notethat d + BREAKERmayaswellrevealDtoMAKER. ThestrategyofBREAKERgoesasfollows.WithoutlossofgeneralitywemayassumethatMAKER’sstrategyisalways tobuildaforest,sinceclaiminganedgewithinaconnectedcomponentdoesnothelpMAKER.7 Thus,oneachmove MAKERmergestwotreesT1andT2toasingletreeT byclaimingafreeedgefromT1toT2.BREAKERthenclaimsd 2 − freeedgesaccordingtothefollowingpriorities: 1. E(V \T,T2); 2. E(V \T,T1); 3. E(T,V \T). 6Itispossiblethatthetailisempty,thatis,pisacycleoflengthk. 7Formally,MAKERclaimsedgesinsidehisconnectedcomponentsonlywhenallremainingfreeedgesaresuch;bythistime,theoutcomeofthe gamehasalreadybeendetermined. 5 Ineachstep,BREAKERclaimsanarbitraryfreeedgefromthesetwiththesmallestindex.Ifthereisnofreeedgeamong thesesets,hejustclaimsanarbitraryfreeedge. Claim12. EachtreeT inMAKER’sgraphisadirectedtreeinD;thatis,thereissomer T —whichwedenotebytheroot ∈ ofT —suchthateveryvertexinT isreachablefromr. Moreover,atthebeginningofeachround(i.e.,after BREAKER’s move),nofreeedgesenterT\{r}. Proof. Theclaimistriviallytrueatthebeginningofthegame,astheinitialconnectedcomponentsaresinglevertices, soeveryvertexistherootandonlymemberofitsowndirectedtree.SupposenowthatMAKERmergedT1andT2,two treeswithrootsr andr ,respectively,byclaiminganedgefromT toT . Byourassumption,beforethemergethe 1 2 1 2 onlyfreeedgesenteringT1andT2wereintor1andr2,respectively.Hence,MAKERmusthaveclaimedanedgeintor2. Clearly,themergedcomponentisadirectedtree,andallverticesinT T arenowreachablefromr ,whichbecomes 1 2 1 ∪ the rootofthe new tree. Furthermore, thein-degreeof every vertexinD, andinparticular ofr , isatmost d 1, 2 − soBREAKER’spreferencetowardsE(V \T,T2)ensuresthatalltheedgesenteringr2areclaimedafterBREAKER’smove (onebythemergeandalltherestbyBREAKER),andsoallthefreeedgesenteringthenewtreeenteritsroot. ItisbeneficialtoclassifyMAKER’streesbythenumberoffreein-edges. Definition. ThetypeofatreeT inMAKER’sgraphisthenumberoffreeedgesinE(V \T,T). By Claim 12, the type of a tree is bounded by the in-degree of its root, so the possible types are 0,1,...,d 1. − Claim12alsoenablesustopartiallyordertheverticesineachtree,givingrisetothefollowingdefinition: Definition. LetT beatreeinMAKER’sgraph.Theheightofavertexv T,denotedbyh(v),isthelengthofthe(unique) ∈ pathr v inT,wherer istherootofT;theheightofanedge(u,v) E(T,V \T)ish(u,v) h(u);theheightofT, ∈ = denotedh(T),isthemaximumheightoverallv T. ∈ WewishtoboundthesizeofMAKER’strees. BythechoiceofD,weknowthatthetreesarenottoo“high”,butwe alsoneedtoensuretheydonotbecometoo“wide”. Forthis,werefineBREAKER’sstrategyabit. InthetreeT justcreatedbyMAKER, BREAKER claimsin-edgesfrom highesttolowest,andthenout-edgesfromlowesttohighest.Inmoredetail,ineachstepBREAKERclaimsanincoming freeedge x,y E(V \T,T)suchthath y ismaximal,ifpossible;otherwiseheclaimsanoutgoingfreeedge x,y ∈ ∈ E(T,V \T)suchthath x,y h(x)isminimal.Inbothcases,tiesarebrokenarbitrarily. ¡ ¢ = ¡ ¢ ¡ ¢ BREAKER’spreferenceofclaiminglowout-edgesgivesthefollowing: ¡ ¢ Claim13. LetT beatreeinMAKER’sgraph. Iftheedgee E(T,V \T)wasclaimedbyBREAKER,thenh e′ h(e)for ∈ ≥ everyfreeedgee′∈E(T,V \T). ¡ ¢ Proof. NotefirstthatifBREAKERhasclaimedanedge(u,v) E(T,V \T)forsometreeT,thenfromthatpointuntil ∈ theendofthegameuwillonlybelongtotreesoftypezero. Indeed,accordingtohisstrategy,BREAKERhasclaimed (u,v)onlysincetherewerenofreeedgesenteringT,soatthatpointT isoftypezero. Furthermore,byClaim12we havethatatanypointuntiltheendofthegameuwillonlybelongtotreesrootedatT’sroot,implyingthattheywillbe oftypezeroaswell.Therefore,Claim13triviallyholdswhenthetypeofT ispositive,sincethatimpliesthatBREAKER hasclaimedonlyedgesenteringT.WethusassumeT isoftypezero. Atthemoment BREAKER claimse, thereisnoedgelowerthane amongalledgesinE(T,V \T). Insubsequent rounds,theonlychangestoE(T,V \T)(andtoT)arewhenMAKERclaimssomeedgee′fromT toanothertreeT′.The heightofallverticesofT′inthemergedtree,andthusalsoofallnewedgesinE(T,V \T),isatleasth e′ 1 h(e). + > Recallthatinthecounter-strategytothetreestrategy,BREAKERonlyallowedMAKERtopursuese¡lf-c¢ollidingpaths, soMAKER’sfinalcomponentconsistedofd pathspv sharingarootvertex. Here,similarly,BREAKER’sstrategyallows MAKERtoextendeveryfreeedgeinE(T,V \T)toadirectedpath.Thismotivatesthefollowingdefinitionofwidth: Definition. LetT beatreeinMAKER’sgraph.Thei-widthofT,denotedwi(T),isthenumberofverticesinT ofheight i plusthenumberoffreeedgesinE(T,V \T)ofheightstrictlysmallerthani. ThewidthofT,denotedw(T),isthe maximumi-widthinT,takenoveri 0,1,...,h(T). = Wearereadytoprovethefollowingproposition,whichimpliesTheorem2since T 1 h(T) w(T). | |≤ + · Proposition14. LetT beatreeoftypetinMAKER’sgraph.Then, d t, 1 t d 1; w(T) − ≤ ≤ − ≤(2d 2, t 0. − = 6 Proof. We prove this by induction on the number of rounds in the game. The proposition holds for trivial trees. AssumeMAKERmergestreesT1andT2oftypest1andt2,respectively,byclaimingtheedge(u,v),wherev istheroot ofT2.Then,themergedtreeT hastypet max(0,t1 t2 d 1)afterBREAKER’smove.Notethatnecessarilyt2 0. = + − + > TheverticesofT1maintaintheirheightinT;verticesthathadheightj inT2,nowhaveheighth(u) 1 j inT.For + + i h(u),wehavewi(T) wi(T1) w(T1);fori h(v),thenow-claimededge(u,v)nolongercountsforthei-width ≤ = ≤ > ofT,so wi(T) wi(T1) 1 wi h(u) 1(T2) w(T1) w(T2) 1. (1) = − + − − ≤ + − Ift1 0then,bytheinductionhypothesis,w(T1) d t1andw(T2) d t2,so > ≤ − ≤ − w(T) w(T1) w(T2) 1 d t1 d t2 1 d t. ≤ + − ≤ − + − − = − Ift1 0thent 0too;bytheinductionhypothesis, w(T1) 2d 2andw(T2) d t2 d 1. Fori h(u),as = = ≤ − ≤ − ≤ − ≤ before,wehavewi(T) w(T1) 2d 2;fori h(u),assumingweshowthatwi(T1) d,thesamecalculationasin(1) ≤ ≤ − > ≤ yieldswi(T) wi(T1) w(T2) 1 d (d 1) 1 2d 2. ≤ + − ≤ + − − = − Bythedefinitionofwi(T1),thereexistasetU T1ofverticesofheighti andasetA E(T,V \T)offreeedgesof ⊆ ⊆ heightlessthani suchthatwi(T1) U A.Foreveryvertexx U,pickaleafx′ T1reachable(inT1)fromx.The =| |+| | ∈ ∈ out-degreeofx′ inD ispositive,sopicksomeedgee x′,y E(D). Ify T1,noonewilleverclaime;otherwise, = ∈ ∈ e∈E(T,V \T)soMAKERhasnotyetclaimedit.ByClaim¡13,n¢eitherdidBREAKERsinceh(e)=h x′ ≥h(x)=i>h(u) and(u,v)∈E(T1,V \T1)wasfreebeforeMAKER’smove. Altogether,wehaveaset A′of A′ =|U¡ |¢freeedgescoming outofT ,disjointfrom Asinceedgeheightsin A areallatleasti. ByClaim8,T isincidenttoatmostd freeedges, 1 ′ 1 ¯ ¯ sowi(T1) A A′ A A′ d,establishingtheproposition. ¯ ¯ =| |+ = ∪ ≤ ¯ ¯ ¯ ¯ Remark. Inthep¯rev¯iou¯ssubse¯ction,usingthecounter-strategytothetreestrategy,BREAKER couldboundw(T)by ensuringthat,besidesasinglevertexofdegreed,thedegreesofallverticesinT wereatmosttwo. Withthestrategy presentedinthissubsection,BREAKERcannotlimitw(T)byboundingthenumberofforksinT,i.e.,thenumberof verticesofout-degreeatleast2. Indeed,alreadyford 3,thereexistsapositiveout-degreeorientationD ofacubic = graphGandastrategyforMAKERtobuildatreeT withΩ(h(T))forksina(1:1)gameonG. 4 Shortgraphorientations InthissectionwediscussandproveLemma3.Webeginbyintroducingthefollowingnotation: Definition. For a directedgraph D, wedenote byl(D) themaximal length ofa simple directedpath inD. For an undirectedgraphGandj {0,1},wedenotebyl (G)theminimumofl(D)overallorientationsDofGsuchthatevery j ∈ vertexhasout-degreeatleast j. The case j 0, that is, when we drop the positive out-degrees requirement, was considered by (at least) four = independentworks. Theorem15(Gallai[6]–Hasse[8]–Roy[17]–Vitaver[20]). ForeverygraphG,l0(G) χ(G). = Wemention hereonly the easyside oftheproof, whichwill beused shortly. Tosee thatl0(G) χ(G), colorG ≤ properlybythecolors 1,2,...,χ(G) andorienteachedge{u,v}fromutoviffu’scolorisgreaterthanv’s. Returningtotheca©se j 1,wecªannotexpectanorientationD withpositiveout-degreesforwhichl(D)isinde- = pendentofn.Indeed,wheneveryvertexhasapositiveout-degree,Dsurelycontainsadirectedcycle,sol1(G) g(G). ≥ Knownconstructionsofd-regulargraphsofhighgirth(see,e.g.,[3,5,14])yieldfamiliesofgraphsofordern,chromatic numberΩ d/logd andgirthΩ logd−1n .Thus,ourbesthopewouldbetoshowthatl1(G)=O logn . Thema¡inideao¢ftheproofth¡atfollow¢sisthis:wefindinGasetofdisjointshortcycles,which¡weo¢rientcyclically, andweorienttherestoftheedges“towards”thecycles.Lemma10willassistusinshowingthatsimpledirectedpaths outsidethecyclesarenecessarilyshort. ProofofLemma3. Fixk max 3, logδ/loglogδ andsetγ log n ,γ log n . LetC beamaximal c=ollectionofnonadjacentinduced cδy=clesofδ−le1ngth akt=mostk2−γ1 . Thatis, webeginwithan ¡ § ¨¢ § ¨ § k ¨ emptycollectionC ∅and,aslongasthereexistsaninducedcycleC inG oflength C 2γ whoseverticeshave k = | |≤ noneighborsamongVC,theverticesofcyclesinC,weaddC toC.NotethatC isnonemptysincethegirthofGisat most2γ 2γ ,byLemma10(ortheMoorebound). δ k ≤ FixanycyclicorientationofthecyclesinC,andorienttheedgesofE(VC,V \VC)intoC.AlledgesincidenttoC arethusoriented,asthecyclesinC areinducedandnonadjacent.SincenoedgesareleavinganycycleinC,oncewe orienttherestofthegraph,anysimpledirectedpathcancontainatmost2γk verticesofVC,whichformitssuffix. 7 WenowfusealltheverticesofcyclesinC toasinglevertex s. LetG V ,E betheresultinggraph; makeit ′ ′ ′ = simplebydiscardingloopsandparalleledgesincidenttos. ¡ ¢ Forevery vertex v V′ wedenoteitsdistancefrom s byρ(v). Weclaimthatρ(v) 1 γδ; indeed, v iswithin ∈ ≤ + distanceγ ofsomeshortcycleC byLemma10(specifically,v iswithindistanceγ ofanyvertexonC),andC either δ δ intersectssomecycleinC,isadjacenttosomecycleinC,orsimplyC C,bythemaximalityofC. ∈ Fori ∈ 1,2,...,1+γδ , considerthelevelsetVi′= v∈V′:ρ(v)=i andthesubgraphGi ⊂G′ itinduces. Asin theproofofTheorem15,weorientedgesbetweenV andV “downwards”(i.e.,fromV toV ). Thisensuresall © ª i′ © i′ 1 ª i′ 1 i′ verticesexceptshaveapositiveout-degree,viashortestpaths+tos. + By definition, every edge either lies inside a level set or connects two successive level sets. Therefore, it only remainstoorientedgesbetweensameheightvertices,whichwillbedoneusingTheorem15.ForG1wehavel0(G1) = χ(G1) χ(G)sinceG1 G.BythemaximalityofC,foralli 1,Gi hasnocycleoflengthatmost2γk.ApplyLemma10 ≤ ⊂ > todeducethatG cannothaveasubgraphwithminimumdegreek;inotherwords,G is(k 1)-degenerate,and,in i i − particular,k-colorable. Altogether,wehaveanorientationD ofG satisfying ′ ′ 1+γδ 1+γδ l D′ l0(Gi) χ(Gi) χ(G) kγδ; ≤ = ≤ + i 1 i 1 ¡ ¢ X= X= combinedwiththeorientationofedgesincidenttoC definedabove,wegetanorientationD ofGwithpositiveout- degreesandl(D) χ(G) kγ 2γ .Therefore, δ k ≤ + + l1(G) l(D) χ(G) O logn/loglogδ , ≤ = + ¡ ¢ asthelemmastates. 5 Concludingremarksandopenproblems Componentgamesonothergraphs. Forthesakeofsimplicity,wepresentedourresultsinthispaperonlyforregular graphs,butthesestayputunderthealternativedefinition sb∗(n,d)=max sb∗(G):Gisagraphonnverticesand∆(G)≤d . © ª Itwouldbeinterestingtoconsiderthecomponentgameonfamiliesofgraphsofunboundedmaximumdegree. For instance,theMaker–BreakercomponentgameonG isconsideredby[12]. n,p Doubly-biasedgames. AsshowninRemark7,Theorem4canbeeasilyextendedtothedoubly-biasedgame(m:b) forb/m (d 2);similarly,Remark9extendsProposition1tothe(m:b)gameforb/m (d 2).However,thestrategy < − > − presentedinSubsection3.3isinadequateinthe(m:(d 2)m)game.Indeed,alreadyform 2,thereexistsapositive − = out-degreeorientationDofad-regulargraphGandastrategyforMAKERtobuildaconnectedcomponentSofwidth Ω dh(S) ina(2:2d 4)gameonG.ThekeystepinMAKER’sstrategyistomergeconnectedcomponentsbyclaiming − twoout-edgesenteringthesamevertex,nullifyingClaims12and13,andthusProposition14nolongerholds. ¡ ¢ WebelievethatnotallhopeislostforBREAKER. Conjecture16. LetG bead-regulargraphonn vertices,whered 3, and letm beapositiveinteger. Then, inthe ≥ (m:(d 2)m)gameonG,BREAKERcanforceMAKERtobuildonlyconnectedcomponentsofsizeo(n),perhapspolylog- − arithmic(orevenlogarithmic)inn. Verylargedegrees. OurresultsinSubsection1.2holdforanyvalueofd,butyieldlittleford Ω(n). = ǫn fIrnompaPrtriocuploasri,tifoonrG5=(nKotne+1thaantdΨfoEr(Kenver1y,kǫ)>0n,we1gektsf(∗o1r+ǫe)nve(Kryn+11)≤k2/ǫnf/r2o)m; hPorwopevoesri,tifoonr1bandds(∗1n−ǫ)wne(Kgne+t1t)h≥e + = + − ≤ ≤ = = meaninglessbounds0≤sn∗(Kn)≤n.Aslightlybetterupperboundwouldbesn∗(Kn+1)≤1+⌈n/2⌉,justbecausea(1:b) gameonanygraphGlasts E(G) /(b 1) rounds. ⌈| | + ⌉ Itwouldbeinterestingtogetanontrivialboundonsn∗(Kn 1). + Verylargecomponents. RecalltheproofofTheorem4inSection2,whichcombinedthetreestrategywithedgeex- pansionviaProposition5.HowfarcanProposition5pushMAKER?CanMAKERuseittobuildaconnectedcomponent ofsize n/2 ? ThefollowingupperboundontheCheegerconstantofregulargraphs,duetoAlon[1],saysthatthisis ⌊ ⌋ onlypossiblewhenthebiasiswellbelowd/2. 8 Theorem17([1]). Foreveryd-regulargraphG,ΨE(G, n/2 ) d/2 Ω(pd). ⌊ ⌋ ≤ − Proposition5posesasufficient,butobviouslynotanecessary,conditionforthetreestrategytosucceed.Itmaybe possibleforMAKERtobuildaconnectedcomponentofsize n/2 viathetreestrategyorsomeotherstrategy,without ⌊ ⌋ relyingonexpansion. Shortorientations. TheproofofLemma3showsthatl1(G) χ(G) O logn/loglogd .Ontheotherhand,l1(G) ≤ + ≥ Ωg(Gd)/alongddl1((Gse)e≥,el.0g(.G,[)3=,5χ,1(G4]))adnedmthounsstcroatnesttrhuacttsioonmseotifmde-rselg1u(Gla)r≥grχap(Ghs)¡+ofΩgirlothgΩn/¡llooggdd¢−1.n¢andchromaticnumber ¡ Wesusp¢ectthecorrectbehaviorofl1(G)isactuallythelowerbound,asthe¡followingc¢onjecturestates. Conjecture18. LetGbead-regulargraphonnvertices,whered 3.Then,l1(G) χ(G) O logn/logd . ≥ = + Onecanalsoaskaboutthevalueofl (G)for j 1. ¡ ¢ j > Acknowledgements TheauthorswishtothankNogaAlon,AsafFerber,DannyHefetz,andMichaelKrivelevichforusefuldiscussionsand comments. References [1] NogaAlon,Ontheedge-expansionofgraphs.Combin.Probab.Comput.6:145–152(1997). [2] Noga Alon, Itai Benjamini, and Alan Stacey, Percolation on finite graphs and isoperimetric inequalities. Ann. Probab.32(3):1727–1745(2004). [3] BélaBollobás,Chromaticnumber,girthandmaximaldegree.DiscreteMath.24:311–314(1978). [4] VašekChvátalandPaulErdo˝s,Biasedpositionalgames.Ann.DiscreteMath.2:221–228(1978). [5] PaulErdo˝sandHorstSachs,Regulargraphswithgivengirthandminimalnumberofknots(inGerman).Wiss. Z.Martin-Luther-Univ.Halle-Wittenberg,Math.-Naturwiss12:251–257(1963). [6] TiborGallai,Ondirectedgraphsandcircuits.In:TheoryofGraphs,Proc.Colloq.Tihany1966,NewYorkAcademic Press,pp.115–118(1968). [7] HeidiGebauerandTiborSzabó,Asymptoticrandomgraphintuitionforthebiasedconnectivitygame.Random StructuresandAlgorithms35:431–443(2009). [8] Maria Hasse, Zur algebraischen Begründung der Graphentheorie. I (in German). Mathematische Nachrichten28(5–6):275–290(1965). [9] Dan Hefetz, Michael Krivelevich, Miloš Stojakovic´ and Tibor Szabó, Global Maker-Breaker games on sparse graphs.EuropeanJ.Combinatorics32:162–177(2011). [10] DanHefetz,MirjanaMikalacˇkiandMilošStojakovic´,DoublybiasedMaker-BreakerConnectivitygame.Electronic J.Combinatorics19:P61(2012). [11] Shlomo Hoory, Nathan Linial and Avi Wigderson, Expander graphs and their applications. Bull. Amer. Math. Soc.43:439–561(2006). [12] MichaelKrivelevichandTobiasMüller,privatecommunication. [13] AlfredLehman,AsolutionoftheShannonswitchinggame.J.Soc.Indust.Appl.Math.12:687–725(1964). [14] AlexanderLubotzky,R.PhillipsandPeterSarnak,Ramanujangraphs.Combinatorica8(3):261–277(1988). [15] Asaf Nachmias and Yuval Peres, Criticalpercolation on random regular graphs. Random Structuresand Algo- rithms36(2):111–148(2010). [16] CrispinSt.JohnAlvahNash–Williams,Edge-disjointspanningtreesoffinitegraphs.J.LondonMath.Soc.36:445– 450(1961). 9 [17] B.Roy,Nombrechromatiqueetpluslongscheminsd’ungraphe(inFrench).Rev.FrançaiseInformat.Recherche Opérationnelle1(5):129–132(1967). [18] Miloš Stojakovic´ and Tibor Szabó, Positional games on random graphs. Random Structures and Algo- rithms26:204–223(2005). [19] William Thomas Tutte, On the problem of decomposing a graph into n connected factors. J. London Math. Soc.36:221–230(1961). [20] L.M.Vitaver,DeterminationofminimalcoloringofverticesofagraphbymeansofBooleanpowersoftheinci- dencematrix(inRussian).Dokl.Akad.NaukSSSR147:758–759(1962). 10