REVIEW 3 major objections 4 minor 13 references
Quasi-strongly regular graphs on the flags of symmetric designs
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Two flag graphs built from point-block flags are quasi-strongly regular, and each determines the original design up to isomorphism.
desk verdict Solid counting results and a clean Whitney application, but the main Γ2 isomorphism theorem rests on an unproved set identity in Lemma 4.1(ii), and the spectral section overclaims. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
A flag is an incident ordered pair $(p,c)$ of a point and a block, and every design parameter count in the paper reduces to counting flags through points or blocks. $\Gamma_1(D)$ is the line graph of the incidence graph of $D$, so line-graph isomorphism theory carries the proof that $\Gamma_1$ is a complete invariant. $\Gamma_2(D)$ uses the biplane property that any two blocks meet in exactly two points: two flags are adjacent exactly when their blocks' intersection is the two points of the flags, and because $\lambda=2$ the number of common neighbours of a non-adjacent pair is bounded by 2. The proof that $\Gamma_2$ is a complete invariant rests on Lemma 4.1, which claims that any isomorphism of $\Gamma_2$ graphs preserves which flags share a point and which share a block, thereby inducing bijections on the point set and block set.
What would settle it
Construct the three $(16,6,2)$-biplanes named in Section 5 and compare their $\Gamma_2$ graphs pairwise; if two non-isomorphic biplanes yield isomorphic $\Gamma_2$ graphs, Theorem 5 is false, and even if they are all non-isomorphic, inspecting the preimage sets of adjacent pairs tests the set-identity step in Lemma 4.1.
Extended reading notes
Core claim
For a non-trivial $(v,b,r,k,\lambda)$-BIBD, Theorem 1 says the flag graph $\Gamma_1(D)$ is an almost-quasi-strongly regular graph with common-neighbour counts $\{r-2,k-2\}$ for adjacent vertices and $\{0,1\}$ when $\lambda=1$, or $\{0,1,2\}$ when $\lambda>1$; when $D$ is symmetric this becomes a QSRG with parameters $(vk,2(k-1),k-2;0,1)$ or $(vk,2(k-1),k-2;0,1,2)$ (Corollary 1). Theorem 3 states $D\cong D'$ if and only if $\Gamma_1(D)\cong\Gamma_1(D')$, proved through the line graph of the incidence graph. For biplanes, Theorem 4 states that $\Gamma_2(D)$ is a $(vk,k-1,0;0,1,2)$-QSRG: it is $k-1$-regular, triangle-free, and every non-adjacent pair has 0, 1, or 2 common neighbours. Theorem 5 states $D\cong D'$ if and only if $\Gamma_2(D)\cong\Gamma_2(D')$. The paper closes by computing spectra of both graphs for all biplanes with at most 16 points, identifying which of those small flag graphs are determined by their spectrum.
Load-bearing premise
In Lemma 4.1(ii), the proof assumes without proof that an isomorphism of $\Gamma_2$ graphs maps the four flags built from two intersecting blocks onto the four preimages of the corresponding adjacent pairs in the target graph; if that set identity can fail, the claimed bijections on points and blocks do not follow and Theorem 5's converse is not established.
Editorial extensions
If this is right
- Symmetric designs and biplanes acquire graph-theoretic invariants from the QSRG parameters of their flag graphs, including degree, triangle-freeness, and common-neighbour sets.
- The isomorphism theorems rule out the possibility that $\Gamma_1$ or $\Gamma_2$ fails to distinguish distinct designs with the same parameters.
- For the three non-isomorphic $(16,6,2)$-biplanes, the $\Gamma_1$ flag graphs are cospectral but pairwise non-isomorphic, so $\Gamma_1$ is not determined by spectrum in that family; the spectrum of one $(16,6,2)$ $\Gamma_2$ graph is determined by its spectrum, while the status of the other two is left open.
- The known spectral characterizations of the $(7,4,2)$ and $(11,5,2)$ biplane flag graphs reappear as special cases of the parameter framework developed in the paper.
Reading between the lines
- A direct next step is to test whether cospectrality with $\Gamma_2(D)$ forces isomorphism to a biplane flag graph, using the unresolved 16-point components as the first nontrivial cases.
- The same two-flag adjacency idea could be extended to symmetric designs with $\lambda\ge3$ by declaring two flags adjacent when their blocks share $\lambda$ points and both flag points lie in that intersection; the resulting graphs' regularity and common-neighbour bounds are a natural open question.
- Because $\Gamma_1(D)$ is the line graph of the incidence graph, the QSRG parameters established here connect to biregular spectral theory and suggest that similar flag-graph encodings could be studied for other ranked incidence structures, such as flags of polytopes.
- If Lemma 4.1's unproved set identity fails for some biplane, Theorem 5 might still be true but would need a different proof; comparing all graph isomorphisms among the three 16-point $\Gamma_2$ graphs would expose such a failure.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines two graphs on the flags of a BIBD: Γ1, the line graph of the incidence graph, and Γ2, the Blokhuis–Brouwer graph restricted to biplanes. It claims that Γ1 is an AQSRG for every nontrivial BIBD and a QSRG for symmetric designs; that Γ1(D) and Γ2(D) determine D up to isomorphism (Theorems 3 and 5); that Γ2(D) is a (vk, k−1, 0; 0,1,2)-QSRG; and it computes spectra of these graphs for the known biplanes with at most 16 points.
Significance. The QSRG parameter results for Γ1 and Γ2 (Theorems 1 and 4) are elementary, self-contained counting arguments and appear correct; they give clean new examples of quasi-strongly regular graphs. The spectral computations in Section 5, based on Sage, are a useful contribution and are reported transparently. However, the advertised isomorphism characterizations are not correct as stated: Theorem 3 is false because of dualities, and the proof of Theorem 5 rests on a false lemma. The paper therefore cannot be accepted in its present form, but the correct QSRG and spectral results could form the basis of a substantially revised paper.
major comments (3)
- [3, Theorem 3] Theorem 3 is false as stated. Let D be a non-self-dual projective plane, for instance the Hall plane of order 9, and let D' be its dual. The incidence graphs Γ_D and Γ_{D'} are isomorphic as undirected bipartite graphs via the map interchanging points and blocks, so their line graphs Γ1(D) and Γ1(D') are isomorphic. But D and D' are not isomorphic as designs. The proof asserts that an isomorphism α of incidence graphs preserves the bipartition because the graphs are "directed"; this is not justified, since Γ_D is defined in Section 2 as a simple, undirected bipartite graph. For symmetric designs the correct statement is that Γ1(D) determines D only up to isomorphism or duality; for non-symmetric BIBDs with v ≠ b the bipartition is forced by degrees and the claim is correct.
- [4, Lemma 4.1 and Theorem 5] The proof of Lemma 4.1, which is the load-bearing step for the converse of Theorem 5, contains an unjustified set identity. In part (ii), after choosing blocks c1' and d' with c1' ∩ d' = {q1', q2'}, the proof asserts without argument that the preimages of the adjacent pairs (q1',c1') ∼ (q2',d') and (q1',d') ∼ (q2',c1') are exactly the four vertices {(p1,ci), (p1,cj), (pi,c1), (pj,c1)}. The isomorphism only shows that these preimages form two edges of Γ2(D); they could involve vertices such as (xij,ci) and (xij,cj) or other flags, and without the stated identity the induced maps β_P and β_B are not well-defined. Part (i) has the same gap. Moreover, the lemma is not merely missing a detail: for any self-dual biplane, the canonical isomorphism Γ2(D) → Γ2(D^T) given by (p,c) ↦ (c,p), composed with a duality D^T → D, is an automorphism of Γ2(D) that does not factor into point and block bijections, contradicting the lemma's conclusion. Consequently the converse of Theorem 5 is not established.
- [5.2] The claim that Γ2(D1) is determined by its spectrum because it is the disjoint union of six Clebsch graphs (each determined by its spectrum) is not justified. A disjoint union of graphs that are individually determined by their spectra need not itself be determined by its spectrum: a graph cospectral with the union could decompose into components of different sizes or connect components in a way that is not ruled out by the spectrum alone. An additional argument is needed, or the claim should be weakened to "not known from this argument."
minor comments (4)
- [5.1] In the displayed general spectrum formula for Γ1(D), the term under the square root should be (k − r)^2 + 4(r − λ), not (k − r)^2 − 4(r − λ); as written the formula gives non-real values in the symmetric case r = k and contradicts the correct formula given later for symmetric designs.
- [5.1] In the paragraph on the four non-isomorphic (6,20,10,3,4)-BIBDs, the phrase "by Theorem 5" should be "by Theorem 3," since the statement concerns Γ1, not Γ2.
- [5, Theorem 5] In the proof of Theorem 5, the expression "β(c,d) ∼ β(q,d)" should be "β(p,c) ∼ β(q,d)".
- [General] Throughout the text, "Blockhuis" should be "Blokhuis," and there are several typographical glitches such as an extra parenthesis in "Γ2(D))" and ligature errors in "flags."
Circularity Check
No circularity: the derivation chain uses direct counting from BIBD axioms, standard external theorems (Whitney, Hoffman-Ray-Chaudhuri), and an explicit external definition from Blokhuis-Brouwer.
full rationale
The paper's derivation chain is self-contained. Theorem 1 and Corollary 1 count flags and common neighbours directly from BIBD axioms (Section 3), with no fitted parameters and without assuming the conclusion. Theorem 3 is proved by invoking Whitney's line-graph theorem (Theorem 2) after noting that Γ1(D) = L(Γ_D); this is a standard external theorem, and the exceptional K3/K1,3 cases are excluded by Observation 1, so the equivalence D ≅ D′ ⇔ Γ1(D) ≅ Γ1(D′) is not assumed. The Γ2 results (Definition 2, Theorems 4 and 5) use the Blokhuis-Brouwer graph definition explicitly as a definition from [2], not as a derived prediction or ansatz smuggled in by the present authors. Theorem 4 is established by direct counting: regularity, triangle-freeness, and common-neighbour counts for non-adjacent flags. Theorem 5's forward direction follows from design isomorphism preserving block intersections; the converse rests on Lemma 4.1, which attempts to reconstruct point and block bijections from graph isomorphism. Whatever the status of the set-identity step in Lemma 4.1(ii), that is a potential proof gap, not circularity: the claimed reduction is not equivalent to its inputs by construction, and no load-bearing conclusion is imported from the authors' own prior work. References [2], [3], [8], [9], and [13] are prior work of other authors or standard results; there is no self-citation chain. Hence the paper is not circular.
Assumptions & free parameters
assumptions (5)
- standard math Whitney's theorem: connected graphs with isomorphic line graphs are isomorphic, with the single exception K3 versus K1,3.
- standard math Hoffman-Ray-Chaudhuri: a connected regular graph on vk vertices with the line-graph spectrum of a (v,k,λ)-symmetric design is the line graph of the incidence graph of such a design, with one exception for (4,3,2).
- domain assumption In a (v,k,2)-biplane, every pair of points lies in exactly two blocks, so any two blocks intersect in exactly two points.
- ad hoc to paper Lemma 4.1(ii): the adjacent pairs formed by c1' and d' must pull back to exactly the four-flag set {(p1,ci),(p1,cj),(pi,c1),(pj,c1)}.
- domain assumption The three non-isomorphic (16,6,2) biplanes D1, D2, D3 are exactly the biplanes on 16 points and are known from the literature.
Cite this review
Pith. "Pith review of Quasi-strongly regular graphs on the flags of symmetric designs." pith.science (2026). https://pith.science/paper/3ZTQKQI7
@misc{pith2026250521272,
author = {Pith},
title = {Pith review of: Quasi-strongly regular graphs on the flags of symmetric designs},
year = {2026},
howpublished = {\url{https://pith.science/paper/3ZTQKQI7}},
note = {Machine review of arXiv:2505.21272}
}
abstract
This paper was inspired by a paper by Blokhuis and Brouwer [Designs, Codes and Cryptography 65, 2012] in which a definition of a graph on the flags of a biplane is given, and they prove that the graph corresponding to the unique $(11,5,2)$-biplane is determined by its spectrum. It is also inspired by the different definition of flag-graph seen in the context of maps and abstract polytopes. Here we use this definition for $(v,k,\lambda)$-BIBDs, and prove that if the design is symmetric then the graph is quasi-strongly regular. We will also use the definition given by Blokhuis and Brouwer for the case of biplanes and prove that this too, is a QSRG, (with different parameters). We investigate whether these graphs are determined by their spectra for some of the known biplanes.
Reference graph
Works this paper leans on
-
[1]
Antonucci, S., A generalization of T -graphs, and quasistrong regularity, Riv. Mat. Univ. Parma , 13 (1987) no.4, 395–400
work page 1987
-
[2]
Blokhuis, A., Brouwer, A.E., Spectral characterization of a grap h on the flags of the eleven point biplane. Des. Codes Cryptogr. , 65 (2012), 65–69
work page 2012
-
[3]
Cunningham, G., del R ´ ıo Francos, M., Hubard, I., Toledo, M., Symm etry type graphs of polytopes and maniplexes, Ann. Comb. , 19 (2015) no.2, 243– 368
work page 2015
-
[4]
Doob, M., A spectral characterization of the line graph of a BIBD with λ = 1, Linear Algebra Appl. , 12 (1975), 11–20
work page 1975
-
[5]
Godsil, C., Royle, G., Algebraic Graph Theory, Springer, New York , (2001)
work page 2001
-
[6]
Hoffman, A.J., On the line graph of the projective plane, Proc. Amer. Math. Soc., 16 (1965), 297–302
work page 1965
-
[7]
Hoffman, A.J., Ray-Chaudhury, D.K., On the line graph of a finite affin e plane, Canadian Journal of Mathematics , 17 (1965), 687–694
work page 1965
-
[8]
Hoffman, A.J., Ray-Chaudhury, D.K., On the line graph of a symmetr ic balanced incomplete block design, Trans. Amer. Math. Soc., 116 (1965), 238– 252
work page 1965
Show all 13 references
-
[9]
Medial symmetry type graphs, Electron
Hubard, I., del R ´ ıo Francos, M., Orbani´ c, A., Pisanski, T. Medial symmetry type graphs, Electron. J. Combin. 20 (2013) no. 3, paper 29, 28pp
2013
-
[10]
Rao S.B., Rao A.R., A characterization of the line graph of a BIBD wit h λ = 1, Sanky¯ a, A31 (1969), 369–370
1969
-
[11]
Stein, W., Sage: Open Source Mathematical Software, Version 9.7 , The Sage Group , (2008), http://www.sagemath.org
2008
-
[12]
Stinson, D.R., Combinatorial designs, Springer-Verlag, New York, 2004 , (2004), xvi+300pp
2004
-
[13]
Whitney, H., Congruent graphs and the connectivity of graphs , Amer. J. Math. 54 (1932), 150–168. 16
1932
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.