PaperlayerView exact revision on arXiv

Source-linked AI summary

A sharp higher-order Cheeger inequality

Yunpeng Li

arXiv:2609.35369v2math.COcs.DSmath.SP

TL;DR

The paper addresses whether the higher-order Cheeger bound can provide k disjoint sets at spectral index k, rather than only a constant fraction of k. It combines cut improvement with adaptive spectral localization; the logarithmic exponent is sharp.

  • Problem

    Earlier results with logarithmic dependence provided only a constant fraction of k sets, leaving open whether the same dependence holds for k sets at spectral index k.

    Source: §1 · p. 2

  • Method

    The proof combines cut improvement with adaptive spectral localization, using a fixed threshold in the construction.

    Source: §1 · p. 2, §5 · p. 8

  • Results

    The bound improves by a factor of log k, and the exponent 1/2 on the logarithm cannot be decreased.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The construction gives k disjoint sets at spectral index k, matching the count of sets to the eigenvalue index.

    Source: §1 · p. 2

    The construction is presented for k ≥ 2 and λ_k > 0; the remaining cases are handled separately in the theorem proof.

    Source: §5 · p. 8

Abstract

from arXiv · show

Let $\lambda_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph $G$ with positive degrees, where $k$ is an integer satisfying $1\le k\le |V(G)|$. Let $\varphi_k(G)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove $\varphi_k(G)\le C\sqrt{\lambda_k(G)\log(k+1)}$ for an absolute constant $C$. The number of sets and the spectral index are both $k$, and conductance is measured in the original graph. The logarithmic dependence is optimal up to an absolute constant. The proof combines geometric partitioning of the spectral embedding with minimum-cut improvement and adaptive projections in coefficient space. A single conductance threshold is used throughout the construction. The resulting maps have disjoint supports, and the sum of their Gram matrices is bounded below by an absolute positive multiple of the identity. A dyadic maximal estimate bounds the sum of their internal energies uniformly over unit coefficient vectors. A dimension argument using local eigenvalues then yields exactly $k$ disjoint sparse cuts.

1 Introduction

The paper improves the higher-order Cheeger bound while keeping the number of sets equal to the spectral index, k. Its proof combines cut improvement with adaptive spectral localization, and the logarithmic exponent is shown to be sharp.

1 Introduction

  • Earlier bounds with the same logarithmic dependence produced only a constant fraction of k sets, leaving open whether all k were possible at spectral index k.Source: §1 · p. 2
  • The bound is improved by a factor of log k while the number of sets and the spectral index both remain k.Source: §1 · p. 2
  • The exponent 1/2 on the logarithm cannot be decreased; the noisy-hypercube example gives a lower bound at spectral index k.Source: §1 · p. 2

1.1 Proof overview

  • Adaptive selection retains spectral directions with little mass on previously selected sets, so boundary contributions are controlled without increasing the fixed threshold.Source: §1.1 · p. 3
  • A trace estimate reduces the active dimension by a constant factor, and the selected maps’ Gram matrices sum to at least an absolute positive multiple of the identity.Source: §1.1 · p. 3
  • A dyadic maximal estimate bounds total internal energy, and local eigenvalue counts with Cheeger rounding yield exactly k disjoint sparse cuts.Source: §1.1 · p. 3

2 Notation and preliminaries

The preliminaries set the weighted graph and spectral conventions used in the proof. They also define local operators, spectral embeddings, and the rounding tools connecting energy to conductance.

2 Notation and preliminaries

  • The graph is finite, undirected, and weighted, with positive degrees; the random-walk Laplacian is self-adjoint in the degree-weighted inner product and has the same spectrum as the normalized Laplacian.Source: §2 · p. 3
  • For a nonzero function, the Rayleigh quotient is its energy divided by its squared degree-weighted norm.Source: §2 · p. 3
  • The local graph on S retains internal edges and adds outgoing weight to loops, preserving original degrees; its operator is distinct from the Dirichlet operator.Source: §2 · p. 4
  • The first k eigenfunctions define a spectral embedding, and restricting FZ to a vertex set gives a weighted Gram matrix of the map’s columns there.Source: §2 · p. 4
  • Coarea and Cheeger rounding relate function energy to a conductance bound, including for the local graph on a set.Source: §2 · p. 4

3 Cut improvement at a fixed threshold

Cut improvement selects a set at a fixed threshold and gives it a boundary stability property. That property also controls boundary mass when functions are rounded locally.

3 Cut improvement at a fixed threshold

  • In the cut-improvement lemma, a minimizing set S (with the empty set allowed) satisfies, for every T ⊆ S, w(T, Sc) ≤ τ vol(T) + w(T, S \\ T).Source: §3 · p. 5
  • The same minimization controls spectral mass rejected by S for functions supported in B.Source: §3 · p. 5
  • The minimization is a source–sink minimum cut with source capacities τd_v, sink capacities w(v, Bc), and original capacities on internal edges.Source: §3 · p. 5
  • The boundary-mass inequality transfers local conductance to original-graph conductance, with the local boundary term accounting for the difference.Source: §3 · p. 5

4 Geometric partitioning of the embedding

