Citation

## Material Information

Title:
On r-Percolation in dense draphs
Creator:
Graber, Catrina
Place of Publication:
Denver, CO
Publisher:
Publication Date:
Language:
English

## Thesis/Dissertation Information

Degree:
Master's ( Master of science)
Degree Grantor:
Degree Divisions:
Department of Mathematical and Statistical Sciences, CU Denver
Degree Disciplines:
Applied mathematics
Committee Chair:
Pfender, Florian
Committee Members:
Ferrara, Michael
Hartke, Stephen

## Notes

Abstract:
Bootstrap percolation is a form of cellular automata where each vertex in a graph G starts in one of two states: active or dormant. Once a vertex becomes active, it remains that way. At each stage a dormant vertex v becomes active if it is adjacent to r active vertices where r is an integer. We say a graph r-percolates from the initial set A of active vertices if every vertex becomes active after some number of steps. In this thesis we discuss the history of bootstrap percolation and its applications. We then give a sharp density condition that ensure a graph on n vertices will r-percolate from any given initial active set of size r.

## Record Information

Source Institution:
Holding Location:
Auraria Library
Rights Management:
Copyright Catrina Graber. Permission granted to University of Colorado Denver to digitize and display this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.

Full Text

PAGE 1

PAGE 2

ThisthesisfortheMasterofSciencedegreeby CatrinaGraber hasbeenapprovedforthe AppliedMathematicsProgram by FlorianPfender,Chair MichaelFerrara StephenHartke Date:28July2018 ii

PAGE 3

Graber,CatrinaM.S.,AppliedMathematicsProgram On r -PercolationinDenseGraphs ThesisdirectedbyAssociateProfessorFlorianPfender ABSTRACT Bootstrappercolationisaformofcellularautomatawhereeachvertexinagraph G startsinoneoftwo states:activeordormant.Onceavertexbecomesactive,itremainsthatway.Ateachstageadormant vertex v becomesactiveifitisadjacentto r activeverticeswhere r isaninteger.Wesayagraph r -percolates fromtheinitialset A ofactiveverticesifeveryvertexbecomesactiveaftersomenumberofsteps.Inthis thesiswediscussthehistoryofbootstrappercolationanditsapplications.Wethengiveasharpdensity conditionthatensureagraphon n verticeswill r -percolatefromanygiveninitialactivesetofsize r . Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:FlorianPfender iii

PAGE 4

TABLEOFCONTENTS CHAPTER I.INTRODUCTION 1 CELLULARAUTOMATA2 BOOTSTRAPPERCOLATION3 APPLICATIONS 4 II.COMPLEXITYRESULTS7 PROBABILISTICRESULTS8 OPTIMIZATIONRESULTS9 DENSITY-BASEDRESULTS9 III.OURRESULTS 13 IV.OPENQUESTIONS20 REFERENCES 21 iv

PAGE 5

CHAPTERI INTRODUCTION Agraph G isadiscretestructureconsistingofasetofvertices V G andasetofedges E G theelements ofwhichare2-elementsubsetsof V G .Avertexthatisasubsetofanedgeissaidtobe incident tothat edgeandtwoverticesareconsideredtobe adjacent iftheyareincidenttothesameedge.Thevertices adjacenttoavertex v areconsidered neighbors of v .Inthisthesiswewillonlyconsider simplegraphs ,in whicheverypairofverticesareconnectedbyatmostoneedgeandeveryedgeisincidenttoexactlytwo distinctvertices.Avertexthathasnoneighborsissaidtobean isolated vertex.The degree d v ofavertex v isequaltothenumberofverticesadjacentto v .Let G denotetheminimumdegreeoverallthevertices in G ,andlet 2 G denotetheminimumdegreesumofapairofnonadjacentverticesin G , 2 G =min f d u + d v : uv 62 E G g : The degreesequence ofagraph G isamonotonicnonincreasingsequenceofthedegreesoftheverticesin G . A clique isasetofverticesthatareallpairwiseadjacent.A path isasetofdistinctvertices v 0 ;v 1 ;:::;v k where v i isadjacentto v i +1 forall0 i
PAGE 6

numberofcolorsnecessarytocoloreveryedgesuchthatnotwoincidentedgeshavethesamecolorwecan knowthefewestnumberoftimeslotsneededsothateveryonegetsachancetointerviewforeverycompany theywishto.Thedierentcolorswouldrepresentthedierenttimeslots. AgraphmakesanaturalmodelformoleculesinChemistrywheretheverticesrepresenttheatomsand theedgesrepresentthecovalentbonds.See[3],[7],[27],and[38]formorechemistryrelatedapplications ofgraphtheory.Agraphalsomakesforawonderfulmodelofabrainwhenscientistsarestudyinghow dierentconnectionsorlackthereofaecthowthebraincommunicateswiththerestofthebodysee[1], [10],[29],and[39]. CELLULARAUTOMATA Acellularautomatonconsistsofauniformgridofcells,eachinoneofanitesetofstates.Everymodelhas asetofrulesthatdeterminethestateacellisin,whichisdeterminedlocallybyitsneighbors,andeachcell isassumedtohaveaniteamountofneighbors.Thesimplestcellularautomatonmodelcanbethoughtof ashavingcellsthatareeitheractive"ordormant". Forinstanceinarectangular,2-dimensionalgrid,themostcommonlyconsideredneighborhoodsarethe vonNeumannneighborhood,whichconsistsofthefourcellsthatshareasidewiththecentercellseeFigure 1a,andtheMooreneighborhood,whichconsistsoftheeightcellsimmediatelyadjacenttothecentercell seeFigure1b.Everycellisupdatedsimultaneouslyateachstage. a b Figure1: ThevonNeumannNeighborhoodandtheMooreNeighborhood ForexampleinConway'sGameofLife[24],adormantcellbecomesactiveifithasexactlythreeactive neighborsusingtheMooreneighborhoodandbecomesdormantifithasanythingotherthantwoorthree activeneighbors.LikeConway'sGameofLife,thevonNeumanncellularautomaton[11]alsousesa2Dgrid butithas29distinctpossiblestatesandmanymorerulesthanLife. A reversible cellularautomatonisacellularautomatoninwhicheverycongurationhasexactlyone 2

PAGE 7

