AFTD Auto-Formalizing Theoretical Domains

seidel_codegree_bounds_254

theoremverified

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ᶜ.

  1. 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.

    line 8

      constructor
  2. Every 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).

    lines 9–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
  3. 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).

    lines 16–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

/-- 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
See it in the graphDiscuss this resultChallenge it