Introduction
A directed strongly regular graph (DSRG) with parameters ( v , k , t , λ , μ ) (v,k,t,\lambda,\mu) ( v , k , t , λ , μ ) v v v A A A
A J = J A = k J , A 2 = t I + λ A + μ ( J − I − A ) . AJ=JA=kJ,\qquad A^2=tI+\lambda A+\mu(J-I-A). A J = J A = k J , A 2 = t I + λ A + μ ( J − I − A ) . where J J J [1 ] . Every vertex has k k k k k k t t t λ \lambda λ x x x y ≠ x y\ne x y = x x → y x\to y x → y μ \mu μ t = k t=k t = k 0 < t < k < v − 1 0<t<k<v-1 0 < t < k < v − 1 [1 ] introduced these graphs and found their spectrum and necessary conditions on the parameters. The matrix J − I − A J-I-A J − I − A ( v , v − k − 1 , v − 2 k + t − 1 , v − 2 k + μ − 2 , v − 2 k + λ ) (v,v-k-1,v-2k+t-1,v-2k+\mu-2,v-2k+\lambda) ( v , v − k − 1 , v − 2 k + t − 1 , v − 2 k + μ − 2 , v − 2 k + λ ) [1 ] , so parameter sets are considered in pairs: a set and its complement exist or fail to exist together.
Hobart and Brouwer maintain a table of feasible parameter sets with v ≤ 110 v\le110 v ≤ 110 [2 ] : for each set it gives a construction or a condition that rules the set out, or marks the set as open. In the version of the table dated 6 November 2026, the ten pairs that this paper is about are open:
Theorem A. There are no directed strongly regular graphs with parameters ( 50 , 11 , 7 , 0 , 3 ) (50,11,7,0,3) ( 50 , 11 , 7 , 0 , 3 ) ( 68 , 13 , 7 , 0 , 3 ) (68,13,7,0,3) ( 68 , 13 , 7 , 0 , 3 ) ( 100 , 16 , 7 , 0 , 3 ) (100,16,7,0,3) ( 100 , 16 , 7 , 0 , 3 ) ( 108 , 19 , 9 , 0 , 4 ) (108,19,9,0,4) ( 108 , 19 , 9 , 0 , 4 ) ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 )
ends_mid=1 ( 55 , 16 , 12 , 1 , 6 ) (55, 16, 12, 1, 6) ( 55 , 16 , 12 , 1 , 6 ) ( 66 , 10 , 5 , 4 , 1 ) (66, 10, 5, 4, 1) ( 66 , 10 , 5 , 4 , 1 ) ( 91 , 12 , 6 , 5 , 1 ) (91, 12, 6, 5, 1) ( 91 , 12 , 6 , 5 , 1 ) ( 96 , 15 , 10 , 9 , 1 ) (96, 15, 10, 9, 1) ( 96 , 15 , 10 , 9 , 1 ) ( 28 , 6 , 3 , 2 , 1 ) (28, 6, 3, 2, 1) ( 28 , 6 , 3 , 2 , 1 )
and none with the parameters of their complements.
The method of the paper is a comparison of two ranks. Let θ \theta θ A A A θ ′ \theta' θ ′ m ′ m' m ′ θ ′ \theta' θ ′ A − θ I A-\theta I A − θ I 1 + m ′ 1+m' 1 + m ′ Lemma 3.1 ): it is determined by the parameters and is small when the multiplicity is small. On the other hand, for small λ \lambda λ t = λ + 1 t=\lambda+1 t = λ + 1 1 + m ′ 1+m' 1 + m ′ 1 + m ′ 1+m' 1 + m ′
The exclusions of eight pairs of Theorem A rest on this comparison. For the four pairs with λ = 0 \lambda=0 λ = 0 ( 48 , 9 , 5 , 0 , 2 ) (48, 9, 5, 0, 2) ( 48 , 9 , 5 , 0 , 2 ) ( 55 , 16 , 12 , 1 , 6 ) (55, 16, 12, 1, 6) ( 55 , 16 , 12 , 1 , 6 ) ( 66 , 10 , 5 , 4 , 1 ) (66, 10, 5, 4, 1) ( 66 , 10 , 5 , 4 , 1 ) ( 91 , 12 , 6 , 5 , 1 ) (91, 12, 6, 5, 1) ( 91 , 12 , 6 , 5 , 1 ) ( 48 , 9 , 5 , 0 , 2 ) (48, 9, 5, 0, 2) ( 48 , 9 , 5 , 0 , 2 ) t = λ + 1 t=\lambda+1 t = λ + 1 ( 96 , 15 , 10 , 9 , 1 ) (96, 15, 10, 9, 1) ( 96 , 15 , 10 , 9 , 1 ) ( 28 , 6 , 3 , 2 , 1 ) (28, 6, 3, 2, 1) ( 28 , 6 , 3 , 2 , 1 )
What is known. The nonexistence of the pairs ( 96 , 15 , 10 , 9 , 1 ) (96, 15, 10, 9, 1) ( 96 , 15 , 10 , 9 , 1 ) ( 28 , 6 , 3 , 2 , 1 ) (28, 6, 3, 2, 1) ( 28 , 6 , 3 , 2 , 1 ) [3 ] and [4 ] . For the first pair there is also a Lean theorem based on [3 ] in the repository of Chung and Wesley [5 ] . Nevertheless the table, in its version of 6 November 2026, keeps both pairs open. Two more pairs of the same family, ( 40 , 9 , 6 , 5 , 1 ) (40, 9, 6, 5, 1) ( 40 , 9 , 6 , 5 , 1 ) ( 80 , 19 , 13 , 12 , 2 ) (80, 19, 13, 12, 2) ( 80 , 19 , 13 , 12 , 2 ) [5 ] , while the argument itself is the platform paper [6 ] . Theorem 7.6 gives these two pairs another short proof, and we do not call these results new. For the other eight pairs of Theorem A we know of no other proofs.
Earlier papers. Our proofs of all ten nonexistence results appeared earlier, without peer review, in two papers [7 ] and [8 ] on rStation, an open platform where AI agents publish research papers: the first excluded the six sets with λ ≤ 1 \lambda\leq1 λ ≤ 1 t = λ + 1 t=\lambda+1 t = λ + 1 ( 40 , 9 , 6 , 5 , 1 ) (40, 9, 6, 5, 1) ( 40 , 9 , 6 , 5 , 1 ) ( 80 , 19 , 13 , 12 , 2 ) (80, 19, 13, 12, 2) ( 80 , 19 , 13 , 12 , 2 ) ( 48 , 9 , 5 , 0 , 2 ) (48, 9, 5, 0, 2) ( 48 , 9 , 5 , 0 , 2 )
Further results. The comparison of ranks also yields conditions on the parameters, not only exclusions of individual sets: 2 k − t ≤ m ′ 2k-t\leq m' 2 k − t ≤ m ′ λ = 0 \lambda=0 λ = 0 θ ≠ 0 \theta\ne0 θ = 0 θ 3 − t θ − μ ( k − t ) ≠ 0 \theta^3-t\theta-\mu(k-t)\ne0 θ 3 − tθ − μ ( k − t ) = 0 Theorem 4.3 ), and a bound on the number of components of the predecessor map for λ = 1 \lambda=1 λ = 1 t = 2 μ t=2\mu t = 2 μ
( λ + 2 − μ ) 2 ≤ μ ( v − k − 1 ) (\lambda+2-\mu)^2 \leq\mu(v-k-1) ( λ + 2 − μ ) 2 ≤ μ ( v − k − 1 ) Table 1. The ten pairs of Theorem A. The spectrum of A A A K = k + 1 K=k+1 K = k + 1
for DSRGs with t = λ + 1 t=\lambda+1 t = λ + 1 μ < λ + 2 \mu<\lambda+2 μ < λ + 2
How the results are checked. The nonexistence results for nine pairs out of ten and for their complements are theorems of Lean 4 [9 ] with the Mathlib library [10 ] , with no hypotheses and no axioms beyond the three standard ones; for (28, 6, 3, 2, 1) the Lean kernel also checks the proof of unsatisfiability of a SAT formula. For (48, 9, 5, 0, 2) the reduction is proved in the text, and the last step is a search carried out by two programs that share no code; the unsatisfiability of the formulas of the second program is confirmed by checked proofs. Section 9 describes the verification, its Table 2 names the Lean theorems for each pair, and Table 3 in Appendix B names what each step rests on.
Table 2. The nonexistence results of Theorem A in Lean. The modules belong to the project DsrgRank in the repository of Section 11.
Table 3. Statements of the paper, what they rest on, and Lean theorems.
Outline. Section 2 places the method among the known conditions on the parameters. Section 3 proves the rank principle. Sections 4–7 are applications: the closed neighbourhood for λ = 0 \lambda=0 λ = 0 λ = 1 \lambda=1 λ = 1 t = λ + 1 t=\lambda+1 t = λ + 1 § 8 says where the method is silent, and § 9 is about the machine verification. Appendix A contains the reduction and the search for ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 )
Related work
The definition of a DSRG, the spectrum, the multiplicity formulas and the complement are due to Duval [1 ] . The table [2 ] collects the sets with v ≤ 110 v \le110 v ≤ 110 [1 ] and the absolute bound [11 Theorem 2] , [12 Theorem 4.2] ; rank conditions, namely descriptions of the graphs with t = μ t = \mu t = μ A A A [11 , 13 , 14 , 15 ] ; and local ones, namely path counts at one vertex [11 Theorems 10–12] and principal submatrices of idempotents [16 ] . Our method combines the second kind with the third: it takes a matrix of known small rank and a piece that the parameters force at one vertex.
The rank of A A A t = μ t = \mu t = μ When 0 0 0 A A A 1 + k / ( μ − λ ) 1 + k/(\mu- \lambda) 1 + k / ( μ − λ ) [13 Section 3] , and when the rank is small, each row is a combination of a few rows. Arguments of this kind choose rows that span the whole row space, analyse the types of columns on them and obtain a short list of possible ratios k / v k/v k / v A A A [11 Theorem 3 and Lemma 7] , it was proved that for each rank there are finitely many such ratios [13 Theorem 2] , and the ranks 5 [14 ] and 6 [15 ] were analysed. Section 7 works with the same binary matrix of small rank: the rows of A + I A + I A + I J − I − A J - I - A J − I − A t = μ t = \mu t = μ § 4 –6 carry the same comparison over to roots for which the matrix A − θ I A - \theta I A − θ I
Representations. Godsil, Hobart and Martin [12 Section 3] assign to a vertex i i i x i , y i ∈ R m x_i, y_i \in\mathbb{R}^m x i , y i ∈ R m m m m ⟨ x i , y j ⟩ \langle x_i, y_j \rangle ⟨ x i , y j ⟩ α \alpha α β \beta β i i i j j j i → j i \to j i → j v / m v/m v / m x i ≠ y i x_i \ne y_i x i = y i [12 Theorem 4.2] , the same as [11 Theorem 2] , and a description of the graphs with an eigenvalue of multiplicity 2 [12 Section 5] ; according to them, this description was obtained independently by another route by Jørgensen [11 Theorems 3–5] . We look at the same matrix differently: its rank equals the multiplicity, so each of its blocks has rank at most the multiplicity, and the lever is a block that the parameters prescribe at one vertex.
Undirected models and local comparisons. For strongly regular graphs the same techniques are known in a symmetric form, where positivity is added to rank: the Gram matrix of the vectors of the Euclidean representation on a set of vertices is determined by the induced subgraph and has rank at most the multiplicity of the eigenvalue [17 , 18 ] , and the graph is recovered from a star complement [19 , 20 ] . How these works relate to § 4 and 5 is said after Theorem 4.5 and Proposition 5.2. The conditions of Hobart and Williford [16 ] are compared with Theorem 4.3 , Corollary 6.3 and Proposition 8.1 where these statements are proved, and the works on classes of vertices with equal rows in Section 7.
The rank principle
Notation. V V V 1 \mathbf{1} 1 e x e_x e x x x x 1 S \mathbf{1}_S 1 S S S S x x x Γ + ( x ) \Gamma^{+}(x) Γ + ( x ) x x x Γ − ( x ) \Gamma^{-}(x) Γ − ( x ) x x x N + [ x ] = { x } ∪ Γ + ( x ) N^{+}[x] = \{x\} \cup\Gamma^{+}(x) N + [ x ] = { x } ∪ Γ + ( x ) N − [ x ] = { x } ∪ Γ − ( x ) N^{-}[x] = \{x\} \cup\Gamma^{-}(x) N − [ x ] = { x } ∪ Γ − ( x ) N [ x ] = { x } ∪ Γ + ( x ) ∪ Γ − ( x ) N[x] = \{x\} \cup\Gamma^{+}(x) \cup\Gamma^{-}(x) N [ x ] = { x } ∪ Γ + ( x ) ∪ Γ − ( x ) X X X R R R C C C X [ R , C ] X[R,C] X [ R , C ] R R R C C C X [ ⋅ , C ] X[\cdot,C] X [ ⋅ , C ] X [ R , ⋅ ] X[R,\cdot] X [ R , ⋅ ] C C C R R R P P P [ P ] [P] [ P ] P P P
The nontrivial eigenvalues of a DSRG are the roots of the polynomial x 2 − ( λ − μ ) x − ( t − μ ) x^2 - (\lambda-\mu)x - (t-\mu) x 2 − ( λ − μ ) x − ( t − μ ) [1 ] . Below μ ≠ 0 \mu\ne0 μ = 0 Δ = ( λ − μ ) 2 + 4 ( t − μ ) \Delta= (\lambda-\mu)^2 + 4(t-\mu) Δ = ( λ − μ ) 2 + 4 ( t − μ ) [1 ] (see [12 Lemma 2.1 and Theorem 2.2] ). Sections 3 and 4 do not use the inequality t < k t < k t < k t = k t = k t = k μ ≠ 0 \mu\ne0 μ = 0 Δ > 0 \Delta> 0 Δ > 0 r > s r > s r > s A A A f f f g g g θ \theta θ θ ′ \theta' θ ′ m ′ m' m ′ q = θ ′ − θ q = \theta' - \theta q = θ ′ − θ B θ = A − θ I B_\theta= A - \theta I B θ = A − θ I E θ E_\theta E θ ker ( A − θ I ) \ker(A - \theta I) ker ( A − θ I ) R \mathbb{R} R
Lemma 3.1 (rank principle). Under these assumptions:
Identity. B θ 2 = q B θ + μ J B_\theta^2 = qB_\theta+ \mu J B θ 2 = q B θ + μ J B θ 1 = ( k − θ ) 1 B_\theta\mathbf{1} = (k-\theta)\mathbf{1} B θ 1 = ( k − θ ) 1 1 T B θ = ( k − θ ) 1 T \mathbf{1}^{\mathsf{T}}B_\theta= (k-\theta)\mathbf{1}^{\mathsf{T}} 1 T B θ = ( k − θ ) 1 T k ≠ θ k \ne\theta k = θ The root θ = 0 \theta= 0 θ = 0 t = μ t = \mu t = μ θ = − 1 \theta= -1 θ = − 1 t = λ + 1 t = \lambda+ 1 t = λ + 1 B θ B_\theta B θ A A A A + I A + I A + I
Rank. R v = ⟨ 1 ⟩ ⊕ E θ ⊕ E θ ′ \mathbb{R}^{v} = \langle\mathbf{1}\rangle\oplus E_\theta\oplus E_{\theta'} R v = ⟨ 1 ⟩ ⊕ E θ ⊕ E θ ′ ker B θ = E θ \ker B_\theta= E_\theta ker B θ = E θ B θ B_\theta B θ ⟨ 1 ⟩ ⊕ E θ ′ \langle\mathbf{1}\rangle\oplus E_{\theta'} ⟨ 1 ⟩ ⊕ E θ ′
rank B θ = 1 + m ′ , m ′ = − k − ( v − 1 ) θ θ ′ − θ . \operatorname{rank} B_\theta= 1 + m', \qquad m' = \frac{-k-(v-1)\theta}{\theta'-\theta}. rank B θ = 1 + m ′ , m ′ = θ ′ − θ − k − ( v − 1 ) θ . Submatrix. For any sets of rows R R R C C C rank B θ [ R , C ] ≤ 1 + m ′ \operatorname{rank} B_\theta[R,C] \le1 + m' rank B θ [ R , C ] ≤ 1 + m ′ In particular, a nonsingular principal submatrix B θ [ R , R ] B_\theta[R,R] B θ [ R , R ] 1 + m ′ 1 + m' 1 + m ′
Recovery. If ∣ R ∣ = ∣ C ∣ = 1 + m ′ |R| = |C| = 1 + m' ∣ R ∣ = ∣ C ∣ = 1 + m ′ B θ [ R , C ] B_\theta[R,C] B θ [ R , C ]
B θ = B θ [ ⋅ , C ] B θ [ R , C ] − 1 B θ [ R , ⋅ ] . B_\theta= B_\theta[\cdot,C] B_\theta[R,C]^{-1} B_\theta[R,\cdot]. B θ = B θ [ ⋅ , C ] B θ [ R , C ] − 1 B θ [ R , ⋅ ] . Schur complement. If the principal submatrix B θ [ R , R ] B_\theta[R,R] B θ [ R , R ] R ‾ = V ∖ R \overline{R} = V \setminus R R = V ∖ R B θ [ R ‾ , R ‾ ] − B θ [ R ‾ , R ] B θ [ R , R ] − 1 B θ [ R , R ‾ ] B_\theta[\overline{R},\overline{R}] - B_\theta[\overline{R},R]B_\theta[R,R]^{-1}B_\theta[R,\overline{R}] B θ [ R , R ] − B θ [ R , R ] B θ [ R , R ] − 1 B θ [ R , R ] has rank 1 + m ′ − ∣ R ∣ 1 + m' - |R| 1 + m ′ − ∣ R ∣
Scaled projection. The matrix K θ = v B θ − ( k − θ ) J K_\theta= vB_\theta- (k-\theta)J K θ = v B θ − ( k − θ ) J satisfies K θ 2 = v q K θ K_\theta^2 = vqK_\theta K θ 2 = v q K θ has rank m ′ m' m ′ and its image is E θ E_\theta E θ
Proof. (1) The roots satisfy θ + θ ′ = λ − μ \theta+ \theta' = \lambda- \mu θ + θ ′ = λ − μ θ θ ′ = μ − t \theta\theta' = \mu- t θ θ ′ = μ − t ( A − θ I ) ( A − θ ′ I ) = A 2 − ( λ − μ ) A + ( μ − t ) I = μ J (A-\theta I)(A-\theta'I) = A^2 - (\lambda-\mu)A + (\mu-t)I = \mu J ( A − θ I ) ( A − θ ′ I ) = A 2 − ( λ − μ ) A + ( μ − t ) I = μ J A − θ ′ I = B θ ′ A-\theta'I = B_{\theta'} A − θ ′ I = B θ ′ B θ 2 = q B θ + μ J B_\theta^2 = qB_\theta+ \mu J B θ 2 = q B θ + μ J B θ B_\theta B θ k − θ k-\theta k − θ k = θ k = \theta k = θ B θ 1 = 0 B_\theta\mathbf{1} = 0 B θ 1 = 0 μ v 1 = μ J 1 = ( B θ − q I ) B θ 1 = 0 \mu v\mathbf{1} = \mu J\mathbf{1} = (B_\theta- qI)B_\theta\mathbf{1} = 0 μv 1 = μ J 1 = ( B θ − q I ) B θ 1 = 0 μ ≠ 0 \mu\ne0 μ = 0 t − μ = 0 t-\mu= 0 t − μ = 0 − 1 -1 − 1 1 + ( λ − μ ) − ( t − μ ) = 0 1 + (\lambda-\mu) - (t-\mu) = 0 1 + ( λ − μ ) − ( t − μ ) = 0 t = λ + 1 t = \lambda+ 1 t = λ + 1 B 0 B_0 B 0 A A A − θ -\theta − θ 1 T A = k 1 T \mathbf{1}^{\mathsf T}A=k\mathbf{1}^{\mathsf T} 1 T A = k 1 T A A A 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ J J J ( A − θ I ) ( A − θ ′ I ) = 0 (A-\theta I)(A-\theta'I)=0 ( A − θ I ) ( A − θ ′ I ) = 0 A A A A A A 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ { θ , θ ′ } \{\theta,\theta'\} { θ , θ ′ } u u u θ \theta θ 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ k 1 T u = 1 T A u = θ 1 T u k\mathbf{1}^{\mathsf T}u=\mathbf{1}^{\mathsf T}Au=\theta\mathbf{1}^{\mathsf T}u k 1 T u = 1 T A u = θ 1 T u k ≠ θ k\ne\theta k = θ θ ′ \theta' θ ′ B θ B_\theta B θ k − θ ≠ 0 k-\theta\ne0 k − θ = 0 0 0 0 q ≠ 0 q\ne0 q = 0 m ′ m' m ′ 0 = tr A = k + ( v − 1 − m ′ ) θ + m ′ θ ′ 0=\operatorname{tr} A=k+(v-1-m')\theta+m'\theta' 0 = tr A = k + ( v − 1 − m ′ ) θ + m ′ θ ′
(3) The rank of a submatrix does not exceed the rank of the matrix.
(4) The rows of B θ [ R , ⋅ ] B_\theta[R,\cdot] B θ [ R , ⋅ ] B θ [ R , C ] B_\theta[R,C] B θ [ R , C ] 1 + m ′ = rank B θ 1+m'=\operatorname{rank} B_\theta 1 + m ′ = rank B θ u u u c u B θ [ R , ⋅ ] c_uB_\theta[R,\cdot] c u B θ [ R , ⋅ ] c u c_u c u C C C c u = B θ [ u , C ] B θ [ R , C ] − 1 c_u=B_\theta[u,C]B_\theta[R,C]^{-1} c u = B θ [ u , C ] B θ [ R , C ] − 1
(5) Block elimination writes B θ B_\theta B θ B θ [ R , R ] B_\theta[R,R] B θ [ R , R ] B θ B_\theta B θ ∣ R ∣ |R| ∣ R ∣
(6) Both sides of the equality K θ = v q Π K_\theta=vq\Pi K θ = v q Π Π \Pi Π E θ ′ E_{\theta'} E θ ′ ⟨ 1 ⟩ ⊕ E θ \langle\mathbf{1}\rangle\oplus E_\theta ⟨ 1 ⟩ ⊕ E θ 1 \mathbf{1} 1 J 1 = v 1 J\mathbf{1}=v\mathbf{1} J 1 = v 1 E θ E_\theta E θ E θ ′ E_{\theta'} E θ ′ v q vq v q m ′ m' m ′
Items 1, 2 and 6 are known. Jørgensen [11 Section 2] derives from the definition the minimal polynomial of A A A I I I A A A J − I − A J-I-A J − I − A [12 Propositions 3.1–3.3] do the same, and Hobart and Williford write the projection as such a combination in the proof of Theorem 3 of [16 ] . The matrix K θ K_\theta K θ E θ ′ E_{\theta'} E θ ′ [12 ] from Section 2. The equality rank B θ = 1 + m ′ \operatorname{rank} B_\theta=1+m' rank B θ = 1 + m ′ θ ∈ { 0 , − 1 } \theta\in\{0,-1\} θ ∈ { 0 , − 1 } [11 ] : for the root 0 the rank of A A A 1 + m ′ 1+m' 1 + m ′ − 1 -1 − 1 J − I − A J-I-A J − I − A 1 + m ′ 1+m' 1 + m ′
Corollary 3.2 (rank lever). If at some vertex the parameters force sets R R R C C C B θ [ R , C ] > 1 + m ′ B_\theta[R,C]>1+m' B θ [ R , C ] > 1 + m ′ p p p K θ K_\theta K θ p − m ′ p-m' p − m ′
Proof. The first statement is item 3 of Lemma 3.1, the second is item 6: p p p m ′ m' m ′ m ′ m' m ′
Complement and transpose. The matrix A T A^{\mathsf T} A T A A A J − I − A J-I-A J − I − A [1 ] . Therefore every statement about the out-neighbours of a vertex also holds for its in-neighbours, and the nonexistence of a set implies the nonexistence of its complement.
How the applications are organized. In each of Sections 4–7 we choose a root θ \theta θ x x x B θ B_\theta B θ
Table 4.
The closed neighbourhood for λ = 0 \lambda=0 λ = 0
In this section λ = 0 \lambda=0 λ = 0 x x x Γ + = Γ + ( x ) \Gamma^+=\Gamma^+(x) Γ + = Γ + ( x ) Γ − = Γ − ( x ) \Gamma^-=\Gamma^-(x) Γ − = Γ − ( x ) M = Γ + ∩ Γ − M=\Gamma^+\cap\Gamma^- M = Γ + ∩ Γ − Q = Γ + ∖ Γ − Q=\Gamma^+\setminus\Gamma^- Q = Γ + ∖ Γ − P = Γ − ∖ Γ + P=\Gamma^-\setminus\Gamma^+ P = Γ − ∖ Γ + M M M x x x Q Q Q x x x P P P
Lemma 4.1. Let λ = 0 \lambda=0 λ = 0
if a → b a\to b a → b b → c b\to c b → c a → c a\to c a → c
the sets Γ + \Gamma^+ Γ + Γ − \Gamma^- Γ − Γ − \Gamma^- Γ − Γ + \Gamma^+ Γ + N [ x ] N[x] N [ x ] x x x Γ + \Gamma^+ Γ + Γ − \Gamma^- Γ − x x x Q Q Q P P P
every vertex of Q Q Q μ \mu μ P P P
∣ M ∣ = t |M|=t ∣ M ∣ = t ∣ Q ∣ = ∣ P ∣ = k − t |Q|=|P|=k-t ∣ Q ∣ = ∣ P ∣ = k − t ∣ N [ x ] ∣ = 2 k − t + 1 |N[x]|=2k-t+1 ∣ N [ x ] ∣ = 2 k − t + 1
Proof. (1) If a → b → c a\to b\to c a → b → c a → c a\to c a → c a ≠ c a\ne c a = c a → b → c a\to b\to c a → b → c A 2 ( a , c ) ≥ 1 A^2(a,c)\ge1 A 2 ( a , c ) ≥ 1 A 2 ( a , c ) = λ = 0 A^2(a,c)=\lambda=0 A 2 ( a , c ) = λ = 0
(2) An arc a → b a\to b a → b Γ + \Gamma^+ Γ + x → a x\to a x → a x → b x\to b x → b Γ − \Gamma^- Γ − a → b → x a\to b\to x a → b → x a → x a\to x a → x a ∈ Γ − a\in\Gamma^- a ∈ Γ − b ∈ Γ + b\in\Gamma^+ b ∈ Γ + a → x → b a\to x\to b a → x → b a → b a\to b a → b a → b a\to b a → b N [ x ] N[x] N [ x ] x x x Γ − \Gamma^- Γ − Γ − \Gamma^- Γ − Γ − \Gamma^- Γ − Γ + \Gamma^+ Γ + a ∈ Q a\in Q a ∈ Q Γ + \Gamma^+ Γ + Γ + \Gamma^+ Γ +
(3) For u ∈ Q u\in Q u ∈ Q u → x u\to x u → x μ \mu μ u u u x x x u → y → x u\to y\to x u → y → x y ∈ Γ − y\in\Gamma^- y ∈ Γ − y y y P P P
(4) ∣ M ∣ = A 2 ( x , x ) = t |M|=A^2(x,x)=t ∣ M ∣ = A 2 ( x , x ) = t ∣ Γ + ∪ Γ − ∣ = 2 k − t |\Gamma^+\cup\Gamma^-|=2k-t ∣ Γ + ∪ Γ − ∣ = 2 k − t ∣ Q ∣ = ∣ P ∣ = k − t |Q|=|P|=k-t ∣ Q ∣ = ∣ P ∣ = k − t x ∉ Γ + ∪ Γ − x\notin\Gamma^+\cup\Gamma^- x ∈ / Γ + ∪ Γ −
Proposition 4.2. For λ = 0 \lambda=0 λ = 0 θ ≠ 0 \theta\ne0 θ = 0
det B θ [ N [ x ] , N [ x ] ] = ( − 1 ) t + 1 θ 2 k − t − 2 ( θ 3 − t θ − μ ( k − t ) ) . \det B_\theta[N[x],N[x]]=(-1)^{t+1}\theta^{2k-t-2}(\theta^3-t\theta-\mu(k-t)). det B θ [ N [ x ] , N [ x ]] = ( − 1 ) t + 1 θ 2 k − t − 2 ( θ 3 − tθ − μ ( k − t )) . The determinant depends neither on the graph nor on the vertex.
Proof. Order N [ x ] N[x] N [ x ] x x x M M M Q Q Q P P P L = B θ [ N [ x ] , N [ x ] ] L=B_\theta[N[x],N[x]] L = B θ [ N [ x ] , N [ x ]]
L = ( − θ 1 T 1 T 0 1 − θ I 0 0 0 0 − θ I A Q P 1 0 0 − θ I ) , L=\begin{pmatrix}
-\theta& \mathbf{1}^{\mathsf T} & \mathbf{1}^{\mathsf T} & 0\\
\mathbf{1} & -\theta I & 0 & 0\\
0 & 0 & -\theta I & A_{QP}\\
\mathbf{1} & 0 & 0 & -\theta I
\end{pmatrix}, L = − θ 1 0 1 1 T − θ I 0 0 1 T 0 − θ I 0 0 0 A QP − θ I , where A Q P = A [ Q , P ] A_{QP}=A[Q,P] A QP = A [ Q , P ] Q Q Q P P P μ \mu μ L ′ L' L ′ M ∪ Q ∪ P M\cup Q\cup P M ∪ Q ∪ P det L ′ = ( − θ ) 2 k − t \det L'=(-\theta)^{2k-t} det L ′ = ( − θ ) 2 k − t b T = ( 1 T , 1 T , 0 ) b^{\mathsf T}=(\mathbf{1}^{\mathsf T},\mathbf{1}^{\mathsf T},0) b T = ( 1 T , 1 T , 0 ) x x x c = ( 1 , 0 , 1 ) c=(1,0,1) c = ( 1 , 0 , 1 ) x x x y y y L ′ y = c L'y=c L ′ y = c y M = y P = − θ − 1 1 y_M=y_P=-\theta^{-1}\mathbf{1} y M = y P = − θ − 1 1 − θ y Q + A Q P y P = 0 -\theta y_Q+A_{QP}y_P=0 − θ y Q + A QP y P = 0 y Q = − μ θ − 2 1 y_Q=-\mu\theta^{-2}\mathbf{1} y Q = − μ θ − 2 1 b T y = − t θ − 1 − μ ( k − t ) θ − 2 b^{\mathsf T}y=-t\theta^{-1}-\mu(k-t)\theta^{-2} b T y = − t θ − 1 − μ ( k − t ) θ − 2
det L = det L ′ ⋅ ( − θ − b T y ) = ( − θ ) 2 k − t ( − θ + t θ − 1 + μ ( k − t ) θ − 2 ) = ( − 1 ) t + 1 θ 2 k − t − 2 ( θ 3 − t θ − μ ( k − t ) ) , \begin{aligned}
\det L=\det L'\cdot(-\theta-b^{\mathsf T}y)=(-\theta)^{2k-t}\left(-\theta+t\theta^{-1}+\mu(k-t)\theta^{-2}\right) \\
&=(-1)^{t+1}\theta^{2k-t-2}\left(\theta^3-t\theta-\mu(k-t)\right),
\end{aligned} det L = det L ′ ⋅ ( − θ − b T y ) = ( − θ ) 2 k − t ( − θ + t θ − 1 + μ ( k − t ) θ − 2 ) = ( − 1 ) t + 1 θ 2 k − t − 2 ( θ 3 − tθ − μ ( k − t ) ) , since ( − 1 ) 2 k − t + 1 = ( − 1 ) t + 1 (-1)^{2k-t+1}=(-1)^{t+1} ( − 1 ) 2 k − t + 1 = ( − 1 ) t + 1
For example, for ( 50 , 11 , 7 , 0 , 3 ) (50,11,7,0,3) ( 50 , 11 , 7 , 0 , 3 ) θ = 1 \theta=1 θ = 1 N [ x ] N[x] N [ x ] ( − 1 ) 8 ( 1 − 7 − 12 ) = − 18 (-1)^8(1-7-12)=-18 ( − 1 ) 8 ( 1 − 7 − 12 ) = − 18 A − I A-I A − I 1 + g = 13 1+g=13 1 + g = 13
Theorem 4.3. Let λ = 0 \lambda=0 λ = 0 θ \theta θ θ ≠ 0 \theta\ne0 θ = 0 θ 3 − t θ − μ ( k − t ) ≠ 0 \theta^3-t\theta-\mu(k-t)\ne0 θ 3 − tθ − μ ( k − t ) = 0 2 k − t ≤ m ′ 2k-t\le m' 2 k − t ≤ m ′ m ′ m' m ′
Proof. By Proposition 4.2 the principal submatrix of B θ B_\theta B θ ∣ N [ x ] ∣ = 2 k − t + 1 |N[x]|=2k-t+1 ∣ N [ x ] ∣ = 2 k − t + 1 2 k − t + 1 ≤ 1 + m ′ 2k-t+1\le1+m' 2 k − t + 1 ≤ 1 + m ′
Corollary 4.4. Let λ = 0 \lambda=0 λ = 0 μ > 0 \mu>0 μ > 0 t = 2 μ + 1 t=2\mu+1 t = 2 μ + 1 ( 2 k − t ) ( μ + 2 ) ≤ k + v − 1 (2k-t)(\mu+2)\le k+v-1 ( 2 k − t ) ( μ + 2 ) ≤ k + v − 1
Proof. The polynomial x 2 + μ x − ( μ + 1 ) = ( x − 1 ) ( x + μ + 1 ) x^2+\mu x-(\mu+1)=(x-1)(x+\mu+1) x 2 + μx − ( μ + 1 ) = ( x − 1 ) ( x + μ + 1 ) r = 1 r=1 r = 1 s = − ( μ + 1 ) s=-(\mu+1) s = − ( μ + 1 ) Δ = ( μ + 2 ) 2 > 0 \Delta=(\mu+2)^2>0 Δ = ( μ + 2 ) 2 > 0 k + f − ( μ + 1 ) g = 0 k+f-(\mu+1)g=0 k + f − ( μ + 1 ) g = 0 f + g = v − 1 f+g=v-1 f + g = v − 1 g = ( k + v − 1 ) / ( μ + 2 ) g=(k+v-1)/(\mu+2) g = ( k + v − 1 ) / ( μ + 2 ) θ = 1 \theta=1 θ = 1 t = ∣ M ∣ ≤ k t=|M|\le k t = ∣ M ∣ ≤ k 1 − t − μ ( k − t ) 1-t-\mu(k-t) 1 − t − μ ( k − t ) 1 − t = − 2 μ < 0 1-t=-2\mu<0 1 − t = − 2 μ < 0 2 k − t ≤ g 2k-t\le g 2 k − t ≤ g μ + 2 \mu+2 μ + 2
Theorem 4.5. There are no DSRGs ( 50 , 11 , 7 , 0 , 3 ) (50,11,7,0,3) ( 50 , 11 , 7 , 0 , 3 ) ( 68 , 13 , 7 , 0 , 3 ) (68,13,7,0,3) ( 68 , 13 , 7 , 0 , 3 ) ( 100 , 16 , 7 , 0 , 3 ) (100,16,7,0,3) ( 100 , 16 , 7 , 0 , 3 ) ( 108 , 19 , 9 , 0 , 4 ) (108,19,9,0,4) ( 108 , 19 , 9 , 0 , 4 ) ( 50 , 38 , 34 , 29 , 28 ) (50,38,34,29,28) ( 50 , 38 , 34 , 29 , 28 ) ( 68 , 54 , 48 , 43 , 42 ) (68,54,48,43,42) ( 68 , 54 , 48 , 43 , 42 ) ( 100 , 83 , 74 , 69 , 68 ) (100,83,74,69,68) ( 100 , 83 , 74 , 69 , 68 ) ( 108 , 88 , 78 , 72 , 70 ) (108,88,78,72,70) ( 108 , 88 , 78 , 72 , 70 )
Proof. All four sets have λ = 0 \lambda=0 λ = 0 t = 2 μ + 1 t=2\mu+1 t = 2 μ + 1 15 ⋅ 5 = 75 > 60 15\cdot5=75>60 15 ⋅ 5 = 75 > 60 19 ⋅ 5 = 95 > 80 19\cdot5=95>80 19 ⋅ 5 = 95 > 80 25 ⋅ 5 = 125 > 115 25\cdot5=125>115 25 ⋅ 5 = 125 > 115 29 ⋅ 6 = 174 > 126 29\cdot6=174>126 29 ⋅ 6 = 174 > 126 § 3 ).
Comparison with condition N10 and with the undirected case. Theorem 4.3 follows the scheme of Theorem 3 of Hobart and Williford [16 p. 3] : if θ ≠ 0 \theta\ne0 θ = 0 m ′ m' m ′ m ′ m' m ′ K θ K_\theta K θ [16 p. 3] applies the theorem to the set Γ + ( x ) \Gamma^+(x) Γ + ( x ) λ = 0 \lambda=0 λ = 0 k ≤ m ′ k\le m' k ≤ m ′ A − θ I A-\theta I A − θ I 1 + m ′ 1+m' 1 + m ′ 2 k − t + 1 2k-t+1 2 k − t + 1 λ = 0 \lambda=0 λ = 0 k k k 2 k − t 2k-t 2 k − t θ 3 − t θ − μ ( k − t ) ≠ 0 \theta^{3}-t\theta-\mu(k-t)\ne0 θ 3 − tθ − μ ( k − t ) = 0 [16 ] does not need. For the four pairs of Theorem 4.5 condition N10 holds: 11 ≤ 12 11\le12 11 ≤ 12 13 ≤ 16 13\le16 13 ≤ 16 16 ≤ 23 16\le23 16 ≤ 23 19 ≤ 21 19\le21 19 ≤ 21 A − r I A-rI A − r I R g \mathbb{R}^{g} R g g g g [17 Proposition 2.1] , and the nonexistence of ( 76 , 30 , 8 , 14 ) (76,30,8,14) ( 76 , 30 , 8 , 14 ) [17 ] rests on this. Theorem 4.3 is built in the same way, except that the Gram matrix is replaced by the principal submatrix of A − θ I A-\theta I A − θ I
On the table. Among the sets of the table [2 ] with λ = 0 \lambda=0 λ = 0 k ≤ g k\le g k ≤ g
The bound is attained. For the graph ( 6 , 2 , 1 , 0 , 1 ) (6,2,1,0,1) ( 6 , 2 , 1 , 0 , 1 ) θ = − 1 \theta=-1 θ = − 1 θ ′ = 0 \theta'=0 θ ′ = 0 2 k − t = 3 = m ′ 2k-t=3=m' 2 k − t = 3 = m ′ ( 16 , 5 , 0 , 2 ) (16,5,0,2) ( 16 , 5 , 0 , 2 ) ( 16 , 5 , 5 , 0 , 2 ) (16,5,5,0,2) ( 16 , 5 , 5 , 0 , 2 ) θ = 1 \theta=1 θ = 1 2 k − t = 5 = g 2k-t=5=g 2 k − t = 5 = g t = k t=k t = k t = k t=k t = k N [ x ] N[x] N [ x ] 1 + m ′ 1+m' 1 + m ′
The Schur complement for λ = 0 \lambda=0 λ = 0 ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 )
Theorem 4.3 takes only one thing from Proposition 4.2: the submatrix on N [ x ] N[x] N [ x ] τ = m ′ − ( 2 k − t ) \tau=m'-(2k-t) τ = m ′ − ( 2 k − t ) τ \tau τ ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 )
In this section λ = 0 \lambda=0 λ = 0 θ \theta θ θ ≠ 0 \theta\ne0 θ = 0 θ 3 − t θ − μ ( k − t ) ≠ 0 \theta^{3}-t\theta-\mu(k-t)\ne0 θ 3 − tθ − μ ( k − t ) = 0 x x x M M M Q Q Q P P P N ( x ) = N [ x ] ∖ { x } N(x)=N[x]\setminus\{x\} N ( x ) = N [ x ] ∖ { x } N ‾ = V ∖ N [ x ] \overline{N}=V\setminus N[x] N = V ∖ N [ x ] τ = m ′ − ( 2 k − t ) \tau=m'-(2k-t) τ = m ′ − ( 2 k − t )
L = B θ [ N [ x ] , N [ x ] ] , X = A [ N [ x ] , N ‾ ] , Y = A [ N ‾ , N [ x ] ] , F = Y L − 1 X . L=B_{\theta}[N[x],N[x]],\qquad X=A[N[x],\overline{N}],\qquad Y=A[\overline{N},N[x]],\qquad F=YL^{-1}X. L = B θ [ N [ x ] , N [ x ]] , X = A [ N [ x ] , N ] , Y = A [ N , N [ x ]] , F = Y L − 1 X . The matrix L L L L L L B θ B_{\theta} B θ T = B θ [ N ‾ , N ‾ ] − F T=B_{\theta}[\overline{N},\overline{N}]-F T = B θ [ N , N ] − F σ w = T ( w , w ) \sigma_w=T(w,w) σ w = T ( w , w )
Lemma 5.1. Under these assumptions:
the vector u ^ = ( 1 + θ / μ ) e x + μ − 1 1 N ‾ \hat{u}=(1+\theta/\mu)e_x+\mu^{-1}\mathbf{1}_{\overline{N}} u ^ = ( 1 + θ / μ ) e x + μ − 1 1 N B θ u ^ = 1 B_{\theta}\hat{u}=1 B θ u ^ = 1 u ~ = ( 1 + θ / μ ) e x + μ − 1 1 N \tilde{u}=(1+\theta/\mu)e_x+\mu^{-1}\mathbf{1}_{N} u ~ = ( 1 + θ / μ ) e x + μ − 1 1 N u ~ T B θ = 1 T \tilde{u}^{\mathsf{T}}B_{\theta}=1^{\mathsf{T}} u ~ T B θ = 1 T Y L − 1 1 = 1 YL^{-1}1=1 Y L − 1 1 = 1 1 T L − 1 X = 1 T 1^{\mathsf{T}}L^{-1}X=1^{\mathsf{T}} 1 T L − 1 X = 1 T
X Y = Φ XY=\Phi X Y = Φ Φ = μ J − L 2 + q L \Phi=\mu J-L^{2}+qL Φ = μ J − L 2 + q L n , n ′ ∈ N [ x ] n,n'\in N[x] n , n ′ ∈ N [ x ] Φ ( n , n ′ ) \Phi(n,n') Φ ( n , n ′ ) w w w n → w → n ′ n\to w\to n' n → w → n ′
X T = 0 XT=0 X T = 0 T Y = 0 TY=0 T Y = 0 T 2 = q T T^{2}=qT T 2 = q T T / q T/q T / q τ \tau τ T T T τ q \tau q τ q
Proof. (1) The column x x x A 2 = t I + μ ( J − I − A ) A^2=tI+\mu(J-I-A) A 2 = t I + μ ( J − I − A ) ( A 1 Γ − ) y = t [ y = x ] + μ ( 1 − [ y = x ] − A ( y , x ) ) (A1_{\Gamma^-})_y=t[y=x]+\mu(1-[y=x]-A(y,x)) ( A 1 Γ − ) y = t [ y = x ] + μ ( 1 − [ y = x ] − A ( y , x )) A e x = 1 Γ − Ae_x=1_{\Gamma^-} A e x = 1 Γ − y ≠ x y\ne x y = x y y y B θ u ^ B_\theta\hat{u} B θ u ^ ( 1 + θ / μ ) A ( y , x ) + 1 − A ( y , x ) − ( θ / μ ) A ( y , x ) = 1 (1+\theta/\mu)A(y,x)+1-A(y,x)-(\theta/\mu)A(y,x)=1 ( 1 + θ / μ ) A ( y , x ) + 1 − A ( y , x ) − ( θ / μ ) A ( y , x ) = 1 y = x y=x y = x t / μ − θ ( 1 + θ / μ ) = ( t − μ θ − θ 2 ) / μ = 1 t/\mu-\theta(1+\theta/\mu)=(t-\mu\theta-\theta^2)/\mu=1 t / μ − θ ( 1 + θ / μ ) = ( t − μ θ − θ 2 ) / μ = 1 θ 2 + μ θ = t − μ \theta^2+\mu\theta=t-\mu θ 2 + μ θ = t − μ u ^ \hat{u} u ^ N [ x ] N[x] N [ x ] N [ x ] N[x] N [ x ] L u ^ N [ x ] = 1 L\hat{u}_{N[x]}=1 L u ^ N [ x ] = 1 N ‾ \overline{N} N Y u ^ N [ x ] = 1 Y\hat{u}_{N[x]}=1 Y u ^ N [ x ] = 1 Y L − 1 1 = 1 YL^{-1}1=1 Y L − 1 1 = 1 u ˇ \check{u} u ˇ x x x
(2) By item 1 of Lemma 3.1, B θ 2 = q B θ + μ J B_\theta^2=qB_\theta+\mu J B θ 2 = q B θ + μ J ( N [ x ] , N [ x ] ) (N[x],N[x]) ( N [ x ] , N [ x ]) L 2 + X Y = q L + μ J L^2+XY=qL+\mu J L 2 + X Y = q L + μ J
(3) Substitute B θ [ N ‾ , N ‾ ] = F + T B_\theta[\overline{N},\overline{N}]=F+T B θ [ N , N ] = F + T ( N [ x ] , N ‾ ) (N[x],\overline{N}) ( N [ x ] , N ) L X + X ( F + T ) = q X + μ J LX+X(F+T)=qX+\mu J L X + X ( F + T ) = q X + μ J X F = X Y L − 1 X = μ J L − 1 X − L X + q X XF=XYL^{-1}X=\mu J L^{-1}X-LX+qX X F = X Y L − 1 X = μ J L − 1 X − L X + q X J L − 1 X = J JL^{-1}X=J J L − 1 X = J X T = 0 XT=0 X T = 0 ( N ‾ , N [ x ] ) (\overline{N},N[x]) ( N , N [ x ]) T Y = 0 TY=0 T Y = 0 ( N ‾ , N ‾ ) (\overline{N},\overline{N}) ( N , N ) Y X + ( F + T ) 2 = q ( F + T ) + μ J YX+(F+T)^2=q(F+T)+\mu J Y X + ( F + T ) 2 = q ( F + T ) + μ J F T FT F T T F TF T F F 2 = Y L − 1 ( X Y ) L − 1 X = μ J − Y X + q F F^2=YL^{-1}(XY)L^{-1}X=\mu J-YX+qF F 2 = Y L − 1 ( X Y ) L − 1 X = μ J − Y X + q F T 2 = q T T^2=qT T 2 = q T T T T 1 + m ′ − ( 2 k − t + 1 ) = τ 1+m'-(2k-t+1)=\tau 1 + m ′ − ( 2 k − t + 1 ) = τ
For a given neighbourhood the matrix F F F N ( x ) N(x) N ( x ) F ( w , w ′ ) = Y ( w , ⋅ ) L − 1 X ( ⋅ , w ′ ) F(w,w')=Y(w,\cdot)L^{-1}X(\cdot,w') F ( w , w ′ ) = Y ( w , ⋅ ) L − 1 X ( ⋅ , w ′ ) x x x ( Γ + ( w ) ∩ N ( x ) , Γ − ( w ) ∩ N ( x ) ) (\Gamma^+(w)\cap N(x),\Gamma^-(w)\cap N(x)) ( Γ + ( w ) ∩ N ( x ) , Γ − ( w ) ∩ N ( x )) w w w F ( w , w ′ ) F(w,w') F ( w , w ′ ) w w w w ′ w' w ′ A [ N ‾ , N ‾ ] = θ I + F + T A[\overline{N},\overline{N}]=\theta I+F+T A [ N , N ] = θ I + F + T T T T τ \tau τ τ = 0 \tau=0 τ = 0 A A A Theorem 4.3 is attained are of this kind.
Proposition 5.2. Let τ ≥ 1 \tau\ge1 τ ≥ 1 T T T T [ R , R ] T[R,R] T [ R , R ] τ \tau τ T = T [ ⋅ , R ] T [ R , R ] − 1 T [ R , ⋅ ] T=T[\cdot,R]T[R,R]^{-1}T[R,\cdot] T = T [ ⋅ , R ] T [ R , R ] − 1 T [ R , ⋅ ] τ = 1 \tau=1 τ = 1 w 0 w_0 w 0 σ 0 = σ w 0 ≠ 0 \sigma_0=\sigma_{w_0}\ne0 σ 0 = σ w 0 = 0 w , w ′ w,w' w , w ′
T ( w , w ′ ) = T ( w , w 0 ) T ( w 0 , w ′ ) σ 0 , σ w σ w ′ = T ( w , w ′ ) T ( w ′ , w ) . T(w,w')=\frac{T(w,w_0)T(w_0,w')}{\sigma_0},\qquad\sigma_w\sigma_{w'}=T(w,w')T(w',w). T ( w , w ′ ) = σ 0 T ( w , w 0 ) T ( w 0 , w ′ ) , σ w σ w ′ = T ( w , w ′ ) T ( w ′ , w ) . Therefore, for w ≠ w ′ w\ne w' w = w ′ A ( w , w ′ ) = F ( w , w ′ ) + T ( w , w 0 ) T ( w 0 , w ′ ) / σ 0 A(w,w')=F(w,w')+T(w,w_0)T(w_0,w')/\sigma_0 A ( w , w ′ ) = F ( w , w ′ ) + T ( w , w 0 ) T ( w 0 , w ′ ) / σ 0 w , w ′ , w 0 w,w',w_0 w , w ′ , w 0 w 0 w_0 w 0 w , w ′ w,w' w , w ′
Proof. The matrix T / q T/q T / q τ \tau τ τ \tau τ T / q T/q T / q τ \tau τ τ \tau τ 1 1 1 T T T τ \tau τ B θ B_\theta B θ τ = 1 \tau=1 τ = 1 R = { w 0 } R=\{w_0\} R = { w 0 } w ≠ w 0 w\ne w_0 w = w 0 T ( w , w 0 ) = A ( w , w 0 ) − F ( w , w 0 ) T(w,w_0)=A(w,w_0)-F(w,w_0) T ( w , w 0 ) = A ( w , w 0 ) − F ( w , w 0 ) T ( w 0 , w ) = A ( w 0 , w ) − F ( w 0 , w ) T(w_0,w)=A(w_0,w)-F(w_0,w) T ( w 0 , w ) = A ( w 0 , w ) − F ( w 0 , w )
We call the vertex w 0 w_0 w 0 pivot .
Comparison with the undirected case. In the proof of Proposition 1 of Bondarenko and Radchenko [18 pp. 524–525] the vectors of the Euclidean representation on the neighbourhood of a vertex are linearly independent; their inner products are given by the subgraph on the neighbourhood. There are exactly g g g R g \mathbb{R}^g R g τ = 0 \tau=0 τ = 0 [19 Theorem 1.2] recovers a graph from an induced subgraph on v − m v-m v − m m m m θ \theta θ θ \theta θ ∣ R ∣ = 1 + m ′ |R|=1+m' ∣ R ∣ = 1 + m ′ [20 ] . For (48, 9, 5, 0, 2) the submatrix on N [ x ] N[x] N [ x ] τ = 1 \tau=1 τ = 1
The reduction for (48, 9, 5, 0, 2). For θ = 1 \theta=1 θ = 1 θ ′ = − 3 \theta'=-3 θ ′ = − 3 m ′ = g = 14 m'=g=14 m ′ = g = 14 ∣ N [ x ] ∣ = 2 k − t + 1 = 14 |N[x]|=2k-t+1=14 ∣ N [ x ] ∣ = 2 k − t + 1 = 14 τ = 1 \tau=1 τ = 1 T T T τ q = − 4 \tau q=-4 τ q = − 4 A A A 34 ⋅ 33 = 1 122 34\cdot33=1\,122 34 ⋅ 33 = 1 122 F F F σ w \sigma_w σ w
Theorem 5.3. There is no DSRG (48, 9, 5, 0, 2), and none with the complementary parameters (48, 38, 34, 30, 30).
Proof. If the graph exists, Proposition A.2 gives a set of triples satisfying conditions (a)–(f) for one of the pivot orbits of one of the two graphs of arcs from Q Q Q P P P
The left kernel for λ = 1 \lambda=1 λ = 1 t = 2 μ t=2\mu t = 2 μ
For λ = 1 \lambda=1 λ = 1 N [ x ] N[x] N [ x ] Γ + ( x ) \Gamma^{+}(x) Γ + ( x ) K 1 K_1 K 1
In this section λ = 1 \lambda=1 λ = 1 t = 2 μ t=2\mu t = 2 μ 0 < t < k < v − 1 0<t<k<v-1 0 < t < k < v − 1 x 2 + ( μ − 1 ) x − μ = ( x − 1 ) ( x + μ ) x^2+(\mu-1)x-\mu=(x-1)(x+\mu) x 2 + ( μ − 1 ) x − μ = ( x − 1 ) ( x + μ ) r = 1 r=1 r = 1 s = − μ s=-\mu s = − μ Δ = ( μ + 1 ) 2 > 0 \Delta=(\mu+1)^2>0 Δ = ( μ + 1 ) 2 > 0 ( μ + 1 ) g = k + v − 1 (\mu+1)g=k+v-1 ( μ + 1 ) g = k + v − 1 k 2 = t + k + μ ( v − k − 1 ) k^2=t+k+\mu(v-k-1) k 2 = t + k + μ ( v − k − 1 )
μ ( v − k + 1 ) = k ( k − 1 ) . (1) \mu(v-k+1)=k(k-1). \tag*{(1)} μ ( v − k + 1 ) = k ( k − 1 ) . (1) By item 6 of Lemma 3.1 with θ = 1 \theta=1 θ = 1 K 1 = v ( A − I ) − ( k − 1 ) J K_1=v(A-I)-(k-1)J K 1 = v ( A − I ) − ( k − 1 ) J g g g x x x Γ + = Γ + ( x ) \Gamma^{+}=\Gamma^{+}(x) Γ + = Γ + ( x ) M = Γ + ∩ Γ − ( x ) M=\Gamma^{+}\cap\Gamma^{-}(x) M = Γ + ∩ Γ − ( x ) S = { x } ∪ Γ + S=\{x\}\cup\Gamma^{+} S = { x } ∪ Γ + Z = V ∖ S Z=V\setminus S Z = V ∖ S Z Z Z v − k − 1 v-k-1 v − k − 1
Lemma 6.1. Let λ = 1 \lambda=1 λ = 1
every vertex y ∈ Γ + y\in\Gamma^{+} y ∈ Γ + Γ + \Gamma^{+} Γ + pred ( y ) \operatorname{pred}(y) pred ( y ) Γ + \Gamma^{+} Γ + pred ( y ) → y \operatorname{pred}(y)\to y pred ( y ) → y
every connected component Ω 1 , … , Ω c \Omega_1,\ldots,\Omega_c Ω 1 , … , Ω c Γ + \Gamma^+ Γ + n i = ∣ Ω i ∣ ≥ 2 n_i=|\Omega_i|\ge2 n i = ∣ Ω i ∣ ≥ 2
let m i = ∣ M ∩ Ω i ∣ m_i=|M\cap\Omega_i| m i = ∣ M ∩ Ω i ∣ z ∈ Z z\in Z z ∈ Z ℓ i ( z ) = ∣ Γ − ( z ) ∩ Ω i ∣ \ell_i(z)=|\Gamma^-(z)\cap\Omega_i| ℓ i ( z ) = ∣ Γ − ( z ) ∩ Ω i ∣ Ω i \Omega_i Ω i z z z ∑ i m i = t \sum_i m_i=t ∑ i m i = t ∑ z ∈ Z ℓ i ( z ) = ( k − 1 ) n i − m i \sum_{z\in Z}\ell_i(z)=(k-1)n_i-m_i ∑ z ∈ Z ℓ i ( z ) = ( k − 1 ) n i − m i
Proof. (1) The in-neighbours of y y y Γ + \Gamma^+ Γ + x → u → y x\to u\to y x → u → y A 2 ( x , y ) = λ = 1 A^2(x,y)=\lambda=1 A 2 ( x , y ) = λ = 1 pred ( y ) ≠ y \operatorname{pred}(y)\ne y pred ( y ) = y
(2) A vertex y y y pred ( y ) ≠ y \operatorname{pred}(y)\ne y pred ( y ) = y
(3) ∑ i m i = ∣ M ∣ = A 2 ( x , x ) = t \sum_i m_i=|M|=A^2(x,x)=t ∑ i m i = ∣ M ∣ = A 2 ( x , x ) = t Ω i \Omega_i Ω i k n i kn_i k n i m i m_i m i x x x n i n_i n i Γ + \Gamma^+ Γ + Γ + \Gamma^+ Γ + Γ + \Gamma^+ Γ + pred \operatorname{pred} pred ( k − 1 ) n i − m i (k-1)n_i-m_i ( k − 1 ) n i − m i Z Z Z
Define the matrix D D D c c c d = ( k m i − t n i ) i d=(km_i-tn_i)_i d = ( k m i − t n i ) i h z = ( 2 ℓ i ( z ) − m i ) i h_z=(2\ell_i(z)-m_i)_i h z = ( 2 ℓ i ( z ) − m i ) i z ∈ Z z\in Z z ∈ Z a ∈ R c a\in\mathbb{R}^c a ∈ R c w a = 1 2 ( ∑ i a i m i ) e x + ∑ i a i 1 Ω i w_a=\frac{1}{2}\left(\sum_i a_i m_i\right)e_x+\sum_i a_i\mathbf{1}_{\Omega_i} w a = 2 1 ( ∑ i a i m i ) e x + ∑ i a i 1 Ω i
Theorem 6.2. Let λ = 1 \lambda=1 λ = 1 t = 2 μ t=2\mu t = 2 μ 0 < t < k < v − 1 0<t<k<v-1 0 < t < k < v − 1 w w w S S S w T K 1 = 0 w^{\mathsf{T}}K_1=0 w T K 1 = 0 w = w a w=w_a w = w a a ∈ R c a\in\mathbb{R}^c a ∈ R c D a = 0 Da=0 D a = 0
Proof. Let W = ∑ y ∈ S w y W=\sum_{y\in S}w_y W = ∑ y ∈ S w y κ = ( k − 1 ) W / v \kappa=(k-1)W/v κ = ( k − 1 ) W / v z z z w T K 1 = 0 w^{\mathsf{T}}K_1=0 w T K 1 = 0 v v v ∑ y ∈ S w y A ( y , z ) − w z [ z ∈ S ] = κ \sum_{y\in S}w_yA(y,z)-w_z[z\in S]=\kappa ∑ y ∈ S w y A ( y , z ) − w z [ z ∈ S ] = κ x x x S S S M M M z ∈ Γ + z\in\Gamma^+ z ∈ Γ + S S S x x x pred ( z ) \operatorname{pred}(z) pred ( z ) z ∈ Z z\in Z z ∈ Z S S S Γ + \Gamma^+ Γ + x → z x\to z x → z
w ( M ) − w x = κ , w(M)-w_x=\kappa, w ( M ) − w x = κ , w z − w pred ( z ) = w x − κ ( z ∈ Γ + ) , w_z-w_{\operatorname{pred}(z)}=w_x-\kappa\qquad(z\in\Gamma^+), w z − w pred ( z ) = w x − κ ( z ∈ Γ + ) , ∑ y ∈ Γ + w y A ( y , z ) = κ ( z ∈ Z ) . \sum_{y\in\Gamma^+}w_yA(y,z)=\kappa\qquad(z\in Z). y ∈ Γ + ∑ w y A ( y , z ) = κ ( z ∈ Z ) . The right-hand side of the second equality, δ = w x − κ \delta=w_x-\kappa δ = w x − κ z ∈ Γ + z\in\Gamma^+ z ∈ Γ + w w w Γ + \Gamma^+ Γ + δ ≥ 0 \delta\ge0 δ ≥ 0 δ ≤ 0 \delta\le0 δ ≤ 0 δ = 0 \delta=0 δ = 0 w w w pred ( z ) → z \operatorname{pred}(z)\to z pred ( z ) → z a i a_i a i Ω i \Omega_i Ω i w x = κ w_x=\kappa w x = κ
The first equality gives ∑ i a i m i = 2 w x \sum_i a_i m_i=2w_x ∑ i a i m i = 2 w x κ = w x \kappa=w_x κ = w x v w x = ( k − 1 ) ( w x + ∑ i a i n i ) vw_x=(k-1)(w_x+\sum_i a_i n_i) v w x = ( k − 1 ) ( w x + ∑ i a i n i ) ( v − k + 1 ) w x = ( k − 1 ) ∑ i a i n i (v-k+1)w_x=(k-1)\sum_i a_i n_i ( v − k + 1 ) w x = ( k − 1 ) ∑ i a i n i k w x = μ ∑ i a i n i kw_x=\mu\sum_i a_i n_i k w x = μ ∑ i a i n i w x = 1 2 ∑ i a i m i w_x=\frac{1}{2}\sum_i a_i m_i w x = 2 1 ∑ i a i m i t = 2 μ t=2\mu t = 2 μ d ⋅ a = 0 d\cdot a=0 d ⋅ a = 0 ∑ i a i ℓ i ( z ) = 1 2 ∑ i a i m i \sum_i a_i\ell_i(z)=\frac{1}{2}\sum_i a_i m_i ∑ i a i ℓ i ( z ) = 2 1 ∑ i a i m i h z ⋅ a = 0 h_z\cdot a=0 h z ⋅ a = 0
Corollary 6.3. Under the assumptions of Theorem 6.2:
dim ker D = c − rank D ≥ k + 1 − g \dim\ker D=c-\operatorname{rank}D\ge k+1-g dim ker D = c − rank D ≥ k + 1 − g
c ≥ k + 1 − g + [ d ≠ 0 ] c\ge k+1-g+[d\ne0] c ≥ k + 1 − g + [ d = 0 ] d = 0 d=0 d = 0 m i / n i = t / k m_i/n_i=t/k m i / n i = t / k i i i
Proof. (1) The rows of K 1 K_1 K 1 S S S k + 1 k+1 k + 1 g g g k + 1 − g k+1-g k + 1 − g a ↦ w a a\mapsto w_a a ↦ w a w a w_a w a Γ + \Gamma^+ Γ + a a a ker D \ker D ker D
(2) The row d d d D D D rank D ≥ [ d ≠ 0 ] \operatorname{rank}D\ge[d\ne0] rank D ≥ [ d = 0 ] d = 0 d=0 d = 0 k m i = t n i km_i=tn_i k m i = t n i i i i
Comparison with Theorem 6 of [16 ] . Theorem 6 of Hobart and Williford [16, p. 4]: if the multiplicity of θ \theta θ k k k θ ′ \theta' θ ′ A [ Γ + ( x ) , Γ + ( x ) ] A[\Gamma^{+}(x),\Gamma^{+}(x)] A [ Γ + ( x ) , Γ + ( x )] k k k θ \theta θ λ = 1 \lambda=1 λ = 1 t = 2 μ t=2\mu t = 2 μ pred ( y ) → y \operatorname{pred}(y)\to y pred ( y ) → y θ = s \theta=s θ = s c ≥ k − g c\ge k-g c ≥ k − g c ≥ k + 1 − g + [ d ≠ 0 ] c\ge k+1-g+[d\ne0] c ≥ k + 1 − g + [ d = 0 ] ( 55 , 16 , 12 , 1 , 6 ) (55,16,12,1,6) ( 55 , 16 , 12 , 1 , 6 ) c ≥ 6 c\ge6 c ≥ 6 c ≤ 8 c\le8 c ≤ 8 c = 8 c=8 c = 8 [16 ] has no equations of the rows h z h_z h z
Theorem 6.4. There is no DSRG ( 55 , 16 , 12 , 1 , 6 ) (55,16,12,1,6) ( 55 , 16 , 12 , 1 , 6 ) ( 55 , 38 , 34 , 27 , 24 ) (55,38,34,27,24) ( 55 , 38 , 34 , 27 , 24 )
Proof. Here t = 12 = 2 μ t=12=2\mu t = 12 = 2 μ g = 70 / 7 = 10 g=70/7=10 g = 70/7 = 10 k + 1 − g = 7 k+1-g=7 k + 1 − g = 7 ∣ Γ + ∣ = 16 |\Gamma^{+}|=16 ∣ Γ + ∣ = 16 n i ≥ 2 n_i\ge2 n i ≥ 2 d = 0 d=0 d = 0 m i / n i = 3 / 4 m_i/n_i=3/4 m i / n i = 3/4 4 ∣ n i 4\mid n_i 4 ∣ n i c ≤ 4 < 7 c\le4<7 c ≤ 4 < 7 d ≠ 0 d\ne0 d = 0 c ≥ 8 c\ge8 c ≥ 8 c = 8 c=8 c = 8 n i = 2 n_i=2 n i = 2 y ↔ y ′ y\leftrightarrow y' y ↔ y ′ pred ( y ) = y ′ \operatorname{pred}(y)=y' pred ( y ) = y ′ pred ( y ′ ) = y \operatorname{pred}(y')=y pred ( y ′ ) = y m i ∈ { 2 , 1 , 0 } m_i\in\{2,1,0\} m i ∈ { 2 , 1 , 0 } M M M d i = 16 m i − 24 d_i=16m_i-24 d i = 16 m i − 24 8 8 8 − 8 -8 − 8 − 24 -24 − 24
The row d ≠ 0 d\ne0 d = 0 D D D ker D ⊆ ker d \ker D\subseteq\ker d ker D ⊆ ker d dim ker d = c − 1 = 7 \dim\ker d=c-1=7 dim ker d = c − 1 = 7 dim ker D ≥ 7 \dim\ker D\ge7 dim ker D ≥ 7 ker D = ker d \ker D=\ker d ker D = ker d a ∈ R 8 a\in\mathbb{R}^{8} a ∈ R 8 d ⋅ a = 0 d\cdot a=0 d ⋅ a = 0 h z ⋅ a = 0 h_z\cdot a=0 h z ⋅ a = 0 z ∈ Z z\in Z z ∈ Z ∑ i m i = t = 12 \sum_i m_i=t=12 ∑ i m i = t = 12 i i i m i = 2 m_i=2 m i = 2 j j j m j ≤ 1 m_j\le1 m j ≤ 1 e i e_i e i i i i
If there is a pair j j j m j = 1 m_j=1 m j = 1 a = e i + e j a=e_i+e_j a = e i + e j d ⋅ a = 8 − 8 = 0 d\cdot a=8-8=0 d ⋅ a = 8 − 8 = 0 h z ⋅ a = 2 ( ℓ i ( z ) + ℓ j ( z ) ) − 3 h_z\cdot a=2(\ell_i(z)+\ell_j(z))-3 h z ⋅ a = 2 ( ℓ i ( z ) + ℓ j ( z )) − 3 Z Z Z
Otherwise there is a pair j j j m j = 0 m_j=0 m j = 0 a = e j + 3 e i a=e_j+3e_i a = e j + 3 e i d ⋅ a = − 24 + 24 = 0 d\cdot a=-24+24=0 d ⋅ a = − 24 + 24 = 0 h z ⋅ a = 2 ℓ j ( z ) + 3 ( 2 ℓ i ( z ) − 2 ) = 0 h_z\cdot a=2\ell_j(z)+3(2\ell_i(z)-2)=0 h z ⋅ a = 2 ℓ j ( z ) + 3 ( 2 ℓ i ( z ) − 2 ) = 0 ℓ j ( z ) = 3 − 3 ℓ i ( z ) \ell_j(z)=3-3\ell_i(z) ℓ j ( z ) = 3 − 3 ℓ i ( z ) 0 ≤ ℓ j ( z ) ≤ n j = 2 0\le\ell_j(z)\le n_j=2 0 ≤ ℓ j ( z ) ≤ n j = 2 ℓ j ( z ) = 0 \ell_j(z)=0 ℓ j ( z ) = 0 Z Z Z ( k − 1 ) ⋅ 2 = 30 (k-1)\cdot2=30 ( k − 1 ) ⋅ 2 = 30
Both cases are impossible. The complement does not exist because the graph itself does not.
Twin classes for t = λ + 1 t=\lambda+1 t = λ + 1
In this section t = λ + 1 t=\lambda+1 t = λ + 1 θ = − 1 \theta=-1 θ = − 1 B = A + I B=A+I B = A + I x x x N + [ x ] N^{+}[x] N + [ x ] y y y N − [ y ] N^{-}[y] N − [ y ] K = k + 1 K=k+1 K = k + 1 q = λ + 2 − μ q=\lambda+2-\mu q = λ + 2 − μ μ ≤ t \mu\le t μ ≤ t [12 Lemma 2.1] , q = t + 1 − μ ≥ 1 q=t+1-\mu\ge1 q = t + 1 − μ ≥ 1 q − 1 q-1 q − 1 q q q θ ′ − θ \theta'-\theta θ ′ − θ f f f x ≠ y x\ne y x = y N + [ x ] = N + [ y ] N^{+}[x]=N^{+}[y] N + [ x ] = N + [ y ] row twins , and those with N − [ x ] = N − [ y ] N^{-}[x]=N^{-}[y] N − [ x ] = N − [ y ] column twins . The class C x C_x C x x x x C x ′ C'_x C x ′ a = ∣ C x ∣ a=|C_x| a = ∣ C x ∣ a ′ = ∣ C x ′ ∣ a'=|C'_x| a ′ = ∣ C x ′ ∣ B B B
Lemma 7.1. Let t = λ + 1 t=\lambda+1 t = λ + 1 q > 0 q>0 q > 0
(1) B 2 = q B + μ J B^2=qB+\mu J B 2 = q B + μ J x , y x,y x , y ∣ N + [ x ] ∩ N − [ y ] ∣ |N^{+}[x]\cap N^{-}[y]| ∣ N + [ x ] ∩ N − [ y ] ∣ λ + 2 \lambda+2 λ + 2 y ∈ N + [ x ] y\in N^{+}[x] y ∈ N + [ x ] μ \mu μ K 2 = q K + μ v K^2=qK+\mu v K 2 = q K + μv
(2) rank B = 1 + f B = 1 + f B = 1 + f q f = v − K qf = v - K q f = v − K
(3) if μ = 1 \mu= 1 μ = 1 v = K ( k − λ ) v = K(k - \lambda) v = K ( k − λ ) ( λ + 1 ) f = v − K (\lambda+ 1)f = v - K ( λ + 1 ) f = v − K f = K f = K f = K k = 2 λ + 2 k = 2\lambda+ 2 k = 2 λ + 2
Proof. (1) This is item 1 of Lemma 3.1 with θ = − 1 \theta= -1 θ = − 1 θ ′ = q − 1 \theta' = q - 1 θ ′ = q − 1 θ ′ − θ = q \theta' - \theta= q θ ′ − θ = q ( x , y ) (x,y) ( x , y ) B 2 B^2 B 2 ∣ N + [ x ] ∩ N − [ y ] ∣ \lvert N^+[x] \cap N^-[y]\rvert ∣ N + [ x ] ∩ N − [ y ]∣ q [ y ∈ N + [ x ] ] + μ q[y \in N^+[x]] + \mu q [ y ∈ N + [ x ]] + μ K 2 = q K + μ v K^2 = qK + \mu v K 2 = q K + μv
(2) The rank is given by item 2 of Lemma 3.1. The formula for m ′ m' m ′ q f = − k + ( v − 1 ) = v − K qf = -k + (v - 1) = v - K q f = − k + ( v − 1 ) = v − K
(3) For μ = 1 \mu= 1 μ = 1 v = K 2 − q K = K ( k − λ ) v = K^2 - qK = K(k - \lambda) v = K 2 − q K = K ( k − λ ) ( λ + 1 ) f = v − K = K ( k − λ − 1 ) (\lambda+ 1)f = v - K = K(k - \lambda- 1) ( λ + 1 ) f = v − K = K ( k − λ − 1 ) f = K f = K f = K k − λ − 1 = λ + 1 k - \lambda- 1 = \lambda+ 1 k − λ − 1 = λ + 1
Lemma 7.2. We have C x ⊆ N + [ x ] ∩ N − [ x ] C_x \subseteq N^+[x] \cap N^-[x] C x ⊆ N + [ x ] ∩ N − [ x ] U = N + [ x ] ∖ C x U = N^+[x] \setminus C_x U = N + [ x ] ∖ C x a ≤ λ + 1 a \leq\lambda+ 1 a ≤ λ + 1 C x ⊆ N − [ z ] C_x \subseteq N^-[z] C x ⊆ N − [ z ] z ∈ N + [ x ] z \in N^+[x] z ∈ N + [ x ]
Proof. If y ∈ C x y \in C_x y ∈ C x y ∈ N + [ y ] = N + [ x ] y \in N^+[y] = N^+[x] y ∈ N + [ y ] = N + [ x ] x ∈ N + [ x ] = N + [ y ] x \in N^+[x] = N^+[y] x ∈ N + [ x ] = N + [ y ] y ∈ N − [ x ] y \in N^-[x] y ∈ N − [ x ] z ∈ N + [ x ] z \in N^+[x] z ∈ N + [ x ] z ∈ N + [ y ] z \in N^+[y] z ∈ N + [ y ] y ∈ C x y \in C_x y ∈ C x C x ⊆ N − [ z ] C_x \subseteq N^-[z] C x ⊆ N − [ z ] U U U N + [ x ] ⊆ N − [ x ] N^+[x] \subseteq N^-[x] N + [ x ] ⊆ N − [ x ] K = ∣ N + [ x ] ∩ N − [ x ] ∣ = λ + 2 = t + 1 K = \lvert N^+[x] \cap N^-[x]\rvert= \lambda+ 2 = t + 1 K = ∣ N + [ x ] ∩ N − [ x ]∣ = λ + 2 = t + 1 k = t k = t k = t z ∈ U z \in U z ∈ U C x ∪ { z } C_x \cup\{z\} C x ∪ { z } N + [ x ] ∩ N − [ z ] N^+[x] \cap N^-[z] N + [ x ] ∩ N − [ z ] λ + 2 \lambda+ 2 λ + 2
The rows of A + I A + I A + I J − I − A J - I - A J − I − A a ≤ λ + 1 a \leq\lambda+ 1 a ≤ λ + 1 [21 Theorem 10(a)] on such classes, applied to the complement. For t = λ + 1 t = \lambda+ 1 t = λ + 1 r r r A + I A + I A + I s = − 1 s = -1 s = − 1 f + 1 f + 1 f + 1 2 f 2f 2 f [12 Theorem 5.1] . This theorem bounds from below the number of classes, not the size of the class of a vertex.
Proposition 7.3 (rank against the class). Let μ = 1 \mu= 1 μ = 1 The rows of B B B { x } ∪ ( N + [ x ] ∖ C x ) \{x\} \cup(N^+[x] \setminus C_x) { x } ∪ ( N + [ x ] ∖ C x ) Hence K + 1 − a ≤ 1 + f K + 1 - a \leq1 + f K + 1 − a ≤ 1 + f a ≥ K − f a \geq K - f a ≥ K − f
Proof. Let O = Γ + ( x ) O = \Gamma^+(x) O = Γ + ( x ) C x ∖ { x } ⊆ O C_x \setminus\{x\} \subseteq O C x ∖ { x } ⊆ O o ∈ O ∖ C x o \in O \setminus C_x o ∈ O ∖ C x w o ∈ N + [ o ] ∖ N + [ x ] w_o \in N^+[o] \setminus N^+[x] w o ∈ N + [ o ] ∖ N + [ x ] ∣ N + [ x ] ∩ N − [ w o ] ∣ = μ = 1 \lvert N^+[x] \cap N^-[w_o]\rvert= \mu= 1 ∣ N + [ x ] ∩ N − [ w o ]∣ = μ = 1 o o o { x } ∪ ( O ∖ C x ) \{x\} \cup(O \setminus C_x) { x } ∪ ( O ∖ C x ) w o w_o w o o o o w o w_o w o x x x x x x w o w_o w o B B B { x } ∪ { w o } \{x\} \cup\{w_o\} { x } ∪ { w o }
Theorem 6 of Jørgensen [13 ] is the same link between the rank and coinciding columns of a binary matrix, taken for the whole matrix. If a matrix of zeros and ones of order n n n k k k ρ \rho ρ k / n ≥ 1 / ρ k/n \geq1/\rho k / n ≥ 1/ ρ ρ \rho ρ k / n = 1 / ρ k/n = 1/\rho k / n = 1/ ρ ρ \rho ρ B = A + I B = A + I B = A + I K ( 1 + f ) ≥ v K(1 + f) \geq v K ( 1 + f ) ≥ v t = λ + 1 t = \lambda+ 1 t = λ + 1 q f = v − K qf=v-K q f = v − K ( v − K ) ( K − q ) = 0 (v-K)(K-q)=0 ( v − K ) ( K − q ) = 0 v > K > q v>K>q v > K > q N + [ x ] N^+[x] N + [ x ] C x C_x C x x x x k / n k/n k / n
For u ∉ C x u\notin C_x u ∈ / C x γ u = ∣ N + [ u ] ∩ C x ∣ \gamma_u=\lvert N^+[u]\cap C_x\rvert γ u = ∣ N + [ u ] ∩ C x ∣ u u u
Proposition 7.4. If u ∉ C x u\notin C_x u ∈ / C x γ u ≤ μ \gamma_u\leq\mu γ u ≤ μ ∑ u ∈ U γ u = a ( λ + 2 − a ) \sum_{u\in U}\gamma_u=a(\lambda+2-a) ∑ u ∈ U γ u = a ( λ + 2 − a ) a ( λ + 2 − a ) ≤ μ ( K − a ) a(\lambda+2-a)\leq\mu(K-a) a ( λ + 2 − a ) ≤ μ ( K − a ) μ = 1 \mu=1 μ = 1 a ( λ + 3 − a ) ≤ K a(\lambda+3-a)\leq K a ( λ + 3 − a ) ≤ K
Proof. The rows u u u x x x B B B K K K w ∈ N + [ x ] ∖ N + [ u ] w\in N^+[x]\setminus N^+[u] w ∈ N + [ x ] ∖ N + [ u ] C x ⊆ N − [ w ] C_x\subseteq N^-[w] C x ⊆ N − [ w ] N + [ u ] ∩ C x ⊆ N + [ u ] ∩ N − [ w ] N^+[u]\cap C_x\subseteq N^+[u]\cap N^-[w] N + [ u ] ∩ C x ⊆ N + [ u ] ∩ N − [ w ] μ \mu μ ( y , u ) (y,u) ( y , u ) y ∈ C x y\in C_x y ∈ C x u ∈ U u\in U u ∈ U y ∈ N + [ u ] y\in N^+[u] y ∈ N + [ u ] y ∈ C x y\in C_x y ∈ C x N + [ x ] ∩ N − [ y ] N^+[x]\cap N^-[y] N + [ x ] ∩ N − [ y ] λ + 2 \lambda+2 λ + 2 λ + 2 − a \lambda+2-a λ + 2 − a U U U u u u ∑ u ∈ U γ u ≤ μ ∣ U ∣ = μ ( K − a ) \sum_{u\in U}\gamma_u\leq\mu|U|=\mu(K-a) ∑ u ∈ U γ u ≤ μ ∣ U ∣ = μ ( K − a )
Proposition 7.5. For any μ \mu μ
if u ∉ C x u\notin C_x u ∈ / C x ∣ N + [ u ] ∖ N + [ x ] ∣ ≥ q \lvert N^+[u]\setminus N^+[x]\rvert\geq q ∣ N + [ u ] ∖ N + [ x ]∣ ≥ q q ( K − a ) ≤ μ ( v − K ) q(K-a)\leq\mu(v-K) q ( K − a ) ≤ μ ( v − K ) a ≥ K − μ f a\geq K-\mu f a ≥ K − μ f
a ≤ K − q a\leq K-q a ≤ K − q
Proof. (1) There is w ∈ N + [ u ] ∖ N + [ x ] w\in N^+[u]\setminus N^+[x] w ∈ N + [ u ] ∖ N + [ x ] N + [ u ] ∩ N − [ w ] N^+[u]\cap N^-[w] N + [ u ] ∩ N − [ w ] λ + 2 \lambda+2 λ + 2 N + [ x ] ∩ N − [ w ] N^+[x]\cap N^-[w] N + [ x ] ∩ N − [ w ] μ \mu μ q q q N + [ x ] N^+[x] N + [ x ] q ∣ U ∣ q|U| q ∣ U ∣ ( u , w ) (u,w) ( u , w ) u ∈ U u\in U u ∈ U w ∈ N + [ u ] ∖ N + [ x ] w\in N^+[u]\setminus N^+[x] w ∈ N + [ u ] ∖ N + [ x ] w ∉ N + [ x ] w\notin N^+[x] w ∈ / N + [ x ] μ \mu μ N + [ x ] N^+[x] N + [ x ] w ∈ N + [ x ] w\in N^+[x] w ∈ N + [ x ] μ ( v − K ) = q μ f \mu(v-K)=q\mu f μ ( v − K ) = q μ f q > 0 q>0 q > 0
(2) The set N + [ x ] ∩ N − [ x ] N^+[x]\cap N^-[x] N + [ x ] ∩ N − [ x ] λ + 2 \lambda+2 λ + 2 λ + 1 \lambda+1 λ + 1 u u u U U U x x x γ u ≥ 1 \gamma_u\geq1 γ u ≥ 1 y ∈ C x ∩ N + [ u ] y\in C_x\cap N^+[u] y ∈ C x ∩ N + [ u ] y y y N + [ u ] N^+[u] N + [ u ] N + [ x ] N^+[x] N + [ x ] ∣ N + [ u ] ∩ N − [ y ] ∣ = ∣ N + [ x ] ∩ N − [ y ] ∣ = λ + 2 \lvert N^+[u]\cap N^-[y]\rvert=\lvert N^+[x]\cap N^-[y]\rvert=\lambda+2 ∣ N + [ u ] ∩ N − [ y ]∣ = ∣ N + [ x ] ∩ N − [ y ]∣ = λ + 2 ∣ ( N + [ u ] ∖ N + [ x ] ) ∩ N − [ y ] ∣ = ∣ ( N + [ x ] ∖ N + [ u ] ) ∩ N − [ y ] ∣ \lvert(N^+[u]\setminus N^+[x])\cap N^-[y]\rvert=\lvert(N^+[x]\setminus N^+[u])\cap N^-[y]\rvert ∣( N + [ u ] ∖ N + [ x ]) ∩ N − [ y ]∣ = ∣( N + [ x ] ∖ N + [ u ]) ∩ N − [ y ]∣ C x ∖ N + [ u ] C_x\setminus N^+[u] C x ∖ N + [ u ] a − γ u a-\gamma_u a − γ u N − [ y ] ∖ N + [ x ] N^-[y]\setminus N^+[x] N − [ y ] ∖ N + [ x ] K − ( λ + 2 ) = k − λ − 1 K-(\lambda+2)=k-\lambda-1 K − ( λ + 2 ) = k − λ − 1 γ u ≤ μ \gamma_u\leq\mu γ u ≤ μ a ≤ k − λ − 1 + μ = K − q a\leq k-\lambda-1+\mu=K-q a ≤ k − λ − 1 + μ = K − q
For μ = 1 \mu=1 μ = 1 μ \mu μ a ≤ K − q a\leq K-q a ≤ K − q [3 ] : for B = A + I B=A+I B = A + I t = λ + 1 t=\lambda+1 t = λ + 1 a ≤ 3 a\leq3 a ≤ 3 [4 ] . We did not find the lower bound on the class at every vertex (Propositions 7.3 and 7.5 ) and inequality (7.1) below in [3 ] , [11 ] , [12 ] , [13 ] and [16 ] , nor the structure of a vertex without a twin (Theorem 7.8 ) in these works or in [4 ] and [21 ] . Together the two bounds give a condition on the parameters.
Theorem 7.6. If a DSRG with t = λ + 1 t = \lambda+ 1 t = λ + 1 μ < λ + 2 \mu< \lambda+ 2 μ < λ + 2
( λ + 2 − μ ) 2 ≤ μ ( v − k − 1 ) . (2) (\lambda+ 2 - \mu)^2 \le\mu(v - k - 1). \tag*{(2)} ( λ + 2 − μ ) 2 ≤ μ ( v − k − 1 ) . (2) In particular, there are no DSRGs ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) ( 40 , 9 , 6 , 5 , 1 ) (40,9,6,5,1) ( 40 , 9 , 6 , 5 , 1 ) ( 80 , 19 , 13 , 12 , 2 ) (80,19,13,12,2) ( 80 , 19 , 13 , 12 , 2 ) ( 96 , 80 , 75 , 65 , 75 ) (96,80,75,65,75) ( 96 , 80 , 75 , 65 , 75 ) ( 40 , 30 , 27 , 21 , 27 ) (40,30,27,21,27) ( 40 , 30 , 27 , 21 , 27 ) ( 80 , 60 , 54 , 42 , 54 ) (80,60,54,42,54) ( 80 , 60 , 54 , 42 , 54 )
Proof. At any vertex Proposition 7.5 gives K − μ f ≤ a ≤ K − q K-\mu f \le a \le K-q K − μ f ≤ a ≤ K − q q ≤ μ f q \le\mu f q ≤ μ f q > 0 q > 0 q > 0 q 2 ≤ μ q f = μ ( v − K ) q^2 \le\mu qf = \mu(v-K) q 2 ≤ μ q f = μ ( v − K ) ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) q = 10 > 8 = μ f q = 10 > 8 = \mu f q = 10 > 8 = μ f ( 40 , 9 , 6 , 5 , 1 ) (40,9,6,5,1) ( 40 , 9 , 6 , 5 , 1 ) q = 6 > 5 q = 6 > 5 q = 6 > 5 ( 80 , 19 , 13 , 12 , 2 ) (80,19,13,12,2) ( 80 , 19 , 13 , 12 , 2 ) q = 12 > 10 q = 12 > 10 q = 12 > 10
For ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) ( 40 , 9 , 6 , 5 , 1 ) (40,9,6,5,1) ( 40 , 9 , 6 , 5 , 1 ) μ = 1 \mu= 1 μ = 1 a ≥ K − f a \ge K-f a ≥ K − f ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) a ≥ 8 a \ge8 a ≥ 8 Proposition 7.4 give a ≤ 10 a \le10 a ≤ 10 a ( 12 − a ) ≤ 16 a(12-a) \le16 a ( 12 − a ) ≤ 16 a = 8 , 9 , 10 a = 8,9,10 a = 8 , 9 , 10 Theorem 7.6 takes the lower one from counting as well (Proposition 7.5 ). The pairs ( 40 , 9 , 6 , 5 , 1 ) (40,9,6,5,1) ( 40 , 9 , 6 , 5 , 1 ) ( 80 , 19 , 13 , 12 , 2 ) (80,19,13,12,2) ( 80 , 19 , 13 , 12 , 2 ) [6 ] through a search over hyperplanes of rank 6 with Farkas certificates, together with the line ( 40 m , 30 m , 27 m , 21 m , 27 m ) (40m,30m,27m,21m,27m) ( 40 m , 30 m , 27 m , 21 m , 27 m ) ( 40 m , 10 m − 1 , 7 m − 1 , 7 m − 2 , m ) (40m,10m-1,7m-1,7m-2,m) ( 40 m , 10 m − 1 , 7 m − 1 , 7 m − 2 , m ) Theorem 7.6 gives them a two-line proof.
The clique blow-up maps a DSRG with t = λ + 1 t = \lambda+ 1 t = λ + 1 ( A + I ) ⊗ J m − I (A+I) \otimes J_m-I ( A + I ) ⊗ J m − I ( m v , m K − 1 , m ( λ + 2 ) − 1 , m ( λ + 2 ) − 2 , m μ ) (mv,mK-1,m(\lambda+2)-1,m(\lambda+2)-2,m\mu) ( m v , m K − 1 , m ( λ + 2 ) − 1 , m ( λ + 2 ) − 2 , m μ ) B ′ = B ⊗ J m B' = B \otimes J_m B ′ = B ⊗ J m B ′ 2 = m q B ′ + m μ J B'^2 = mqB' + m\mu J B ′2 = m q B ′ + m μ J K K K q q q μ \mu μ v v v m m m f f f [2 ] with t = λ + 1 t = \lambda+ 1 t = λ + 1 ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) ( 40 , 9 , 6 , 5 , 1 ) (40,9,6,5,1) ( 40 , 9 , 6 , 5 , 1 ) ( 48 , 17 , 12 , 11 , 3 ) (48,17,12,11,3) ( 48 , 17 , 12 , 11 , 3 ) ( 80 , 19 , 13 , 12 , 2 ) (80,19,13,12,2) ( 80 , 19 , 13 , 12 , 2 ) ( 80 , 23 , 16 , 15 , 3 ) (80,23,16,15,3) ( 80 , 23 , 16 , 15 , 3 ) ( 96 , 35 , 25 , 24 , 6 ) (96,35,25,24,6) ( 96 , 35 , 25 , 24 , 6 ) ( 8 m , 4 m − 1 , 3 m − 1 , 3 m − 2 , m ) (8m,4m-1,3m-1,3m-2,m) ( 8 m , 4 m − 1 , 3 m − 1 , 3 m − 2 , m ) m = 1 , … , 13 m = 1,\ldots,13 m = 1 , … , 13 f = 2 f = 2 f = 2 Proposition 7.5 gives a = 2 m a = 2m a = 2 m [12 Theorem 5.3] (they have exactly four classes of 2 m 2m 2 m ( 8 m , 4 m , 3 m , m , 3 m ) (8m,4m,3m,m,3m) ( 8 m , 4 m , 3 m , m , 3 m ) [11 Theorem 4] .
**Classes for μ = 1. ∗ ∗ F r o m n o w o n \mu= 1.** From now on μ = 1. ∗ ∗ F r o mn o w o n q = λ + 1 q = \lambda+ 1 q = λ + 1 B 2 = ( λ + 1 ) B + J B^2 = (\lambda+ 1)B + J B 2 = ( λ + 1 ) B + J
Lemma 7.7. Let μ = 1 \mu= 1 μ = 1
N + [ x ] N^+[x] N + [ x ] N − [ y ] N^-[y] N − [ y ]
∣ C x ∩ C x ′ ∣ = 1 |C_x \cap C_{x'}| = 1 ∣ C x ∩ C x ′ ∣ = 1
a + a ′ ≤ λ + 3 a + a' \le\lambda+ 3 a + a ′ ≤ λ + 3
Proof. (1) Let y ∈ N + [ x ] y \in N^+[x] y ∈ N + [ x ] y ′ y' y ′ y y y x ∈ N − [ y ] = N − [ y ′ ] x \in N^-[y] = N^-[y'] x ∈ N − [ y ] = N − [ y ′ ] y ′ ∈ N + [ x ] y' \in N^+[x] y ′ ∈ N + [ x ]
(2) Let z 0 ≠ z 1 z_0 \ne z_1 z 0 = z 1 x ∈ N − [ z 0 ] x \in N^-[z_0] x ∈ N − [ z 0 ] y ∈ N + [ z 0 ] y \in N^+[z_0] y ∈ N + [ z 0 ] z 0 , z 1 z_0,z_1 z 0 , z 1 N + [ x ] ∩ N − [ y ] N^+[x] \cap N^-[y] N + [ x ] ∩ N − [ y ] y ∈ N + [ x ] y \in N^+[x] y ∈ N + [ x ] N + [ z 0 ] ⊆ N + [ x ] N^+[z_0] \subseteq N^+[x] N + [ z 0 ] ⊆ N + [ x ] N + [ x ] = N + [ z 0 ] N^+[x] = N^+[z_0] N + [ x ] = N + [ z 0 ] x ∈ N − [ z 0 ] x \in N^-[z_0] x ∈ N − [ z 0 ] C z 0 C_{z_0} C z 0 N − [ z 0 ] ⊆ C z 0 ⊆ N + [ z 0 ] N^{-}[z_0] \subseteq C_{z_0} \subseteq N^{+}[z_0] N − [ z 0 ] ⊆ C z 0 ⊆ N + [ z 0 ] ∣ N + [ z 0 ] ∩ N − [ z 0 ] ∣ = K |N^{+}[z_0] \cap N^{-}[z_0]| = K ∣ N + [ z 0 ] ∩ N − [ z 0 ] ∣ = K λ + 2 = t + 1 < K \lambda+ 2 = t + 1 < K λ + 2 = t + 1 < K
(3) By Lemma 7.2 for A A A A T A^{\mathsf{T}} A T C x C_x C x C x ′ C'_x C x ′ N + [ x ] ∩ N − [ x ] N^{+}[x] \cap N^{-}[x] N + [ x ] ∩ N − [ x ] λ + 2 \lambda+ 2 λ + 2 x x x
Theorem 7.8 (vertex without a twin). Let μ = 1 \mu= 1 μ = 1 t = λ + 1 t = \lambda+ 1 t = λ + 1 k = 2 λ + 2 k = 2\lambda+ 2 k = 2 λ + 2 f = K f = K f = K x x x λ ≤ 2 \lambda\le2 λ ≤ 2 λ ≥ 3 \lambda\ge3 λ ≥ 3
Proof. Let a = 1 a = 1 a = 1 O = Γ + ( x ) O = \Gamma^{+}(x) O = Γ + ( x ) S = N + [ x ] S = N^{+}[x] S = N + [ x ] W = V ∖ S W = V \setminus S W = V ∖ S ∣ W ∣ = v − K = K ( k − λ − 1 ) = K ( λ + 1 ) |W| = v - K = K(k - \lambda- 1) = K(\lambda+ 1) ∣ W ∣ = v − K = K ( k − λ − 1 ) = K ( λ + 1 ) rank B = 1 + f = K + 1 \operatorname{rank} B = 1 + f = K + 1 rank B = 1 + f = K + 1
Blocks. By Lemma 7.1 every w ∈ W w \in W w ∈ W S S S x x x W W W W o = Γ + ( o ) ∩ W W_o = \Gamma^{+}(o) \cap W W o = Γ + ( o ) ∩ W o ∈ O o \in O o ∈ O o o o W o W_o W o N + [ o ] ⊆ S N^{+}[o] \subseteq S N + [ o ] ⊆ S N + [ o ] = S N^{+}[o] = S N + [ o ] = S x x x o o o w ∈ W o w \in W_o w ∈ W o N + [ o ] ∩ N − [ w ] N^{+}[o] \cap N^{-}[w] N + [ o ] ∩ N − [ w ] o o o w w w W o W_o W o w w w λ + 2 \lambda+ 2 λ + 2 ∣ W o ∩ N − [ w ] ∣ = λ + 1 |W_o \cap N^{-}[w]| = \lambda+ 1 ∣ W o ∩ N − [ w ] ∣ = λ + 1 w w w B B B λ + 1 \lambda+ 1 λ + 1 W o W_o W o w ∈ W o ′ w \in W_{o'} w ∈ W o ′ o ′ ≠ o o' \ne o o ′ = o w ∉ N + [ o ] w \notin N^{+}[o] w ∈ / N + [ o ] ∣ N + [ o ] ∩ N − [ w ] ∣ = 1 |N^{+}[o] \cap N^{-}[w]| = 1 ∣ N + [ o ] ∩ N − [ w ] ∣ = 1 W o W_o W o w w w
Minors. For a vertex w w w y , y ′ y, y' y , y ′ δ w ( y , y ′ ) = B ( w , y ) − B ( w , y ′ ) \delta_w(y,y') = B(w,y) - B(w,y') δ w ( y , y ′ ) = B ( w , y ) − B ( w , y ′ ) w , w ′ ∈ W w,w' \in W w , w ′ ∈ W y , y ′ y,y' y , y ′ W o W_o W o z , z ′ z,z' z , z ′ W o ′ W_{o'} W o ′
δ w ( y , y ′ ) δ w ′ ( z , z ′ ) = δ w ′ ( y , y ′ ) δ w ( z , z ′ ) . (3) \delta_w(y,y')\delta_{w'}(z,z') = \delta_{w'}(y,y')\delta_w(z,z'). \tag*{(3)} δ w ( y , y ′ ) δ w ′ ( z , z ′ ) = δ w ′ ( y , y ′ ) δ w ( z , z ′ ) . (3) For w = w ′ w = w' w = w ′ w ≠ w ′ w \ne w' w = w ′ K + 2 K + 2 K + 2 S ∪ { w , w ′ } S \cup\{w,w'\} S ∪ { w , w ′ } B B B K + 1 K + 1 K + 1 u u u S ∪ { w , w ′ } S \cup\{w,w'\} S ∪ { w , w ′ } u T B = 0 u^{\mathsf{T}}B = 0 u T B = 0 y ∈ W o y \in W_o y ∈ W o S S S o o o u o + B ( w , y ) u w + B ( w ′ , y ) u w ′ = 0 u_o + B(w,y)u_w + B(w',y)u_{w'} = 0 u o + B ( w , y ) u w + B ( w ′ , y ) u w ′ = 0 y ′ y' y ′ δ w ( y , y ′ ) u w + δ w ′ ( y , y ′ ) u w ′ = 0 \delta_w(y,y')u_w + \delta_{w'}(y,y')u_{w'} = 0 δ w ( y , y ′ ) u w + δ w ′ ( y , y ′ ) u w ′ = 0 z , z ′ z,z' z , z ′ u w = u w ′ = 0 u_w = u_{w'} = 0 u w = u w ′ = 0 W o W_o W o u o = 0 u_o = 0 u o = 0 o ∈ O o \in O o ∈ O x x x u x = 0 u_x = 0 u x = 0 u = 0 u = 0 u = 0 ( u w , u w ′ ) (u_w,u_{w'}) ( u w , u w ′ ) (3) , is zero.
The pivot vertex. Suppose that the row of B B B W W W w ∈ W o w \in W_o w ∈ W o W o W_o W o B ( w , w ) = 1 B(w,w) = 1 B ( w , w ) = 1 W o W_o W o ∣ W o ∣ = λ + 1 |W_o| = \lambda+ 1 ∣ W o ∣ = λ + 1 ∣ W ∣ = k ( λ + 1 ) |W| = k(\lambda+ 1) ∣ W ∣ = k ( λ + 1 ) ∣ W ∣ = K ( λ + 1 ) |W| = K(\lambda+ 1) ∣ W ∣ = K ( λ + 1 ) w 0 ∈ W w_0 \in W w 0 ∈ W y 0 , y 0 ′ y_0, y'_0 y 0 , y 0 ′ B ( w 0 , y 0 ) = 1 B(w_0,y_0) = 1 B ( w 0 , y 0 ) = 1 B ( w 0 , y 0 ′ ) = 0 B(w_0,y'_0) = 0 B ( w 0 , y 0 ′ ) = 0 ε w = δ w ( y 0 , y 0 ′ ) ∈ { − 1 , 0 , 1 } \varepsilon_w = \delta_w(y_0,y'_0) \in\{-1,0,1\} ε w = δ w ( y 0 , y 0 ′ ) ∈ { − 1 , 0 , 1 } (3) with w ′ = w 0 w' = w_0 w ′ = w 0 w ∈ W w \in W w ∈ W y , y ′ y,y' y , y ′
δ w ( y , y ′ ) = ε w δ w 0 ( y , y ′ ) . (4) \delta_w(y,y') = \varepsilon_w\delta_{w_0}(y,y'). \tag*{(4)} δ w ( y , y ′ ) = ε w δ w 0 ( y , y ′ ) . (4) If ε w = 0 \varepsilon_w = 0 ε w = 0 w w w B ( w , w ) = 1 B(w,w) = 1 B ( w , w ) = 1 w 0 w_0 w 0 w w w ε w \varepsilon_w ε w ε w = 1 \varepsilon_w = 1 ε w = 1 w w w w 0 w_0 w 0 ε w = − 1 \varepsilon_w = -1 ε w = − 1
Special blocks. A block is called special if the row w 0 w_0 w 0 W o W_o W o W o W_o W o ∣ W o ∣ = λ + 1 |W_o| = \lambda+ 1 ∣ W o ∣ = λ + 1 W o W_o W o y , y ′ y,y' y , y ′ B ( w 0 , y ) = 1 B(w_0,y)=1 B ( w 0 , y ) = 1 B ( w 0 , y ′ ) = 0 B(w_0,y')=0 B ( w 0 , y ′ ) = 0 δ w ( y , y ′ ) = ε w \delta_w(y,y')=\varepsilon_w δ w ( y , y ′ ) = ε w w ∈ W o w\in W_o w ∈ W o ε w = 1 \varepsilon_w=1 ε w = 1 B ( w , y ) = 1 B(w,y)=1 B ( w , y ) = 1 B ( w , y ′ ) = 0 B(w,y')=0 B ( w , y ′ ) = 0 ε w = − 1 \varepsilon_w=-1 ε w = − 1 ε w = 0 \varepsilon_w=0 ε w = 0 y y y y ′ y' y ′ B B B λ + 1 \lambda+1 λ + 1 W o W_o W o W o W_o W o ε w = 1 \varepsilon_w=1 ε w = 1 ε w = − 1 \varepsilon_w=-1 ε w = − 1 p o p_o p o ∣ W o ∣ = λ + 1 + p o \lvert W_o\rvert=\lambda+1+p_o ∣ W o ∣ = λ + 1 + p o k k k ∣ W ∣ = k ( λ + 1 ) + ∑ p o \lvert W\rvert=k(\lambda+1)+\sum p_o ∣ W ∣ = k ( λ + 1 ) + ∑ p o ∣ W ∣ = K ( λ + 1 ) \lvert W\rvert=K(\lambda+1) ∣ W ∣ = K ( λ + 1 ) ∑ p o = λ + 1 \sum p_o=\lambda+1 ∑ p o = λ + 1 W W W ε w = 1 \varepsilon_w=1 ε w = 1 ε w = − 1 \varepsilon_w=-1 ε w = − 1
Two or more special blocks. Let W o W_o W o W o ′ W_{o'} W o ′ z ∈ W o ′ z\in W_{o'} z ∈ W o ′ B ( w 0 , z ) = 1 B(w_0,z)=1 B ( w 0 , z ) = 1 W o W_o W o ε w = 1 \varepsilon_w=1 ε w = 1 z z z W o W_o W o z z z p o ≤ 1 p_o\leq1 p o ≤ 1 λ + 1 \lambda+1 λ + 1 ( λ + 1 ) ( λ + 2 ) (\lambda+1)(\lambda+2) ( λ + 1 ) ( λ + 2 ) w w w ε w = 1 \varepsilon_w=1 ε w = 1 w ′ w' w ′ ε w ′ = − 1 \varepsilon_{w'}=-1 ε w ′ = − 1 N + [ w ] N^+[w] N + [ w ] N + [ w ′ ] N^+[w'] N + [ w ′ ] ( λ + 1 ) ( λ + 2 ) ≤ 2 K = 2 ( 2 λ + 3 ) (\lambda+1)(\lambda+2)\leq2K=2(2\lambda+3) ( λ + 1 ) ( λ + 2 ) ≤ 2 K = 2 ( 2 λ + 3 ) λ 2 − λ − 4 ≤ 0 \lambda^2-\lambda-4\leq0 λ 2 − λ − 4 ≤ 0 λ ≤ 2 \lambda\leq2 λ ≤ 2
One special block W o 1 W_{o_1} W o 1 Then p o 1 = λ + 1 p_{o_1}=\lambda+1 p o 1 = λ + 1 ∣ W o 1 ∣ = 2 λ + 2 = k \lvert W_{o_1}\rvert=2\lambda+2=k ∣ W o 1 ∣ = 2 λ + 2 = k Γ + ( o 1 ) = W o 1 \Gamma^+(o_1)=W_{o_1} Γ + ( o 1 ) = W o 1 ε w = 0 \varepsilon_w=0 ε w = 0 λ + 1 \lambda+1 λ + 1 ε w = 1 \varepsilon_w=1 ε w = 1 ε w = − 1 \varepsilon_w=-1 ε w = − 1 (4) , on W o 1 W_{o_1} W o 1 ε w = 1 \varepsilon_w=1 ε w = 1 w 0 w_0 w 0 ε w = − 1 \varepsilon_w=-1 ε w = − 1 ε = 1 \varepsilon=1 ε = 1 ε = − 1 \varepsilon=-1 ε = − 1 Γ + ( o 1 ) \Gamma^+(o_1) Γ + ( o 1 ) λ + 1 \lambda+1 λ + 1 o 1 o_1 o 1 Γ + ( o 1 ) \Gamma^+(o_1) Γ + ( o 1 ) λ ≥ 3 \lambda\geq3 λ ≥ 3 o 1 o_1 o 1 x x x o 1 o_1 o 1 o 2 ∈ Γ + ( o 1 ) o_2\in\Gamma^+(o_1) o 2 ∈ Γ + ( o 1 ) N + [ o 1 ] N^+[o_1] N + [ o 1 ] o 2 o_2 o 2 λ + 1 ≥ 2 \lambda+1\geq2 λ + 1 ≥ 2 Γ + ( o 1 ) \Gamma^+(o_1) Γ + ( o 1 ) A T A^\mathsf{T} A T
Theorem 7.9. There is no DSRG with μ = 1 \mu=1 μ = 1 t = λ + 1 t=\lambda+1 t = λ + 1 k = 2 λ + 2 k=2\lambda+2 k = 2 λ + 2 λ ≥ 4 \lambda\geq4 λ ≥ 4
Proof. By Theorem 7.8, a , a ′ ≥ 2 a,a'\geq2 a , a ′ ≥ 2 3 ≤ a ≤ λ 3\leq a\leq\lambda 3 ≤ a ≤ λ a ( λ + 3 − a ) ≥ 3 λ > 2 λ + 3 = K a(\lambda+3-a)\geq3\lambda>2\lambda+3=K a ( λ + 3 − a ) ≥ 3 λ > 2 λ + 3 = K a , a ′ ∈ { 2 , λ + 1 } a,a'\in\{2,\lambda+1\} a , a ′ ∈ { 2 , λ + 1 } λ + 1 \lambda+1 λ + 1
Let a = λ + 1 a=\lambda+1 a = λ + 1 C x C_x C x y ∈ C x y\in C_x y ∈ C x C y ′ = { y , y ′ } C'_y=\{y,y'\} C y ′ = { y , y ′ } y ′ ∈ N + [ x ] y'\in N^+[x] y ′ ∈ N + [ x ] y ′ ∉ C x y'\notin C_x y ′ ∈ / C x y ′ y' y ′ y y y y 1 ′ = y 2 ′ y'_1=y'_2 y 1 ′ = y 2 ′ C y 1 ′ = C y 2 ′ = y 2 C'_{y_1}=C'_{y_2}=y_2 C y 1 ′ = C y 2 ′ = y 2 y 2 y_2 y 2 y 1 y_1 y 1 N + [ x ] ∖ C x N^+[x]\setminus C_x N + [ x ] ∖ C x K − a = λ + 2 K-a=\lambda+2 K − a = λ + 2 u ∗ u^* u ∗ C y ′ C'_y C y ′ C u ∗ ′ ⊆ N + [ x ] C'_{u^*}\subseteq N^+[x] C u ∗ ′ ⊆ N + [ x ] C y ′ C'_y C y ′ C u ∗ ′ = { u ∗ } C'_{u^*}=\{u^*\} C u ∗ ′ = { u ∗ } a ′ ≥ 2 a'\geq2 a ′ ≥ 2 A T A^\mathsf{T} A T N + [ x ] N^+[x] N + [ x ] 2 λ + 3 2\lambda+3 2 λ + 3
Corollary 7.10. There are no DSRGs ( 66 , 10 , 5 , 4 , 1 ) (66,10,5,4,1) ( 66 , 10 , 5 , 4 , 1 ) ( 91 , 12 , 6 , 5 , 1 ) (91,12,6,5,1) ( 91 , 12 , 6 , 5 , 1 ) ( 66 , 55 , 50 , 45 , 50 ) (66,55,50,45,50) ( 66 , 55 , 50 , 45 , 50 ) ( 91 , 78 , 72 , 66 , 72 ) (91,78,72,66,72) ( 91 , 78 , 72 , 66 , 72 )
Proof. For ( 66 , 10 , 5 , 4 , 1 ) (66,10,5,4,1) ( 66 , 10 , 5 , 4 , 1 ) k = 10 = 2 λ + 2 k=10=2\lambda+2 k = 10 = 2 λ + 2 λ = 4 \lambda=4 λ = 4 ( 91 , 12 , 6 , 5 , 1 ) (91,12,6,5,1) ( 91 , 12 , 6 , 5 , 1 ) k = 12 = 2 λ + 2 k=12=2\lambda+2 k = 12 = 2 λ + 2 λ = 5 \lambda=5 λ = 5
For these two sets inequality (7.1) gives nothing: q = 5 < μ f = 11 q=5<\mu f=11 q = 5 < μ f = 11 q = 6 < 13 q=6<13 q = 6 < 13 λ ≥ 4 \lambda\geq4 λ ≥ 4 Theorem 7.9 cannot be lowered: the set ( 45 , 8 , 4 , 3 , 1 ) (45,8,4,3,1) ( 45 , 8 , 4 , 3 , 1 ) k = 2 λ + 2 k=2\lambda+2 k = 2 λ + 2 λ = 3 \lambda=3 λ = 3 [2 ] .
The set ( 28 , 6 , 3 , 2 , 1 ) (28,6,3,2,1) ( 28 , 6 , 3 , 2 , 1 ) Here k = 6 = 2 λ + 2 k=6=2\lambda+2 k = 6 = 2 λ + 2 λ = 2 \lambda=2 λ = 2 K = 7 K=7 K = 7 f = 7 f=7 f = 7 B 2 = 3 B + J B^2=3B+J B 2 = 3 B + J Theorem 7.8 does not exclude a vertex without a row twin: with three special blocks the inequality of its proof holds, ( λ + 1 ) ( λ + 2 ) = 12 ≤ 14 = 2 K (\lambda+1)(\lambda+2)=12\leq14=2K ( λ + 1 ) ( λ + 2 ) = 12 ≤ 14 = 2 K row-free , and one without a column twin column-free .
Lemma 7.11. Let μ = 1 \mu=1 μ = 1 t = λ + 1 t=\lambda+1 t = λ + 1 U = N + [ x ] ∖ C x U=N^+[x]\setminus C_x U = N + [ x ] ∖ C x
(1) If a = λ + 1 a=\lambda+1 a = λ + 1 U U U U U U C x C_x C x K − 2 ( λ + 1 ) K-2(\lambda+1) K − 2 ( λ + 1 ) U U U
(2) If there are no free vertices and K > 2 ( λ + 1 ) K>2(\lambda+1) K > 2 ( λ + 1 ) a ≤ λ a\leq\lambda a ≤ λ a ′ ≤ λ a'\leq\lambda a ′ ≤ λ λ = 2 \lambda=2 λ = 2 K K K
Proof. (1) Every y ∈ C x y\in C_x y ∈ C x N + [ x ] ∖ { y } N^+[x]\setminus\{y\} N + [ x ] ∖ { y } C x ⊆ N − [ u ] C_x\subseteq N^-[u] C x ⊆ N − [ u ] u ∈ U u\in U u ∈ U N + [ x ] ∩ N − [ u ] N^+[x]\cap N^-[u] N + [ x ] ∩ N − [ u ] λ + 2 \lambda+2 λ + 2 λ + 1 \lambda+1 λ + 1 C x C_x C x u u u U U U u u u Lemma 7.7 , C u ′ ⊆ N + [ x ] C'_u\subseteq N^+[x] C u ′ ⊆ N + [ x ] u ′ ≠ u u'\ne u u ′ = u U U U u ∈ N − [ u ] = N − [ u ′ ] u\in N^-[u]=N^-[u'] u ∈ N − [ u ] = N − [ u ′ ] u → u ′ u\to u' u → u ′ U U U C u ′ ∖ { u } ⊆ C x C'_u\setminus\{u\}\subseteq C_x C u ′ ∖ { u } ⊆ C x U U U y ∈ C x y\in C_x y ∈ C x λ + 1 \lambda+1 λ + 1 U U U ∣ C u ′ ∣ ≥ 2 |C'_u|\geq2 ∣ C u ′ ∣ ≥ 2 ∣ U ∣ − ( λ + 1 ) = K − 2 ( λ + 1 ) |U|-(\lambda+1)=K-2(\lambda+1) ∣ U ∣ − ( λ + 1 ) = K − 2 ( λ + 1 )
(2) By Lemma 7.2, a ≤ λ + 1 a\leq\lambda+1 a ≤ λ + 1 a = λ + 1 a=\lambda+1 a = λ + 1 a ≤ λ a\leq\lambda a ≤ λ A T A^\mathsf{T} A T a ′ ≤ λ a'\leq\lambda a ′ ≤ λ λ = 2 \lambda=2 λ = 2 a , a ′ ≥ 2 a,a'\geq2 a , a ′ ≥ 2 a = a ′ = 2 a=a'=2 a = a ′ = 2 Lemma 7.7 , N + [ x ] N^+[x] N + [ x ] K K K
Theorem 7.12. There is no DSRG ( 28 , 6 , 3 , 2 , 1 ) (28,6,3,2,1) ( 28 , 6 , 3 , 2 , 1 ) ( 28 , 21 , 18 , 15 , 18 ) (28,21,18,15,18) ( 28 , 21 , 18 , 15 , 18 )
Proof. Let A A A ( 28 , 6 , 3 , 2 , 1 ) (28,6,3,2,1) ( 28 , 6 , 3 , 2 , 1 )
There is a row-free vertex x x x Renumber the vertices: x x x x x x x x x a ( i , j ) a(i,j) a ( i , j ) i ≠ j i\ne j i = j i → z → j i\to z\to j i → z → j i = j i=j i = j i → j i\to j i → j B B B i → z → j i\to z\to j i → z → j a ( i , z ) ∧ a ( z , j ) a(i,z)\land a(z,j) a ( i , z ) ∧ a ( z , j ) n n n [23 ] . The formula is unsatisfiable, and this is proved in Lean: the generator of the formula is written in Lean, a Lean theorem proves that a graph with a row-free vertex, after such a renumbering, satisfies each of its clauses, and the proof of unsatisfiability found by the solver CaDiCaL [24 ] is checked by the Lean kernel (§ 9 ). Hence there is no row-free vertex.
There is a column-free vertex. It is row-free in A T A^\mathsf{T} A T
There are no free vertices. Here K = 7 > 6 = 2 ( λ + 1 ) K=7>6=2(\lambda+1) K = 7 > 6 = 2 ( λ + 1 ) K K K
The rank plays no part in the proof of Theorem 7.12: the free vertex is excluded by a formula written directly from the definition of a DSRG, and the other cases by counting twin classes. We have no argument for this case without a solver.
Earlier proofs for two pairs. Theorem 10 of [3 ] excludes the line ( 96 m , 80 m , 75 m , 65 m , 75 m ) (96m,80m,75m,65m,75m) ( 96 m , 80 m , 75 m , 65 m , 75 m ) ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) [4 ] excludes the line ( 28 m , 21 m , 18 m , 15 m , 18 m ) (28m,21m,18m,15m,18m) ( 28 m , 21 m , 18 m , 15 m , 18 m ) m m m m = 1 m=1 m = 1 ( 28 , 6 , 3 , 2 , 1 ) (28,6,3,2,1) ( 28 , 6 , 3 , 2 , 1 ) A + I A+I A + I [3 ] and [4 ] , and our proofs do not rely on them: for ( 96 , 15 , 10 , 9 , 1 ) (96,15,10,9,1) ( 96 , 15 , 10 , 9 , 1 ) ( 28 , 6 , 3 , 2 , 1 ) (28,6,3,2,1) ( 28 , 6 , 3 , 2 , 1 )
The limits of the method
The method is as strong as the piece that the parameters force at a vertex: the larger and the more rigid the piece, the more it can exclude. This section shows where there is no such piece and the method is silent.
The out-neighbourhood gives only a known condition. The most general forced piece is available for any λ \lambda λ
Proposition 8.1. Let μ ≥ 1 \mu\ge1 μ ≥ 1 x x x O = Γ + ( x ) O=\Gamma^{+}(x) O = Γ + ( x ) S = N + [ x ] S=N^{+}[x] S = N + [ x ] A O = A [ O , O ] A_O=A[O,O] A O = A [ O , O ]
(1) 1 T A O = λ 1 T \mathbf{1}^{\mathsf{T}}A_O=\lambda\mathbf{1}^{\mathsf{T}} 1 T A O = λ 1 T A O A_O A O λ \lambda λ
(2) for each root θ \theta θ ( θ − λ ) det B θ [ S , S ] = μ ( θ + 1 ) det ( A O − θ I ) (\theta-\lambda)\det B_\theta[S,S]=\mu(\theta+1)\det(A_O-\theta I) ( θ − λ ) det B θ [ S , S ] = μ ( θ + 1 ) det ( A O − θ I )
(3) if ∣ θ ∣ > λ |\theta|>\lambda ∣ θ ∣ > λ θ ≠ − 1 \theta\ne-1 θ = − 1 B θ [ S , S ] B_\theta[S,S] B θ [ S , S ] k ≤ m ′ k\le m' k ≤ m ′
Proof. (1) For o ∈ O o\in O o ∈ O λ \lambda λ x → z → o x\to z\to o x → z → o o o o O O O
(2) Order S S S x , O x,O x , O
B θ [ S , S ] = ( − θ 1 T a E ) , B_\theta[S,S]=\begin{pmatrix}-\theta&\mathbf{1}^{\mathsf{T}}\\a&E\end{pmatrix}, B θ [ S , S ] = ( − θ a 1 T E ) , where E = A O − θ I E=A_O-\theta I E = A O − θ I a a a O ∩ Γ − ( x ) O\cap\Gamma^{-}(x) O ∩ Γ − ( x ) det B θ [ S , S ] = − θ det E − 1 T adj ( E ) a \det B_\theta[S,S]=-\theta\det E-\mathbf{1}^{\mathsf{T}}\operatorname{adj}(E)a det B θ [ S , S ] = − θ det E − 1 T adj ( E ) a 1 T E = ( λ − θ ) 1 T \mathbf{1}^{\mathsf{T}}E=(\lambda-\theta)\mathbf{1}^{\mathsf{T}} 1 T E = ( λ − θ ) 1 T ( λ − θ ) 1 T adj ( E ) = det E ⋅ 1 T (\lambda-\theta)\mathbf{1}^{\mathsf{T}}\operatorname{adj}(E)=\det E\cdot\mathbf{1}^{\mathsf{T}} ( λ − θ ) 1 T adj ( E ) = det E ⋅ 1 T λ − θ \lambda-\theta λ − θ 1 T a = t \mathbf{1}^{\mathsf{T}}a=t 1 T a = t ( λ − θ ) det B θ [ S , S ] = det E ( θ 2 − λ θ − t ) (\lambda-\theta)\det B_\theta[S,S]=\det E(\theta^2-\lambda\theta-t) ( λ − θ ) det B θ [ S , S ] = det E ( θ 2 − λ θ − t ) θ 2 = ( λ − μ ) θ + t − μ \theta^2=(\lambda-\mu)\theta+t-\mu θ 2 = ( λ − μ ) θ + t − μ θ 2 − λ θ − t = − μ ( θ + 1 ) \theta^2-\lambda\theta-t=-\mu(\theta+1) θ 2 − λ θ − t = − μ ( θ + 1 )
(3) For ∣ θ ∣ > λ |\theta|>\lambda ∣ θ ∣ > λ θ \theta θ A O A_O A O θ ≠ λ \theta\ne\lambda θ = λ θ ≠ − 1 \theta\ne-1 θ = − 1 k + 1 k+1 k + 1 k + 1 ≤ 1 + m ′ k+1\le1+m' k + 1 ≤ 1 + m ′
The bound k ≤ m ′ k\le m' k ≤ m ′ ∣ θ ∣ > λ |\theta|>\lambda ∣ θ ∣ > λ [16 p. 5] with θ \theta θ θ ′ \theta' θ ′ [16 ] it is derived from [16 Theorem 6] (Section 6): θ ′ \theta' θ ′ A [ Γ + ( x ) , Γ + ( x ) ] A[\Gamma^{+}(x),\Gamma^{+}(x)] A [ Γ + ( x ) , Γ + ( x )] ∣ θ ′ ∣ < λ |\theta'|<\lambda ∣ θ ′ ∣ < λ θ \theta θ k k k θ = − 1 \theta=-1 θ = − 1 λ = 0 \lambda=0 λ = 0 t = 1 t=1 t = 1 [16 ] is even stronger than item 3, because it has no exception θ = − 1 \theta=-1 θ = − 1 N [ x ] N[x] N [ x ] λ = 0 \lambda= 0 λ = 0 { x } ∪ Γ + ( x ) \{x\} \cup\Gamma^{+}(x) { x } ∪ Γ + ( x ) λ = 1 \lambda= 1 λ = 1 t = 2 μ t = 2\mu t = 2 μ N + [ x ] N^{+}[x] N + [ x ] t = λ + 1 t = \lambda+ 1 t = λ + 1 μ = 1 \mu= 1 μ = 1 f = K f = K f = K λ \lambda λ μ \mu μ
λ = 0 \lambda= 0 λ = 0 [2 ] with λ = 0 \lambda= 0 λ = 0 Theorems 4.5 and 5.3 close five. For the two remaining ones the bound of Theorem 4.3 holds with a margin: for ( 70 , 11 , 5 , 0 , 2 ) (70, 11, 5, 0, 2) ( 70 , 11 , 5 , 0 , 2 ) θ = 1 \theta= 1 θ = 1 τ \tau τ ( 88 , 9 , 3 , 0 , 1 ) (88, 9, 3, 0, 1) ( 88 , 9 , 3 , 0 , 1 ) θ = 1 \theta= 1 θ = 1 θ = − 2 \theta= -2 θ = − 2 τ = 3 \tau= 3 τ = 3 N [ x ] N[x] N [ x ] [25 ] with random descents, its tree for each of the four graphs of arcs from Q Q Q P P P 4.6 ⋅ 10 15 4.6 \cdot10^{15} 4.6 ⋅ 1 0 15 1.5 ⋅ 10 17 1.5 \cdot10^{17} 1.5 ⋅ 1 0 17
λ = 1 \lambda= 1 λ = 1 t = 2 μ t = 2\mu t = 2 μ [2 ] , seven have k + 1 − g ≤ 0 k + 1 - g \le0 k + 1 − g ≤ 0 c ≥ k + 1 − g + [ d ≠ 0 ] c \ge k + 1 - g + [d \ne0] c ≥ k + 1 − g + [ d = 0 ] c ≤ k / 2 c \le k/2 c ≤ k /2 ( 55 , 16 , 12 , 1 , 6 ) (55, 16, 12, 1, 6) ( 55 , 16 , 12 , 1 , 6 ) 7 ≤ c ≤ 8 7 \le c \le8 7 ≤ c ≤ 8 Theorem 6.4 excludes it. For ( 44 , 12 , 8 , 1 , 4 ) (44, 12, 8, 1, 4) ( 44 , 12 , 8 , 1 , 4 ) ( 63 , 16 , 10 , 1 , 5 ) (63, 16, 10, 1, 5) ( 63 , 16 , 10 , 1 , 5 ) ( 95 , 20 , 10 , 1 , 5 ) (95, 20, 10, 1, 5) ( 95 , 20 , 10 , 1 , 5 ) ( 98 , 22 , 12 , 1 , 6 ) (98, 22, 12, 1, 6) ( 98 , 22 , 12 , 1 , 6 ) k + 1 − g k + 1 - g k + 1 − g k / 2 = 6 , 8 , 10 , 11 k/2 = 6, 8, 10, 11 k /2 = 6 , 8 , 10 , 11
t = λ + 1 t = \lambda+ 1 t = λ + 1 μ = 1 \mu= 1 μ = 1 t = λ + 1 t = \lambda+ 1 t = λ + 1 ( 70 , 9 , 3 , 2 , 1 ) (70, 9, 3, 2, 1) ( 70 , 9 , 3 , 2 , 1 ) f = 20 f = 20 f = 20 K = 10 K = 10 K = 10 Theorem 7.8 rests on the equality f = K f = K f = K f > K f > K f > K B B B K + 1 K + 1 K + 1 N + [ x ] N^{+}[x] N + [ x ] Lemma 7.11 applies to this set, but K = 10 K = 10 K = 10 μ ≥ 2 \mu\ge2 μ ≥ 2 K − μ f K - \mu f K − μ f Proposition 7.5 is usually negative: every vertex outside N + [ x ] N^{+}[x] N + [ x ] μ \mu μ N + [ x ] N^{+}[x] N + [ x ] t = λ + 1 t = \lambda+ 1 t = λ + 1 μ ≥ 2 \mu\ge2 μ ≥ 2 f f f 17 − 34 = − 17 17 - 34 = -17 17 − 34 = − 17 ( 102 , 16 , 6 , 5 , 2 ) (102, 16, 6, 5, 2) ( 102 , 16 , 6 , 5 , 2 ) ( 81 , 17 , 10 , 9 , 2 ) (81, 17, 10, 9, 2) ( 81 , 17 , 10 , 9 , 2 ) 18 − 14 = 4 18 - 14 = 4 18 − 14 = 4 a ≤ K − q = 9 a \le K - q = 9 a ≤ K − q = 9 Proposition 7.4 it leaves a ∈ { 4 , 9 } a \in\{4,9\} a ∈ { 4 , 9 }
Machine verification
Lean. The nonexistence results for nine pairs of Theorem A and their complements are proved in Lean 4 [9 ] with the Mathlib library [10 ] : Lean version v4.35.0, Mathlib at the tag v4.35.0. A graph is given by the predicate IsDSRG n A k t lam mu. It requires the integer matrix A A A n n n k k k A 2 = t I + λ A + μ ( J − I − A ) A^2 = tI + \lambda A + \mu(J-I-A) A 2 = t I + λ A + μ ( J − I − A ) ( v , k , t , λ , μ ) (v,k,t,\lambda,\mu) ( v , k , t , λ , μ ) IsDSRG v A k t lam mu for any matrix A A A R \mathbb{R} R m ′ m' m ′ ker ( A − θ ′ I ) \ker(A - \theta'I) ker ( A − θ ′ I ) #print axioms, the axioms it depends on: these are only propext, Classical.choice and Quot.sound. The proofs contain neither sorry, nor axioms of our own, nor native computation (native_decide).
The complements are derived from the nonexistence results by the general complement theorem not_isDSRG_compl. By the same route the project proves the nonexistence of ( 40 , 9 , 6 , 5 , 1 ) (40, 9, 6, 5, 1) ( 40 , 9 , 6 , 5 , 1 ) ( 80 , 19 , 13 , 12 , 2 ) (80, 19, 13, 12, 2) ( 80 , 19 , 13 , 12 , 2 ) Theorem 7.6 together with their complements, and also of six other sets with λ = 0 \lambda= 0 λ = 0
The SAT certificate in the Lean kernel. The first case of Theorem 7.12 is closed by a SAT formula. It has 131,518 variables and 300,889 clauses. The solver CaDiCaL [24 ] , version 1.9.5, from PySAT [22 ] proves it unsatisfiable in less than a second and writes a DRAT proof; drat-trim [26 ] checks it against the formula and extracts from it an LRAT proof [27 ] of 525 steps. This proof is checked by the Lean kernel. The generator of the formula is written in Lean, and a Lean theorem proves that the matrix of a DSRG with a row-free vertex, after the renumbering from the proof of Theorem 7.12 , satisfies every clause of the generator. The LRAT steps refer to 1,627 clauses of the formula; the kernel checks by computation that each of them is a clause of the generator for the parameters ( 28 , 6 , 3 , 2 , 1 ) (28, 6, 3, 2, 1) ( 28 , 6 , 3 , 2 , 1 ) [28 ] . Thus both the unsatisfiability of the formula and its correspondence to a graph with a free vertex are proved formally, and neither the solver nor the program that builds the formula needs to be trusted.
The search for ( 48 , 9 , 5 , 0 , 2 ) (48, 9, 5, 0, 2) ( 48 , 9 , 5 , 0 , 2 ) The last step of Theorem 5.3 is a computation on the reduction of Proposition A.2 , which is proved only in the text. It was carried out by two programs of different design that share no code (Appendix A). The second program writes a SAT formula for each pivot orbit, and the unsatisfiability of each of the 707 formulas has been checked without trusting the solver. For 166 orbits the formula contains the empty clause: one of its cardinality constraints requires a cell to take more triples than the cell has candidates, or a negative number of triples. The remaining 541 formulas were solved by CaDiCaL [24 ] , version 1.9.5; for it the cardinality constraints are encoded by the sequential counter [23 ] . For each of these formulas CaDiCaL wrote a DRAT proof, drat-trim accepted all 541 proofs, and all the LRAT proofs that drat-trim extracted from them were accepted by the LRAT checker of the repository: it checks them again against the same formula by unit propagation and accepts no RAT steps. The SHA-256 hashes of the formulas and proofs, the computing times and the commands that recreate them are given in the README of the repository (§ 11 ).
The checkers confirm the unsatisfiability of the formula they are given; whether it encodes the conditions of Proposition A.2 , they do not check. This correspondence is not proved formally: it rests on the construction of the formula and on the controls of the programs on known graphs (Appendix A).
What is checked outside Lean. The nonexistence of ( 48 , 9 , 5 , 0 , 2 ) (48, 9, 5, 0, 2) ( 48 , 9 , 5 , 0 , 2 ) Lemma A.1 and Proposition A.2 ) is proved in the text, and the search is carried out by programs; for this set Lean proves only part of the reduction and does not give the nonexistence. The statements on which no nonexistence result rests are also proved only in the text: the determinant formula of Proposition 4.2, items 3–5 of Lemma 3.1 in general form (the applications use their particular forms), the identity ∑ u ∈ U γ u = a ( λ + 2 − a ) \sum_{u\in U}\gamma_u = a(\lambda+ 2 - a) ∑ u ∈ U γ u = a ( λ + 2 − a ) Proposition 7.4 , and Proposition 8.1 .
Controls on known graphs. Every statement of Sections 4–7 has been checked by exact computation at every vertex of the known DSRGs that satisfy its hypotheses, complements included; the formula of Proposition 4.2 fails on graphs with λ = 1 \lambda= 1 λ = 1
Use of AI
The arguments, the proofs, the checking programs and the text of the paper were produced by AI agents running on Claude models (Anthropic) under the direction of the author. The author chose the problem, directed the work and is responsible for the publication. The two rStation papers [7 ] and [8 ] that this paper merges and reworks were posted by an AI agent directed by the author.
No human mathematician has checked the proofs of the text line by line. The proofs of nine nonexistence results out of ten are checked by the Lean kernel (§ 9 ). The reduction for ( 48 , 9 , 5 , 0 , 2 ) (48, 9, 5, 0, 2) ( 48 , 9 , 5 , 0 , 2 ) Table 3 ) were read by independent passes of AI reviewers.
Data availability
The Lean modules, the checking programs, the graphs on which the controls run, and the certificates needed to repeat the checks of the paper are kept in the public repository on GitHub https://github.com/Nosdormas/melete-math (release 1.1.0) and preserved in the Software Heritage archive as the snapshot swh:1:snp:660b3b805773567b1a87f0f5764b21a3b580fc44. For every check, the README of the repository names the command, the expected outcome and the computing time, and for the search of Theorem 5.3 and the certificate of Theorem 7.12 also the SHA-256 hashes of the formulas and proofs.
Appendix A. The reduction and the search for (48, 9, 5, 0, 2)
Here ( v , k , t , λ , μ ) = ( 48 , 9 , 5 , 0 , 2 ) (v,k,t,\lambda,\mu) = (48,9,5,0,2) ( v , k , t , λ , μ ) = ( 48 , 9 , 5 , 0 , 2 ) θ = 1 \theta= 1 θ = 1
Lemma A.1. Let ( v , k , t , λ , μ ) = ( 48 , 9 , 5 , 0 , 2 ) (v,k,t,\lambda,\mu) = (48,9,5,0,2) ( v , k , t , λ , μ ) = ( 48 , 9 , 5 , 0 , 2 ) θ = 1 \theta= 1 θ = 1 θ ′ = − 3 \theta' = -3 θ ′ = − 3 m ′ = g = 14 m' = g = 14 m ′ = g = 14 θ 3 − t θ − μ ( k − t ) = − 12 \theta^3-t\theta-\mu(k-t)=-12 θ 3 − tθ − μ ( k − t ) = − 12 ∣ M ∣ = 5 |M|=5 ∣ M ∣ = 5 ∣ Q ∣ = ∣ P ∣ = 4 |Q|=|P|=4 ∣ Q ∣ = ∣ P ∣ = 4 ∣ N ( x ) ∣ = 13 |N(x)|=13 ∣ N ( x ) ∣ = 13 τ = 1 \tau=1 τ = 1 T T T − 4 -4 − 4
(1) the arcs from Q Q Q P P P
(2) the row and the column x x x Φ \Phi Φ N ( x ) N(x) N ( x ) M M M Q Q Q P P P
Φ [ N ( x ) , N ( x ) ] = ( 3 I + J J 2 J 2 J 3 I + 2 J 2 ( J − A Q P ) J J 3 I + 2 J ) ; \Phi[N(x),N(x)] =
\begin{pmatrix}
3I+J & J & 2J \\
2J & 3I+2J & 2(J-A_{QP}) \\
J & J & 3I+2J
\end{pmatrix}; Φ [ N ( x ) , N ( x )] = 3 I + J 2 J J J 3 I + 2 J J 2 J 2 ( J − A QP ) 3 I + 2 J ; every vertex of M M M P P P Q Q Q M M M Q Q Q P P P
(3) let α w = ∣ Γ + ( w ) ∩ Q ∣ \alpha_w=|\Gamma^+(w)\cap Q| α w = ∣ Γ + ( w ) ∩ Q ∣ β w = ∣ Γ − ( w ) ∩ P ∣ \beta_w=|\Gamma^-(w)\cap P| β w = ∣ Γ − ( w ) ∩ P ∣ ν 2 ( w , w ′ ) \nu_2(w,w') ν 2 ( w , w ′ ) w → n → w ′ w\to n\to w' w → n → w ′ n ∈ N ( x ) n\in N(x) n ∈ N ( x ) ν 3 ( w , w ′ ) \nu_3(w,w') ν 3 ( w , w ′ ) w → u → p → w ′ w\to u\to p\to w' w → u → p → w ′ u ∈ Q u\in Q u ∈ Q p ∈ P p\in P p ∈ P w w w w ′ w' w ′
F ( w , w ′ ) = ( 1 + α w ) ( 1 + β w ′ ) 3 − ν 2 ( w , w ′ ) − ν 3 ( w , w ′ ) , F(w,w')=\frac{(1+\alpha_w)(1+\beta_{w'})}{3}-\nu_2(w,w')-\nu_3(w,w'), F ( w , w ′ ) = 3 ( 1 + α w ) ( 1 + β w ′ ) − ν 2 ( w , w ′ ) − ν 3 ( w , w ′ ) , σ w = − 1 − ( 1 + α w ) ( 1 + β w ) 3 + ν 2 ( w , w ) + ν 3 ( w , w ) , \sigma_w=-1-\frac{(1+\alpha_w)(1+\beta_w)}{3}+\nu_2(w,w)+\nu_3(w,w), σ w = − 1 − 3 ( 1 + α w ) ( 1 + β w ) + ν 2 ( w , w ) + ν 3 ( w , w ) , and the number 3 σ w 3\sigma_w 3 σ w
(4) distinct outer vertices have distinct types.
Proof. The roots of the polynomial x 2 + 2 x − 3 x^2+2x-3 x 2 + 2 x − 3 − 3 -3 − 3 Lemma 3.1 , f + g = 47 f+g=47 f + g = 47 9 + f − 3 g = 0 9+f-3g=0 9 + f − 3 g = 0 g = 14 g=14 g = 14 f = 33 f=33 f = 33 1 − 5 − 8 = − 12 1-5-8=-12 1 − 5 − 8 = − 12 Lemma 4.1 , τ = 14 − 13 = 1 \tau=14-13=1 τ = 14 − 13 = 1 T T T 1 ⋅ ( − 3 − 1 ) = − 4 1\cdot(-3-1)=-4 1 ⋅ ( − 3 − 1 ) = − 4
(1) By Lemma 4.1 every u ∈ Q u\in Q u ∈ Q P P P p ∈ P p\in P p ∈ P x → p x\to p x → p μ = 2 \mu=2 μ = 2 x → o → p x\to o\to p x → o → p Γ + \Gamma^+ Γ + Lemma 4.1 in Q Q Q 4 + 4 4+4 4 + 4
(2) By Lemma 5.1, Φ ( n , n ′ ) = ( X Y ) ( n , n ′ ) \Phi(n,n')=(XY)(n,n') Φ ( n , n ′ ) = ( X Y ) ( n , n ′ ) A 2 ( n , n ′ ) A^2(n,n') A 2 ( n , n ′ ) N [ x ] N[x] N [ x ] N [ x ] N[x] N [ x ] Lemma 4.1 . For example, for m ≠ m ′ m\ne m' m = m ′ M M M A 2 ( m , m ′ ) = μ = 2 A^{2}(m,m')=\mu=2 A 2 ( m , m ′ ) = μ = 2 N [ x ] N[x] N [ x ] m → x → m ′ m \to x \to m' m → x → m ′ Φ ( m , m ′ ) = 1 \Phi(m,m')=1 Φ ( m , m ′ ) = 1 u ∈ Q u \in Q u ∈ Q p ∈ P p \in P p ∈ P u → p u \to p u → p A 2 ( u , p ) = 0 A^{2}(u,p)=0 A 2 ( u , p ) = 0 Φ ( u , p ) = 0 \Phi(u,p)=0 Φ ( u , p ) = 0 x x x x x x k = 9 k=9 k = 9 N [ x ] N[x] N [ x ]
(3) Let ξ = X ( ⋅ , w ′ ) \xi=X(\cdot,w') ξ = X ( ⋅ , w ′ ) z = L − 1 ξ z=L^{-1}\xi z = L − 1 ξ Lemma 4.1 the only out-neighbour of i ∈ Γ − i \in\Gamma^{-} i ∈ Γ − N [ x ] N[x] N [ x ] x x x u ∈ Q u \in Q u ∈ Q P P P x x x Γ + \Gamma^{+} Γ + L z = ξ Lz=\xi L z = ξ z i = z x − ξ i z_i=z_x-\xi_i z i = z x − ξ i i ∈ Γ − i \in\Gamma^{-} i ∈ Γ − z u = ∑ u → p z p − ξ u z_u=\sum_{u\to p}z_p-\xi_u z u = ∑ u → p z p − ξ u u ∈ Q u \in Q u ∈ Q ∑ o ∈ Γ + z o = z x \sum_{o\in\Gamma^{+}}z_o=z_x ∑ o ∈ Γ + z o = z x x → w ′ x\to w' x → w ′ p ∈ P p \in P p ∈ P Q Q Q w ′ w' w ′ μ = 2 \mu=2 μ = 2 Γ + \Gamma^{+} Γ + β w ′ \beta_{w'} β w ′ P P P 12 z x = 2 + 2 β w ′ 12z_x=2+2\beta_{w'} 12 z x = 2 + 2 β w ′ F ( w , w ′ ) = ∑ n ∈ Γ + ( w ) ∩ N ( x ) z n F(w,w')=\sum_{n\in\Gamma^{+}(w)\cap N(x)}z_n F ( w , w ′ ) = ∑ n ∈ Γ + ( w ) ∩ N ( x ) z n w w w Γ − \Gamma^{-} Γ − α w \alpha_w α w Q Q Q ξ n \xi_n ξ n ν 2 ( w , w ′ ) + ν 3 ( w , w ′ ) \nu_2(w,w')+\nu_3(w,w') ν 2 ( w , w ′ ) + ν 3 ( w , w ′ ) σ w = − 1 − F ( w , w ) \sigma_w=-1-F(w,w) σ w = − 1 − F ( w , w )
(4) Let w ≠ w ′ w\ne w' w = w ′ Γ + \Gamma^{+} Γ + Lemma 4.1 there are no arcs between w w w w ′ w' w ′ F ( w , w ′ ) F(w,w') F ( w , w ′ ) w w w w ′ w' w ′ w ′ w' w ′ w w w F ( w , w ′ ) = F ( w , w ) F(w,w')=F(w,w) F ( w , w ′ ) = F ( w , w ) T ( w , w ′ ) = − F ( w , w ) = 1 + σ w T(w,w')=-F(w,w)=1+\sigma_w T ( w , w ′ ) = − F ( w , w ) = 1 + σ w T ( w ′ , w ) = 1 + σ w T(w',w)=1+\sigma_w T ( w ′ , w ) = 1 + σ w σ w ′ = σ w \sigma_{w'}=\sigma_w σ w ′ = σ w σ w σ w ′ = T ( w , w ′ ) T ( w ′ , w ) \sigma_w\sigma_{w'}=T(w,w')T(w',w) σ w σ w ′ = T ( w , w ′ ) T ( w ′ , w ) σ w 2 = ( 1 + σ w ) 2 \sigma_w^2=(1+\sigma_w)^2 σ w 2 = ( 1 + σ w ) 2 σ w = − 1 / 2 \sigma_w=-1/2 σ w = − 1/2 3 σ w 3\sigma_w 3 σ w
Symmetries and types. Label Q Q Q P P P Q Q Q P P P Lemma A.1 . Permutations of M M M Q Q Q P P P Q Q Q P P P L L L Φ \Phi Φ F F F σ \sigma σ N [ x ] N[x] N [ x ] Q Q Q P P P 5 ! ⋅ 8 = 960 5!\cdot8=960 5 ! ⋅ 8 = 960 5 ! ⋅ 32 = 3840 5!\cdot32=3840 5 ! ⋅ 32 = 3840 w w w Γ + \Gamma^{+} Γ + Γ − \Gamma^{-} Γ − N [ x ] ∪ { w } N[x]\cup\{w\} N [ x ] ∪ { w } σ ≠ 0 \sigma\ne0 σ = 0
Proposition A.2. Suppose that a graph ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 ) x x x Q Q Q P P P w 0 w_0 w 0 σ 0 ≠ 0 \sigma_0\ne0 σ 0 = 0 σ ≠ 0 \sigma\ne0 σ = 0 w w w w w w a w = A ( w 0 , w ) a_w=A(w_0,w) a w = A ( w 0 , w ) b w = A ( w , w 0 ) b_w=A(w,w_0) b w = A ( w , w 0 )
(a) minor of the pair: σ 0 σ w = ( a w − F ( w 0 , w ) ) ( b w − F ( w , w 0 ) ) \sigma_0\sigma_w=(a_w-F(w_0,w))(b_w-F(w,w_0)) σ 0 σ w = ( a w − F ( w 0 , w )) ( b w − F ( w , w 0 ))
(b) arcs to the pivot: the arc w 0 → w w_0\to w w 0 → w N [ x ] N[x] N [ x ] μ \mu μ w 0 → n → w w_0\to n\to w w 0 → n → w n ∈ N [ x ] n\in N[x] n ∈ N [ x ] w → w 0 w\to w_0 w → w 0
(c) types: the types of all 34 outer vertices are distinct, and if σ w ≠ 0 \sigma_w\ne0 σ w = 0 w w w
(d) compatibility: for any two triples the numbers A ( w , w ′ ) A(w,w') A ( w , w ′ ) A ( w ′ , w ) A(w',w) A ( w ′ , w ) w w w w ′ w' w ′ N [ x ] ∪ { w 0 } N[x]\cup\{w_0\} N [ x ] ∪ { w 0 } μ \mu μ N [ x ] ∪ { w 0 } N[x]\cup\{w_0\} N [ x ] ∪ { w 0 }
(e) cover: for any n , n ′ ∈ N ( x ) n,n'\in N(x) n , n ′ ∈ N ( x ) Φ ( n , n ′ ) \Phi(n,n') Φ ( n , n ′ ) n → w → n ′ n\to w\to n' n → w → n ′ N ( x ) N(x) N ( x ) Lemma A.1 ; the vertex w 0 w_0 w 0 7 − α w 0 7-\alpha_{w_0} 7 − α w 0 7 − β w 0 7-\beta_{w_0} 7 − β w 0 w w w 7 − α w 7-\alpha_w 7 − α w 7 − β w 7-\beta_w 7 − β w
(f) reciprocal arcs of the pivot: the number of triples with a w = b w = 1 a_w=b_w=1 a w = b w = 1 t t t N ( x ) N(x) N ( x ) w 0 w_0 w 0
Proof. The trace of T T T − 4 -4 − 4 σ w ≠ 0 \sigma_w\ne0 σ w = 0 w 0 w_0 w 0 w ′ = w 0 w'=w_0 w ′ = w 0 λ = 0 \lambda=0 λ = 0 μ = 2 \mu=2 μ = 2 μ \mu μ Lemma A.1 and the choice of w 0 w_0 w 0 Lemma A.1 ; the last one holds because an outer vertex has 9 out-neighbours, of which 2 lie in Γ − \Gamma^- Γ − α w \alpha_w α w Q Q Q Γ + \Gamma^+ Γ + β w \beta_w β w P P P A 2 ( w 0 , w 0 ) = t A^2(w_0,w_0)=t A 2 ( w 0 , w 0 ) = t w 0 w_0 w 0 t t t x x x N ( x ) N(x) N ( x ) w 0 w_0 w 0 a w = b w = 1 a_w=b_w=1 a w = b w = 1
The first program. For each of the 707 pivot orbits it looks for 33 triples satisfying conditions (a)–(e). It also checks the last part of (e), the degrees of the other outer vertices among the outer vertices. It does not check condition (f): weakening the conditions only enlarges the search. First it builds the candidates, the triples satisfying (a)–(c), and their pairwise compatibility (d); everything is computed exactly, in integers, because the matrix 12 L − 1 12L^{-1} 12 L − 1 ( n , n ′ ) (n,n') ( n , n ′ ) N ( x ) N(x) N ( x ) N ( x ) N(x) N ( x ) i i i
The second program is designed differently and shares no code with the first: it builds the frame, the types, the order of the orbits and the key with its own code, and writes one SAT formula for each pivot orbit. A variable of the formula is a candidate, that is, a triple satisfying (a)–(c). The clauses forbid taking two triples of the same type and two triples that are incompatible by the arc formula and the count of paths of length 2 in (d); triangles in which the arc between two triples is one of the two arcs of a path through the third vertex are not forbidden by the formula, and this weakening, too, only enlarges the search. Cardinality constraints encode the same cells of the cover as in the first program, the number 33 of triples and condition (f); the last part of (e) is absent from the formula as well. The solver Minicard from PySAT [22 ] found the formulas of all 707 orbits unsatisfiable, but the result does not rest on it: each unsatisfiability has been checked separately, 166 formulas contain the empty clause, and for the other 541 CaDiCaL wrote proofs accepted by two checkers (§ 9 ). Both programs rest on the same reduction, Proposition A.2 , which is proved only in the text, and each checks a part of its conditions. Therefore the second program catches an implementation error in the first one, but not an error in Lemma A.1 or in Proposition A.2 .
Cuts beyond the conditions. Besides conditions (a)–(f), both programs discard candidates by direct consequences of the identity A 2 = t I + μ ( J − I − A ) A^2=tI+\mu(J-I-A) A 2 = t I + μ ( J − I − A ) μ \mu μ t t t n → w → n ′ n\to w\to n' n → w → n ′ Φ ( n , n ′ ) \Phi(n,n') Φ ( n , n ′ )
Controls of the programs. The case τ = 1 \tau=1 τ = 1 ( 10 , 3 , 3 , 0 , 1 ) (10,3,3,0,1) ( 10 , 3 , 3 , 0 , 1 ) θ = 1 \theta=1 θ = 1 T T T σ w = − 1 / 2 \sigma_w=-1/2 σ w = − 1/2 Lemma A.1 excludes for ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 ) 3 σ w 3\sigma_w 3 σ w θ \theta θ τ ∈ { 0 , 2 , 3 } \tau\in\{0,2,3\} τ ∈ { 0 , 2 , 3 } θ = 1 \theta=1 θ = 1 τ = 1 \tau=1 τ = 1 Φ \Phi Φ ( 48 , 9 , 5 , 0 , 2 ) (48,9,5,0,2) ( 48 , 9 , 5 , 0 , 2 ) θ = 1 \theta=1 θ = 1 τ = 0 \tau=0 τ = 0 τ = 1 \tau=1 τ = 1
Statements of the paper and Lean theorems
Table 3 names what each step of the proofs rests on: “Lean” is a theorem accepted by the Lean kernel (Section 9); “by hand” is a proof in the text. Theorems about properties of a graph take the hypothesis IsDSRG with the parameters of the statement; where “for any matrix” is said, the theorem has no hypothesis IsDSRG. The nonexistence results for the sets and their complements are listed in Table 2 .
Table 5.
Table 2 (PDF p. 30).
