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)
- Expectation of a real random variable on a finite probability space
- The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ
- Asymptotic quantifiers and uniform parameter ranges
- 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
- The indicator random variable of an event
- The natural logarithm as the inverse of the exponential function
- The exponential is a continuous bijection from ℝ onto (0,∞)
- Algebra of limits: sums, scalar multiples, products and quotients
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function
- Continuous functions have an oriented Riemann integral
- The oriented Riemann integral is linear in continuous integrands
- Monotone change of variable for Riemann-integrable functions
- The real exponential function and the number e by a power series
- Finite probability spaces, outcome weights, events, and event probabilities
- Real random variables on finite probability spaces and their finite distributions
- Real powers for positive bases, with the zero-base positive-exponent convention
- Integer powers aᵐ
- A parent-map bound for isolated components
- 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]ᵏ|
- Elementary binomial probability envelopes
- The exponential function is strictly increasing
- The exponential addition formula exp(x+y)=exp(x)exp(y)
- Reversible labels for adjacency slots
- Regular multigraph and normalized adjacency
- Dyck words and elementary Catalan growth
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Pairings, simple-graph conditioning and model transfer
- Gaussian entry moments and triangular independence
- Finite vertex Hilbert space in the article convention
- The Axiom of Choice
- Cauchy–Schwarz: |⟨ u,v⟩|≤‖ u‖‖ v‖, with equality exactly for linearly dependent vectors
- Closure properties of measurable functions used by the integral
- Monotonicity and nonnegative homogeneity of the nonnegative integral
- The Lebesgue integral is linear on L¹(μ)
- The operator norm as the least bound and as the unit-sphere or unit-ball supremum
- The operator norm is a norm on the space of bounded linear operators
- Continuous functions on Euclidean spaces are Borel measurable
- Composition with a Borel measurable outer map preserves measurability
- A map into ℝⁿ is measurable exactly when its coordinates are measurable
- Finite symmetric networks and loop removal
- The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖
- First-order systems, initial value problems, and solutions on intervals
- Sine and cosine defined by their real power series
- Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials
- Pairwise and mutual independence of finite-valued random variables
- An elementary sufficient budget for the synchronization criterion
- Square roots exist: a unique √a ≥ 0 with (√a)² = a; the positives are {x² : x ≠ 0}
- Pi as twice the smallest positive zero of cosine
- Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1
- Uniform edge orderings, graph-process times and independent labels
- Threshold characterisations of real-valued and extended-real-valued measurability
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
Factorial moments of isolated vertices at the connectivity window
Lemma
Finite sieve determines the probability of a zero count
Lemma
Components between two vertices and half the graph disappear in the window
Lemma
Matrix powers count closed labelled slot walks
Lemma
Stack construction of closed walks with loops and repeated edges
Lemma
Feasible labelled simple regular graph orders
Lemma
Triangular Gaussian coordinates: metric and moment control
Lemma
Loop coupling preserves the dynamics and centered Laplacian
Lemma
Every fixed positive squared logarithmic density satisfies the budget
Lemma