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
- Uniform edge orderings, graph-process times and independent labels
- Asymptotic quantifiers and uniform parameter ranges
- Finite probability spaces, outcome weights, events, and event probabilities
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- The integral logarithm L is the published natural logarithm
- The integral logarithm L(x):=∫₁ˣdt/t for x>0
- Exponential clocks and the uniform edge-order process
- Expectation of a real random variable on a finite probability space
- Regular adjacency spectra and normalized expansion
- Dyck words and elementary Catalan growth
- Extracting a nonconstant eigenvalue from closed-walk moments
- Logarithmic tangent bound and a quadratic entropy envelope
- Entropy endpoint limits and the two monotone branches
- 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
- Differentiable entropy inverse branches and shifted contracts
- Sum, product, quotient, and chain rules from difference quotients
- Vertex relabeling preserves the uniform regular graph law
- Intersecting finitely many high-probability events
- Feasible orders for labelled simple regular graphs
- Hamiltonian cycles as finite cyclic-order events
- Ordered eigenvalues and the centered regular norm
- Pairings, simple-graph conditioning and model transfer
- The adjacency matrix of a finite simple graph
- Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set
- The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖
- Probability measures and probability spaces
- Feasible labelled simple regular graph orders
- Quadratic Gaussian process and its increment metric
- Triangular Gaussian coordinates: metric and moment control
- The Axiom of Choice
- From finite Gaussian comparisons to a sphere supremum
- Self-adjoint order, norm bounds and diagonal tests
- Finite vertex Hilbert space in the article convention
- Cauchy-Schwarz |⟨ x,y⟩| ≤ ‖ x‖₂‖ y‖₂ with its equality case, the triangle inequality for ‖·‖₂, the parallelogram law and polarisation
- Cauchy-Schwarz for random variables
- A finite stack of independent Gaussian vectors is jointly Gaussian
- Multivariate normal law, including singular covariance
- Cramer wold device
- A map into ℝⁿ is measurable exactly when its coordinates are measurable
- Continuous functions on Euclidean spaces are Borel measurable
- Composition with a Borel measurable outer map preserves measurability
- Gaussian entry moments and triangular independence
- The Lebesgue integral is linear on L¹(μ)
- Monotonicity and nonnegative homogeneity of the nonnegative integral
- Law or distribution of a random element
- Change of variables for expectation
- Loop coupling preserves the dynamics and centered Laplacian
- Simultaneous degree deviations on the squared logarithmic scale
- Normalized graph Laplacian and its nontrivial spectrum
- Charles Bordenave, A new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts · arXiv:1502.04482v4 (5 March 2019), Section 1, simple ensemble definition and Theorem 1, PDF/printed p. 2; eigenvalue ordering on p. 1
- Finite symmetric networks and loop removal
- R. W. Robinson and N. C. Wormald, Almost All Regular Graphs are Hamiltonian · Section 1, first paragraph and Theorem 1, printed/PDF page 2
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
An isolated vertex before three quarters of the connectivity scale
Theorem
The fixed-degree Alon–Boppana lower bound
Lemma
Parameter bounds giving the signs of shifted entropy roots
Lemma
From Hamiltonicity and an invariant event to a prescribed cycle
Lemma
Disconnected and bipartite spectral witnesses
Lemma
Exact normalized spectral threshold transfer
Lemma
Simple-model spectral events as conditional pairing counts
Lemma
Expected extreme eigenvalues from finite Gaussian comparison
Lemma
The unnormalized Laplacian needs its own degree deviation
Lemma
A spectral window giving condition number below two
Theorem
Friedman spectral expansion in the uniform simple model
Theorem