Symmetric Groups and Expander Graphs

arXiv:math/0505624v1[math.GR]28May2005SymmetricGroupsandExpanderGraphsMartinKassabovFebruary1,2008AbstractWeconstructexplicitgeneratingsetsSnand˜Snofthealternatingandthesymmetricgroups,whichturntheCayleygraphsC(Alt(n),Sn)andC(Sym(n),˜Sn)intoafamilyofboundeddegreeexpandersforalln.Thisanswersaffirmativelyanoldquestionwhichhasbeenaskedmanytimesintheliterature.Theseexpandershavemanyapplicationsinthetheoryofrandomwalksongroups,cardshufflingandotherareas.IntroductionAfinitegraphiscalledanexpanderifforany(nottoobig)setofverticestherearemanyedgesleavingthisset.Thisimpliesthatexpandergraphsarehighlyconnectedandhaveasmalldiameter.Suchgraphshavemanypracticalapplications,forexampleinconstructionofcomputernetworks.Usingsimplecountingargumentsitcanbeshownthattherandomk-regulargraphsareexpandersfork≥5.Howevertheseexpandersarenotsufficientformanyapplicationswhereoneneedsexplicitfamiliesofexpandergraphs.Constructingsuchexamplesisadifficultproblem.AnaturalcandidateforafamilyofexpandersaretheCayleygraphsC(Gi,Si)ofasequenceoffinitegroupsGiwithrespecttosome(suitablychosen)gen-eratingsetsSi.ItisknownthatifthereisauniformboundforthesizeofthegeneratingsetsSithentheexpandingpropertiesoftheCayleygraphsarerelatedtotherepresentationtheoryofthegroupsGi,morespecificallytotheirKazhdanconstants.UsingthisconnectionG.Margulisin[29]gavethefirstexplicitconstructionofafamilyofexpanders,usingtheKazhdanpropertyTofSL3(Z).Currentlythereareseveraldifferentconstructionsofexpandersusingtherepresentationtheoryofinfinitegroups—typicallyonefindsafinitelygeneratedinfinitegroupGwitha‘nice’representationtheory(usuallythegrouphassomevariantofpropertyT,propertyτ,Selbergpropertyetc.).InthiscasetheCayleygraphs2000MathematicsSubjectClassification:Primary20B30;Secondary05C25,05E15,20C30,20F69,60C05,68R05,68R10.Keywordsandphrases:expanders,symmetricgroups,alternatinggroups,randomper-mutations,propertyT,Kazhdanconstants.1of(some)finitequotientsGiofGwithrespecttotheimagesofageneratingsetSofthebiggroupformanexpanderfamily.Itisveryinterestingtoaskwhencanonedotheopposite—whichleadstothefollowingdifficultproblem(see[26]):Problem1LetGibeaninfinitefamilyoffinitegroups.IsitpossibletomaketheirCayleygraphsexpandersusingsuitablychosengeneratingsets?Currentlythereisnotheorywhichcangiveasatisfactoryanswertothisquestion.Theanswerisknownonlyinafewspecialcases:IfthefamilyoffinitegroupscomesfromafinitelygeneratedinfinitegroupwithpropertyT(oritsweakerversions)thentheanswerisYES.1Alsoifallgroupsinthefamilyare“almost”abelianthentheanswerisNO(see[23])andthisisessentiallytheonlycasewhereanegativeanswerofProblem1isknown.Anaturalfamilyofgroupswhicharesufficientlyfarfromabelianisthefamilyofallsymmetricgroups.ThespecialcaseofProblem1forthesymmetricgroups,i.e.,theexistenceofageneratingsetswhichmakethierCayleygraphsexpanders,isanoldopenquestionwhichhasbeenaskedseveraltimesintheliterature,see[3,25,26,28].Theasymptoticasn→∞ofKazhdanconstantofthesymmetricgroupSym(n)withrespecttosomenaturalgeneratingsetsareknown,see[5].Unfor-tunatelyinallknownexamplestheKazhdanconstantgoestozeroasthesizeofthesymmetricgroupsincrease(eventhoughinmanycasesthesizesofthegeneratingsetsarenotbounded),whichsuggestthatProblem1hasanegativeanswerforthefamilyofallsymmetricgroups.OntheotherhandthesymmetricgroupSym(n)canbeviewedasagenerallineargroupover“thefield”withoneelement,see[12].In[17],itisshownthattheCayleygraphsofSLn(Fp)foranyprimepandinfinitelymanyncanbemadeexpanderssimultaneouslybychoosingasuitablegeneratingsets.UsingthepreviousremarkthispresentsastrongsupportingevidencethatProblem1hasapositiveanswer.Themainresultofthispaper2answersaffirmativelyProblem1inthecaseofalternating/symmetricgroups.Theorem2ForallnthereexistsanexplicitgeneratingsetSn(ofsizeatmostL)ofthealternatinggroupAlt(n),suchthattheCayleygraphsC(Alt(n),Sn)formafamilyofǫ-expanders.Here,Landǫ0aresomeuniversalconstants.TheproofusestheequivalencebetweenfamilyofexpandersandgroupswithuniformlyboundedKazhdanconstants.UsingboundedgenerationandrelativeKazhdanconstantofsomesmallgroups,wecanobtainlowerboundsforthe1Theoppositeisalsotrue:ForanyinfinitefamilyoffinitegroupsGitheexistenceofgeneratingsetsSisuchthattheCayleygraphsC(Gi,Si)areafamilyofexpandersisequivalenttotheexistenceofafinitelygeneratedsubgroupofQGiwhichhasavariantofpropertyT(morepreciselypropertyτwithrespecttotheinducedtopologyfromtheproducttopologyonQGi).2Thisresultwasannouncedin[16].2KazhdanconstantsofthesymmetricgroupsSym(n)withrespecttoseveraldifferentgeneratingsets.AlltheseestimatesrelayonTheorem1.6,whoseproofusesupperboundsforthecharactersofthesymmetricgroupandestimatesofthemixingtimeofrandomwalks.Theorem2hasmanyinterestingapplications:First,itprovidesoneofthefewconstructionsofanexpanderfamilyofCayleygraphsC(Gi,Si)suchthatthegroupsGiarenotobtainedasquotientsofsomeinfinitegrouphavingavariantofKazhdanpropertyT.3TheotherconstructionswhichdonotuseavariantofpropertyTarebasedonanentirelydifferentidea—thesocalled‘zig-zag’productofgraphs,fordetailssee[2,30,32,35].Second,theautomorphismgroupsofthefreegroupAut(Fn)canbemappedontoinfinitelymanyal