Ett grundläggande faktum i spektral grafteori är att antalet anslutna komponenter i en oriktad graf är lika med multipliciteten av eigenvärde noll i den Laplacian matrisen av grafen. I synnerhet är grafen frånkopplad om och endast om det finns minst två eigenvärden som är lika med noll. Cheegers ojämlikhet och dess varianter ger en ungefärlig version av det senare faktumet; de anger att en graf har ett glest snitt om och endast om det finns minst två eigenvärden som är nära noll. Det har förmodats att en analog karakterisering innehar för högre multipliciteter, d.v.s., det finns k eigenvärden nära noll om och endast om vertex-uppsättningen kan delas upp i k-undergrupper, där var och en definierar ett glest snitt. Vi löser det här. Vårt resultat ger en teoretisk motivering för kluster algoritmer som använder botten k eigenvectors för att inbädda hörn i R k, och sedan tillämpa geometriska överväganden för inbäddning. Vi visar också att dessa tekniker ger en nästan optimal kvantitativ koppling mellan expansionen av uppsättningar av storlek  på n/k och λ k, det kth minsta eigenvärdet av den normaliserade Laplacian, där n är antalet hörn. I synnerhet visar vi att det i varje graf finns minst k/2 separata uppsättningar (av vilka en kommer att ha storlek högst 2n/k), var och en har expansion som mest O ( ε λ k log k). Louis, Raghavendra, Tetali och Vempala har självständigt visat sig vara en något svagare version av detta sista resultat [LRTV12]. Den logg k bundna är tight, upp till konstanta faktorer, för "noisy hypercube" grafer.
Lee och Al. REF studerar de högre ordningen Cheeger ojämlikheter, och visar att varje graf kan delas in i k icke-tomma undergrupper sådan att varje delmängd i partitionen har expansion O(k 3 ) λ k.
Multi-way spectral partitioning and higher-order cheeger inequalities
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}