IsAmplyRegular
A graph G on a finite vertex set is amply regular with parameters (k, ℓ, μ) if it is regular of degree k, every pair of adjacent vertices has ℓ common neighbors, and every pair of vertices at distance 2 in G has μ common neighbors.
Statement
structure IsAmplyRegular {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k ℓ μ : ℕ) : Prop where regular : G.IsRegularOfDegree k adj_commonNeighbors : ∀ ⦃u v : V⦄, G.Adj u v → Fintype.card (G.commonNeighbors u v) = ℓ dist_two_commonNeighbors : ∀ ⦃u v : V⦄, G.dist u v = 2 → Fintype.card (G.commonNeighbors u v) = μ
- Defined in
- arXiv:2610.36620, Section 1.1
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 7
- amply_regular_lambda_add_two_le_degree_of_three_le_diamAn amply regular graph with parameters (k, ℓ, μ) whose diameter is at least 3 satisfies ℓ + 2 ≤ k. (Equivalently: if k ≤ ℓ + 1 then the…
- amply_regular_mu_le_degree_of_dist_twoIn an amply regular graph with parameters (k, ℓ, μ), if there exists a pair of vertices at distance 2, then μ ≤ k.
- srg_is_amply_regularEvery strongly regular graph with parameters (n, k, ℓ, μ) on a finite vertex set is an amply regular graph with parameters (k, ℓ, μ).
- icosahedron_is_amply_regularThe icosahedron graph on Fin 12 is an amply regular graph with parameters (5, 2, 2) and its diameter is 3.
- amply_regular_dist_two_lipschitz_sum_boundScale-two Lipschitz estimate of arXiv:2610.36620, Section 3.1 (inequality (21) with gain B ≥ μ): let G be amply regular with parameters…
- amply_regular_diameter_bound_of_diam_le_twoAn amply regular graph with parameters (k, ℓ, μ) whose diameter is at most 2 has diameter at most 2k/(ℓ+2). No hypothesis on μ is needed:…
- amply_regular_sphere_two_card_mulIn an amply regular graph with parameters (k, ℓ, μ), for every vertex v the number of vertices at distance exactly 2 from v, multiplied by…
Read back from the Lean
IsAmplyRegular G k ℓ μ is the proposition (defined as a structure) asserting that a simple graph G on a finite vertex type V (with decidable adjacency) is an amply regular graph with parameters k, ℓ, μ : ℕ. It consists of three conditions:
1. regular: G is regular of degree k (G.IsRegularOfDegree k, i.e., every vertex has degree k).
2. adj_commonNeighbors: for all vertices u, v : V, if u and v are adjacent in G (G.Adj u v), then the number of common neighbors of u and v (Fintype.card (G.commonNeighbors u v)) equals ℓ.
3. dist_two_commonNeighbors: for all vertices u, v : V, if the shortest-path distance between u and v in G is 2 (G.dist u v = 2), then the number of common neighbors of u and v equals μ. (This field is given the default value by sorry.)
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A simple graph G is amply regular with parameters (k, ℓ, μ) if it is regular of degree k, any two adjacent vertices share ℓ common neighbors, and any two vertices at distance 2 share μ common neighbors. -/ structure IsAmplyRegular {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k ℓ μ : ℕ) : Prop where regular : G.IsRegularOfDegree k adj_commonNeighbors : ∀ ⦃u v : V⦄, G.Adj u v → Fintype.card (G.commonNeighbors u v) = ℓ dist_two_commonNeighbors : ∀ ⦃u v : V⦄, G.dist u v = 2 → Fintype.card (G.commonNeighbors u v) = μ