Den berömda Cheeger's Ojämlikhet [AM85, Alo86] etablerar en gräns på expansionen av en graf via dess spektrum. Denna ojämlikhet är central för en rik spektral teori av grafer, baserat på att studera eigenvärden och eigenvectors av adjacency matrisen (och andra relaterade matriser) av grafer. Det har förblivit öppet för att definiera en lämplig spektral modell för hypergrafer vars spektra kan användas för att uppskatta olika kombinatoriska egenskaper hos hypergrafen. I detta papper introducerar vi en ny hypergraf Laplacian operatör generalisera Laplacian matris av grafer. Vår operatör kan ses som den gradient operatör tillämpas på en viss naturlig kvadratisk form för hypergrafer. Vi visar att olika hypergrafparametrar (t.ex. Expansion, diameter, etc.) kan begränsas med hjälp av operatörens eigenvärden. Vi studerar den värmespridningsprocess som är förknippad med denna Laplacian operatör, och avgränsade dess parametrar i termer av dess spektra. Alla våra resultat är generaliseringar av motsvarande resultat för grafer. Vi visar att det inte kan finnas någon linjär operatör för hypergrafer vars spektra fångar hypergrafexpansion på ett Cheeger-liknande sätt. Vår Laplacian operatör är icke-linjär, och därmed beräkning av dess eigenvärden exakt är intractable. För alla k  till Z ≥0, vi ger en polynom tid algoritm för att beräkna en approximation till k th minsta eigenvärde av operatören. Vi visar att denna approximationsfaktor är optimal under SSE-hypotesen (inledd av [RS10]) för konstanta värden av k. Slutligen, med hjälp av faktorbevarande reduktion från vertex-expansion i grafer till hypergrafexpansion, visar vi att alla våra resultat för hypergrafer sträcker sig till vertex-expansion i grafer.
Cheegers ojämlikhet har nyligen generaliserats till hypergrafer av Louis REF.
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}