Citation
On r-Percolation in dense draphs

Material Information

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

Thesis/Dissertation Information

Degree:
Master's ( Master of science)
Degree Grantor:
University of Colorado Denver
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:
University of Colorado Denver
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.

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

ONr-PERCOLATIONINDENSEGRAPHS by CATRINAGRABER B.S.,UniversityofNorthernColorado,2015 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof MastersofScience AppliedMathematicsProgram 2018

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

a b c Figure6: Q 3 doesnot2-percolatefromaninitialactivesetofsize2 playedtogetheratrecess.Avertexwouldbecomeactiveifthatstudentgotsickanddormantiftheywere healthy.Theuspreadsbybeingaroundotherpeoplewhohavetheu.Thus r wouldbehowmanypeople onecancomeincontactwiththatalmostguaranteesonegetssick.Ofcoursethismodelwouldneedtobe runmanytimesandaverageslookedattounderstandwhatmightactuallyhappeninarealworldsetting. In1993MarcelleKaufmanandDietrichStauerusedreversiblebootstrappercolationtohelpunderstand whyT-cellsmaybecomeunresponsive[31].TheyusedasquarelatticetomodelthesurfaceoftheT-cell. NormallywewouldcallthesquaresinthelatticecellsbutconsideringthewholelatticerepresentsaT-cell, theyreferredtothemassites.Theinitialcongurationofthelatticeisrandom.Asiteiseitherempty oroccupied.Thesesitesremainemptyoroccupiedforever.Occupiedsitesareeitheraphosphorylated receptororanunphosphorylatedreceptor.Asiteisaphosphorylatedreceptorifandonlyifatleasttwo ofitsfournearestneighborsarealsophosphorylatedreceptors.Thisreectstheresultingnetbalanceof phosphorylationoftheT-cellreceptorswhichinturnallowsthescientiststomodelunresponsiveT-cells. Bootstrappercolationhasnumerousapplicationstothespreadofinuenceandinformationinsocial networks.AsanexampleweuseFacebookasoursocialmediaplatformandwedeneagraph F represent thisnetworkasfollows.Theuserswouldbetheverticesof F andtwoverticeswouldbeconsideredadjacentif thecorrespondinguserswereFacebookfriends.Wewouldconsideravertexin F activeifthecorresponding userhadseenthefakenewsarticleweweretracking.Themoreactivefriendsauserhas,themorelikelythat userwouldbetobecomingactive.Ifwewantedtomodelbeliefinthefakenewsarticle,wewouldwantto usereversiblebootstrappercolationsincesomeusersmightbelieveanarticleatrstandthenlaterrealize itisfalse.Tomodelhowbeliefinafakenewsarticlespreadsonadierentsocialmediaplatformsuchas Twitter,wewoulduseadirectedgraph T .AuserisinuencedonTwitteronlybytheuserstheyfollow 5

PAGE 10

andthuscanonlybecomeactivethroughedgescomingintotheircorrespondingvertex.Likewisetheuser canonlyinuencetheirfollowerswhichwouldbemodeledthroughtheout-edges.Wecouldmakethemodel moreaccuratebyassigningweightstoavertex'sout-edges.Forexample,afakenewsarticlepostedbya popularcelebritywouldbefarmorelikelytoberepostedbytheirfollowersthanapersonwithrelativelyfew followers.Wewouldweightthecelebrity'sout-edgeswithalargerchanceofspreadingtotheirfollowers. In[25],theyusedbootstrappercolationtostudyhoweectivesocialnetworkssuchasLiveJournal,HP Labsemailnetwork,andBelgianmobilephonenetworkareatspreadinginformation.Theybuiltothe researchdonebyShresthaandMoorein[37]whichstudiedhowsocialbehaviorsliketrendsandopinions percolatethroughsocialgroups.M.Ramosetal.[35]investigatedwhenpublicopinionchangesfrom moderatetoextremeusingrelaxedbootstrappercolationmodel.Intheirmodel,theverticesrepresented peopleandinsteadofbeinginoneoftwostates,theycouldbeinoneoffour:istronglybelieve,iibelieve, iiidisbelieve,orivstronglydisbelieve.Theynoticedthathavingmoreneighborswithamoreextreme opinionmadeitmorelikelyforthatvertextobecomemoreextremeandinturnmakeitsneighborsmore extreme.Intheirpapertheyshowthatabootstrappercolationtransitionhappensrightwhenasociety's opinionabruptlychangesfrommoderatetoextreme[35].Thatis,afteracertainpercentofthepopulation hadanextremeopinion,theopinionwouldpercolatethroughoutthegraph.Theyconcludedtheymightbe abletopredictwhenasociety'sviewswillchangebeforeitactuallyhappens. 6

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