Lune

FOCS2022Top-tier venue

Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung

Abstract

The classical Cheeger's inequality relates the edge conductance φ of a graph and the second smallest eigenvalue λ 2 of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality

) and the maximum reweighted second smallest eigenvalue λ * 2 of the Laplacian matrix. In this work, we first improve their result to ψ 2 / log d λ * 2 ψ where d is the maximum degree in G, which is optimal up to a constant factor. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti.

Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analog in relating vertex expansions and reweighted eigenvalues. These include:

• An analog of Trevisan's result that relates the bipartite vertex expansion ψ B of a graph and the maximum reweighted lower spectral gap ζ * of the adjacency matrix. This implies the first approximation algorithm for bipartite vertex expansion.

• An analog of higher-order Cheeger's inequalities that relates the k-way vertex expansion ψ k of a graph and the maximum reweighted k-th smallest eigenvalue λ * k of the Laplacian matrix. This implies the first approximation algorithm for k-way vertex expansion.

• An analog of improved Cheeger's inequality that relates the vertex expansion ψ and the reweighted eigenvalues λ * 2 and λ * k . This provides an improved bound for ψ using λ * 2 , when the k-way vertex expansion ψ k is large for a small k.

Finally, inspired by this connection, we present negative evidence to the 0/1-polytope edge expansion conjecture by Mihail and Vazirani. We construct 0/1-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these 0/1-polytopes is almost linear in the graph size. This does not provide a counterexample to the conjecture, but this is in contrast with known positive results which proved poly-logarithmic mixing time to the uniform distribution on the vertices of subclasses of 0/1-polytopes.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues cites Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
  • New Approximation Bounds for Small-Set Vertex Expansion cites Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted EigenvaluesLap Chi Lau, Kam Chuen Tung, Robert WangSODA 2024 · 2 citations
  2. Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted EigenvaluesLap Chi Lau, Kam Chuen Tung, Robert WangSTOC 2023 · 1 citation
  3. New Approximation Bounds for Small-Set Vertex ExpansionSuprovat Ghoshal, Anand LouisSODA 2024

Related papers

  1. Higher-Order Cheeger Inequality for Partitioning with BuffersKonstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan VijayaraghavanSODA 2024
  2. Edge Expansion and Spectral Gap of Nonnegative MatricesJenish C. Mehta, Leonard J. SchulmanSODA 2020 · 3 citations
  3. Local and Global Expansion in Random Geometric GraphsSiqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth YangSTOC 2023 · 4 citations
  4. On the edge expansion of random polytopesAsaf Ferber, Michael Krivelevich, Marcelo Sales, Wojciech SamotijSODA 2026 · 2 citations
  5. Finding Colorings in One-Sided ExpandersRares-Darius Buhai, Yiding Hua, David Steurer, Andor Vári-KakasFOCS 2025 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines