资源描述：
《lambda isoperimetric inequalities for graphs and superconcentrators图地Lsop观算式不等式 超浓缩器.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、JOURNALOFCOMBINATORIALTHEORY,SeriesB38,73-88(1985)il,,lsoperimetricInequalitiesforGraphs,andSuperconcentratorsN.ALON*DepartmentofMathematics,MassachusettsInstituteqfTechnologyANDV.D.MILMANDepartmentofMathematics,TelAvivUniversity,IsraelCommunicatedbyrheManagingEdit
2、orsReceivedMarch24,1984Ageneralmethodforobtainingasymptoticisoperimetricinequalitiesforfamiliesofgraphsisdeveloped.Someoftheseinequalitieshavebeenappliedtofunctionalanalysis,Thismethodusesthesecondsmallesteigenvalueofacertainmatrixassociatedwiththegraphanditisthedi
3、screteversionofamethodusedbeforeforRiemannianmanifolds.Alsosomeresultsareobtainedonspectraofgraphsthatshowhowthiseigenvalueisrelatedtothestructureofthegraph.Combiningtheseresultswithsomeknownresultsongrouprepresentationsmanynewexamplesareconstructedexplicitlyofline
4、arsizedexpandersandsuperconcentrators.‘i:1985AcademicPress.Inc.1.INTRODUCTIONSuppose131andletG=G,=(V,,E,)=(V,E)bethegraphofthel-dimensionalcube.TheverticesofGarethe2’binaryvectorsoflength1andtwoverticesareadjacentifftheydifferinexactlyonecoordinate.Thedistancebetw
5、eenanytwoverticesisthusthenumberofcoordinatesinwhichtheydiffer.ForuEV,andn>1letB(u,d)denoteaHammingballwithcentervandradiusd,i.e.,asetconsistingofallverticesofGwhosedistancefromvislessthandandsomeverticesofGwhosedistancefromvisd.Let0andidenotetheall-zerosandtheall-
6、onesverticesofG.Awell-knowntheoremofHarper([22],seealso[171forasimpleproofand[35]forageneralization)assertsthatifA,Caretwosubsetsofverticesof*ResearchsponsoredinpartbytheWeizmannFellowshipforScientificResearch.730095-8956/85$3.00Copyrightc1985byAcademicPress,Inc.Al
7、lrightsofreproductionmanyformreserved74ALONANDMILMANGandp=p(A,C)isthedistancebetweenthem,thenthereexisttwoHam-mingballsB,=B(O,d,)andB,=B(i,d,)suchthatlB,l=IAl,l&l=ICIandthedistancebetweenB,andB,isatleastp.Thistheorem,whichgivestheprecisesolutiontotheisoperimetricpr
8、oblemforG,isusedin[4]toobtainthefollowingasymptoticresult.PROPOSITION1.1.SupposeA,CcV,u(A)=(AI/lV24andp(C)=ICI/lVI.IfP=AA,Clthenp(C)
