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.

Strict forms of the nested mixing estimates — Remark 3.9

PDF p. 22: Remark 3.9

Statement

Let $G = (V, E)$ be an $(n, d^{*}, α, c^{-}, c^{+})$ -expander as in Two-sided spectral expander — Definition 1.9, with $d^{*} > 0$ and $c^{+} \neq c^{-}$ . Thus $n = ∣ V ∣ > 0$ . For vertex subsets $P, Q$ , let $e (P, Q)$ be the ordered adjacency count and $P^{c} = V ∖ P$ as in Oriented edge count between sets. Let $ε > 0$ and put $δ = ε / (c^{+} - c^{-})$ . If $X \subseteq Y \subseteq V$ , $∣ Y ∣ \leq n / 2$ , and $∣ Y ∣ < (1 + δ) ∣ X ∣$ , then the two bounds in Lemma 3.7 become strict:

$(1 + c^{-} - ε) \frac{d^{*}}{n} ∣ X ∣ ∣ Y^{c} ∣ < e (X, Y^{c}) < (1 + c^{+} + ε) \frac{d^{*}}{n} ∣ X ∣ ∣ Y^{c} ∣ .$

If in addition $α > 0$ , $ρ > 0$ , $∣ X ∣ \leq ρ α n$ , and $1 + c^{-} - ε > 0$ , then the bound in Lemma 3.8 also becomes strict:

$e (X, Y^{c}) > \frac{1 + c^{-} - ε}{2 (1 + ρ) α} e (X, X) .$

For a phase configuration $θ \in R^{V} / (2 π Z)^{V}$ and angles $β, γ \in [0, π]$ , these conclusions apply with $X = C_{β} (θ)$ and $Y = C_{γ} (θ)$ whenever these phase-tail sets are nested and satisfy the displayed hypotheses. Here $C_{ψ} (θ) = {x \in V : \cos θ_{x} \leq \cos ψ}$ for $0 \leq ψ \leq π$ , as in Phase tail sets for amplification. The stronger size hypotheses $∣ C_{γ} ∣ < n / 2$ , $∣ C_{γ} ∣ < (1 + δ) ∣ C_{β} ∣$ , and, for the second conclusion, $∣ C_{β} ∣ < ρ α n$ are sufficient when the other stated conditions also hold.

Facts & Assumptions

[F1]

The expander definition gives $n > 0$ and $c^{-} d^{*} I ⪯ Δ_{L} ⪯ c^{+} d^{*} I$ , where order means nonnegative quadratic-form difference (Two-sided spectral expander — Definition 1.9).

[F2]

For any subset $Z$ , put $q (Z) = ∣ Z ∣ ∣ Z^{c} ∣$ . Its centered cut count $e (Z, Z^{c}) - (d^{*} / n) q (Z)$ lies between $c^{-} (d^{*} / n) q (Z)$ and $c^{+} (d^{*} / n) q (Z)$ (Cut-edge mixing bound — Lemma 3.4). For nested $X \subseteq Y$ , twice $e (X, Y^{c})$ equals the cut counts of $X$ and $Y$ minus that of $Y ∖ X$ (Nested-cut polarization identity).

[F3]

Internal-edge mixing gives $e (X, X) \leq (d^{*} / n) ∣ X ∣^{2} + α d^{*} ∣ X ∣$ (Internal-edge mixing bound — Lemma 3.3). Edge counts are nonnegative finite sums of adjacency entries (Oriented edge count between sets).

[F4]

Lemmas 3.7 and 3.8 give the corresponding non-strict estimates under their stated hypotheses (Mixing for two nearby nested sets — Lemma 3.7, Relative mixing for a small nested set — Lemma 3.8).

Proof

Given: The expander, parameters and nested sets in the statement.

Goal: Establish the strict estimates and their phase-tail specialization.

1.1F1algebra

Testing the difference of the order bounds in [F1] on a nonzero vector gives $(c^{+} - c^{-}) d^{*} \geq 0$ . Since $d^{*} > 0$ and $c^{+} \neq c^{-}$ , $w : = c^{+} - c^{-} > 0$ and $δ = ε / w > 0$ . Put $a = ∣ X ∣$ , $b = ∣ Y ∖ X ∣$ , and $c = ∣ Y^{c} ∣$ . The strict size condition says $b < δ a$ , so $a > 0$ . Also $a \leq ∣ Y ∣ \leq n / 2 \leq c$ , hence $c > 0$ .

2.1F2step 1.1algebra

The three sets $X$ , $Y ∖ X$ , and $Y^{c}$ partition $V$ . Thus $q (X) = a (b + c)$ , $q (Y) = (a + b) c$ , $q (Y ∖ X) = b (a + c)$ , and $q (X) + q (Y) - q (Y ∖ X) = 2 a c$ . Applying [F2] to the three centered cuts, with the bound reversed for the subtracted cut, gives $c^{-} (d^{*} / n) a c - (d^{*} / 2 n) w b (a + c) \leq e (X, Y^{c}) - (d^{*} / n) a c \leq c^{+} (d^{*} / n) a c + (d^{*} / 2 n) w b (a + c)$ .

3.1F4step 1.1step 2.1algebra

Because $b < δ a$ , $a + c > 0$ , and $a \leq c$ , we have $w b (a + c) / 2 < w δ a (a + c) / 2 \leq ε a c$ . Multiplication by $d^{*} / n > 0$ and substitution into step 2.1 proves both strict bounds. These refine the non-strict bounds recorded in [F4].

4.1F3F4step 1.1step 3.1algebra

For the additional hypotheses set $k = 1 + c^{-} - ε > 0$ . By [F3] and $a / n \leq ρ α$ , $e (X, X) \leq d^{*} a (a / n + α) \leq (1 + ρ) α d^{*} a$ . Step 3.1 and $c \geq n / 2$ give $e (X, Y^{c}) > k (d^{*} / n) a c \geq k d^{*} a / 2$ . Since $2 (1 + ρ) α > 0$ , the preceding internal-edge bound gives $k d^{*} a / 2 \geq k e (X, X) / (2 (1 + ρ) α)$ , proving the strict relative bound refining [F4].

5.1step 3.1step 4.1algebra∎

The phase-tail definition identifies each displayed $C_{ψ} (θ)$ as a subset of $V$ . Substituting the two nested sets into steps 3.1 and 4.1 proves the specialization; each strict size hypothesis in the last sentence implies the corresponding weak hypothesis used above.

Source notes

Remark 3.9 of the cited article attributes the strictness observation. The estimates above are derived from the declared cut and internal-edge bounds. The conditions $d^{*} > 0$ and, for the relative estimate, $1 + c^{-} - ε > 0$ make the strictness argument explicit under the frozen expander definition; the article attribution alone is not used as proof.

Depends on

Used by · 2

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. 22, Remark 3.9; pp. 24–26, amplification argument