Alphabeta MathSupporting prerequisites · 01 — Spectral edge and vertex expansion
Presents 18 supporting prerequisites, covering published library prerequisites and dependency levels 0–3.
1 · Prerequisites
- Constant vector is a top eigenvector
- The Binomial count has its usual probability mass function
- Stirling's formula for factorials
- The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t
- The logarithm grows more slowly than every positive real power
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials
- C(n, k) k! (n-k)! = n! for k ≤ n; hence C(n, k) k! = n^k̲, the quotient n!/(k!(n-k)!) is a natural number, and C(n, k) = C(n, n-k)
- Real powers for positive bases, with the zero-base positive-exponent convention
- The Erdős-Rényi finite random graph G(n,p)
- Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1
- The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ
- The integral logarithm is unbounded above and below
- The natural logarithm as the inverse of the exponential function
- The exponential addition formula exp(x+y)=exp(x)exp(y)
- The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
- Basic identities for a probability measure
- If u,v are differentiable on [a,b] with u',v' integrable, then ∫ₐᵇ u v' = u(b)v(b)-u(a)v(a) - ∫ₐᵇ u'v
- The finite product of finite probability spaces
- Expectation of a real random variable on a finite probability space
- Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree
- Variance, standard deviation, and covariance on a finite probability space
- Finite probability spaces, outcome weights, events, and event probabilities
- The indicator random variable of an event
- The real exponential function and the number e by a power series
- 1+x≤exp(x) for every real x, hence (1-p)ᵐ≤exp(-mp)
- The exponential function is strictly increasing
- For |r| < 1, ∑_k ≥ 0 rᵏ = 1/(1-r), and for |r| ≥ 1 the series diverges
- The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖
- The adjacency matrix of a finite simple graph
- The operator norm is a norm on the space of bounded linear operators
- Eigenvalues, eigenvectors, eigenspaces E_λ(T)=ker(T-λ I), and the spectrum σ_F(T) of an endomorphism
- Benaych-Georges, Bordenave and Knowles, Spectral radii of sparse random matrices (19 September 2019) · PDF p. 3, Definition 2.1; p. 4, Theorem 2.2
- Ceilings give the least positive integer meeting a real threshold
- Real random variables on finite probability spaces and their finite distributions
- Pairwise and mutual independence of finite-valued random variables
- Angular order and elementary inverse-trigonometric bounds
- Geometric growth, truncation and total decrement budgets
- Finite vertex Hilbert space in the article convention
- Probability measures and probability spaces
- Random elements and real random variables
- Independent random elements
- Symmetric real random variables
- Expectation of a nonnegative or integrable random variable
- The integral of a nonnegative simple function
- The nonnegative integral agrees with the simple integral on simple functions
- Product weights normalize, and coordinate events are mutually independent
- A. S. Bandeira and R. van Handel, Sharp nonasymptotic bounds on the norm of random matrices with independent entries (2016) · Corollary 3.6, reprint PDF p. 15; sigma definition, p. 2; proof, p. 16
- Single-vertex degree laws and the shared-edge dependence
- Markov's inequality on a finite probability space
- Expectation factors over a finite product of mutually independent random variables
- The finite union bound
- The exponential function is smooth and (exp)'=exp
- A Bernoulli(p) variable has mean p and variance p(1-p); a binomial(n,p) variable has mean np and variance np(1-p)
- Normalization, nonnegativity, monotonicity, complements, and differences in a finite probability space
- Norm symmetrization at the actual matrix mean
- Erdős–Rényi random graph and high probability
- The exponential is positive and satisfies exp(-x)=1/exp(x)
- Centered graph matrices and reference degree
- The integral logarithm is continuous and strictly increasing on (0,∞)
- The integral logarithm L is the published natural logarithm
2 · Logical flowchart
Arrows show item dependencies. A grouped prerequisite node points to items that use one or more of its members; their exact links are listed above.
3 · Items
Definition
Spectral edge and vertex expansion
Lemma
Exact logarithmic binomial masses at bounded distance from an entropy root
Lemma
A logarithmic low-degree atom for the gamma-two graph
Lemma
A second-moment bound for the absence of low-degree vertices
Lemma
A maximum-degree tail with an explicit logarithmic exponent
Lemma
Transfer two nonbacktracking good events to the required norm bound
Lemma
Explicit parameters for the small-gamma logarithmic density
Lemma
Independent degrees into a fixed half of a random graph
Lemma
Strict numerical budgets for the two-stage PSD amplification
Lemma
Bounded symmetric matrix expectation at the variance scale
Lemma
A positive minimum degree envelope at every fixed supercritical ratio
Lemma
A rare logarithmic degree occurs with probability of its first-moment order
Lemma
The gamma-two graph has a vertex of degree at most log n with high probability
Lemma
A lower estimate for a binomial point probability
Lemma
An explicit lower bound on a sparse binomial atom
Lemma
Uniform small centered adjacency above logarithmic mean degree
Lemma
Independent cross-degrees produce a large degree at logarithmic density
Lemma