Discrepancy and Eigenvalues of Cayley Graphs (extended abstract)
- 格式：pdf
- 大小：163.78 KB
- 文档页数：6
DiscrepancyandEigenvaluesofCayleyGraphs(extendedabstract)
Y.Kohayakawa†,¶V.R¨odl‡,¶M.Schacht§,¶AbstractWeconsiderquasirandompropertiesforCayleygraphsoffiniteabeliangroups.Inparticular,weshowthathavinguniformedge-distribution(i.e.,smalldiscrepancy)andhavinglargeeigenvaluegapareequivalentpropertiesforCayleygraphs,eveniftheyaresparse.ThispositivelyanswersaquestionofChungandGraham[“Sparsequasi-randomgraphs”,Combinatorica22(2002),no.2,217–244]fortheparticularcaseofCayleygraphs,whileingeneraltheanswerisnegative.
1IntroductionOuraimhereistoinvestigatecertainaspectsofawellknownconnectionbetweentheeigenvaluegappropertyandquasirandomnessofgraphs.Letann-vertexgraphGbegiven.RecallthattheeigenvaluesofGaresimplytheeigenvaluesofthenbyn,0–1adjacencymatrixofG,with1indicatingedges.Asusual,letλk=λk(G)bethekthlargesteigenvalueofG,inabsolutevalue.RecallthatGissaidtobe“quasirandom”iftheedgesofGare“uniformlydistributed”(wepostponetheprecisedefinition,seeDefinition1).
†TheauthorwasonleavefromInstitutodeMatem´aticaeEstat´ıstica,Universidade
deS˜aoPaulo,RuadoMat˜ao1010,05508–090S˜aoPaulo,Brazil,whilepartofthisworkwasdone.HewaspartiallysupportedbyMCT/CNPqthroughtheProNExPro-gramme(Proj.107/97,Proc.CNPq664107/1997–4)andbyCNPq(Proc.300334/93–1and468516/2000–0).‡ResearchwaspartiallysupportedbyNSFGrantDMS0300529.
§TheparticipationoftheauthorinEuroComb’03waspartiallysupportedbyDIMATIA
andtheEuropeanprojectCOMBSTRU.¶DepartmentofMathematicsandComputerScience,EmoryUniversity,Atlanta,GA
30322,USA,E-mail:{yoshi|rodl|mschach}@mathcs.emory.edu
1ThankstotheworkofTanner[14],AlonandMilman[3]andAlon[1](seealsoAlonandSpencer[4,Chapter9])itiswellknownthatagapbetweenthelargestandthesecondlargesteigenvalueofagraphGisrelatedtothequasirandomnessofG.Here,theconceptof“quasirandomness”willbethatofChung,Graham,andWilson[7].Recallthat[7]presentsa“theoryofquasirandomness”fordensegraphs,exhibitingseveral,quitedisparatealmostsurepropertiesofrandomgraphsthatare,quitesurprisingly,equivalentinadeterministicsense.(EarlierworkinthisdirectionisduetoThomason[15](seealso[16]),andseveralotherauthors[1,2,8,13].)Oneoftheso-called“quasirandomproperties”thatispresentedin[7]istheeigenvaluegapbetweenλ1andλk(k≥2).Morerecently,ChungandGraham[6]setouttoinvestigatetheextensionoftheresultsin[7]tosparsegraphs,thatis,graphswithvanishingedge-density.Asitturnsout,ana¨ıveapproachtosuchaprojectfails,astheresultsin[7]donotfullygeneralisetothe“sparsecase”intheexpectedmanner(forathoroughdiscussiononthispoint,see[6]andalsoto[9,11]).Ontheotherhand,somepositiveresultshavebeenestablished.Inpar-ticularitwasshownin[6]thatalargeeigenvaluegapimpliesuniformedge-distribution.ChungandGrahamaskedwhethertheconversealsoholds(see[6,p.230]).Anaffirmativeanswertothisquestionwouldfullygener-alisetherelationshipbetweenthesetwoconceptstothesparsecase.However,KrivelevichandSudakov[12]discoveredthat,unfortunately,theanswertothequestionposedbyChungandGrahamisnegative,byconstructingasuitablefamilyofcounterexamples.Here,ouraimistoshowthattheanswerispositiveifoneconsidersCayleygraphsoffiniteabeliangroups,regardlessofthedensityofthegraph.Weleavethenon-abeliancaseasanopenquestion.ItisworthnotingthatseveralexplicitconstructionsofquasirandomgraphsareindeedCayleygraphs(see,e.g.,[16]and[12,Section3]).Beforeweproceedtostateourresultprecisely,wementionthatourproofmethodalsoshedssomelightontheinvestigationofquasirandomsubsetsofZn=Z/nZ,inthespiritofChungandGraham[5],inthesparsecase(andforgeneralabeliangroups,assuggestedin[5,p.85]).Weshallcomebacktothistopicinthenearfuture.
2StatementofthemainresultWeusethefollowingnotation.IfG=(V,E)isagraph,wewritee(G)forthenumberofedges|E|inG.IfU⊂VisasetofverticesofG,thenG[U]denotesthesubgraphofGinducedbyU.Furthermore,ifW⊂Visdisjoint
2fromU,thenwewriteG[U,W]forthebipartitesubgraphofGnaturallyinducedbythepair(U,W).WealsosometimeswriteE(U,W)=EG(U,W)fortheedgesetofG[U,W].Ifδ>0,wewritex∼δytomeanthat
(1−δ)y≤x≤(1+δ)y.Definition1(DISC(δ)).Let0graphG(n≥2)satisfiespropertyDISC(δ)ifthefollowingassertionholds:forallU⊂V(G)with|U|≥δn,wehave
e(G[U])∼δe(G)|U|2n2.GivenagraphG,letA=A(G)=(avv)v,v∈V(G)bethe0–1adjacencymatrixofG,with1denotingedges.TheeigenvaluesofGaresimplytheeigenvaluesofA.SinceAissymmetric,itseigenvaluesarereal.Asusual,weadjustthenotationsothattheseeigenvaluesaresuchthat
λ1≥|λ2|≥···≥|λn|.(1)Definition2(EIG(ε)).Let0graphGsatisfiespropertyEIG(ε)ifthefollowingholds.Let¯d=¯d(G)=2e(G)/nbetheaveragedegreeofG,andletλ1,...,λnbetheeigenvaluesofG,withthenotationadjustedinsuchawaythat(1)holds.Then
