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
- The Erdős-Rényi finite random graph G(n,p)
- Connected graphs and connected components defined by the existence of vertex paths
- Asymptotic quantifiers and uniform parameter ranges
- Factorial moments of isolated vertices at the connectivity window
- Finite sieve determines the probability of a zero count
- Components between two vertices and half the graph disappear in the window
- Finite coupling makes connectivity probability monotone
- Finite probability spaces, outcome weights, events, and event probabilities
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- The logarithm grows more slowly than every positive real power
- The exponential tends to +∞ at +∞ and to 0 at -∞
- The exponential is a continuous bijection from ℝ onto (0,∞)
- Algebra of limits: sums, scalar multiples, products and quotients
- The natural logarithm as the inverse of the exponential function
- Divergence to +∞ and to -∞
- Limits at +∞ and -∞, and infinite limits at a point
- Finite symmetric networks and loop removal
- Regular adjacency spectra and normalized expansion
- Interlacing families I: Bipartite Ramanujan graphs of all degrees · Section 2.1, printed p. 308; Theorem 5.5 and its proof, printed p. 316
- Entropy endpoint limits and the two monotone branches
- The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t
- Choice-free smooth inverse function theorem in Euclidean space
- Cᵏ Euclidean maps and diffeomorphisms
- 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
- 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
- A function differentiable at c is continuous at c
- The principle of mathematical induction
- Pairings, simple-graph conditioning and model transfer
- Hamiltonian cycles as finite cyclic-order events
- The symmetric group Sym(X): the bijections of a set X under composition
- The uniform probability space on a nonempty finite set
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Matrix powers count closed labelled slot walks
- Stack construction of closed walks with loops and repeated edges
- Regular multigraph and normalized adjacency
- Reversible labels for adjacency slots
- Dyck words and elementary Catalan growth
- The adjacency matrix of a finite simple graph
- Triangular Gaussian coordinates: metric and moment control
- Gaussian process
- The Axiom of Choice
- A finite stack of independent Gaussian vectors is jointly Gaussian
- Multivariate normal law, including singular covariance
- Gaussian entry moments and triangular independence
- The Lebesgue integral is linear on L¹(μ)
- Cauchy-Schwarz |⟨ x,y⟩| ≤ ‖ x‖₂‖ y‖₂ with its equality case, the triangle inequality for ‖·‖₂, the parallelogram law and polarisation
- Stochastic processes and their finite-dimensional distributions
- Continuity of a map between metric spaces, at a point and globally, in the ε-δ form
- Finite vertex Hilbert space in the article convention
- Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely
- Self-adjoint order, norm bounds and diagonal tests
- Closure properties of measurable functions used by the integral
- Monotonicity and nonnegative homogeneity of the nonnegative integral
- Extended-real-valued measurable functions
- The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖
- Standard normal and normal laws
- Independent random elements
- Random elements and real random variables
- Expectation of a nonnegative or integrable random variable
- Chernoff bounds with the exact degree mean
- Single-vertex degree laws and the shared-edge dependence
- Uniform edge orderings, graph-process times and independent labels
- Support connectivity and the unnormalized Laplacian kernel
- Eigenvalues, eigenvectors, eigenspaces E_λ(T)=ker(T-λ I), and the spectrum σ_F(T) of an endomorphism
- Self-adjoint and normal endomorphisms of a finite-dimensional real or complex inner product space
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
Theorem
Connectivity in the logarithmic random-graph window
Theorem
Bipartite Ramanujan existence and the centered spectrum
Lemma
Differentiable entropy inverse branches and shifted contracts
Lemma
Vertex relabeling preserves the uniform regular graph law
Lemma
Extracting a nonconstant eigenvalue from closed-walk moments
Lemma
Ordered eigenvalues and the centered regular norm
Lemma
Quadratic Gaussian process and its increment metric
Lemma
Even trace moments transfer from the operator norm
Lemma
Simultaneous degree deviations on the squared logarithmic scale
Definition