资源描述：
《michael krivelevich benny sudakov pseudo random graphs》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、BOLYAISOCIETYConferenceonFiniteMATHEMATICALSTUDIES,15andInfiniteSetsBudapest,pp.199-262.PSEUDO-RANDOMGRAPHSM.KRIVELEVICH*andB.SUDAKOVt1.INTRODUCTIONRandomgraphshaveproventobeoneofthemostimportantandfruit•fulconceptsinmodernCombinatoricsandTheoreticalComputerScience.Besidesbeinga
2、fascinatingstudysubjectfortheirownsake,theyserveasessentialinstrumentsinprovinganenormousnumberofcombinatorialstatements,makingtheirrolequitehardtooverestimate.Theirtremen•doussuccessservesasanaturalmotivationforthefollowingverygeneralanddeepinformalquestions:whataretheessential
3、propertiesofrandomgraphs?Howcanonetellwhenagivengraphbehaveslikearandomgraph?Howtocreatedeterministicallygraphsthatlookrandom-like?Thisleadsustoaconceptofpseudo-randonigraphs.Speakingveryinformally,apseudo-randomgraphG=(V,E)isagraphthatbehaveslikeatrulyrandomgraphG(IVI,p)ofthesa
4、meedgedensityp=IEI/(I~I).Althoughthelastsentencegivessomeinitialideaaboutthisconcept,itisnotveryinformative,asfirstofallitdoesnotsayinwhichaspectthepseudo-randomgraphbehaviorissimilartothatofthecorrespondingrandomgraph,andsecondlyitdoesnotsupplyanyquantitativemeasureofthissimila
5、rity.Therearequiteafewpossiblegraphparametersthatcanpotentiallyserveforcomparingpseudo-randomand'ResearchsupportedinpartbyaUSA-IsraelBSFGrant,byagrant.fromtheIsraelScienceFoundationandbyaBergmannMemorialGrant.tResearchsupportedinpartbyNSFgrantsDMS-0355497,DMS-0106589,andbyanAlfr
6、edP.Sloanfellowship.Partofthisresearchwasdonewhilevisit.ingMicrosoftResearch.200M.KrivelevichandB.Sudakovrandomgraphs(andinfactquiteafewofthemareequivalentincertain,verynaturalsense,aswewillseelater),butprobablythemostimportantcharacteristicsofatrulyrandomgraphisitsedgedistribut
7、ion.Wecanthusmakeasignificantstepforwardandsaythatapseudo-randomgraphisagraphwithedgedistributionresemblingtheoneofatrulyrandomgraphwiththesameedgedensity.Still,thequantitativemeasureofthisresemblanceremainstobeintroduced.Althoughfirstexamplesandapplicationsofpseudo-randomgraphs
8、ap•pearedverylongtimeago,itwasAndrewThomasonwho
