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.

Cheeger lower bound — Remark 3.5

PDF p. 20: Remark 3.5

Statement

Let $G = (V, E)$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander with $n \geq 2$ . Its unnormalized edge isoperimetric constant, also called its Cheeger constant, is $h (G) = \min_{0 < ∣ X ∣ \leq n / 2} e (X, X^{c}) / ∣ X ∣$ , where $X \subseteq V$ , $X^{c} = V ∖ X$ , and $e (X, X^{c})$ counts each edge crossing the cut once. Then

$h (G) \geq \frac{(1 + c^{-}) d^{*}}{2} .$

Here $G$ is called connected when the graph on $V$ obtained by deleting all self-loops is connected, meaning that every two vertices are joined by a path.

If $d^{*} > 0$ and $c^{-} > - 1$ , then $G$ is connected. Conversely, a connected graph admits a choice of expander parameters with $c^{-} > - 1$ , but connectivity does not force every admissible prescribed lower parameter to exceed $- 1$ .

Statement references

Two-sided spectral expander — Definition 1.9

Oriented edge count between sets

Edge isoperimetric constant convention

Connected graphs and connected components defined by the existence of vertex paths

Facts & Assumptions

[F1]

For every $X \subseteq V$ , the cut estimate gives $e (X, X^{c}) \geq (1 + c^{-}) (d^{*} / n) ∣ X ∣ ∣ X^{c} ∣$ (Cut-edge mixing bound — Lemma 3.4).

[F2]

The cut count is nonnegative, and for $n \geq 2$ the Cheeger constant is the minimum of the displayed quotients over the nonempty family of admissible subsets (Oriented edge count between sets, Edge isoperimetric constant convention).

[F3]

For an expander with $n \geq 2$ and a positive reference parameter, $c^{-} > - 1$ implies connectivity. Conversely, if such an expander is connected, it admits a choice of expander parameters whose lower parameter exceeds $- 1$ . An arbitrary prescribed admissible lower parameter need not exceed $- 1$ , as shown by the $K_{2}$ example. Connectivity and the lower Laplacian parameter

[F4]

Connectedness in the loop-free graph means that every two vertices are joined by a path; this is the connectedness convention used for $G$ after deleting its self-loops. Connected graphs and connected components defined by the existence of vertex paths

[F5]

For every finite real symmetric matrix $B$ , its induced operator norm is finite and nonnegative, and $- ∥ B ∥ I ⪯ B ⪯ ∥ B ∥ I$ . Self-adjoint order, norm bounds and diagonal tests

Proof

Given: An expander $G$ with $n \geq 2$ , and, for the connectivity implication, $d^{*} > 0$ .

Goal: Prove the Cheeger lower bound and the qualified connectivity statements.

1.1F1F2algebra

Put $t = (1 + c^{-}) d^{*}$ . If $t \geq 0$ , take any admissible $X$ . Since $∣ X^{c} ∣ / n = 1 - ∣ X ∣ / n \geq 1 / 2$ , [F1] gives $e (X, X^{c}) / ∣ X ∣ \geq t ∣ X^{c} ∣ / n \geq t / 2$ . Taking the minimum using [F2] yields $h (G) \geq t / 2$ .

1.2givenF3F4

If the given representation has $d^{*} > 0$ and $c^{-} > - 1$ , the positive-reference implication of [F3] gives connectivity in the convention of [F4].

1.3givenF4F5choosealgebra

Conversely, suppose $G$ is connected. In the notation of the expander definition, $A$ and $L$ are finite real symmetric matrices, as are $I$ and $J$ . Choose ${\tilde{d}}^{*} = 1$ , put $α_{0} = ∥ A - J / n ∥$ and $b = ∥ L - I + J / n ∥$ , and set $c_{0}^{-} = - b$ , $c_{0}^{+} = b$ . These are finite real parameters by [F5]. The adjacency norm inequality holds with equality, and [F5] gives $- b I ⪯ L - I + J / n ⪯ b I$ . Thus $G$ is an $(n, 1, α_{0}, c_{0}^{-}, c_{0}^{+})$ -expander with positive reference parameter, independently of its original $d^{*}$ (Two-sided spectral expander — Definition 1.9).

2.1F2step 1.1algebra

If $t < 0$ , every admissible quotient is nonnegative by [F2], so $h (G) \geq 0 > t / 2$ . Together with step 1.1 this proves the bound without an additional sign assumption on $t$ .

3.1F3F4step 1.3∎

Apply the converse in [F3] to the connected positive-reference expander constructed in step 1.3. All its stated hypotheses now hold, so it provides a choice of expander parameters with lower parameter greater than $- 1$ , as claimed. The $K_{2}$ example in [F3] supplies the limitation for arbitrary prescribed lower parameters.

Source notes

Remark 3.5 of Expander graphs are globally synchronizing states the Cheeger bound and describes $c^{-} > - 1$ as equivalent to connectivity. The qualification above accounts for nonoptimal admissible lower parameters; the cited article supplies attribution, not the proof.

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 p. 20, Remark 3.5