seidel_codegree_bounds_254
For any simple graph G on 254 vertices with decidable adjacency whose Seidel matrix S has all row sums equal to 1 and (S^2)_{ij} ≤ 0 for all distinct vertices i ≠ j, every adjacent pair in G has at most 62 common neighbors, and every distinct non-adjacent pair has at most 63 common neighbors in the complement graph Gᶜ.
Statement
theorem seidel_codegree_bounds_254
(G : SimpleGraph (Fin 254)) [DecidableRel G.Adj]
(h_row : ∀ i : Fin 254, ∑ j : Fin 254, seidel_matrix G i j = 1)
(h_sq : ∀ i j : Fin 254, i ≠ j → (seidel_matrix G * seidel_matrix G) i j ≤ 0) :
(∀ u v : Fin 254, G.Adj u v → Fintype.card (G.commonNeighbors u v) ≤ 62) ∧
(∀ u v : Fin 254, u ≠ v → ¬ G.Adj u v → Fintype.card (Gᶜ.commonNeighbors u v) ≤ 63)- Source
- step towards op_605_ramsey_b63_b64_graph_exists
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- seidel_matrix_codegree_eqFor any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in G, four times the number…
- seidel_matrix_compl_codegree_eqFor any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in the complement Gᶜ, four…
- seidel_matrixThe Seidel matrix of a simple graph G is the matrix S with zero on the diagonal, -1 for adjacent pairs of vertices, and 1 for distinct…
The proof, explained
The theorem is proved by splitting into two parts and applying the Seidel codegree formulas for G and Gᶜ. For adjacent vertices u and v in G, four times their common neighbor count is |V| - 4 - ∑ S_{uk} - ∑ S_{vk} + (S²)_{uv} ≤ 254 - 4 - 1 - 1 + 0 = 248, giving at most 62 common neighbors. For distinct non-adjacent vertices, they are adjacent in Gᶜ, where four times their common neighbor count is |V| - 4 + ∑ S_{uk} + ∑ S_{vk} + (S²)_{uv} ≤ 254 - 4 + 1 + 1 + 0 = 252, giving at most 63 common neighbors in Gᶜ.
The goal splits into two independent bounds: one for adjacent pairs in G and one for distinct non-adjacent pairs in Gᶜ.
The theorem statement is a conjunction of two universal statements. The `constructor` tactic separates it into two subgoals.
constructorEvery adjacent pair of vertices in G has at most 62 common neighbors.
Fix adjacent vertices u and v in G (line 9). The identity `seidel_matrix_codegree_eq` expresses four times their codegree as |V| - 4 - ∑ₖ S_{uk} - ∑ₖ S_{vk} + (S²)_{uv} (line 10). Simplifying |V| = 254 using `Fintype.card_fin` (line 14), substituting the row sums ∑ₖ S_{uk} = ∑ₖ S_{vk} = 1 (lines 11–12), and applying (S²)_{uv} ≤ 0 since u ≠ v (line 13), the right-hand side is at most 254 - 4 - 1 - 1 + 0 = 248. Linear integer arithmetic (`omega`) concludes that the number of common neighbors is at most 248 / 4 = 62 (line 15).
uses
seidel_matrix_codegree_eq,Fintype.card_fin· intro u v huv have h := seidel_matrix_codegree_eq G u v huv have h1 := h_row u have h2 := h_row v have h3 := h_sq u v huv.ne simp only [Fintype.card_fin] at h omega
Every distinct, non-adjacent pair of vertices in G has at most 63 common neighbors in the complement graph Gᶜ.
Fix distinct vertices u and v that are not adjacent in G (line 16). By `SimpleGraph.compl_adj`, they are adjacent in the complement graph Gᶜ (lines 17–18). The identity `seidel_matrix_compl_codegree_eq` expresses four times their codegree in Gᶜ as |V| - 4 + ∑ₖ S_{uk} + ∑ₖ S_{vk} + (S²)_{uv} (line 19). Simplifying |V| = 254 via `Fintype.card_fin` (line 23), substituting the row sums ∑ₖ S_{uk} = ∑ₖ S_{vk} = 1 (lines 20–21), and applying (S²)_{uv} ≤ 0 since u ≠ v (line 22), the right-hand side is at most 254 - 4 + 1 + 1 + 0 = 252. Linear integer arithmetic (`omega`) yields that their codegree in Gᶜ is at most 252 / 4 = 63 (line 24).
uses
SimpleGraph.compl_adj,seidel_matrix_compl_codegree_eq,Fintype.card_fin· intro u v hne hna have hcomp : Gᶜ.Adj u v := by rw [SimpleGraph.compl_adj]; exact ⟨hne, hna⟩ have h := seidel_matrix_compl_codegree_eq G u v hcomp have h1 := h_row u have h2 := h_row v have h3 := h_sq u v hne simp only [Fintype.card_fin] at h omega
Fintype.card_fin- The cardinality of the standard finite type `Fin n` is n.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph Gᶜ if and only if they are distinct and not adjacent in G.
seidel_matrix_codegree_eq- For an adjacent pair of vertices u and v in a finite graph G, four times their number of common neighbors equals |V| - 4 minus the Seidel row sums of u and v, plus the (u, v)-entry of the square of the Seidel matrix S².
seidel_matrix_compl_codegree_eq- For an adjacent pair of vertices u and v in the complement graph Gᶜ, four times their number of common neighbors in Gᶜ equals |V| - 4 plus the Seidel row sums of u and v in G, plus the (u, v)-entry of the square of the Seidel matrix S².
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For any simple graph G on 254 vertices with decidable adjacency whose Seidel matrix has all row sums 1 and non-positive off-diagonal square entries, the codegree in G of any adjacent pair is at most 62, and the codegree in Gᶜ of any distinct non-adjacent pair is at most 63. -/theorem seidel_codegree_bounds_254 (G : SimpleGraph (Fin 254)) [DecidableRel G.Adj] (h_row : ∀ i : Fin 254, ∑ j : Fin 254, seidel_matrix G i j = 1) (h_sq : ∀ i j : Fin 254, i ≠ j → (seidel_matrix G * seidel_matrix G) i j ≤ 0) : (∀ u v : Fin 254, G.Adj u v → Fintype.card (G.commonNeighbors u v) ≤ 62) ∧ (∀ u v : Fin 254, u ≠ v → ¬ G.Adj u v → Fintype.card (Gᶜ.commonNeighbors u v) ≤ 63) := by constructor · intro u v huv have h := seidel_matrix_codegree_eq G u v huv have h1 := h_row u have h2 := h_row v have h3 := h_sq u v huv.ne simp only [Fintype.card_fin] at h omega · intro u v hne hna have hcomp : Gᶜ.Adj u v := by rw [SimpleGraph.compl_adj]; exact ⟨hne, hna⟩ have h := seidel_matrix_compl_codegree_eq G u v hcomp have h1 := h_row u have h2 := h_row v have h3 := h_sq u v hne simp only [Fintype.card_fin] at h omega