pith. sign in

arxiv: 2204.04755 · v3 · submitted 2022-04-10 · 🧮 math.CO

Pseudo-Geometric Strongly Regular Graphs with a Regular Point

Edwin van Dam , Krystal Guo This is my paper

Pith reviewed 2026-05-24 11:27 UTC · model grok-4.3

classification 🧮 math.CO
keywords strongly regular graphspseudo-geometric graphsregular pointgeneralized quadranglesgraph coverscollinearity graphscombinatorics
0
0 comments X

The pith

Characterization of pseudo-geometric strongly regular graphs with a regular point yields explicit constructions of many new graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines pseudo-geometric strongly regular graphs that possess a regular point, meaning a vertex whose second subconstituent forms a cover of a strongly regular graph or is itself complete. Through structural analysis, it characterizes every graph meeting these conditions. This characterization directly enables the construction of q distinct new graphs sharing parameters with the collinearity graph of a generalized quadrangle of order (q,q) for any prime power q. It also yields a new non-geometric graph with the parameters of the Hermitian generalized quadrangle of order (q squared, q). The results include the enumeration of 135478 new graphs with parameters (85,20,3,5) and 27039 with parameters (156,30,4,6), resolving an earlier open question.

Core claim

The authors characterize all pseudo-geometric strongly regular graphs containing a regular point under the condition that the second subconstituent with respect to that vertex is a cover of a strongly regular graph or a complete graph. This leads to an explicit construction for q new pairwise non-isomorphic graphs with the same parameters as the collinearity graph of generalized quadrangles of order (q,q) and a new non-geometric graph with the parameters of the Hermitian generalized quadrangle of order (q^2, q), for prime powers q. The characterization is also used to compute large numbers of new strongly regular graphs for two specific parameter tuples.

What carries the argument

The key mechanism is the structural decomposition around a regular point in a pseudo-geometric strongly regular graph, where the second subconstituent being a cover determines the possible extensions and global graph properties.

If this is right

  • q new pairwise non-isomorphic graphs exist for each prime power q with parameters of GQ(q,q) collinearity graphs.
  • There exists at least one new non-geometric graph with parameters of the Hermitian GQ(q^2,q).
  • The open question of Gardiner, Godsil, Hensel, and Royle is answered affirmatively by the constructions.
  • Over 135000 new SRGs with parameters (85,20,3,5) can be constructed.
  • Over 27000 new SRGs with parameters (156,30,4,6) exist.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may extend to finding new graphs in other families of distance-regular graphs by similar subconstituent analysis.
  • These constructions suggest that the parameter sets for generalized quadrangles allow significantly more realizations than the geometric ones alone.
  • The computational enumeration indicates that exhaustive search methods combined with the characterization can scale to larger parameter sets.

Load-bearing premise

The characterization applies only to pseudo-geometric strongly regular graphs where the second subconstituent with respect to a vertex is a cover of a strongly regular graph or a complete graph.

What would settle it

A single counterexample would be a pseudo-geometric strongly regular graph with a regular point whose second subconstituent covers an SRG but whose structure does not match any of the characterized forms, or the inability to produce q non-isomorphic new graphs for a small q such as q=3.

Figures

Figures reproduced from arXiv: 2204.04755 by Edwin van Dam, Krystal Guo.

