Abstrakt. Vi anser att två generaliseringar av problemet med att hitta ett glesaste snitt i en graf. Den första är att hitta en partition av vertex inställd i m delar så att minimera glesheten av partitionen (definierad som förhållandet mellan vikten av kanterna mellan delar och den totala vikten av kanterna incident till den minsta m - 1 delar). Den andra, som har dykt upp i samband med förståelsen av de unika spel gissning, är att hitta en delmängd av minsta sparhet som innehåller högst en 1/m bråkdel av hörnen. Våra huvudsakliga resultat är förlängningar av Cheegers klassiska ojämlikhet till dessa problem via högre eigenvärden av grafen Laplacian. Särskilt för den glesaste m-partionen, bevisar vi att glesheten är högst 8 ε 1 − λm log m där λm är den normaliserade adjacensmatrisens m th största eigenvärde. För den glesaste lilla uppsättningen band vi glesheten med O( (1 - λ m 2 ) log m). Våra resultat är algoritmiska, med den första med en rekursiv spektral nedbrytning och den andra med en konvex avslappning.
där vol(S) definieras som summan av graderna av hörnen i S. REF gav en algoritm för att hitta en k-partition som skär högst O λ k log k-fraktion av kanterna.
Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}