regularitygraph

Longcyclesinsubgraphsof(pseudo)randomdirectedgraphsIdoBen-EliezerMichaelKrivelevichBennySudakovMarch31,2011AbstractWestudytheresilienceofrandomandpseudorandomdirectedgraphswithrespecttothepropertyofhavinglongdirectedcycles.
Forevery0graphonnverticesandwithatleastalinearnumberofedges,andletGbeasubgraphofGwith(1/2+γ)|E|edges.
ThenGcontainsadirectedcycleoflengthatleast(co(1))n.
Moreover,thereisasubgraphGofGwith(1/2+γo(1))|E|edgesthatdoesnotcontainacycleoflengthatleastcn.
1IntroductionGivenapropertyP,atypicalprobleminextremalgraphtheorycanbestatedasfollows.
Givenanumberofverticesn,whatistheminimal(ormaximal)numberfP(n)suchthatanygraphonnverticeswithf(n)edgespossessesPManyexamplesofsuchproblemsandresultscanbefound,e.
g.
,in[8].
Usually,thepropertyPweconsiderinextremalproblemsiseithermonotoneincreasingormonotonedecreasing.
ApropertyPismonotoneincreasing(respectively,decreasing)ifitispreservedunderedgeaddition(respectively,deletion).
TheresilienceofagraphGwithrespecttoapropertyPmeasureshowfarthegraphisfromanygraphHthatdoesnothaveP.
Inparticular,thestudyofresilienceusuallyfocusesonmonotoneproperties,andthefollowingtwotypesofproblemsarestudied.
SchoolofComputerScience,RaymondandBeverlySacklerFaculyofExactSciences,TelAvivUniversity,TelAviv69978,Israel,e-mail:idobene@post.
tau.
ac.
il.
ResearchsupportedinpartbyanERCadvancedgrant.
SchoolofMathematicalSciences,RaymondandBeverlySacklerFacultyofExactSciences,TelAvivUniversity,TelAviv69978,Israel,e-mail:krivelev@post.
tau.
ac.
il.
ResearchsupportedinpartbyUSA-IsraelBSFgrant2006322andbygrant1063/08fromtheIsraelScienceFoundation.
DepartmentofMathematics,UCLA,LosAngeles,CA90095.
Email:bsudakov@math.
ucla.
edu.
ResearchsupportedinpartbyNSFCAREERawardDMS-0812005andbyaUSA-IsraeliBSFgrant.
1GlobalResilience.
GivenamonotoneincreasingpropertyP,theglobalresilienceofGwithrespecttoPisthemaximalintegerRsuchthatforeverysubsetE0E(G)of|E0|=Redges,thegraphGE0stillpossessesP.
ForthecaseofamonotonedecreasingpropertyP,theglobalresilienceofGwithrespecttoPisdenedasthemaximumnumberRsuchthattheadditionofanysubsetofRedgestoGstillresultsinagraphG∈P.
Onecanalsodenethenotionoflocalresilienceofagraphwithrespectto,say,amonotoneincreasingpropertyPasthemaximumnumberrsuchthatforanysubgraphHGofmaximumdegreer,thegraphGHisstillinP.
Sinceinthispaperwewillbeconcernedwithpropertiesrelatedtoglobalresilience,wewillnotdwellonthenotionoflocalresilienceanymore.
Tothebestofourknowledge,SudakovandVuweretherst[18]todenethenotionofglobalresilienceexplicitlyandquantitativelyandtoputitforwardasasubjectofinde-pendentstudy(itiscloselyrelatedthoughtothewellstudiednotionoffaulttolerance,see,e.
g.
,[1]).
However,inasensemanywellknowntheoremsinextremalgraphtheorycanbestatedusingthisterminology.
Forexample,givenaxedgraphH,theTurannumberofH,denotedbyex(H,n),istheminimumnumbermsuchthatanygraphonnverticeswithmedgescontainsacopyofH.
Clearly,thestudyofTurannumbersisequivalenttothestudyoftheglobalresilienceofthecompletegraphKnwithrespecttothepropertyofhavingacopyofH.
Woodall[20]gavetightboundsforthenumberofedgesinanundirectedgraphthatguaranteestheexistenceofacycleoflengthatleast.
Inourterminology,hegavetightboundsontheglobalresilienceofKnwithrespecttothepropertyofhavingacycleoflengthatleast.
WewilldiscussWoodall'sresultlaterandwillalsousehisresultinourwork.
Lewin[17]studiedtheanalogousproblemfordirectedgraphs,andhegavetightboundsonthenumberofedgesrequiredforhavingadirectedcycleoflengthatleast.
Manyextremalresultsregardingtheexistenceofcyclesindirectedgraphscanbefound,e.
g.
,in[7].
Recently,therehasbeenaseriesofworksstudyingtheresilienceofgraphswithrespecttodierentproperties.
Dellamonicaetal.
[11]studiedthelocalandglobalresilienceoflongcyclesinpseudorandomundirectedgraphs.
Krivelevichetal.
[16]studiedtheresiliencewithrespecttopancyclicity(havingacycleofeverypossiblelength).
Ben-Shimonetal.
[6]stud-iedtheresilienceofseveralgraphpropertiesinrandomregulargraphs.
AlonandSudakov[2]studiedtheresilienceofthechromaticnumberinrandomgraphs.
B¨ottcheretal.
[9]studiedthelocalresilienceofG(n,p)withrespecttothepropertyofhavinganalmostspanningboundeddegreebipartitegraphwithsublinearbandwidth.
Later,answeringaquestionfrom[9],Huanget.
al.
[14]addressedtheresiliencewithrespecttohavingaspanningsub-graphH.
Baloghetal.
[4]studiedtheresilienceofrandomandpseudorandomgraphswithrespecttocontainingacopyofagivennearlyspanningtreeofboundedmaximumdegree.
Herewestudytheresilienceofpseudorandom(andhence,ofrandom)directedgraphswithrespecttothepropertyofhavingalongdirectedcycle(namely,asimpledirectedcyclethatcoversaconstantfractionofthevertices).
Weproveasymptoticallytightbounds,andthusprovidetheasymptoticvalueoftheresilienceofeverygraphwithrespecttothisproperty,assumingithassomepredenedpseudorandomnessproperty.
Ourproofuses2avariantofthecelebratedSzemeredi'sregularitylemmaforsparsedirectedgraphs,andashortandsimpletechniqueforndingalongdirectedpathinpseudorandomdirectedgraphs.
Usingthesetechniqueswecanreduceourproblemtothecaseofundirectedgraphs,wherebyapplyingtechniquesof[11]wecangivetightbounds.
1.
1ThemodelsWeconsiderheredirectedgraphsonnvertices,whereantiparalleledgesareallowed.
WesaythatagraphD=(V,E)hasdensitypif|E|=pn2.
LetD(n,p)bethefollowingprobabilitydistributiononthesetofn-vertexdirectedgraphs.
EverygraphinthesupportofD(n,p)containsnvertices,andforeverytwodistinctverticesx,y,thereisanedgefromxtoywithprobabilityp,andindependentlythereisanedgefromytoxwithprobabilityp.
Clearly,theexpectednumberofedgesis2pn2.
Oncewedeneourrandomdigraphmodel,itisusuallydesirabletodeneapseudoran-domanalog.
Thatis,wewouldliketodeneapropertysuchthatgraphswiththispropertyhavemanyofthe'nice'propertiesofrandomgraphs.
Roughlyspeaking,wesaythatadi-rectedgraphispseudorandomifthenumberofedgesbetweeneverytwolargeenoughsetsisclosetotheexpectednumberofedgesinarandomdirectedgraphwiththesamedensity.
Moreformally,wesaythatadirectedgraphGis(p,r)-pseudorandomifithasedgedensitypandforeverytwodisjointsetsA,BV(G),|A|=|B|,thenumberofedgesfromAtoB,denotedbyeG(A,B),satises|eG(A,B)p|A||B||≤r|A|√pn.
Thisis(uptonormalization)adirectedvariantofthewellknownnotionofjumbledgraphs,thatwasintroducedbyThomason[19].
Inhiscelebratedwork,ThomasonessentiallyprovedthatagraphdistributedasG(n,p)is(p,O(1))-pseudorandomwithhighprobability.
1Ontheotherhand,thereisnoinnitesequenceof(p,o(1))-pseudorandomgraphs.
ThefollowinglemmacanbeeasilyveriedbycombiningaChernotypeboundwiththeunionbound.
Lemma1.
1.
Foreveryconstantc>0thereisaconstantC>0suchthatforp≥Cn,arandomdirectedgraphG∈D(n,p)is(p,c)-pseudorandomwithhighprobability.
Ourresultsinthisworkwillholdforevery(p,r)-pseudorandomgraphwithp≥CnforsomesucientlylargeconstantC,andeveryr≤√pnforsomesmallconstant>0thatdoesnotdependonC.
ByLemma1.
1,arandomdirectedgraphdistributedaccordingtoD(n,p)withp≥Cnhasthispropertywithhighprobability.
Weshowherethatthedirectedcaseisbothsimilaranddierentfromtheundirectedcase.
Infact,sincewereduceherethedirectedcasetotheglobalresilienceproblemoftheundirectedcase,wecanuseideasfromDellamonicaetal.
[11]inordertogetourboundsontheresiliencefordirectedgraphs.
Ontheotherhand,manyofthetechniquesthatwereused1HereasequenceofeventsAn,n≥1issaidtooccurwithhighprobabilityiflimn→∞P[An]=1.
3fortheundirectedcasecannotbeappliedinthedirectedcase.
Also,therangeofparametersrelevanttousisratherdierent,sinceinparticulartheresultofDellamonicaetal.
[11]showsthattheremovalofany0.
99-fractionoftheedgesofa(pseudo)randomundirectedgraphstillleavesacycleoflinearsize.
Forthedirectedcaseitiseasytoseethatonecanalwaysremovehalfoftheedgesofanydirectedgraphandgetanacyclicdirectedgraph,andhenceagraphwithnocyclesatall.
1.
2OurresultsWoodall[20]studiedtheminimalnumberofedgesthatguaranteestheexistenceofalongcycle.
Inourterminology,hestudiedtheglobalresilienceofthecompletegraphKnwithrespecttothepropertyofhavingacycleoflengthatleast.
Heprovedthefollowing.
Theorem1(Woodall[20]).
Let3≤≤n.
EverygraphGonnverticessatisfyinge(G)≥n12·12+r+12+1,wherer=(n1)mod(2),hasacycleoflengthatleast.
ItiseasytoverifythatWoodall'sboundisbestpossible.
Indeed,takeagraphformedbyn12disjointcliquesofsize2,asinglesmallercliqueofsizerandavertexthatisconnectedtoeveryothervertexinthegraph.
Clearly,thelengthofalongestcycleinthisgraphisatmost1.
TheworkofDellamonicaetal.
[11]canbeviewedasageneralizationofWoodall'sworkfromthecaseofKntothecaseofgeneralpseudorandomgraphs.
Inordertocitetheirresultandalsoforfuturereferenceinourpaperthefollowingfunctionisdened.
Denition2.
Foragiven0≤α0.
Foreveryβ>0thereisn0suchthatforeverygraphGonn>n0verticessatisfying|E(G)|≥n2·1(1w(α))(α+w(α))+βhasacycleoflengthatleast(1α)·n.
4Observethatwecanpartitionavertexsetofsizenintok=11αsets,eachofsize(1α)n,andaremainingsetofsize(w(α)n,as1w(α)=k(1α).
Dellamonicaetal.
provedin[11]thatTheorem3canbeextendedto(sparse)pseu-dorandomgraphs;morespecically,theyprovedthatanysubgraphG=(V,E)ofa(p,r)-pseudorandomgraphG=(V,E)(wherepn1,andrisxed)with|E|≥(1(1w(α))(α+w(α))+o(1))|E|edgeshasacycleoflengthatleast(1α)·|V|.
Hereweprovidetightboundsontheresilienceofpseudorandomdirectedgraphswithrespecttothepropertyofhavingalongdirectedcycle.
Ourmaintheoremisadirectedversionoftheirresult.
Theorem4.
Fix0graphonnvertices,wherer≤√npand(γ)>0isasucientlysmallconstantthatdependsonlyonγandnissucientlylarge.
LetGbeasubgraphofGwithatleast(12+γ)|E|edges.
ThenGcontainsadirectedcycleoflengthatleast(1αo(1))·n,whereαsatises2γ=1(1w(α))(α+w(α)).
ObservecruciallythateverydirectedgraphG=(V,E)containsanacyclicsubgraphGwithatleast|E|/2edges.
Indeed,xapermutationσ:V→V,andletG1bethesubgraphwithalledgesxysuchthatσ(x)>σ(y),andG2bethesubgraphwithalledgesxysuchthatσ(x)0thereisaconstantc1(γ)>0suchthatthefollowingholds.
LetGbea(p,r)-pseudorandomgraphonnvertices,r≤√npwhere(γ)>0issomesucientlysmallconstantthatdependsonlyonγandnissucientlylarge.
LetGbeasubgraphofGwithatleast(1/2+γ)|E(G)|edges.
ThenGcontainsadirectedcycleoflengthatleastc1n.
Inotherwords,theabovecorollaryguaranteesthatthedeletionoflessthanhalfoftheedgesofapseudorandomdigraphleavesacycleoflinearlength.
Corollary6.
Thereexistsafunctionc2()withlim→0c2()=0suchthatthefollowingholds.
LetGbea(p,r)-pseudorandomgraphonnvertices,r≤√npwhere(γ)>0issomesucientlysmallconstantthatdependsonlyonγandnissucientlylarge.
LetGbeasubgraphofGwithatleast(1ε)|E(G)|edges.
ThenGcontainsadirectedcycleoflengthatleast(1c2)·n.
Here,weprovethatdeletingasucientlysmallfractionoftheedgesofapseudorandomdigraphleavesacycleoflengthcloseton.
Finally,weprovethefollowingmatchinglowerbound.
5Proposition7.
Fix0graphonnvertices,wherer=O(√np)andpn→∞.
ThereisasubgraphGwith(12+γ)|E|edgesthatdoesnotcontainanydirectedcycleoflengthatleast(1α+o(1))·n,whereαsatises2γ=1(1w(α))(α+w(α)).
OurTools.
OneofthemaintoolsweuseinthisworkisasparsedirectedvariantofSze-meredi'sregularitylemma(Lemma2.
1),thatwasstatedin[12].
Thisallowsustopartitionourgraphintoaconstantnumberofregularpairs,andessentiallytoreducetheproblemtondingalmostspanningpathsinregularpairs.
Tothisend,weuseasimpleyetpowerfullemmathatndsalmostspanningpathsinexpandinggraphs(Lemma2.
3).
Inourcase,aregularpairisabipartiteexpanderinbothdirections.
Theapproachisbasedonideasfrom[10,3,5].
Therestofthepaperisorganizedasfollows.
InSection2westatethesparsedirectedregularitylemma,andprovethatregularpairshaveanalmostspanningdirectedpath.
InSection3,wereducetheresilienceproblemindirectedgraphstoundirectedgraphs,andthenapplyideasfrom[11]andproveTheorem4.
InSection4weproveProposition7andshowthatourresultsareessentiallytight.
ThroughoutthepaperweassumethattheorderofG,denotedbyn,islargeenough.
Wedonottrytooptimizeconstantsandomitoorandceilingsignswheneverthesearenotcrucial.
2Theregularitylemmaforsparsedirectedgraphsandlongpathsinregularpairs2.
1TheregularitylemmaInthissectionwefollow[12]andstatearegularitylemmaforsparsedirectedgraphs.
Werstprovidesomenotation.
GivenadirectedgraphG=(V,E),foranypairofdisjointsetsofverticesU,W,weletEG(U,W)bethesetofedgesdirectedfromUtoW,andleteG(U,W)=|EG(U,W)|.
WesaythatGis(δ,D,p)-boundedifforanytwodisjointsetsU,Wsuchthat|U|,|W|≥δ|V|wehaveeG(U,W)≤Dp|U||W|.
TheedgedensityfromasetUtoasetWisdenedbyeG(U,W)|U||W|.
WesaythattwosetsUandWspanabipartitedirectedgraphofbi-densitypifithasedgedensityatleastpinbothdirections.
Alsodenethedirectedp-densityfromUtoWbydG,p(U,W)=eG(U,W)p|U||W|.
6WeomittheindexgraphGandwritedp(U,W)wheneverthebasegraphisclearfromthecontext.
For0graphGifforeveryUUandWWsuchthat|U|≥δ|U|and|W|≥δ|W|wehaveboth|dG,p(U,W)dG,p(U,W)|graphs,provedindependentlybyKohayakawaandbyR¨odl(see,e.
g.
,[15]).
In[12]thelemmaisstatedfororientedgraphs(wherenoantiparalleledgesareallowed),yettheresultcanbeeasilyadjustedtoourcase,whereantiparalleledgesareallowed.
Lemma2.
1(Lemma3in[12]).
Foranyrealnumberδ>0,anyintegerk0≥1andanyrealnumberD>1,thereexistconstantsη=η(δ,k0,D)andK=K(δ,k0,D)≥k0suchthatforany0graphGadmitsa(δ,k,p)-regularpartitionforsomek0≤k≤K.
2.
2EveryregularpaircontainsalongpathWenextprovethateveryregularpairofpositivebi-densitycontainsanalmostspanningpath.
Tothisend,werstshowatrivialexpansionpropertyofregularpairs,andthenusethispropertytoprovethedesiredresult.
Claim2.
2.
Let(U,W)bea(δ,p)-regularpairfor|U|=|W|withbi-densityatleast2δp,wherep>0.
ThenforeverytwosetsUUandWWsuchthat|U|≥δ|U|and|W|≥δ|W|thereisadirectededgefromUtoW.
Proof.
ByregularitywehaveeG(U,W)≥(dp(U,W)δ)p|U||W|≥(2δδ)p|U||W|=δp|U||W|>0.
Theclaimfollows.
Wenextshowthatabipartitedirectedgraphwithasimpleexpansionpropertycontainsalongdirectedpath.
Theprooffollowsideasfrom[10,3,5].
7Lemma2.
3.
LetH=(V1,V2,E),where|V1|=|V2|=t,beadirectedbipartitegraphthatsatisesthefollowingproperty:foreverytwosetsAV1,BV2ofsizek,thereisatleastoneedgefromAtoBandthereisatleastoneedgefromBtoA.
ThenHcontainsadirectedpathoflength2t4k+3.
Proof.
RecallthatDFS(DepthFirstSearch)isagraphsearchalgorithmthatvisitsalltheverticesofa(directedorundirected)graphGasfollows.
Itmaintainsthreesetsofvertices,lettingSbethesetofverticeswhichwehavecompletedexploring,Tbethesetofunvisitedvertices,andU=V(G)\(S∪T),wheretheverticesofUarekeptinastack(alastin,rstoutdatastructure).
ItisalsoassumedthatsomeorderσontheverticesofGisxed,andthealgorithmprioritizesverticesaccordingtoσ.
ThealgorithmstartswithS=,U=andT=V(G).
WhilethereisavertexinV(G)\S,ifUisnon-empty,letvbethelastvertexthatwasaddedtoU.
Ifvhasanout-neighboru∈T,thealgorithminsertsutoU.
Ifvdoesnothaveanout-neighborinTthenvispoppedoutfromUandismovedtoS.
IfUisempty,thealgorithmchoosesanarbitraryvertexfromTandpushesittoU.
Wenowproceedtotheproofofthelemma.
WeexecutetheDFSalgorithmforanarbitrarychosenorderσontheverticesofthegraphH.
WeletagainS,T,Ubethreesetsofverticesasdenedabove.
Atthebeginningofthealgorithm,alltheverticesareinT,andateachstepasinglevertexeithermovesfromTtoUorfromUtoS.
Attheendofthealgorithm,alltheverticesareinS.
Considerthepointduringtheexecutionofthealgorithmwhen|S|=|T|.
ObservecruciallythatalltheverticesinUformadirectedpath,andwehave||U∩V1||U∩V2||≤1.
Since|U|=2t|S||T|=2t2|S|iseven,wehaveinfact|U∩V1|=|U∩V2|.
Wegetthat|S|=|S∩V1|+|S∩V2|=|T∩V1|+|T∩V2|=|T|,and|V1\U|=|S∩V1|+|T∩V1|=|S∩V2|+|T∩V2|=|V2\U|.
Hence,wegetboth|S∩V2|=|T∩V1|,and|S∩V1|=|T∩V2|.
Assumewithoutlossofgeneralitythat|S∩V1|≥|S|/2≥|S∩V2|.
Then|S∩V1|≥t/2|U|/4andtherefore|T∩V2|≥t/2|U|/4.
ObservecruciallythattherearenoedgesfromStoT.
Bytheassumptionofthelemmaweconcludethat|S∩V1|=|T∩V2|≤k1andthereforewegett/2|U|/4≤k1andhence|U|≥2t4k+4.
ThusHcontainsadirectedpath|U|oflength2t4k+3,asdesired.
8Wethereforehavethefollowingcorollary.
Corollary2.
4.
Let(U,W)bea(δ,p)-regularpairwithbi-densityatleast2δpand|U|=|W|=t,p>0.
ThenthebipartitedirectedgraphbetweenUandWcontainsadirectedpathoflength(12δ)·2t+2thatstartsatU.
Proof.
ByClaim2.
2,thereisanedgeineachdirectionbetweeneverytwosetsofsizeδtinUandW.
ThereforeLemma2.
3impliestheexistenceofadirectedpathoflength(12δ)2t+3.
NotethatiftherstvertexinthepathisfromWwemayremoveit,thusgettingadirectedpathoflengthatleast(12δ)2t+2thatstartsatU.
3ProofofTheorem4Inthissectionweproveourmainresult.
Givenaconstantγ>0,weessentiallywanttoprovethateverysubgraphwitha(1/2+γ)-fractionoftheedgesofapseudorandomdirectedgraphcontainsalongdirectedcycle.
Letδ=δ(γ)beaconstantthatwewillxlater,K=K(δ,1/δ,1+δ)andη=η(δ,1/δ,1+δ)betheconstantsdenedbytheregularitylemma(Lemma2.
1).
LetG=(V,E)bea(p,r)-pseudorandomdirectedgraphwithr≤√np.
For≤δ·min{η,1/K}wehaver≤δ√np·min{η,1/K}.
LetA,BbetwosetsofverticesofsizeηninG.
Observethatrpn|A||B|≤δ√npηpη2n3=δη2n2p≤δη2n2=δ|A||B|.
Therefore,wegetthatGis(η,1+δ,p)-bounded.
GivenasubgraphG=(V,E)ofGthatcontains(1/2+γ)|E|edges,ourgoalistoshowthatGcontainsalongdirectedcycle.
Clearly,Gis(η,1+δ,p)-boundedaswell,andhencewecanapplythesparsedirectedregularitylemma(Lemma2.
1)toGandgetapartitionofVtoclustersV0,V1,Vm,where1/δ≤m≤K,|V0|≤δn,|V1|=|V2|Vm|=tandallbutatmostaδ-fractionofthepairs(Vi,Vj)are(δ,p)-regular.
Notethatn(1δ)m≤t≤nm.
WenextdeneanundirectedauxiliarygraphHontheclustersV1,Vm.
Withaslightabuseofnotation,wedenotetheverticesofHbyV1,V2,Vm.
TwoverticesViandVjareconnectedifthepair(Vi,Vj)is(δ,p)-regularandhasbi-densityatleast2δp.
SinceGis(p,r)-pseudorandomandr≤δ·√npK≤δ·√npm,wegetthatthep-densityofeverypair(Vi,Vj)inGisatleast1δandatmost1+δ.
ObservethatifViandVjarenotconnectedbyanedgeinH,oneofthefollowingmusthappen.
Thepair(Vi,Vj)isnotregular.
Either|EG(Vi,Vj)|2δtweconcludethatwecanconnectPbandP1throughavertexinVi2b+1,thusgettingapathoflengthatleast(b1)·(12δδ)2t=(1αo(1))|V(G)|.
Theorem4follows.
4LowerboundsLetG=(V,E)beadirectedgraph.
Recallthatbyxingapermutationσonthevertices,wecanpartitiontheedgesofGintotwoacyclicsetsasfollows.
Therstsetcontainsalldirectededgesxywhereσ(x)>σ(y),andthesecondsetcontainsalldirectededgesxywhereσ(y)>σ(x).
Therefore,theglobalresilienceofeverydirectedgraphwithrespecttothepropertyofhavingdirectedcyclesisatmost1/2.
Hereweextendthisideaandshowthatourmainresultisasymptoticallytight.
ProofofProposition7.
WeshowthatthereisasubgraphGwitha(1/2+γ)-fractionoftheedges,whoselongestdirectedcycleisoflengthatmost(1α+o(1))n.
Ourapproachfollows[11].
RecallthatGis(p,r)-pseudorandomwithr≤√npandpn→∞.
WerstclaimthatforeverytwodisjointsetsA,Bofsize(n),thenumberofedgesfromAtoBisp|A||B|(1+o(1)).
Indeed,let|A|=anand|B|=bn,andsupposethatagraphwithalledgesfromVitoVj,for1≤igraphswithrespecttotheprop-ertyofhavingalongdirectedcycle.
Wegavematchinglowerandupperbounds,andourproofessentiallyreducedourproblemtothecaseofundirectedgraphs.
Avarietyofquestionsregardingtheresilienceofdirectedgraphscanbeasked.
Afew,somewhatarbitraryexamplesaretheproblemoflocalresiliencewithrespecttohavingalongdirectedcycle,theresiliencewithrespecttothepropertyofhavingsomexeddirectedgraph.
AnotherinterestingproblemistheresiliencewithrespecttoHamilitonicity,whichinthedensecaseissettledin[13].
Inthisworkweconsideredsubgraphswitha(1/2+γ)-fractionoftheedges,andobservedthateverydirectedgraphcontainsanacyclicsubgraphwitha1/2-fractionoftheedges.
In[5],theauthorsprovedthateverytwo-coloringoftheedgesofapseudorandomdigraphcontainsarelativelylongmonochromaticpath.
Thatis,insteadofprovingthatalargesubgraphhasacertainproperty,itisprovedthateverypartitionoftheedgesofthegraphhasacertainproperty.
Itwillbeinterestingtogivesuchresultsforotherpropertiesofdirectedgraphs.
12References[1]N.
Alon,M.
Capalbo,Y.
Kohayakawa,V.
R¨odl,A.
RucinskiandE.
Szemer`edi,Univer-salityandTolerance,Proc.
41IEEEFOCS,IEEE(2000),14–21.
[2]N.
AlonandB.
Sudakov,Increasingthechromaticnumberofarandomgraph,JournalofCombinatorics1(2010),345–356.
[3]J.
Bang-JensenandS.
Brandt,ExpansionandHamiltonicityinDigraphs,manuscript.
[4]J.
Balogh,B.
CsabaandW.
Samotij,Localresilienceofalmostspanningtreesinrandomgraphs,RandomStructuresandAlgorithms38(2011),121–139.
[5]I.
Ben-Eliezer,M.
KrivelevichandB.
Sudakov,ThesizeRamseynumberofadirectedpath,submitted.
[6]S.
Ben-Shimon,M.
KrivelevichandB.
Sudakov,LocalresilienceandHamiltonicityMaker-Breakergamesinrandomregulargraphs,Combinatorics,ProbabilityandCom-puting20(2011),173–211.
[7]J.
C.
BermondandC.
Thomassen,Cyclesindigraphs–Asurvey,JournalofGraphTheory,5(1981),1–43,.
[8]B.
Bollobas,Extremalgraphtheory,Dover2004.
[9]J.
B¨ottcher,Y.
Kohayakawa,andA.
Taraz,Almostspanningsubgraphsofrandomgraphsafteradversarialedgeremoval,ElectronicNotesinDiscreteMathematics35(2009)335-340.
[10]S.
Brandt,H.
Broersma,R.
DiestelandM.
Kriesell,Globalconnectivityandexpansion:longcyclesinf-connectedgraphs,Combinatorica26(2006),17–36.
[11]D.
DellamonicaJr.
,Y.
Kohayakawa,M.
MarciniszynandA.
Steger,Ontheresilienceoflongcyclesinrandomgraphs,ElectronicJournalofCombinatorics15(2008),R32.
[12]J.
DonadelliandY.
Kohayakawa,AdensityresultforrandomsparseorientedgraphsanditsrelationtoaconjectureofWoodall,ElectronicJournalofCombinatorics9(2002),no.
1,R45.
[13]D.
Hefetz,A.
StegerandB.
Sudakov,inpreparation.
[14]H.
Huang,C.
LeeandB.
Sudakov,Bandwidththeoremforsparsegraphs,J.
Combina-torialTheorySer.
B,toappear.
[15]Y.
Kohayakawa,Szemeredi'sregularitylemmaforsparsegraphs,FoundationsofComputationalMathematics(Berlin,Heidelberg)(F.
CuckerandM.
Shub,eds.
),Springer-Verlag,January1997,pp.
216–230.
13[16]M.
Krivelevich,C.
LeeandB.
Sudakov,Resilientpancyclicityofrandomandpseudo-randomgraphs,SIAMJournalonDiscreteMathematics,24(2010),1–16.
[17]M.
Lewin,Onmaximalcircuitsindirectedgraphs,JournalofCombinatorialTheorySer.
B,18(1975),175–179.
[18]B.
SudakovandV.
Vu,Localresilienceofgraphs,RandomStructuresandAlgorithms33(2008),409–433.
[19]A.
Thomason,Pseudo-randomgraphs,2ndInternationalSeminaronRandomGraphsandProbabilisticMethodsinCombinatorics144(1985),307–331.
[20]D.
R.
Woodall,Sucientconditionsforcircuitsingraphs,Proc.
LondonMath.
Soc.
24(1972),739–755.
14