Abstrakt. Vi undersöker Laplacian eigenvärden av en slumpmässig graf G(n, d) med en given förväntad grad fördelning d. Huvudresultatet är att w.h.p. G(n, d) har en stor subgrafkärna(G(n, d)) sådan att spektralgapet hos den normaliserade Laplacian av kärna( min med hög sannolikhet; här c0 > 0 är en konstant, ochdmin betecknar den minsta förväntade graden. Resultatet gäller särskilt glesa grafer meddmin = O(1) som n → ∞, och det är av intresse för att utvidga kända spektralheuristiker för slumpmässiga regelbundna grafer till grafer med oregelbundna gradfördelningar, t.ex. kraftlagar. Detta dokument kompletterar arbetet i Chung, Lu och Vu [Internetmatematik 1, 2003].
I REF studerade vi Laplacian eigen values av glesa slumpmässiga grafer med en given förväntad gradsekvens.
The Spectral Gap of Random Graphs with Given Expected Degrees
{'venue': 'ICALP (1)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}