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
- Symmetric matrices are Euclidean under the Frobenius norm
- The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖
- Convex and strictly convex functions on Euclidean convex sets
- Lipschitz map, α-Hölder map for rational 0 < α ≤ 1, and contraction
- Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis
- In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose
- Cauchy-Schwarz |⟨ x,y⟩| ≤ ‖ x‖₂‖ y‖₂ with its equality case, the triangle inequality for ‖·‖₂, the parallelogram law and polarisation
- Expectation of a nonnegative or integrable random variable
- Layer-cake formulas for random variables
- The nonnegative Lebesgue integral
- The Lebesgue integral is linear on L¹(μ)
- Monotonicity and nonnegative homogeneity of the nonnegative integral
- The Gaussian integral ∫_-∞^∞e^-x² dx=√π
- Substitution: if φ is differentiable on [c,d] with φ' integrable and f is continuous on an interval containing φ([c,d]), then ∫_φ(c)^φ(d) f = ∫_cᵈ (f∘φ) φ'
- A continuous function on [a,b] is Riemann integrable, by Heine-Cantor and Riemann's criterion
- A bounded Riemann integrable function on a closed bounded interval is Lebesgue measurable and has the same integral
- Monotone convergence for the integral
- The Axiom of Countable Choice (AC_ω)
- The Bartle-Sherbert bounds 2.828 < pi < 3.185
- Probability measures and probability spaces
- Random elements and real random variables
- Integrable real and complex functions, and their integrals
- Closure properties of measurable functions used by the integral
- The integral of a nonnegative simple function
- The nonnegative integral agrees with the simple integral on simple functions
- The uniform probability space on a nonempty finite set
- Filtration and filtered probability space
- Discrete stopping time
- Independent random elements
- The product measure of two sigma-finite measure spaces
- The Borel product of ℝᵐ and ℝⁿ is the Borel sigma-algebra of ℝᵐ⁺ⁿ
- A box in ℝⁿ with parameters aᵢ≤ bᵢ is Lebesgue measurable of measure ∏_i<n(bᵢ-aᵢ), whichever of its faces are included
- The sigma-algebra generated by a function
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- The finite union bound
- Finite Sudakov–Fernique comparison for Gaussian maxima
- Gaussian process
- Stochastic processes and their finite-dimensional distributions
- The Axiom of Choice
- Dominated convergence
- For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique
- Independent random elements are characterized by finite rectangle probabilities
- Standard normal and normal laws
- Both ℚ and ℝ ∖ ℚ are dense in ℝ, and every nonempty open subset of ℝ is uncountable
- ℚ is countably infinite
- Heine-Borel in ℝⁿ: with the Euclidean metric a subset of ℝⁿ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line
- Continuity of a map between metric spaces, at a point and globally, in the ε-δ form
- Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials
- Pairwise and mutual independence of finite-valued random variables
- The finite product of finite probability spaces
- Expectation of a real random variable on a finite probability space
- Finite probability spaces, outcome weights, events, and event probabilities
- Real random variables on finite probability spaces and their finite distributions
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- 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
- 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
- The Erdős-Rényi finite random graph G(n,p)
- Connected graphs and connected components defined by the existence of vertex paths
- The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
- Subgraphs, induced subgraphs and spanning subgraphs
- Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention
- The indicator random variable of an event
- Regular multigraph and normalized adjacency
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
Independent-entry coordinates, convexity and Lipschitz constants
Proposition
Tail integration and a median-to-mean bridge
Definition
Uniform edge orderings, graph-process times and independent labels
Proposition
From finite Gaussian comparisons to a sphere supremum
Proposition
Finite Bernoulli difference laws and parity of moments
Lemma
Logarithmic tangent bound and a quadratic entropy envelope
Lemma
A parent-map bound for isolated components
Lemma
Finite coupling makes connectivity probability monotone
Lemma