Alphabeta MathRandom graphs and matrix concentration
Develop degree tails, trace and Gaussian estimates, and concentration; connect them to regular spectra, connectivity and synchronization thresholds with each input's model and asymptotic range.
1 · Prerequisites
- Sequences, convergence, Cauchyness, monotonicity, boundedness and closed intervals in an arbitrary ordered field
- Rational powers aʳ of a positive base
- Monotonicity of r ↦ aʳ and of a ↦ aʳ
- Laws of rational exponents
- The binomial theorem in ℝ: (x+y)ⁿ = ∑_k<n+1 iotaC(n, k) xᵏ y^ n-k
- The Dedekind reals are Archimedean
- The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
- Principal inverse sine and inverse cosine
- The natural logarithm as the inverse of the exponential function
- For -1<y<1, (arcsin y)ᵖʳⁱᵐᵉ=1/√1-y² and (arccos y)ᵖʳⁱᵐᵉ=-1/√1-y²
- Parity and the Pythagorean identity for sine and cosine
- The mean value theorem, as the case g(x) = x of Cauchy's: for f continuous on [a,b] with a < b and differentiable on (a,b) there is c ∈ (a,b) with f(b) - f(a) = f'(c)(b-a)
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- Single-vertex degree laws and the shared-edge dependence
- Chernoff bound for independent bernoulli trials
- The finite union bound
- Finite vertex Hilbert space in the article convention
- Rectangular matrix multiplication and the identity matrix Iₙ, including zero-sized shapes
- The trace tr(A) as the sum of the diagonal entries
- Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis
- Independent random elements
- Expectations factor over finite products of independent random variables
- Change of variables for expectation
- Random elements and real random variables
- The operator norm as the least bound and as the unit-sphere or unit-ball supremum
- Expectation of a nonnegative or integrable random variable
- The Lebesgue integral is linear on L¹(μ)
- Similar matrices have the same trace
- Law or distribution of a random element
- Arithmetic and lattice operations preserve measurability whenever they are defined
- Composition with a Borel measurable outer map preserves measurability
- Monotonicity and nonnegative homogeneity of the nonnegative integral
- Integrable real and complex functions, and their integrals
- Probability measures and probability spaces
- The integral of a nonnegative simple function
- The nonnegative integral agrees with the simple integral on simple functions
- Independent-entry coordinates, convexity and Lipschitz constants
- A convex subset of ℝᵐ contains every line segment between two of its points
- Concentration Inequalities: A Nonasymptotic Theory of Independence · Section 7.5, Theorem 7.12, printed p. 222, PDF p. 231
- Asymptotic quantifiers and uniform parameter ranges
- Moments, variance, and covariance on a probability space
- Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely
- The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖
- Wigner random matrices with non-symmetrically distributed entries · Section 1, equation (1), Theorem 1.1 and Remark 1.1, PDF pages 1–2
- Logarithmic tangent bound and a quadratic entropy envelope
- The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t
- On an interval I, for f continuous on I and differentiable at every interior point: f' ≥ 0 throughout gives f nondecreasing, f' > 0 gives f increasing, f' ≤ 0 and f' < 0 give the two decreasing forms; conversely a nondecreasing f has f' ≥ 0 and a nonincreasing f has f' ≤ 0 wherever it is differentiable, and no strict converse is claimed
- Intermediate value theorem, by bisection with a canonical left-half rule: a continuous function on [a,b] takes every value between f(a) and f(b)
- Sums, scalar multiples, products and quotients: (f+g)'(c) = f'(c) + g'(c), (α f)'(c) = α f'(c), (fg)'(c) = f'(c)g(c) + f(c)g'(c), and (f/g)'(c) = (f'(c)g(c) - f(c)g'(c))/g(c)² when g(c) ≠ 0
- For a natural n ≥ 1 the function x ↦ xⁿ is differentiable everywhere with derivative ι(n) x^ n-1; for n = 0 it is the constant 1, with derivative 0; for a natural n ≥ 1 the function x ↦ x⁻ⁿ is differentiable at every x ≠ 0 with derivative -ι(n) x⁻ⁿ⁻¹; consequently every polynomial function is differentiable at every real, with the derivative computed term by term
- A function differentiable at c is continuous at c
- Square roots exist: a unique √a ≥ 0 with (√a)² = a; the positives are {x² : x ≠ 0}
- The left and right limits of f at c, as limits of the restrictions of f to A ∩ (-∞, c) and A ∩ (c, ∞)
- Limits at +∞ and -∞, and infinite limits at a point
- The derivative f'(c) = lim_x → c f(x) - f(c)/x - c of f : A → ℝ at a point c ∈ A that is a limit point of A, and differentiability on a set
- Nondecreasing, increasing (strictly increasing), nonincreasing, decreasing, monotone and strictly monotone real functions on a subset of ℝ, with the dictionary to monotone sequences
- Continuity of f : A → ℝ at a point of A and on A: the ε-δ condition, its agreement with lim_x → c f(x) = f(c) at a limit point, and continuity at an isolated point
- Pairings, simple-graph conditioning and model transfer
- For n ≥ 1 the congruence classes modulo n form an abelian group (ℤ/n, +) of order n, generated by the class of 1
- Finite symmetric networks and loop removal
- Finite probability spaces, outcome weights, events, and event probabilities
- The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ
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
Lemma
Dyck words and elementary Catalan growth
Lemma
An elementary sufficient budget for the synchronization criterion
Proposition
Chernoff bounds with the exact degree mean
Proposition
Trace powers, closed walks and independent edge moments
Theorem
Convex Lipschitz concentration with its coordinate metric
Theorem
A fixed-law Wigner spectral-edge input
Lemma
Entropy endpoint limits and the two monotone branches
Lemma
Feasible orders for labelled simple regular graphs
Lemma
Hamiltonian cycles as finite cyclic-order events
Lemma