Alphabeta MathExpander Graphs and Constraint Graphs
About this page
Pipeline-generated
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
1 · Prerequisites
- Algebraic Closure, Embeddings, and Separability
- Algebraic Extensions, Extension Degree, and Finite Fields
- Binary Operations, Monoids, Groups and Subgroups
- Composition Series, the Jordan–Hölder Theorem and Solvable Groups
- Congruences, the Integers Modulo n and the Chinese Remainder Theorem
- Construction of the Natural Numbers
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Cosets, Index and Lagrange's Theorem
- Countability and Uncountability
- Cyclic Groups and Direct Products
- Determinants of Matrices over a Commutative Ring
- Diagonalisation and the Minimal Polynomial
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Divisibility, Greatest Common Divisors and Bézout's Identity
- Dual Spaces, Bilinear and Quadratic Forms, and Sylvester's Law of Inertia
- Eigenvalues, Eigenvectors and the Characteristic Polynomial
- Finite Counting, Factorials and Binomial Coefficients
- Foundations of the Real Numbers for Analysis
- Group Actions, Orbits, Stabilisers and Cayley's Theorem
- Group Homomorphisms and the Isomorphism Theorems
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Inner Product Spaces, Gram-Schmidt, Projections and Adjoints
- Limits of Real Functions
- Linear Independence, Bases and Dimension
- Linear Transformations, Rank-Nullity and Quotient Spaces
- Matrices, the Matrix of a Linear Map, and Change of Basis
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- Normal Subgroups and Quotient Groups
- Order, Zorn's Lemma, and the Axiom of Choice
- Polynomial Rings, the Division Algorithm and Roots
- Primes, Euclid's Lemma and the Fundamental Theorem of Arithmetic
- Relations, Functions, and Quotients
- Rings, Subrings, Integral Domains and Fields
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Simple Field Extensions and the Construction of the Complex Numbers
- Splitting Fields
- Suprema and Infima
- Sylow's Theorems, p-Groups and Nilpotent Groups
- Symmetric Groups, Cycle Decomposition and the Sign Homomorphism
- The Determinant of a Linear Operator, Cofactors and Cramer's Rule
- The Fundamental Theorem of Algebra
- The Fundamental Theorem of Finite Abelian Groups
- The Galois Correspondence
- The Spectral Theorem, Positive Operators and Singular Value Decomposition
- The ZFC Axioms and the Basic Set Constructions
- Topology of ℝ
- Triangularisation, Generalised Eigenspaces and Jordan Canonical Form
- Vector Spaces, Linear Subspaces, Span and Direct Sums
2 · Logical flowchart
3 · Items
Definition
Regular multigraph and normalized adjacency
Lemma
Constant vector is a top eigenvector
Definition
Spectral edge and vertex expansion
Theorem
Expander mixing lemma
Lemma
Cheeger indicator and positive part energy
Lemma
Cheeger sweep and layer cake
Theorem
Cheeger inequalities for finite regular graphs
Corollary
Expander independent sets coloring and diameter
Definition
Margulis gabber galil graph
Lemma
Margulis family is constant degree and neighbor computable
Definition
Finite torus fourier transform
Lemma
Finite torus fourier orthogonality and affine change
Lemma
Fourier analysis of margulis adjacency
Lemma
Margulis diamond weight bound
Theorem
Margulis family has uniform spectral gap
Lemma
Expander size adjustment and laziness
Corollary
Explicit polynomial time constant degree expanders exist
Definition
Constraint graph and labeling value
Definition
Constraint graph regularization
Lemma
Cloud plurality rounding
Lemma
Regularization preserves value quantitatively
Lemma
Constraint expander overlay
Definition
Graph power and walk constraint
Lemma
Expander walk contraction
Lemma
Expander walk restricted operator
Theorem
Expander walk hits dense bad sets
Proposition
Expander walk sampled and moving sets
Lemma
Expander walk bad edge return
Proposition
Expander walk hits bad edges
Definition
Gap csp
False statement
Nonconstructive expanders suffice for uniform reductions
Sources
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §§2.1–2.3, pp19–21; Dinur §2.1, p8.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §2.3 spectral properties, pp20–21.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; Definitions2.1–2.3 and §2.3, pp19–21.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §2.4 Lemma2.5, p21.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §4.5.1 and beginning §4.5.2, pp40–42.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §4.5.2 Lemmas4.12–4.13, pp41–42.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §4.5 Theorem4.11 (also Theorem2.4), pp40–42.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §2.4 bullets after Lemma2.6, pp21–22; constants sharpened using centered indicators.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; Chapter8 Construction8.1, p69.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; Construction8.1, p69; explicit arithmetic cost analysis.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §8.1.1 Definition8.4 and torus examples, p70.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §8.1.1 Propositions8.5–8.6, pp70–71, corrected normalization.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §8.2 Theorems8.7–8.8, pp71–72; only the reduction, not the sharp constant.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §8.2 Proposition8.9 and complete weaker-bound proof, pp72–73.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; Theorem8.2 with fully proved weaker bound at end §8.2, pp69–73.
- Irit Dinur, The PCP theorem by gap amplification; §2.1 Lemma2.1 and Corollary2.4, pp8–9; HLW Construction8.1 and §4.5; explicit constants adapted.
- Irit Dinur, The PCP theorem by gap amplification; §2.1 Lemma2.1, p8, instantiated by preceding construction.
- Irit Dinur, The PCP theorem by gap amplification; §1.1 Definition1.1 and §1.2 Definition1.2, pp2–3.
- Irit Dinur, The PCP theorem by gap amplification; §4 Definitions4.1–4.2, PDF pages13–14, with explicit degree and loop conventions.
- Irit Dinur, The PCP theorem by gap amplification; §4 proof of Lemma4.1, PDF pages13–14.
- Irit Dinur, The PCP theorem by gap amplification; §4 Lemma4.1, PDF pages13–14.
- Irit Dinur, The PCP theorem by gap amplification; §4 Lemma4.2 and Corollary4.3, pp14–15.
- Irit Dinur, The PCP theorem by gap amplification; §1.2 Powering, pp4–5; underlying walk edges and original constraints.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §3.1 Definition3.1 and §3.1.1 Theorems3.2–3.3, Lemma3.4, pp25–26.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §3.2 Lemmas3.7–3.8, pp28–29; sharpened constant from the same projection proof.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §3.2 Theorem3.6 with the sharper Lemma3.8 estimate above, pp28–29.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §3.2 Theorems3.10–3.11, p29.
- Irit Dinur, The PCP theorem by gap amplification; §2.1 Proposition2.5 and its full proof, pp9–10.
- Irit Dinur, The PCP theorem by gap amplification; §2.1 Proposition2.5 and §2.2 Fact2.6, pp9–10, direct consequence.
- Irit Dinur, The PCP theorem by gap amplification; §1.1 Definition1.1 and Theorem1.2 formulation, pp2–3.
- Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §2.1 Definition2.3, p19; Dinur §2.1 Lemma2.1 explicitly requires constructibility.