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.

Failure of symmetric Laplacian control near threshold

PDF p. 6: Section 1 expansion motivation; PDF p. 8: Section 1.4 asymmetric expansion; PDF p. 32: Figure 3 and following prose

Statement

Fix $γ > 1$ , put $p = γ \log n / n$ and $d^{*} = p n$ , and let $G (n, p)$ be the loop-free random graph on $[n]$ in which distinct edges occur independently with probability $p$ . Let $A$ be its adjacency matrix, $D$ its diagonal degree matrix, $L = D - A$ , $J$ the all-ones matrix, and $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ as in Centered graph matrices and reference degree. The norm is the Euclidean induced operator norm.

Let $h (c) = (1 + c) \log (1 + c) - c$ for $c > - 1$ . For $γ > 1$ , write $c^{-} (γ) \in (- 1, 0)$ and $c^{+} (γ) > 0$ for the two roots of $h (c) = 1 / γ$ , as in Degree large-deviation rate function and roots. They satisfy $c^{+} (γ) > - c^{-} (γ)$ , with endpoint values $c^{-} (1) = - 1$ and $c^{+} (1) = e - 1$ . The upper root equals $1$ exactly at $γ_{0} = 1 / (2 \log 2 - 1)$ , approximately $2.5886$ .

For every fixed $c < c^{+} (γ)$ , the probability of $∥ Δ_{L} ∥ \leq c d^{*}$ tends to zero as $n \to \infty$ . In particular, for $1 < γ < 2.5886$ , any fixed constant $c$ for which this symmetric norm bound holds with probability tending to one must exceed $1$ . Such a bound with $c > 1$ does not by itself imply connectivity. These asymmetric degree deviations motivate separate lower and upper Laplacian bounds.

Facts & Assumptions

[F1]

The centered matrix has $Δ_{L} = L - d^{*} I + (d^{*} / n) J$ ; in the loop-free graph $L_{x x} = d (x)$ , the degree of vertex $x$ (Centered graph matrices and reference degree).

[F2]

For fixed $γ > 1$ , the maximum degree satisfies $d_{\max} / d^{*} \to 1 + c^{+} (γ)$ in probability (Extremal-degree asymptotics near connectivity).

[F3]

The two roots are unique on their respective branches; $c^{+}$ is strictly decreasing, $c^{+} > - c^{-}$ , and their endpoint values are $e - 1$ and $- 1$ at $γ = 1$ (Degree large-deviation rate function and roots, Monotonicity, endpoints, and asymmetry of the rate roots).

[F4]

The induced operator norm is nonnegative. For $b \geq 0$ , a real symmetric matrix with operator norm at most $b$ has every diagonal entry at most $b$ (Self-adjoint order, norm bounds and diagonal tests).

[F5]

The natural logarithm satisfies $\log 2 = \int_{1}^{2} d t / t$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t).

[F6]

A graph is connected when its vertex set is nonempty and every two vertices are joined by a path (Connected graphs and connected components defined by the existence of vertex paths).

Proof

Given: Fixed $γ > 1$ and the graph sequence in the Statement.

Goal: Establish the root threshold, the probabilistic obstruction to a symmetric norm bound, and the connectivity limitation.

1.1F3F5algebra

Direct substitution gives $h (1) = 2 \log 2 - 1 > 0$ . By the upper-branch uniqueness and strict decrease in [F3], $c^{+} (γ) = 1$ exactly when $γ = γ_{0} = 1 / (2 \log 2 - 1)$ , and $c^{+} (γ) > 1$ when $γ < γ_{0}$ . To locate the threshold, substitute $t = (1 + x) / (1 - x)$ in [F5] and expand the finite geometric sum: $\log 2 = 2 \sum_{k = 0}^{4} 1 / ((2 k + 1) 3^{2 k + 1}) + R$ , where $0 < R < 9 / (4 \cdot 11 \cdot 3^{11})$ . Thus $\log 2 < 189094979 / 272806380 < 0.69315$ , and in fact $2.5886 (2 \log 2 - 1) < 97427117861 / 97430850000 < 1$ . Hence $2.5886 < γ_{0}$ ; the stated decimal is an approximation to $γ_{0}$ . The asymmetry and endpoint assertions are [F3].

2.1F1F2F4step 1.1

For $n \geq 2$ , $d^{*} = γ \log n > 0$ . If $c < 0$ , then $c d^{*} < 0 \leq ∥ Δ_{L} ∥$ by [F4], so the norm-bound event is empty and has probability zero. Now suppose $0 \leq c < c^{+} (γ)$ , so $b = c d^{*} \geq 0$ . By [F1], the diagonal entry at a maximum-degree vertex is $d_{\max} - d^{*} + d^{*} / n$ . If $∥ Δ_{L} ∥ \leq c d^{*}$ , [F4] applies with this $b$ and implies $d_{\max} / d^{*} - 1 + 1 / n \leq c$ . By [F2], the left side converges in probability to $c^{+} (γ)$ . Therefore, for each fixed $c < c^{+} (γ)$ , the probability of the norm bound tends to zero. In the stated range, step 1.1 gives $c^{+} (γ) > 1$ , so a fixed constant yielding the bound with probability tending to one must be greater than $1$ .

3.1F1F4F6algebra∎

The norm bound alone does not imply connectivity when $c > 1$ : for the empty graph on $n \geq 2$ vertices and any $d^{*} > 0$ , $L = 0$ and $Δ_{L} = - d^{*} I + (d^{*} / n) J$ . This matrix has eigenvalue $0$ on constant vectors and $- d^{*}$ on their orthogonal complement, so its norm is $d^{*}$ . Two distinct vertices exist because $n \geq 2$ , and no path joins them because the graph has no edges. By [F6], the graph is disconnected. Thus separate lower and upper bounds can convey information that a symmetric bound with such a constant does not.

Source notes

The asymmetric-expansion motivation, Figure 3 and the original norm-bound observation are attributed to Expander graphs are globally synchronizing, PDF pp. 6, 8 and 32. The proof above gives a fixed-constant, high-probability interpretation using the independently supplied degree result; it does not assert an exact limiting Laplacian norm.

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 pp. 6 and 8, expansion motivation; p. 32, Figure 3 and following paragraph