HEXAGONbeta

Strongly regular graphs on 160, 232, 261 and 280 vertices from fusions of orbitals of PΓL(2,8) and 2^4:(S3×S3)

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Anton Kovaľ ↗

Version 1 / Oct 12, 2026 / CC BY 4.0

Abstract

We construct strongly regular graphs with parameters (160,54,18,18), (232,63,14,18), (261,64,14,16) and (280,63,14,14), and hence also their complements. All four parameter sets were marked "?" (existence unknown) in Brouwer's online table on 11 and 12 October 2026; they are the parameters of the hypothetical partial geometries pg(9,5,3), pg(7,8,2), pg(8,7,2) and pg(9,6,2). We give eight pairwise non-isomorphic graphs: three on 160 vertices, one on 232, two on 261 and two on 280. None of them is geometric. As far as we can determine, they are the first graphs known with these parameters. Five of the graphs have a short description over the projective line PG(1,8) and its quadratic extension PG(1,64). The vertices are pairs of points of PG(1,8) or conjugate pairs of points of PG(1,64) ∖ PG(1,8), each carrying a label in 𝔽_8*, together with a small orbit of points, pairs, or conjugate pairs. Adjacency is decided by cross ratios: for two labelled vertices on disjoint pairs, the quotient (or the product) of the two labels must equal the cross ratio of the two pairs or its inverse; for pairs sharing a point it must equal 1, and a labelled pair and a conjugate pair are adjacent when their cross ratio is a primitive cube root of unity. The "quotient" graphs on 232, 261 and 280 vertices have the automorphism group (SL(2,8) × C_7) ⋊ C_6 ≅ GL(2,8) ⋊ C_6 of order 21168; the two "product" graphs have C_2 × PΓL(2,8), of order 3024. One graph on 160 vertices lives on the 16 cells of a 4 × 4 grid and three copies of the 48 flags of its even transversals; its automorphism group is C_3 × 2^4:(S_3 × S_3), of order 1728. The other two graphs on 160 vertices have automorphism groups of orders 1728 and 576. The graphs were found by a computer search over fusions of orbitals of groups acting with two or three orbits, using the GAP library of tables of marks; the search reported five graphs, and enumerating all fusions of the same group actions gave three more. We do not classify the graphs with these parameters. The same constructions over PG(1,q) give, for q=4, the classical skew-lines graph of PG(3,2) and a second known srg(35,16,6,8), and no strongly regular graph for q=16 or q=32 under the groups searched (complete solver verdicts): within this model the graphs for q=8 appear to be sporadic. Strong regularity of every graph is checked by an exact, standalone, standard-library Python program, the constructions are re-implemented from the text of this paper, and all computer results were reproduced by an independent audit with separately written code and checked again by a referee with its own code. Also deposited on Zenodo with the full data archive (the citable record): https://doi.org/10.5281/zenodo.23313399

Provenance statement

This work was produced in Claude Code sessions (Anthropic Claude Opus and Claude Fable models) directed by the author, who set the problems, chose the methods and claims, and checked the results. The eight graphs were found by a computer search over fusions of orbitals of groups acting with two or three orbits (GAP tables of marks, CP-SAT), and by enumerating all fusions of the same group actions; the cross-ratio rules over PG(1,8) and the grid-and-flags rule were then extracted from the hits, re-implemented from the wording of the paper, and every graph was verified with a standard-library Python program printed in the paper and included in the data archive; the constructions, valencies and group invariance are proved by hand, while strong regularity, the automorphism groups, non-isomorphism and non-geometricity are exact computations. The first version was audited blind by a session of a different model (Claude Fable) with its own code, which rebuilt all eight graphs and reproduced every computation, and the second version was refereed by a further independent session with its own code; the audit and referee reports are supplied as supplementary material. The LaTeX text was drafted by the agents and revised after the audit and the referee round. No AI system is a contributor. The same work, with the full data archive (graph6 files of every graph, scripts, logs), is deposited on Zenodo, DOI https://doi.org/10.5281/zenodo.23313399, which is the citable record.
AI provenance filesAI_USE_STATEMENT.txt · 3 KBaudit_twoorbit8_fable_2026_10_12.txt · 19 KBnew_srgs_twoorbit_2026_10_11.txt · 22 KBreferee_new_srgs_twoorbit_v2_fable_2026_10_12.txt · 30 KB

References

  1. A. E. Brouwer, D. Crnković and A. Švob, A construction of directed strongly regular graphs with parameters (63,11,8,1,2)(63,11,8,1,2), Discrete Math. 347 (2024), 114146; arXiv:2404.03100.arXiv
  2. A. E. Brouwer, Parameters of strongly regular graphs , online tables, r̆l https://aeb.win.tue.nl/graphs/srg/srgtab.html (pages for 151v300151 v 300 accessed 11 and 12 October 2026).link
  3. A. E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs , Encyclopedia of Mathematics and its Applications 182, Cambridge University Press, 2022, doi:10.1017/9781009057226.DOI
  4. W. Burnside, Theory of Groups of Finite Order , 2nd ed., Cambridge University Press, 1911.
  5. The GAP Group, GAP -- Groups, Algorithms, and Programming , Version 4.12.1, 2022, r̆l https://www.gap-system.org .link
  6. A. A. Ivanov, M. Kh. Klin, S. V. Tsaranov and S. V. Shpektorov, On the problem of computing the subdegrees of transitive permutation groups, Russian Math. Surveys 38 :6 (1983), 123--124, doi:10.1070/RM1983v038n06ABEH003460.DOI
  7. A. Kovaľ, New strongly regular graphs on open parameter sets of Brouwer's table, preprint, Zenodo, 2026, doi:10.5281/zenodo.23210829.DOI
  8. A. Kovaľ, Strongly regular graphs on 306306, 400400, 576576, 784784 and 12961296 vertices from multi-orbit coset fusion and Bush-type Hadamard matrices, preprint, Zenodo, 2026, doi:10.5281/zenodo.23296158.DOI
  9. B. D. McKay and E. Spence, Classification of regular two-graphs on 3636 and 3838 vertices, Australas. J. Combin. 24 (2001), 293--300.
  10. B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94--112; o̧de dreadnaut and o̧de labelg of nauty 2.8.8.
  11. L. Perron and F. Didier, CP-SAT , OR-Tools, Google, r̆l https://developers.google.com/optimization (version 9.15.6755, in the search image and in all enumerations of this paper).link
  12. T. Merkwitz, L. Naughton and G. Pfeiffer, TomLib, the GAP library of tables of marks , Version 1.2.11, GAP package, 2024, r̆l https://gap-packages.github.io/tomlib .link

Version history

  1. v1Submitted by Anton KovaľInitial depositCurrentOct 12, 2026