Vi presenterar ett nytt tillvägagångssätt för att visa att slumpmässiga grafer är nästan optimala expanders. Detta tillvägagångssätt är baserat på senaste djupa resultat i combinatorial gruppteori. Det gäller både regelbundna och oregelbundna slumpmässiga grafer. Låta vara en slumpmässig d-regelbunden graf på n hörn, och låt λ vara det största absoluta värdet av en icke-trivial eigenvärde av dess adjakensmatris. Det förmodades av Alon [Alo86] att en slumpmässig d-regelbunden graf är "nästan Ramanujan", i följande mening: för varje Friedman berömda presenterade ett bevis på denna gissning i [fre08]. Här föreslår vi ett nytt, betydligt enklare bevis på ett nästan optimalt resultat: vi visar att en slumpmässig d-regelbunden graf uppfyller λ < 2 ε d − 1 + 1 asymptotiskt nästan säkert. En huvudfördel med vårt tillvägagångssätt är att det är tillämpligt på en generaliserad gissning: En d-regelbunden graf på n hörn är en n-täckande utrymme av en bukett av d/2 loopar. Mer allmänt, fastställande av en godtycklig bas graf., studerar vi spektrumet av., en slumpmässig n-täckning av. Låta λ vara det största absoluta värdet av en icke-trivial eigenvärde av Ε. Friedman [fre03] antog att för varje ε > 0, a.a.s. λ < ρ + ε, där ρ är spektralradien för det universella höljet av ∂. När vi är regelbundna får vi samma gräns som tidigare: ρ + 1, och för en godtycklig  ska vi visa oss vara en nästan optimal övre gräns på ρ 3ρ. Detta är en betydande förbättring av alla kända resultat (av Friedman, Linial-Pudder, Lubetzky-Sudakov-Vu och Addario-Berry-Griffiths).
I det oregelbundna fallet har Puder REF visat att med hög sannolikhet en högorderlyft av en graf G har nya eigenvärden som avgränsas i absolut värde av ε 3ρ, där ρ är den spektralradien av den universella omslaget av G.
Expansion of Random Graphs: New Proofs, New Results
{'venue': 'Inventiones Mathematicae 201 (2015), no. 3, 845-908', 'journal': None, 'mag_field_of_study': ['Mathematics']}