Vi presenterar en metod för att bevisa övre gränser på eigenvärden av grafen Laplacian. Ett huvudsteg innebär att välja en lämplig "Riemannian" metrisk för att likforma geometrin i grafen. I många intressanta fall visas förekomsten av ett sådant mått genom att undersöka kombinatorik av speciella typer av flöden. Detta innebär att visa nya ojämlikheter i korsningen av diagram. I synnerhet använder vi vår metod för att visa att för alla positiva heltal k, den k th minsta eigenvärde av Laplacian på en n-vertex, begränsad grad planar graf är O (k/n). Denna gräns är asymptotiskt tight för varje k, eftersom det är lätt att se att uppnås för fyrkantiga plana rutnät. Vi utvidgar också detta spektralresultat till grafer med avgränsat släkte, och grafer som förbjuder fasta minderåriga. Tidigare var sådana spektral övre gränser endast kända för fallet k = 2.
Till exempel Kelner et al. REF visar att för n-vertex, avgränsade planara grafer, har man att kth minsta eigenvärde uppfyller λ k = O(k/n).
Metric uniformization and spectral bounds for graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}