资源描述：
《Expander Graphs and their Applications》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ExpanderGraphsandtheirApplicationsDraft-notfordistributionShlomoHooryNathanLinialAviWigdersonIBMResearchLaboratoryTheHebrewUniversityInstituteofAdvancedStudyHaifa,IsraelJerusalem,IsraelPrinceton,NJshlomoh@il.ibm.comnati@cs.huji.ac.ilavi@ias.eduMay3,2006DRAFT--DRAFT-
2、-DRAFT--DRAFT--DRAFT--DRAFT--DRAFT--DRAFT--DRAFT--DRAFT--AnOverviewAmajorconsiderationwehadinwritingthissurveywastomakeitaccessibletomathematiciansaswellascomputerscientists,sinceexpandergraphs,theprotagonistsofourstorycomeupinnumerousandoftensurprisingcontextsinbot
3、helds.But,perhaps,weshouldstartwithafewwordsaboutgraphsingeneral.Theyare,ofcourse,oneoftheprimeobjectsofstudyinDiscreteMathematics.However,graphsareamongthemostubiquitousmodelsofbothnaturalandhuman-madestructures.Inthenaturalandsocialsciencestheymodelrelationsamong
4、species,societies,companies,etc.Incomputerscience,theyrepresentnetworksofcommunication,dataorganization,computationaldevicesaswellastheowofcomputation,andmore.InMathematics,CayleygraphsareusefulinGroupTheory.GraphscarryanaturalmetricandarethereforeusefulinGeometry,
5、andthoughtheyare“just”one-dimensionalcomplexestheyareusefulincertainpartsofTopology,e.g.KnotTheory.Instatisticalphysics,graphscanrepresentlocalconnectionsbetweeninteractingpartsofasystem,aswellasthedynamicsofaphysicalprocessonsuchsystems.Thestudyofthesemodelscalls,t
6、hen,forthecomprehensionofthesignicantstructuralpropertiesoftherelevantgraphs.Butaretherenontrivialstructuralpropertieswhichareuniversallyimportant?Thepropertyofbeinganexpanderseemssignicantinmanyofthesemathematical,computationalandphysicalcontexts.Itisnotsurprisin
7、gthatexpandersareusefulinthedesignandanalysisofcommunicationnetworks.Whatislessobviousisthatexpandershavesurprisingutilityinothercomputationalsettingssuchasinthetheoryoferrorcorrectingcodes,andthetheoryofpseudorandomness.Inmathematics,wewillencountere.g.,theirrolein
8、thestudyofmetricembeddings,andinparticularinworkaroundtheBaum-ConnesConjecture[Val03].ExpansioniscloselyrelatedtotheconvergenceratesofMark