possiblepastconguration.Conway'sGameofLifeisnotreversiblebecausemanydierentcongurations leadtothesamecongurations.ForexampleinFigure2,therearetwodistinctcongurations a and b thatbothresultinthesamecongurationinthenextstep. a b Figure2: HerearetwodierentcongurationsthathavethesamefollowingcongurationinLife. Whilecellularautomataoriginallyusedonlygrids,wecanmodelitwithotherdiscretestructuressuch asgraphs.Inagraph,acellwouldberepresentedasavertexandthecell'sneighborhoodwouldbethe correspondingvertex'sneighborhoodseeFigure3.Onethingthatmakesgraphsdierentfromgrids,is thateachvertexcellcanhaveadierentnumberofneighbors. a b Figure3: ThevonNeumannNeighborhoodaandtheMooreNeighborhoodbasGraphs BOOTSTRAPPERCOLATION Inthissection,weintroduce bootstrappercolation ,asimplecellularautomatonthathasreceivedconsiderableattentionintheliteratureandthecentralfocusofthisthesis.Bootstrappercolationwasoriginally posedin1979asanewkindofpercolationproblembyChalupa,LeathandReich[13].Inthissetting,cells existinoneoftwostates:activeordormant.LetGbeagraphandlet A V G bethesetofinitial activevertices.Theverticesin G thatarenotin A areconsidered dormant initially.Adormantvertex becomesactiveifitisadjacenttoatleast r activeverticeswhere r isagivenintegergreaterthanzero.In theirpaperChalupa,LeathandReichstudiedbootstrappercolationonaBetheLatticewhichisaninnite connectedcycle-freegraphwhereeachvertexisconnectedto z neighborsseeFigure4.Theinitialactive 3

PAGE 8

