RemarkRemark: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Disjoint-set lower mixing needs additional hypotheses

PDF p. 20: Paragraph before Lemma 3.7

Statement

A positive multiplicative lower estimate $e (X, Y) \geq ε (d^{*} / n) ∣ X ∣ ∣ Y ∣$ need not hold for every pair of disjoint vertex sets in a two-sided spectral expander. Indeed, the four-cycle is a $(4, 2, 1, 0, 1)$ -expander and has two disjoint singleton sets $X, Y$ for which $e (X, Y) = 0$ . Thus every $ε > 0$ fails for these sets. Here the four-cycle has vertices $1, 2, 3, 4$ and edges ${1, 2}, {2, 3}, {3, 4}, {4, 1}$ ; its two-sided parameters mean the centered adjacency norm is at most $α d^{*}$ and the centered Laplacian lies between $c^{-} d^{*} I$ and $c^{+} d^{*} I$ in quadratic-form order.

Statement references

Two-sided spectral expander — Definition 1.9

Oriented edge count between sets

Adjacency, degrees, graph Laplacian, and spectral notation

Facts & Assumptions

[F1]

For a graph with adjacency matrix $A$ , degree matrix $D$ , Laplacian $L = D - A$ , and all-ones matrix $J$ , the centered matrices are $Δ_{A} = A - (d^{*} / n) J$ and $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ . The expander conditions are the norm and quadratic-form inequalities stated above (Two-sided spectral expander — Definition 1.9, Adjacency, degrees, graph Laplacian, and spectral notation).

[F2]

The ordered edge count is $e (X, Y) = \sum_{x \in X} \sum_{y \in Y} A_{x y}$ (Oriented edge count between sets).

[F3]

Cauchy–Schwarz bounds $∣ v^{*} z ∣$ by $∥ v ∥_{2} ∥ z ∥_{2}$ , and the operator norm is the maximum of $∥ B z ∥_{2}$ over unit vectors $z$ (Cauchy–Schwarz: |⟨ u,v⟩|≤‖ u‖‖ v‖, with equality exactly for linearly dependent vectors, The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖).

Proof

Given: The four-cycle and its vertex ordering as in the statement.

Goal: Verify the expander parameters and exhibit disjoint sets violating the proposed lower estimate.

1.1givenF1algebra

Put $v = (1, - 1, 1, - 1)^{T}$ . Direct inspection of the edges gives $A = (J - v v^{T}) / 2$ and $D = 2 I$ . With $n = 4$ and $d^{*} = 2$ , the centered-matrix formulas give $Δ_{A} = - v v^{T} / 2$ and $Δ_{L} = v v^{T} / 2$ . Also $v^{*} v = 4$ .

2.1F1F3step 1.1

For every complex vector $z$ , Cauchy–Schwarz gives $0 \leq z^{*} Δ_{L} z = ∣ v^{*} z ∣^{2} / 2 \leq 2 ∥ z ∥_{2}^{2}$ , so $0 ⪯ Δ_{L} ⪯ 2 I$ . Likewise $∥ Δ_{A} z ∥_{2} = ∥ v ∥_{2} ∣ v^{*} z ∣ / 2 \leq 2 ∥ z ∥_{2}$ , giving $∥ Δ_{A} ∥ \leq 2$ . These are the required inequalities for $(n, d^{*}, α, c^{-}, c^{+}) = (4, 2, 1, 0, 1)$ .

3.1F2step 2.1algebra∎

Take $X = {1}$ and $Y = {3}$ . They are disjoint and their vertices are not adjacent, so $e (X, Y) = A_{13} = 0$ . For every $ε > 0$ , the proposed right-hand side equals $ε (2 / 4) ∣ X ∣ ∣ Y ∣ = ε / 2 > 0$ . Hence the estimate fails for these sets, despite the verified expander conditions.

Source notes

The observation that additional set assumptions are needed is attributed to the paragraph immediately before Lemma 3.7 in Expander graphs are globally synchronizing. The example and its verification above are local.

Depends on

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Expander graphs are globally synchronizing · PDF page 20, paragraph immediately before Lemma 3.7