The section partitions the spectral embedding into random cells, controlling both cell Gram-matrix tails and the cost of edges separated by the partition. Random-ball partitions supply the geometric separation bound.

4 Geometric partitioning of the embedding

  • The random partition is designed to bound bad-cell mass, where a cell is bad when its Gram matrix has a large sum of eigenvalues beyond the largest.Source: §4 · pp. 6–7
  • Random balls produce cells of diameter at most 2r, with separation probability bounded using the symmetric difference of the two radius-r balls relative to their union.Source: §4 · p. 6
  • For fixed δ and β, the choice of Γ with independent N(0, 1/q) entries lets Lemma 4.1 apply to unnormalized points Γa_v for v∈R with y_v≠0, using q=O_{δ,β}(log(k+1)).Source: §4 · p. 7
  • Discarding whole bad cells creates no new boundary inside retained cells, and their vertices remain available for later stages.Source: §4 · p. 8

5 Adaptive selection of vertex sets

The construction repeatedly selects disjoint, τ-stable sets while retaining coefficient directions that remain concentrated on unassigned vertices. Across O(log(k + 1)) stages, the selected maps have disjoint supports and their Gram matrices sum to a uniform lower bound.

5.1 One selection step

  • The selection step bounds the remaining mass and energy using the spectral embedding and previously selected sets.The reverse triangle inequality bounds the energy of the scalar function α by ℓλ_k, while contributions from earlier sets are controlled using their disjoint internal edges.Source: §5.1 · pp. 8–9
  • At each selection step, geometric partitioning and cut improvement produce disjoint nonempty τ-stable sets from the remaining vertices.The threshold τ is fixed throughout the construction; vertices not selected remain available for later steps.Source: §5 · p. 8, §5.1 · p. 9

5.2 The sum of the Gram matrices

  • At step j, Πj projects within ran Πj−1 onto eigenvalues strictly greater than 1 − ε, so Πj ⪯ Πj−1; N is the first step with ΠN = 0.Source: §5.2 · p. 10
  • The selected maps have pairwise disjoint supports, and their Gram matrices sum to at least an absolute positive multiple of the identity.The selected and remaining Gram matrices add exactly, and the discarded coefficient spaces are orthogonal.Source: §5.2 · p. 10

6 Internal energy and exactly k sets

A dyadic maximal estimate controls the total internal energy of the selected maps, uniformly over coefficient vectors. Combined with Gram-matrix bounds, a local-eigenvalue dimension argument yields exactly k disjoint sparse sets.

6 Internal energy and exactly k sets

  • The dyadic maximal estimate bounds the sum of internal energies by controlling the maximum over nested coefficient projections.Its bound depends on the number of stages through s_N = 2 + ⌈log_2(N + 1)⌉; coefficient-space orthogonality is sufficient.Source: §6 · p. 11
  • Applying the maximal estimate to the edge-gradient map controls all selected sets because each edge lies inside at most one set.The operator norm of the edge-gradient map is bounded by λ_k.Source: §6 · p. 11
  • The dimension argument counts local eigenvalues up to a cutoff, truncated at two, then converts each count into one or two sparse sets.For a count of two, local Cheeger rounding gives two disjoint sets; retaining any k of the resulting sets yields the target count.Source: §6 · p. 12
  • The construction’s Gram-matrix and internal-energy bounds meet the hypotheses of the local-eigenvalue counting argument, yielding exactly k disjoint sets.The theorem proof applies the counting lemma with the construction’s fixed threshold and specified parameters.Source: §6 · pp. 11–12

7 Sharpness of the logarithmic factor

Section 7 gives a weighted noisy-hypercube example for checking the lower bound at the same spectral index. Its argument combines the graph’s eigenvalue calculation with a conductance floor for any family of k disjoint sets.

7 Sharpness of the logarithmic factor

  • For each k ≥3, the example is a weighted graph on {0, 1}^k with Hamming-distance weights and loops.The weights are w_xy = ζ^|x−y|, with ζ = (log 2)/log k.Source: §7 · p. 13
  • The graph’s transition operator is Boolean noise with correlation ρ = (1−ζ)/(1+ζ), and its Walsh-character eigenvalues are ρ^j.The common degree is (1+ζ)k.Source: §7 · p. 13
  • The first nonzero Laplacian eigenvalue has multiplicity k, and λ_k(G) = 2ζ/(1+ζ).The section identifies this as checking the lower bound at the same spectral index.Source: §7 · p. 13
  • Every family of k disjoint nonempty sets contains a set of measure at most 1/k, whose conductance is therefore at least 1/2.This is the lower-bound step stated for the example in Proposition 7.1.Source: §7 · p. 13

Disclosure of AI assistance

The manuscript discloses that OpenAI’s ChatGPT and Codex (GPT-6) were used in developing the proof and preparing the manuscript.

Disclosure of AI assistance

  • OpenAI’s ChatGPT and Codex (GPT-6) were used to develop the proof and prepare the manuscript.The human author takes full responsibility for the mathematical arguments and final manuscript.Source: Disclosure of AI assistance · p. 13
Loading 2609.35369v2…