setwaschosenrandomlyandactivatedverticescouldbecomeinactive.Wedidnotallowverticestobecome inactiveinourresearch.Agraph G issaidto r -percolate from A ifaftersomenitenumberofsteps,every vertexin G isactive.If Gr -percolatesfrom A ,then A isconsidereda contagiousset .Let m G;r denote theminimumsizeofan r )]TJ/F8 9.9626 Tf 7.748 0 Td [(contagiousset. Figure4:ThecenteroftheBetheLatticewith z =4 Foranexampleofbootstrappercolation,wewillndtheminimumsizeofa2-contagioussetforathe 3-dimensionalhypercube Q 3 .InFigure5wecanseethereexistsaninitialactivesetofsizethreefrom which Q 3 2-percolatesin3steps.Figure6depictsthreedistinctinitialactivesetsofsizetwothat,upto symmetry,aretheonlypossibleinitialactivesetsofsizetwo.Caseadoesn'tpercolateanyfartherafter onestepandcasesbandcdon'tpercolateatall.Thus m Q 3 ; 2=2.Noticethatitisimpossiblefora graph G to r -percolatefromasetofsize r if G isnotconnectedandthateveryconnectedgraph1-percolates fromanyinitialset A .Goingforward,wethereforeassumethateverygraphisconnectedandthat r 2. Figure5: Q 3 does2-percolatefromsomeinitialactivesetofsize3 APPLICATIONS Bootstrappercolationcanbeusedtomodelepidemicssuchasdiseasesspreadingthroughoutapopulation. Imagineanelementaryschoolwheresomesubsetofchildrenhavetheu.Howmanychildrenwouldhaveto havetheuinorderfortheentireschooltogetit?Howquicklymightitspread?Wecouldusereversible bootstrappercolationtohelpusanswerthesequestions.Theverticesofthegraphwouldbethestudents. Therewouldbeanedgebetweentwostudentsiftheyinteractedoftene.g.satneareachotherinclass, 4

PAGE 9

PAGE 10

PAGE 11

CHAPTERII COMPLEXITYRESULTS Withtheriseofcomputers,mathematicianshavefoundalgorithmstobehelpfulinprovingtheirconjectures.TherstmajortheoremtouseacomputerprograminitsproofwastheFourColorTheorem in1976[2].Noteveryalgorithmisthesamehowever;someareveryfastwhileothersarequiteslow.In theareaof complexity aproblemisconsidered P ifthereexistsadeterministicalgorithmthatcannda solutiontheansweris'yes'or'no'inapolynomialnumberofsteps.Inotherwords,aproblemis P if thesolutioncanbefoundinpolynomialtime.Forthesepercolationproblems,theinputofthispolynomial isthesizeofthegraph.Notonlydoweneedthealgorithmtogiveusasolution,bewealsoneedtobe abletoverifythesolution.Theclassofdeterministicalgorithmsthatcanbeveriedinpolynomialtimeif thesolutionisayesareconsidered NP .Thatistosay,afteranalgorithmprovesthequestionispossible, theanswercanbecheckedforaccuracyinpolynomialtime.Anexampleofaproblemthatisconsidered NP istestingwhetherornotagraph G isHamiltonian.Analgorithmthatproves G isHamiltonianwould returnaHamiltonianpathin G .Anotheralgorithmcanchecktheaccuracyofthatbyverifyingthatthe pathisindeedHamiltonian.Notethat P isasubsetof NP .Whetherornot P isa proper subsetof NP hasyettobeprovedonewayortheothersee[9],[21],and[22].Themostdicultproblemsin NP are considered NPcompleteproblems.Ifany NP -completeproblemcanbesolvedinpolynomialtime,thenall theproblemsin NP canbesolvedinpolynomialtime. In2009DreyerandRoberts[19]provedthatdetermining m G;r is NP -completefor r 3.Theydid notgureoutthecomplexityforwhen r =2.Fiveyearslater,Kyncl,Lidicky,andVyskocil[32]provedthat when G 4,determining m G; 2is NP -complete.Theyalsofoundthat m G; 2canbedeterminedin polynomialtimeif G 3. Wealsouse big O notation totalkabouthowlonganalgorithmtakestorunwhichwerefertoas time complexity .Let f and g befunctionssuchthat g x isstrictlypositiveforalllargeenoughvaluesof x .If thereexistsapositiverealnumber M andarealnumber N suchthat j f x j Mg x forall x N .For example,analgorithmwithtimecomplexity O n runsinlineartime,analgorithmwithtimecomplexity O n a where a isapositiveconstantgreaterthan1runsinpolynomialtime,andanalgorithmwithtime complexity O log n runsinlogarithmictime.Theinput n dependsontheproblembeingstudied.For bootstrappercolationingraphtheorytheinputistypicallythesizeofthegraphbeinglookedat.Some algorithmsdonotdependonthesizeoftheinputatall.Thesealgorithmsrunin O timeorconstanttime. Thereisalso littleonotation whichisastrongerstatementthan O n inthatfor every positiveconstant M thereexistsand N suchthat j f x j Mg x forall x N .Ofcoursetherearemanymoretimecomplexities 7

PAGE 12

thanthefewwehavementionedandnotallofthemareassimple.Forinstancetheispolylogarithmictime or O log n k where k isaconstantwhichisapolynomialfunctionoftheform a 0 + a 1 log n + a 2 log n 2 + ::: + a k )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 log n k )]TJ/F7 6.9738 Tf 6.226 0 Td [(1 + a k log n k : Thereisalsoquasi-polynomialtimewhichisn'tasfastaspolynomialtimebutisfasterthanexponentialtime. Inhispaper,Riedl[36]introducedsomealgorithmsthatcouldcomputethelargestminimal2-percolating setforatreeandfor r 2,thesmallestminimal r -percolatingsetforatreewith l verticesofdegreeless than r .Thesealgorithmsruninpolynomialtime.Healsoprovedthatthesizeoftheminimal r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolating setsforsuchagraphisatleast r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n +1 r andatmost rn + l r +1 . In2009,Chen[14]provedthattheminimumsizeofaninitial2-percolatingsetcannotbeapproximated withinapolylogarithmicfactorunless NP hasquasi-polynomialtimealgorithms.If P = NP ,thenallofthe problemsin NP canbesolvedandveriedinpolynomialtime.Currentlyallofthebest-knownalgorithmsfor NP -completeproblemstakeexponentialtime,anditisconjecturedthattherearenoquasi-polynomialtime algorithmsfor NP -completeproblems.Itisentirelypossiblethat NP hasquasi-polynomialtimealgorithms. PROBABILISTICRESULTS Sofarwehaveonlytalkedaboutcaseswherewegottopicktheinitialstartingset.Howeverthereisan entireareaofstudydedicatedtostudyingthe randomgraph G n;p .Therandomgraphisformedbystarting with n isolatedverticesandeverypossibleedgeisaddedwithprobability p .Sometimestheedgesareadded independently.Studyingtherandomgraphisusefulasitanswersquestionsfortheaveragegraphon n vertices.Severalresearchershavestudiedbootstrappercolationontherandomgraph.In[30],theystudied thesizeofthenalactivesetontherandomgraph G n;p .Theyfoundthatthesizeofthenalactiveset iseither n )]TJ/F11 9.9626 Tf 10.634 0 Td [(o n or o n .Feige,Krivelevich,andReichman[20]setouttondtheminimalsizeofan r -percolatingonthebinomialrandomgraph.Theyprovedthat m G;r = n d r r )]TJ/F7 6.9738 Tf 6.226 0 Td [(1 log d ! withhighprobabilityfor1 d n loglog n log 2 n r )]TJ/F6 4.9813 Tf 5.397 0 Td [(1 r . Wecanalsostudytheprobability p n thatagraph r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolatesfromanuncertaininitialconguration. Givenagraph G ,wewanttoknowhowlikelyitisfor G to r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolateifeachvertexis p likelytobein theinitialactiveset.BaloghandBollbas[4]studiedbootstrappercolationonthe n -dimensionalhypercube. Theyletavertexbeactivewithprobability p anddormantwithprobability1 )]TJ/F11 9.9626 Tf 10.076 0 Td [(p andprovedthatthere 8

PAGE 13

arepositiveconstants c 1
PAGE 14

Theyprovetheirboundbycountingtheminimumnumberofedgescomingoutoftheinfectedsetandusing thepigeonholeprincipletoarguethatatleastoneofthedormantverticeshasrinfectedneighbors.In2017 Gunderson[26]studiedtheproblemforlarge n andprovedthatforany r 4and n sucientlylargeif G isagraphon n verticeswith G b n= 2 c + r )]TJ/F8 9.9626 Tf 9.913 0 Td [(3,then m G;r = r .Shealsoprovedthatany n )]TJ/F8 9.9626 Tf 7.749 0 Td [(vertex graphwhere n 30with G b n= 2 c +1hasaminimum3-contagioussetofsize3. Ore[33]provedthateverygraph G oforder n 3with 2 G n isHamiltonian.Freund,Poloczek, andReichman[23]showedthatOre'sconditionissucienttoguaranteeagraph G 2-percolatesfroman initialactivesetofsize2. Theorem0.1. If G isagraphoforder n 2 and 2 n ,then m G; 2=2 . Chvatalprovedin[15]thatagraph G on n 3verticesisHamiltonianifthedegreesequenceof G d 1 ;d 2 ;:::;d n satisesChvatal'sconditionwhichisthefollowing: d i i +1or d n )]TJ/F10 6.9738 Tf 6.226 0 Td [(i n )]TJ/F11 9.9626 Tf 9.962 0 Td [(i for1 i n 2 : In[17],M.Dairyko,etal.proved m G; 2=2foraconditionsimilartoChvatal'sseeTheorem0.2.Let P k bethepathon k verticesand C k bethecycleon k vertices. Theorem0.2. Let G beagraphwithdegreesequence d 1 ;d 2 ;:::;d n thatsatisesthefollowing: d i i +1 or d n )]TJ/F10 6.9738 Tf 6.227 0 Td [(i n )]TJ/F11 9.9626 Tf 9.963 0 Td [(i )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 for 1 i n 2 : Thenoneofthesefourcasesistrue. G isdisconnected, G containsexactlytwoverticesofdegreeoneand G 62f P 2 ;P 3 g , G = C 5 ,or m G; 2=2 : Asnotedin[17],therstthreecasesin0.2donothavedegreesequencesthatsatisfyChvatal'scondition. Thusagraph G thatsatisesChvatal'sconditionhasaminimum2-percolatingsetofsize2. However,Hamiltonicityisnotenoughtoguaranteeagraph G hasa2-percolatingsetofsize2.For example,acycleon n verticesisHamiltonianyetrequireseveryothervertextobeintheinitialactiveset to2-percolate. 10

PAGE 15

X Figure7:TheFamily X from[17] G 0 G 1 G 2 G 3 Figure8:ExamplesofGraphsintheInniteFamilies G 0 , G 1 , G 2 , G 3 for n =10from[17]usedwithpermission In2017,M.Dairyko,etal.[17]improvedonTheorem0.1.Theyprovedthatagraph G oforder n 2 with 2 G n )]TJ/F8 9.9626 Tf 10.053 0 Td [(2hasa2-percolatingsetofsize2forallbutafourinnitefamiliesofgraphs G 0 , G 1 , G 2 , G 3 andonenitefamily X . Theorem0.3. Let G beagraphoforder n 2 suchthat G isnotin G 0 ; G 1 ; G 2 ; G 3 or X .If 2 G n )]TJ/F8 9.9626 Tf 10.115 0 Td [(2 , then m G; 2=2 . Thegraphsin X areshowninFigure7andexamplesofeachoftheinnitefamilieson10verticesare showninFigure8.Allgraphsmadeupoftwodisjointnon-emptycliques X and Y ofthesameordierent sizesmakeupthefamily G 0 .Let x;x 0 2 X and y;y 0 2 Y .Thegraphsin G 1 aremadeupofgraphsfrom G 0 withtheaddededge xy .Thegraphsin G 2 aremadeupofgraphsfrom G 0 withtheedges xx 0 and yy 0 removedandtheedges xy and x 0 y 0 added.Thegraphsin G 3 aremadeupofgraphsfrom G 0 withtheadded edges xy and xy 0 andtheedge yy 0 removed.Noneofthesetypesofgraphwill2-percolatefromaninitial 11

PAGE 16

activesetofsize2.Inallfourcasesifbothverticesareareononeside,eitherthereisnowaytomakea vertexactiveontheothersideoratmostonevertexontheothersidebecomesactive.Ifthereisoneon eachside,atmostonevertex v canbeadjacenttobothofthem.Ifthereissuchavertex v ,thentheside that v isonwillpercolatebuttheothersidewillnot. 12

PAGE 17

CHAPTERIII OURRESULTS Thepaperswehavediscussedsofarhavegivenusgraphpropertiesthatguaranteeagraph r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolates from some initialactivesetofagivensize.Hereweinvestigatewhatpropertiesofagraph G guaranteed that G would r -percolatefrom every initialsetofsize r .Therstgraphpropertywelookedatwasminimum degree.SinceFreund,Poloczek,andReichmanshowed[23]thatforagraph G on n verticesand r 2, G r )]TJ/F7 6.9738 Tf 6.226 0 Td [(1 r n guaranteed Gr )]TJ/F8 9.9626 Tf 7.748 0 Td [(percolatedfromsomeinitialactivesetofsize r ,welookedtoseeifthatwas enoughto r -percolatefromeveryinitialsetofsize r .Howevertherearegraphswith G = r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r n thatdo not r -percolatefrom every initialactivesetofsize r seeFigure9.Wefoundthatjustaslightincreasein minimumdegreewasenoughtoensureagraph r -percolatesfromanyinitialactivesetofsize r . Theorem0.4. If r 2 and G isagraphoforder n suchthat G r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n +1 r ,then Gr -percolatesfrom anyinitialactivesetofsize r . Proof. Let G beagraphon n verticeswhere G r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n +1 r .Assumeforcontradictionthatthereissome set A ofsize r that G doesnot r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolatefrom.Because G doesnot r -percolate,thereisastepwhereno moreverticescanbecomeactive.Let B bethesetofactiveverticesand C bethesetofinactivevertices atthisstep.Noticethat j B j r since j A j = r .Becauseeachvertexin C canbeadjacenttoatmost r )]TJ/F8 9.9626 Tf 10.072 0 Td [(1 verticesin B ,theremustbeatleast G )]TJ/F8 9.9626 Tf 10.294 0 Td [( r )]TJ/F8 9.9626 Tf 10.294 0 Td [(1+1verticesin C otherwiseavertexin C wouldhave r neighborsin B andwouldthusbecomeactive.Let E bethenumberofedgesbetween B and C .The minimumnumberofedgesfromavertexin B to C is G )]TJ/F8 9.9626 Tf 10.335 0 Td [( j B j)]TJ/F8 9.9626 Tf 15.688 0 Td [(1.Thusthenumberofedgesgoing from B to C isatleast j B j [ G )]TJ/F8 9.9626 Tf 10.063 0 Td [( j B j)]TJ/F8 9.9626 Tf 15.145 0 Td [(1]and E j B j [ G )]TJ/F8 9.9626 Tf 10.064 0 Td [( j B j)]TJ/F8 9.9626 Tf 15.145 0 Td [(1].Because G doesnotpercolate anyfarther,avertexin C canhaveatmost r )]TJ/F8 9.9626 Tf 10.036 0 Td [(1neighborsin B .Thusthenumberofedgesgoingfrom C to B isatmost j C j r )]TJ/F8 9.9626 Tf 9.629 0 Td [(1and E j C j r )]TJ/F8 9.9626 Tf 9.628 0 Td [(1.Therefore j B j [ G )]TJ/F8 9.9626 Tf 9.628 0 Td [( j B j)]TJ/F8 9.9626 Tf 14.275 0 Td [(1]mustbelessthanorequalto j C j r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1. 13

PAGE 18

j C j r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 j B j [ G )]TJ/F8 9.9626 Tf 9.963 0 Td [( j B j)]TJ/F8 9.9626 Tf 14.944 0 Td [(1] j C j r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 n )-222(j C j [ G )]TJ/F8 9.9626 Tf 9.962 0 Td [( n )-222(j c j )]TJ/F8 9.9626 Tf 9.963 0 Td [(1] j C j r )-222(j C j n )-222(j C j [ G )]TJ/F11 9.9626 Tf 9.962 0 Td [(n + j C j +1] j C j r )-222(j C j n )-222(j C j G )]TJ/F11 9.9626 Tf 9.963 0 Td [(n 2 +2 n j C j + n )-222(j C j 2 )-222(j C j j C j r n )-222(j C j rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +1 r )]TJ/F11 9.9626 Tf 9.962 0 Td [(n 2 +2 n j C j + n )-222(j C j 2 0 )]TJ/F11 9.9626 Tf 19.46 6.74 Td [(n 2 r + n r )-222(j C j n + j C j n r )]TJ 11.158 6.74 Td [(j C j r + n j C j + n )-222(j C j 2 )-222(j C j r 0 )]TJ/F11 9.9626 Tf 18.264 0 Td [(n 2 + n + j C j n )-222(j C j + rn j C j + rn )-222(j C j 2 r )-222(j C j r 2 0 )]TJ/F11 9.9626 Tf 18.264 0 Td [(r j C j 2 + n )]TJ/F8 9.9626 Tf 9.962 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 j C j)]TJ/F11 9.9626 Tf 14.944 0 Td [(n 2 + n + rn Let T = )]TJ/F11 9.9626 Tf 7.749 0 Td [(r j C j 2 + j C j n )]TJ/F8 9.9626 Tf 9.902 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.902 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.902 0 Td [(n 2 + n + rn .Noticethatbyxingallthevariablesexcept j C j , T isaconcavedownparabolasoweonlyneedtochecktheminimumandmaximumvaluesfor j C j .Let's startwiththemaximum.Weknow B hastocontainatleast r verticessothelargest j C j couldbeis n )]TJ/F11 9.9626 Tf 9.962 0 Td [(r . 0 )]TJ/F11 9.9626 Tf 18.265 0 Td [(r j C j 2 + j C j n )]TJ/F8 9.9626 Tf 9.963 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.962 0 Td [(n 2 + n + rn )]TJ/F11 9.9626 Tf 18.265 0 Td [(r n )]TJ/F11 9.9626 Tf 9.962 0 Td [(r 2 + n )]TJ/F11 9.9626 Tf 9.963 0 Td [(r n )]TJ/F8 9.9626 Tf 9.962 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n 2 + n + rn = )]TJ/F11 9.9626 Tf 7.749 0 Td [(rn 2 +2 r 2 n )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 3 + n 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n + rn 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 n )]TJ/F11 9.9626 Tf 9.963 0 Td [(rn + r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 n + r 3 )]TJ/F11 9.9626 Tf 9.962 0 Td [(n 2 + n + rn = r Butweknowthat r isatleast2,sothisisacontradiction. Nowlet'slookattheminimumvalueof j C j .Aswestatedbefore,theremustbeatleast G )]TJ/F8 9.9626 Tf 8.247 0 Td [( r )]TJ/F8 9.9626 Tf 8.247 0 Td [(1+1= rn )]TJ/F10 6.9738 Tf 6.227 0 Td [(n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r +2verticesin C . 14

PAGE 19

0 )]TJ/F11 9.9626 Tf 18.264 0 Td [(r j C j 2 + j C j n )]TJ/F8 9.9626 Tf 9.962 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n 2 + n + rn )]TJ/F11 9.9626 Tf 18.264 0 Td [(r rn )]TJ/F11 9.9626 Tf 9.962 0 Td [(n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r +2 2 + rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r +2 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.962 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n 2 + n + rn = )]TJ/F11 9.9626 Tf 7.748 0 Td [(r 2 rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +1 r )]TJ/F11 9.9626 Tf 9.962 0 Td [(r +2 2 + r rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r +2 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.962 0 Td [(rn 2 + rn + r 2 n = )]TJ/F8 9.9626 Tf 7.748 0 Td [( rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +1 )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 +2 r 2 + rn )]TJ/F11 9.9626 Tf 9.962 0 Td [(n +1 )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 +2 r n )]TJ/F8 9.9626 Tf 9.963 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(r 2 )]TJ/F11 9.9626 Tf 9.962 0 Td [(rn 2 + rn + r 2 n = )]TJ/F8 9.9626 Tf 7.748 0 Td [(2 n 2 + rn 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(3 r 2 n +5 rn +4 n +2 r 3 )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(6 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 Let M = r )]TJ/F8 9.9626 Tf 9.537 0 Td [(2 n 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(3 r 2 +5 r +4 n +2 r 3 )]TJ/F8 9.9626 Tf 9.537 0 Td [(2 r 2 )]TJ/F8 9.9626 Tf 9.537 0 Td [(6 r )]TJ/F8 9.9626 Tf 9.537 0 Td [(2andnotethat dM dn = r )]TJ/F8 9.9626 Tf 9.537 0 Td [(4 n )]TJ/F8 9.9626 Tf 9.537 0 Td [(3 r 2 +5 r +4. Ifwecanshowthat dM dn > 0,itwouldbesucienttocheckthesmallestpossiblevaluefor n .Notethatthis derivativeisdecreasingin r ,sosubstitutingthelargestpossiblevaluefor r givesusthesmallestpossible valueforthederivative.Rememberthat j B j r and j B j = n )-222(j C j = n )]TJ/F8 9.9626 Tf 9.963 0 Td [( r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r +2. n )]TJ/F1 9.9626 Tf 9.963 14.048 Td [( r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(r +2 r n )]TJ/F11 9.9626 Tf 11.158 6.74 Td [(rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +1 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(2 0 rn )]TJ/F11 9.9626 Tf 9.963 0 Td [(rn + n )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r 0 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 2 r Nowweplug n )]TJ/F7 6.9738 Tf 6.226 0 Td [(1 2 infor r in dM dn toshowthat dM dn > 0. r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(3 r 2 +5 r +4 2 n )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 n )]TJ/F8 9.9626 Tf 9.962 0 Td [(3 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 2 2 +5 n )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 2 +4 = n )]TJ/F8 9.9626 Tf 9.962 0 Td [(5 n )]TJ/F8 9.9626 Tf 11.158 6.74 Td [(3 n 2 4 )]TJ/F8 9.9626 Tf 11.158 6.74 Td [(3 n 2 + 3 4 + 5 n 2 )]TJ/F8 9.9626 Tf 11.158 6.74 Td [(5 2 +4 = n 2 4 )]TJ/F11 9.9626 Tf 9.962 0 Td [(n + 3 4 Therootsofthisconcave-upparabolaare n =1 ; 3.Therefore dM dn > 0for n> 3.Notethat n )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 2 r implies that n 2 r +1andrememberthat r 2.Thusweareonlyconcernedwith n 5.Nowwecanplugthe 15

PAGE 20

smallest n valueasafunctionof r . r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 n 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(3 r 2 +5 r +4 n +2 r 3 )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(6 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r +1 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(3 r 2 +5 r +4 r +1+2 r 3 )]TJ/F8 9.9626 Tf 9.962 0 Td [(2 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(6 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(2 = r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r 2 +4 r +1 )]TJ/F8 9.9626 Tf 9.962 0 Td [(6 r 3 +10 r 2 +8 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(3 r 2 +5 r +4+2 r 3 )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r 2 )]TJ/F8 9.9626 Tf 9.962 0 Td [(6 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 =4 r 3 +4 r 2 + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(8 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(8 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 r 3 +5 r 2 +7 r +2 = r 2 Thereforeforalllegalvaluesof j C j ,0 < )]TJ/F11 9.9626 Tf 7.749 0 Td [(r j C j 2 + j C j n )]TJ/F8 9.9626 Tf 10.515 0 Td [(1+ rn )]TJ/F11 9.9626 Tf 10.515 0 Td [(r 2 )]TJ/F11 9.9626 Tf 10.514 0 Td [(n 2 + n + rn andthus G must percolatefarther. ThesharpnessofTheorem0.4isestablishedbythefollowingexample: G r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r n doesnotguarantee r -percolationfromanysetofsize r .Let G beabalanced r )]TJ/F8 9.9626 Tf 7.749 0 Td [(partitegraphoforder n whereeverypartition hasatleasttwovertices.Noticethattheminimumdegreeof G is n )]TJ/F10 6.9738 Tf 11.314 3.922 Td [(n r = r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r n .Takeonevertexineach partitiontobeinthesetofinitialactivevertices.Everyvertexisadjacenttoexactly r )]TJ/F8 9.9626 Tf 10.05 0 Td [(1activevertices. Thus G doesnotpercolateanymore. Figure9:SharpnessExamplewith n =16and r =4 Afterlookingatminimumdegree,wewantedtondastrongerresultforagraph G to r -percolatefrom anysetofsize r .Wedecidedtolookatboundsfor 2 G .NotethatTheorem0.5impliesTheorem0.4. Theorem0.5. If r 2 and G isagraphoforder n suchthat 2 G 2 r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n +1 r ,then Gr -percolatesfrom anyinitialactivesetofsize r . Proof. Let G beagraphon n verticeswhere 2 G 2 r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n +1 r .Assumeforcontradictionthatthereis 16

PAGE 21

somesetof r initialverticesthat G doesnot r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolatefrom.Because G doesnotpercolate,thereis astepwherenodormantverticesareadjacentto r activevertices.Let B bethesetofactiveverticesat thisstepand C bethesetofdormantvertices.Notethat j B j r because A = r .Thustheremustbe somevertex v 2 B andavertex u 2 C thatthatarenotadjacentotherwise u wouldhaveatleast r active neighbors.Sincehavingmoreedgesdoesnotmakeitmoredicultforagraphtopercolate,wewilllook attheextremalcasewhere B and C arecliques.Pick v and u suchthat 2 = d v + d u .Let E bethe numberofedgesbetween B and C .Because G doesn'tpercolate,novertexin C canbeadjacenttomore than r )]TJ/F8 9.9626 Tf 10.189 0 Td [(1verticesin B .Thus E j C j r )]TJ/F8 9.9626 Tf 10.189 0 Td [(1.Let s bethenumberofedgesfrom v to C .Weonlyneed tolookat s because 2 guaranteeseveryothervertexin B hasatleastasmanyneighborsin C as v does. Notethat d v = j B j)]TJ/F8 9.9626 Tf 14.944 0 Td [(1+ s and d u j C j)]TJ/F8 9.9626 Tf 14.944 0 Td [(1+ r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1. v B u C s r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 Figure10: 2 = d v + d u j B j)]TJ/F8 9.9626 Tf 14.944 0 Td [(1+ s + j C j)]TJ/F8 9.9626 Tf 14.944 0 Td [(1+ r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1= j B j + s + n )-222(j B j + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(3= s + n + r )]TJ/F8 9.9626 Tf 9.962 0 Td [(3 Nowwecansolvefor s intermsof r and n . 2 s + n + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(3 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n )]TJ/F11 9.9626 Tf 9.962 0 Td [(r +3 s Therefore j B j 2 )]TJ/F11 9.9626 Tf 10.196 0 Td [(n )]TJ/F11 9.9626 Tf 10.196 0 Td [(r +3 E whichimplies j B j 2 )]TJ/F11 9.9626 Tf 10.196 0 Td [(n )]TJ/F11 9.9626 Tf 10.196 0 Td [(r +3 j C j r )]TJ/F8 9.9626 Tf 10.196 0 Td [(1.Nowweneedtoknow themaximumsize B canbe.Todothis,wewillndtheminimumsizeof C .Since v isn'tadjacentto u or itself, d v n )]TJ/F8 9.9626 Tf 9.581 0 Td [(2.Remember u canhaveatmost r )]TJ/F8 9.9626 Tf 9.58 0 Td [(1neighborsin B so d u = 2 )]TJ/F11 9.9626 Tf 9.58 0 Td [(d v )]TJ/F8 9.9626 Tf 9.58 0 Td [( r )]TJ/F8 9.9626 Tf 9.58 0 Td [(1.Thus j C j 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [( n )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 )]TJ/F8 9.9626 Tf 9.963 0 Td [( r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1+1= 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n )]TJ/F11 9.9626 Tf 9.962 0 Td [(r +4and j B j = n )-222(j C j)]TJ/F11 9.9626 Tf 23.8 0 Td [( 2 +2 n + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4. 17

PAGE 22

j B j 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n )]TJ/F11 9.9626 Tf 9.962 0 Td [(r +3 j C j r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 j B j 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n )]TJ/F11 9.9626 Tf 9.962 0 Td [(r +3 n )]TJ/F11 9.9626 Tf 9.962 0 Td [(B r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 2 )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +2 j B j)]TJ/F11 9.9626 Tf 14.944 0 Td [(n r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 0 Checkthat 2 )]TJ/F11 9.9626 Tf 9.962 0 Td [(n +2 0. 2 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +2 0 2 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 n +2 )]TJ/F11 9.9626 Tf 9.962 0 Td [(rn +2 r 0 rn )]TJ/F8 9.9626 Tf 9.962 0 Td [(2 n +2+2 r 0 Since r 2, rn )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 n +2+2 r 0.Nowwecanplugin n )-222(j C j)]TJ/F11 9.9626 Tf 23.8 0 Td [( 2 +2 n + r )]TJ/F8 9.9626 Tf 9.962 0 Td [(4for j B j . 0 2 )]TJ/F11 9.9626 Tf 9.962 0 Td [(n +2 )]TJ/F11 9.9626 Tf 7.749 0 Td [( 2 +2 n + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 )]TJ/F11 9.9626 Tf 9.962 0 Td [(n r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 0 2 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(1 n +1 r )]TJ/F11 9.9626 Tf 9.963 0 Td [(n +2 )]TJ/F8 9.9626 Tf 7.749 0 Td [(2 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 n +1 r +2 n + r )]TJ/F8 9.9626 Tf 9.962 0 Td [(4 )]TJ/F11 9.9626 Tf 9.963 0 Td [(rn + n 0 rn )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 n +2+2 r )]TJ/F8 9.9626 Tf 4.566 -8.07 Td [(2 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(2+ r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 r )]TJ/F11 9.9626 Tf 9.962 0 Td [(r 3 n + r 2 n = r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 n 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(5 r 2 +10 r +8 n +2 r 3 )]TJ/F8 9.9626 Tf 9.963 0 Td [(6 r 2 )]TJ/F8 9.9626 Tf 9.962 0 Td [(12 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 Weneedtondtheminimumvaluefor n .Recallthat r j B j)]TJ/F11 9.9626 Tf 23.799 0 Td [( 2 +2 n + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4. r )]TJ/F11 9.9626 Tf 18.265 0 Td [( 2 +2 n + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 r )]TJ/F8 9.9626 Tf 18.265 0 Td [(2 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(1 n +1 r +2 n + r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 r 2 )]TJ/F8 9.9626 Tf 18.264 0 Td [(2 rn +2 n )]TJ/F8 9.9626 Tf 9.962 0 Td [(2+2 rn )]TJ/F8 9.9626 Tf 9.962 0 Td [(4 r + r 2 4 r 2 n )]TJ/F8 9.9626 Tf 9.962 0 Td [(2 2 r +1 n Let M = r )]TJ/F8 9.9626 Tf 9.077 0 Td [(4 n 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(5 r 2 +10 r +8 n +2 r 3 )]TJ/F8 9.9626 Tf 9.077 0 Td [(6 r 2 )]TJ/F8 9.9626 Tf 9.078 0 Td [(12 r )]TJ/F8 9.9626 Tf 9.077 0 Td [(4andnoticethat dM dn = r )]TJ/F8 9.9626 Tf 9.078 0 Td [(8 n )]TJ/F8 9.9626 Tf 9.078 0 Td [(5 r 2 +10 r +8. 18

PAGE 23

If dM dn 0foralllegalvaluesof n ,wecanplugtheminimumvaluefor n into M .Rememberthat r 2so 4 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(8isnonnegative. 0 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(8 n )]TJ/F8 9.9626 Tf 9.963 0 Td [(5 r 2 +10 r +8 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(8 r +1 )]TJ/F8 9.9626 Tf 9.962 0 Td [(5 r 2 +10 r +8 =8 r 2 +4 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(16 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(8 )]TJ/F8 9.9626 Tf 9.962 0 Td [(5 r 2 +10 r +8 =3 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(2 r Thus dM dn isnon-decreasingfor n 2 r +1and r 2.Nowwecanplug2 r +1for n into M . 0 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 n 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(5 r 2 +10 r +8 n +2 r 3 )]TJ/F8 9.9626 Tf 9.963 0 Td [(6 r 2 )]TJ/F8 9.9626 Tf 9.962 0 Td [(12 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(4 r +1 2 + )]TJ/F8 9.9626 Tf 7.749 0 Td [(5 r 2 +10 r +8 r +1+2 r 3 )]TJ/F8 9.9626 Tf 9.963 0 Td [(6 r 2 )]TJ/F8 9.9626 Tf 9.962 0 Td [(12 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 =8 r 3 )]TJ/F8 9.9626 Tf 9.962 0 Td [(8 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(12 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(8 )]TJ/F8 9.9626 Tf 9.962 0 Td [(10 r 3 +15 r 2 +26 r +8+2 r 3 )]TJ/F8 9.9626 Tf 9.962 0 Td [(6 r 2 )]TJ/F8 9.9626 Tf 9.963 0 Td [(12 r )]TJ/F8 9.9626 Tf 9.963 0 Td [(4 = r 2 +2 r )]TJ/F8 9.9626 Tf 9.962 0 Td [(4 Thisisacontradictionbecause r 2 +2 r )]TJ/F8 9.9626 Tf 9.722 0 Td [(4 > 0for r 2.Thus G must r -percolatefromanyinitiallyactive setofsize r . NoticethatoursharpnessexampleforTheorem0.4isalsoasharpnessexampleforTheorem0.5.Because everypartitionhasatleasttwoverticeswhicharenonadjacentand G = r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r n , 2 G = r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r 2 n . 19

PAGE 24

CHAPTERIV OPENQUESTIONS Thereareseveralremainingquestionsconcerning r -percolationfromanyinitialactivesetofsize r that wouldbeinterestingtoanswer.Onecouldndthemaximumandminimumnumberofstepsforagraphto r -percolatefromanyinitialactivesetofsize r . Whatisthemin/maxnumberofstepsforagraph G to r -percolatewith G r )]TJ/F7 6.9738 Tf 6.226 0 Td [(1 n +1 r ?With 2 G > 2 n r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r ? Let G beagraphwith G = r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 n r .Canwecountthehowmany r -setstherearethat G doesnot r -percolatefrom?Ifso,whatisthemaximumnumberof r )]TJ/F8 9.9626 Tf 7.748 0 Td [(setsthat G doesn't r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolatefrom?The minimum? Notethatoursharpnessexampleis r )]TJ/F8 9.9626 Tf 7.749 0 Td [(partite.Isthattheonlyfamilyofgraphsthatneed 2 G > 2 n r )]TJ/F7 6.9738 Tf 6.227 0 Td [(1 r to r -percolatefromanyinitialsetofsize r ?Couldwerelaxthedegreeconditionsif G issucientlyconnected and G issucientlyfarfrombeing r )]TJ/F8 9.9626 Tf 7.748 0 Td [(partite? Canwenddierentdegreeconditionsforspecicfamiliesofgraphssuchasallgraphsthatare3chromaticorallgraphsthatarebipartite? Isanysignicancetothefactthatthesizeofthesmallest r -percolatingsetinatreewith l verticesof degreelessthan r isthesameastheminimumdegreeofagraph G requiredforanyinitialsetofsize r to r )]TJ/F8 9.9626 Tf 7.749 0 Td [(percolate G ? Acknowledgments Theauthorwouldliketothank,inalphabeticalorder,MikeFerrara,NathanGraber, andFloPfenderforalloftheirhelpandfeedbackthatmadethispaperpossible. 20

PAGE 25

References [1]H.Amini, BootstrapPercolationinLivingNeuralNetworks. JournalofStatisticalPhysics,Vol.141No. 3,459-475 [2]K.AppelandW.Haken, SolutionoftheFourColorMapProblem. ScienticAmerican,Vol.237No.4 108-121 [3]A.T.Balaban, ApplicationsofGraphTheoryinChemistry. JChem.Inf.Comput.Sci.,Vol.25, 334-343 [4]J.BaloghandB.Bollobas, BootstrapPercolationontheHypercube. ProbabilityTheoryandRelated Fields,Vol.134No.4,624-648 [5]J.Balogh,B.Bollobas,H.Duminil-Copin,andR.Morris,TheSharpThresholdforBootstrapPercolationinallDimensions.arXiv:1010.3326v2[math.PR] [6]F.BenevidesandM.Przykucki, OnSlowlyPercolatingSetsofMinimalsizeinBootstrapPercolation . ElectronicJournalofCombinatorics,Vol.20No.2 [7]D.BonchevandD.H.Rouvray, ChemicalGraphTheory:IntroductionandFundamentals. Gordonand BreachSciencePublishers,,ISBN0-85626-454-7 [8]S.BornholdtandH.G.Schuster, HandbookofGraphsandNetworks:fromtheGenometotheInternet . JohnWileyandSons, [9]D.P.BovetandP.Crescenzi, IntroductiontotheTheoryofComplexity. PrenticeHallPTR,, ISBN0-13-915380-2 [10]E.BullmoreandO.Sporns, ComplexBrainNetworks:GraphTheoreticalAnalysisofStructuraland FunctionalSystems. NatureReviewsNeuroscience,Vol.10,186198 [11]A.W.Burks, VonNeumann'sSelf-ReproducingAutomata. MichiganUniversityAnnArbor,Logicof ComputersGroup, [12]S.Carmi,etal., AModelofInternetTopologyusing k -shellDecomposition .NationalAcademyofSciences,Vol.104No.27,11150-11154 [13]J.Chalupa,P.L.Leath,andG.R.Reich, BootstrapPercolationonaBetheLattice. J.Phys.CSolid StatePhys.,Vol.12,L31 [14]N.Chen, OntheApproximabilityofInuenceinSocialNetworks SIAMJ.DiscreteMath,Vol.23No. 31400-1415 [15]J.Chvatal, OnHamilton'sIdeals. J.Combin.TheorySer.B,Vol.12No.2,163-168 [16]J.ClemensandA.N.Zehmakan, DynamicMonopoliesinReversibleBootstrapPercolation. arXiv:1805.07392[cs.DS] [17]M.Dairyko,M.Ferrara,B.Lidick y ,R.R.Martin,F.Pfender,andA.J.Uzzell, OreandChv a tal-type DegreeConditionsforBootstrapPercolationfromSmallSets. arXiv:1610.04499v2[math.CO] [18]G.A.Dirac, SomeTheoremsonAbstractGraphs. Proc.LondonMath.Soc.,Vol.2,69-81 [19]P.A.DreyerJr.andF.S.Roberts, Irreversible k -ThresholdProcesses:Graph-TheoreticalThreshold ModlesoftheSpreeadofDiseaseandofOpinion. DiscreteAppliedMathematics,Vol.157No.7, 1615-1627 [20] ContagiousSetsinRandomGraphs. arXiv:1602.0175v1[math.PR] [21]L.Fortnow, TheStatusofthe P versus NP Problem CommunicationsoftheACM,Vol.52No.9, 115-116 21

PAGE 26

[22]L.Fortnow, TheGoldenTicket: P , NP ,andtheSearchfortheImpossible. PrincetonUniversityPress, ,ISBN9780691156491 [23]D.Freund,M.Poloczeck,andD.Reichman, ContagiousSetsinDenseGraphs. EuropeanJournalof Combinatorics,Vol.68,66-78 [24]M.Gardner, MathematicalGames-TheFantasticCombinationsofJohnConway'sNewSolitaireGame Life. ScienticAmerican,Vol.223,120-123 [25]J.Gao,T.Zhou,andY.Hu, BootstrapPercolationonSpatialNetworks. ScienticReports,Vol.5 [26]K.Gunderson, MinimumDegreeConditionsforSmallPercolatingSetsinBootstrapPercolation . arXiv:1703.10741[math.CO] [27]P.J.HansenandP.C.Jurs, ChemicalApplicationsofGraphTheory. JournalofChemicalEducation, ,574-580 [28]I.Hartarsky, MaximalBootstrapPercolationTimeontheHypercubeviaGeneralisedSnake-in-the-Box. arXiv:1707.09214v2[math.CO]2018 [29]Y.Iturria-Medinaetal., StudyingtheHumanBrainAnatomicalNetworkviaDiusion-weightedMRI andGraphTheory. NeuroImage,Vol.40No.3,1064-1076 [30]S.Janson,T.Luczak,T.Turova,andT.Vallier, BootstrapPercolationontheRandomGraph G n;p . arXiv:1012.23535v2[math.PR] [31]M.KaufmanandD.Stauer, ADiluteBootstrapPercolation:LatticeModelforUnresponsivenessin T-cellImmunology. JournalofStatisticalPhysics,Vol.13,843-851 [32]J.Kyncl,B.Lidicky,andT.Vyskocil, Irreversible2-ConversionSetinGraphsofBoundedDegree. arXiv:1412.4188v5[cs.DM] [33]O.Ore, NoteonHamiltonianCircuits .Amer.Math.Monthly,Vol.67,55. [34]M.Przykucki, MaximalPercolationTimeinHypercubesUnder2-BootstrapPercolation. ElectronicJournalofCombinatorics,Vol.19No.2 [35]M.Ramos,etal., Howdoespublicopinionbecomeextreme? arXiv:1412.4718[physics.soc-ph] [36]E.Riedl, LargestandSmallestMinimalPercolatingSetsinTrees. ElectronicJournalofCombinatorics, Vol.19No.1 [37]M.ShresthaandC.Moore, Message-PassingApproachforthresholdmodelsofBehaviorinNetworks. Phys.Rev.,Vol.89 [38]NenadTrinajstic, ChemicalGraphTheory,SecondEdition. TaylorandFrancis,,ISBN 1351461575 [39]B.C.M.vanWijk,C.J.Stam,andA.Daertshofer, ComparingBrainNetworksofDierentSizeand ConnectivityDensityUsingGraphTheory. PLOSONE,,0013701 [40]H.T.P.Williams,etal., Networkanalysisrevealsopenforumsandechochambersinsocialmedia discussionsofclimatechange .GlobalEnvironmentalChange,Vol.31126-138 [41]S.ZhouandR.J.Mondragon, TheRich-ClubPhenomenoninInternetTopology .IEEECommunications Letters,Vol.8No.3,180-182 22