Theorem B.6 — induced-subgraph spectral counterexample
OpenClusterDecomp.Supplement.theorem_B_6Fix an integer and a constant for which condition (21) has -regular solutions for arbitrarily large . Then , and there are constants and such that, for every , every -regular graph satisfying (21), and every choice of distinct hosts in Definition B.2, the graph and its bipartition satisfy
Consequently, for every fixed , tends uniformly to zero along these graphs. Hence Lemma B.1 is false. Moreover, even on finite simple unweighted positive-degree graphs whose two parts each have at least two vertices and positive internal degree, there are no constants and such that every bipartition obeys
This separates ordinary induced subgraphs from the degree-preserving subgraphs used by the repaired statement earlier in the paper.
Differences from the source:
- generalization: the chosen expander graph and hosts used to define each → every -regular satisfying (21) and every injective host choice; reason: Propositions B.4 and B.5 use only regularity, (21), and distinct hosts, so the statement specializes to every family chosen by the source
- encoding: "for all sufficiently large ", , and convergence to zero → explicit threshold, absolute-bound, and epsilon quantifiers, all uniform over and the hosts; reason: this is the quantifier-explicit meaning of the three asymptotic clauses
- generalization: falsity for all graphs and the absence of a positive-power bound → falsity already on finite simple unweighted positive-degree graphs and bipartitions with positive-degree induced parts and in-range eigenvalues; reason: the constructed belong to this subclass, so negating the universal bound on the subclass is stronger and implies the source claim without invoking junk eigenvalue values
- encoding: and → weight restriction with no added loop and the one-indexed kth-smallest real root of the normalized-Laplacian characteristic polynomial; reason: this is exactly the paper's ordinary induced graph and eigenvalue convention
import Mathlib import Definitions.Def_ClusterDecomp_Supplement_Gn import Definitions.Def_ClusterDecomp_Supplement_LemmaB1 open Finset
namespace ClusterDecomp.Supplement
open ClusterDecomp
/-- **Theorem B.6 (counterexample to [OGT14, Lemma 1.1]).**
Sun, Zhang, Zhou, *Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee*, STOC 2027
submission (manuscript sha256 ba091f54…), Theorem B.6, p.38 (PDF p.40), under the standing
choice of `d`, `h` and the expander family in (21), p.36 (PDF p.38).
For every fixed integer `d ≥ 3` and `h ∈ (0,1]` admitting infinitely many `d`-regular graphs
satisfying (21), the graphs `G_n` of Definition B.2 have, uniformly over the choice of the graph
`X` and the distinct hosts,
* `λ₂(L_{G_n[P_i]}) ≥ c*²/2` for both parts and all sufficiently large `n`;
* `λ₃(L_{G_n}) = O(n⁻¹⁄²)`, and hence `2 c₀ 3⁶ λ₃(L_{G_n}) → 0` for every fixed
`c₀ > 0`.
Consequently Lemma B.1 is false. More strongly, there is no exponent `γ > 0` and universal
constant `C > 0` for which every graph and bipartition satisfies
`min_i λ₂(L_{G[P_i]}) ≤ C λ₃(L_G)^γ`.
**Formalization Note.**
* The first conjunct spells out "sufficiently large" as `∃ N, ∀ n ≥ N` and big-O as one
`C > 0` quantified before `n`, `X` and the hosts. The second conjunct is the uniform epsilon
definition of the displayed convergence to zero; `c₀` is quantified as the positive constant
appearing in the refuted Lemma B.1.
* `X` ranges over every simple `d`-regular graph satisfying (21), and `x,y` over every injective
choice of the `⌊√n⌋` hosts. This generalizes a fixed expander family, and the proof of
Propositions B.4–B.5 uses only these hypotheses.
* The two negated universal bounds are restricted to finite simple unweighted positive-degree graphs
and partitions whose induced parts have positive degree, with the eigenvalue indices in range.
These are exactly the non-junk instances of `L_G`, `λ₃(L_G)` and `λ₂(L_{G[P_i]})`. Restricting
the class inside a universally quantified claim makes its negation stronger; every `G_n` used by
the counterexample belongs to this class.
* `G[P_i]` is the ordinary induced subgraph `induced G (P i)`, never the degree-preserving `G{P_i}`;
the latter is the repaired statement proved earlier in the paper. -/
theorem theorem_B_6 :
∀ (d : ℕ) (h : ℝ), 3 ≤ d → 0 < h → h ≤ 1 → ExpanderFamily d h →
0 < cStar d h ∧
(∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
∀ (X : SimpleGraph (Fin n)), IsDRegular X d → Expands21 X d h →
∀ (x y : Fin (Nat.sqrt n) → Fin n), Function.Injective x → Function.Injective y →
cStar d h ^ 2 / 2 ≤ lam (induced (Gn X x y) (P1 n)) 2 ∧
cStar d h ^ 2 / 2 ≤ lam (induced (Gn X x y) (P2 n)) 2 ∧
lam (Gn X x y) 3 ≤ C / Real.sqrt n) ∧
(∀ c0 : ℝ, 0 < c0 → ∀ δ : ℝ, 0 < δ → ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
∀ (X : SimpleGraph (Fin n)), IsDRegular X d → Expands21 X d h →
∀ (x y : Fin (Nat.sqrt n) → Fin n), Function.Injective x → Function.Injective y →
2 * c0 * (3 : ℝ) ^ 6 * lam (Gn X x y) 3 ≤ δ) ∧
¬ LemmaB1 ∧
¬ ∃ γ : ℝ, 0 < γ ∧ ∃ C : ℝ, 0 < C ∧
∀ (V : Type) [Fintype V] [DecidableEq V] (G : WGraph V),
IsUnweighted G → G.PosDeg → 3 ≤ Fintype.card V →
∀ P : Fin 2 → Finset V,
(Pairwise fun i j => Disjoint (P i) (P j)) →
(∀ v, ∃ i, v ∈ P i) →
(∀ i, 2 ≤ (P i).card) →
(∀ i, (induced G (P i)).PosDeg) →
∃ i, lam (induced G (P i)) 2 ≤ C * Real.rpow (lam G 3) γ := by sorry
end ClusterDecomp.Supplement