Figure 1
Figure 1. Figure 1: The collinearity graph of W(2), the unique GQ(2, 2), up to isomorphism. It is a strongly regular graph with parameters (15, 6, 1, 3). Another generalized quadrangle which we look at in this paper is the Hermitian gener￾alized quadrangle which we will denote H(3, q2 ). Let H be a nonsingular Hermitian variety of the projective space PG(3, q2 ), where q is a prime power. Then the points and lines of H give a… view at source ↗
Figure 2
Figure 2. Figure 2: The collinearity graph of W(2), with two vertices x, y highlighted in green. The common neighbours of x and y are shown with dotted circles. The span of x and y, |{x, y} ⊥⊥| = t + 1, consists of x, y together with z, the vertex highlighted in yellow. For example, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The subconstituents of the collinearity graph of [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Left: The distance partition of Γ with respect to v. Right: The refined distance partition of Γ with respect to the regular point v. By applying our main theorem, we obtain the following corollary: Corollary 4.1. Γ is a strongly regular graph with parameters (q 3+q 2+q+1, q2+q, q−1, q+1) with a regular point if and only if Γ = Γ(H, I, φ), where (i) H is a distance regular graph1 with intersection array {q … view at source ↗
read the original abstract

We study pseudo-geometric strongly regular graphs whose second subconstituent with respect to a vertex is a cover of a strongly regular graph or a complete graph. By studying the structure of such graphs, we characterize all graphs containing such a vertex, and use our characterization to find many new strongly regular graphs. Thereby, we answer a question posed by Gardiner, Godsil, Hensel, and Royle. We give an explicit construction for q new, pairwise non-isomorphic graphs with the same parameters as the collinearity graph of generalized quadrangles of order $(q,q)$ and a new non-geometric graph with the same parameters as the collinearity graph of the Hermitian generalized quadrangle of order $(q^2, q)$, for prime powers $q$. Using our characterization, we computed 135478 new strongly regular graphs with parameters (85,20,3,5) and 27 039 strongly regular graphs with parameters (156, 30, 4, 6).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 4 minor

Summary. The manuscript studies the subclass of pseudo-geometric strongly regular graphs in which a fixed vertex (called a regular point) has the property that its second subconstituent is a cover of a strongly regular graph or a complete graph. Within this subclass the authors derive a structural characterization of all such graphs, answer a question of Gardiner–Godsil–Hensel–Royle, and apply the characterization to produce explicit constructions and large enumerations. The constructions yield, for every prime power q, q pairwise non-isomorphic graphs with the parameters of the collinearity graph of a generalized quadrangle of order (q,q) together with one new non-geometric graph with the parameters of the Hermitian generalized quadrangle of order (q²,q). Using the same characterization the authors enumerate 135478 previously unknown graphs with parameters (85,20,3,5) and 27039 graphs with parameters (156,30,4,6).

Significance. If the characterization is correct, the work supplies the first systematic source of many new pseudo-geometric SRGs, including the first infinite family of non-geometric examples with Hermitian parameters and two very large explicit enumerations. These results directly enlarge the known stock of strongly regular graphs and provide concrete test cases for conjectures relating SRGs to finite geometries.

major comments (2)
  1. [§4] §4, Construction 4.3: the claim that the q constructed graphs are pairwise non-isomorphic for each fixed q rests on an invariant whose definition is only sketched; an explicit computation of this invariant (or an alternative isomorphism test) for at least one small prime power q is needed to confirm the claim.
  2. [§6] §6, enumeration procedure: the reported counts of 135478 and 27039 new graphs presuppose that every admissible cover of an SRG (or complete graph) has been generated and that isomorphism testing is exhaustive; the manuscript does not state an a-priori bound on the order of the covers or the precise algorithm used for canonical labelling, which is load-bearing for the numerical claims.
minor comments (4)
  1. [Abstract] Abstract: the spacing in “27 039” is inconsistent with the adjacent figure “135478”; adopt a uniform thousands separator or none.
  2. [Introduction] Introduction, paragraph 2: the question of Gardiner, Godsil, Hensel and Royle is cited only by name; supply the precise reference (journal, year, theorem or page).
  3. [Notation] Notation section: the symbol Γ_2(x) for the second subconstituent is introduced without an explicit reminder that the graph is assumed to be pseudo-geometric; a one-sentence clarification would prevent misreading.
  4. [Table 1] Table 1: the column headings for the new graphs versus the classical GQ(q,q) graphs are not aligned with the parameter rows; reformat for readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the significance of our results, and recommendation for minor revision. We address each major comment below.

read point-by-point responses

  1. Referee: [§4] §4, Construction 4.3: the claim that the q constructed graphs are pairwise non-isomorphic for each fixed q rests on an invariant whose definition is only sketched; an explicit computation of this invariant (or an alternative isomorphism test) for at least one small prime power q is needed to confirm the claim.

    Authors: We agree that an explicit verification would strengthen the presentation. In the revised manuscript we will add a concrete computation of the invariant for the smallest prime power q=2, confirming that the two graphs produced by Construction 4.3 are non-isomorphic. The general argument for arbitrary q then follows directly from the definition of the invariant given in the construction. revision: yes

  2. Referee: [§6] §6, enumeration procedure: the reported counts of 135478 and 27039 new graphs presuppose that every admissible cover of an SRG (or complete graph) has been generated and that isomorphism testing is exhaustive; the manuscript does not state an a-priori bound on the order of the covers or the precise algorithm used for canonical labelling, which is load-bearing for the numerical claims.

    Authors: We accept that additional implementation details are required to make the numerical claims fully reproducible. The revised version will state the a-priori bound on the order of admissible covers (derived from the parameters of the target SRG) and will specify the canonical-labelling algorithm employed (including the software package and version). These additions will substantiate that the enumeration is exhaustive within the stated bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained within stated subclass

full rationale

The paper defines its scope explicitly as the subclass of pseudo-geometric SRGs whose second subconstituent (w.r.t. a fixed vertex) is a cover of an SRG or complete graph. Within this definitional subclass it performs structural analysis to obtain a characterization, then applies the characterization to produce explicit constructions and enumerations of new graphs. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or ansatz imported from the authors' prior work; the constructions and counts are presented as direct consequences of the characterization rather than tautological renamings or self-referential fits. The cited question from Gardiner et al. is external. This yields a self-contained derivation with no load-bearing circular reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract, no free parameters or invented entities are apparent; the work uses existing combinatorial structures.

axioms (1)
  • standard math Standard assumptions in graph theory about strongly regular graphs and their parameters.
    The paper builds on established definitions of SRGs and pseudo-geometric graphs.

pith-pipeline@v0.9.0 · 5692 in / 1357 out tokens · 29535 ms · 2026-05-24T11:27:21.578218+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Pseudo-ovals of elliptic quadrics as Delsarte designs of association schemes

    John Bamberg, Giusy Monzillo, and Alessandro Siciliano. Pseudo-ovals of elliptic quadrics as Delsarte designs of association schemes. Linear Algebra and its Applica- tions, 624:281–317, 2021

    work page 2021

  2. [2]

    Strongly regular graphs, partial geometries and partially balanced designs

    Raj Bose. Strongly regular graphs, partial geometries and partially balanced designs. Pacific Journal of Mathematics , 13(2):389–419, 1963

    work page 1963

  3. [3]

    A.E. Brouwer. Distance regular graphs of diameter 3 and strongly regular graphs. Discrete Mathematics, 49(1):101–103, 1984

    work page 1984

  4. [4]

    Brouwer, A.M

    A.E. Brouwer, A.M. Cohen, and A. Neumaier. Distance-regular graphs. Springer-Verlag, Berlin, 1989

    work page 1989

  5. [5]

    Brouwer, A.V

    A.E. Brouwer, A.V. Ivanov, and M.H. Klin. Some new strongly regular graphs. Com- binatorica, 9(4):339–344, 1989

    work page 1989

  6. [6]

    Brouwer and J.H

    A.E. Brouwer and J.H. van Lint. Strongly regular graphs and partial geometries. In D.H. Jackson and S.A. Vanstone, editors, Enumeration and Design, pages 85–122. Academic Press Inc., United States, 1984

    work page 1984

  7. [7]

    Brouwer and H

    Andries E. Brouwer and H. Van Maldeghem. Strongly regular graphs. Cambridge Uni- versity Press, 2022

    work page 2022

  8. [8]

    D. de Caen. The spectra of complementary subgraphs in a strongly regular graph. European Journal of Combinatorics , 19(5):559–565, 1998

    work page 1998

  9. [9]

    Cameron, J.M

    P.J. Cameron, J.M. Goethals, and J.J. Seidel. Strongly regular graphs having strongly regular subconstituents. Journal of Algebra, 55(2):257–280, 1978

    work page 1978

  10. [10]

    Coolsaet, J

    K. Coolsaet, J. Degraer, and E. Spence. The strongly regular (45 , 12, 3, 3) graphs. Electron. J. Combin., 13:R32, 2006. 20

    work page 2006

  11. [11]

    Strongly regular graphs from classical gen- eralized quadrangles

    Antonio Cossidente and Francesco Pavese. Strongly regular graphs from classical gen- eralized quadrangles. Designs, Codes, and Cryptography , 85(3):457–470, 2016

    work page 2016

  12. [12]

    Dean Crnkovi´ c, AndreaˇSvob, and Vladimir D. Tonchev. Strongly regular graphs with parameters (81, 30, 9, 12) and a new partial geometry. Journal of Algebraic Combina- torics, 53(1):253–261, 2021

    work page 2021

  13. [13]

    Edwin R. van Dam. Regular graphs with four eigenvalues. Linear Algebra and its Applications, 226-228:139–162, 1995. Honoring J.J.Seidel

    work page 1995

  14. [14]

    van Dam and Krystal Guo

    Edwin R. van Dam and Krystal Guo. kguo-sagecode/newSRGs: new pseudo-generalized quadrangles, doi:10.5281/zenodo.6596987, May 2022

    work page doi:10.5281/zenodo.6596987 2022

  15. [15]

    Constructions of strongly regular Cayley graphs and skew Hadamard difference sets from cyclotomic classes

    Tao Feng, Koji Momihara, and Qing Xiang. Constructions of strongly regular Cayley graphs and skew Hadamard difference sets from cyclotomic classes. Combinatorica, 35(4):413–434, 2014

    work page 2014

  16. [16]

    Strongly regular graphs from unions of cyclotomic classes

    Tao Feng and Qing Xiang. Strongly regular graphs from unions of cyclotomic classes. Journal of Combinatorial Theory, Series B , 102(4):982–995, 2012

    work page 2012

  17. [17]

    Fon-Der-Flaass

    Dmitry G. Fon-Der-Flaass. New prolific constructions of strongly regular graphs. Ad- vances in Geometry, 2:301–306, 2002

    work page 2002

  18. [18]

    Gardiner

    A. Gardiner. Antipodal covering graphs. Journal of Combinatorial Theory. Series B , 16(3):255–273, 1974

    work page 1974

  19. [19]

    Gardiner, C.D

    A.D. Gardiner, C.D. Godsil, A.D. Hensel, and Gordon F. Royle. Second neighbourhoods of strongly regular graphs. Discrete Mathematics, 103(2):161–170, 1992

    work page 1992

  20. [20]

    Ghinelli and S

    D. Ghinelli and S. L¨ owe. Generalized quadrangles with a regular point and associa- tion schemes. Linear Algebra and its Applications , 226-228:87–104, 1995. Honoring J.J.Seidel

    work page 1995

  21. [21]

    Godsil and G

    C. Godsil and G. Royle. Algebraic graph theory , volume 207 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2001

    work page 2001

  22. [22]

    Godsil and B.D

    C.D. Godsil and B.D. McKay. Constructing cospectral graphs. Aequationes Mathemat- icae, 25:257–268, 1982

    work page 1982

  23. [23]

    Koolen, Greg Markowsky, and Jongyook Park

    Ivan Guo, Jack H. Koolen, Greg Markowsky, and Jongyook Park. On the nonexistence of pseudo-generalized quadrangles. European Journal of Combinatorics , 89:103128, 2020

    work page 2020

  24. [24]

    Haemers and V.D

    W.H. Haemers and V.D. Tonchev. Spreads in strongly regular graphs. Designs, Codes and Cryptography, 8:145–157, 1996

    work page 1996

  25. [25]

    Haemers and Edward Spence

    Willem H. Haemers and Edward Spence. The pseudo-geometric graphs for generalized quadrangles of order (3,t ). European Journal of Combinatorics , 22(6):839–845, 2001. 21

    work page 2001

  26. [26]

    D.G. Higman. Strongly regular designs and coherent configurations of type [323]. Eu- ropean Journal of Combinatorics , 9(4):411–422, 1988

    work page 1988

  27. [27]

    Hobart and S.E

    S.A. Hobart and S.E. Payne. Reconstructing a generalized quadrangle from its distance two association scheme. Journal of Algebraic Combinatorics , 2:261–266, 1993

    work page 1993

  28. [28]

    Ihringer and A

    F. Ihringer and A. Munemasa. New strongly regular graphs from finite geometries via switching. Linear Algebra and its Applications , 580:464–474, 2019

    work page 2019

  29. [29]

    Graphs cospectral with NU(n + 1,q 2), n̸= 3

    Ferdinand Ihringer, Francesco Pavese, and Valentino Smaldore. Graphs cospectral with NU(n + 1,q 2), n̸= 3. Discrete Mathematics, 344(11):112560, 2021

    work page 2021

  30. [30]

    A new partial geometry pg(5,5,2).Journal of Combinatorial Theory, Series A, 183:105493, 2021

    Vedran Krˇ cadinac. A new partial geometry pg(5,5,2).Journal of Combinatorial Theory, Series A, 183:105493, 2021

    work page 2021

  31. [31]

    van Lint and A

    J.H. van Lint and A. Schrijver. Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields. Combinatorica, 1:63–73, 1981

    work page 1981

  32. [32]

    S.E. Payne. Coherent configurations derived from quasiregular points in generalized quadrangles. Finite Geometry and Combinatorics, London Math. Soc. Lecture Note Series, 191:327–339, 1993. Proceedings of Finite Geometry and Combinatorics, Second International Conference at Deinze, Belgium, 1992

    work page 1993

  33. [33]

    Payne and J.A

    S.E. Payne and J.A. Thas. Finite generalized quadrangles , volume 110. European Mathematical Society, 2009

    work page 2009

  34. [34]

    Stanley E. Payne. Nonisomorphic generalized quadrangles. Journal of Algebra , 18(2):201–212, 1971

    work page 1971

  35. [35]

    Shrikhande

    S.S. Shrikhande. The uniqueness of the L 2 association scheme. The Annals of Mathe- matical Statistics, 30(3):781–798, 1959

    work page 1959

  36. [36]

    The strongly regular (40, 12, 2, 4) graphs

    Edward Spence. The strongly regular (40, 12, 2, 4) graphs. Electron. J. Combin., 7:R22, 2000

    work page 2000

  37. [37]

    SageMath, the Sage Mathematics Software System (Version 8.3) ,

    The Sage Developers. SageMath, the Sage Mathematics Software System (Version 8.3) ,

    work page

  38. [38]

    http://www.sagemath.org

    work page

  39. [39]

    D Wallis

    W. D Wallis. Construction of strongly regular graphs using affine designs. Bulletin of the Australian Mathematical Society, 4(1):41–49, 1971. 22

    work page 1971