HEXAGONbeta

Strongly regular graphs on 306, 400, 576, 784 and 1296 vertices from multi-orbit coset fusion and Bush-type Hadamard matrices

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

Contributed by Anton Kovaľ

Version 2 / Oct 11, 2026 / CC BY 4.0

Abstract

We construct strongly regular graphs with parameters (306,55,4,11), (400,171,74,72), (576,253,112,110), (784,351,158,156) and (1296,595,274,272), and hence also their complements. All five parameter sets were marked "?" (existence unknown) in Brouwer's online table on 10 and 11 October 2026. Three of the graphs were found by a computer search that extends the transitive coset fusion of our earlier papers to groups acting with two orbits: the search fuses the orbitals of a group G on G/H_1⊔ G/H_2, screens with tables of marks, solves the exact quadratic equations on the structure constants with a SAT-based solver, and rebuilds every solution from scratch. The groups are 2× M_12, 5^(1+2)_+:4A_5 and Sp(6,2). Also deposited on Zenodo with the full data archive (the citable record): https://doi.org/10.5281/zenodo.23296158 The graphs on 400, 576, 784 and 1296 vertices come from a short step beyond known constructions. A symmetric Bush-type Hadamard matrix of order n^2 whose n× n blocks have unit diagonal, for instance one of Kharaghani's matrices, defines a strongly regular graph Γ_0 with the parameters of the Latin square graph LS_(n/2+1)(n). In Γ_0 the block rows and the block columns form two orthogonal spreads of Delsarte cliques. Deleting one spread gives the known graphs with λ=μ of Bonato, Holzmann and Kharaghani. By an elementary spread lemma, deleting both gives a strongly regular graph with the parameters of LS_(n/2-1)(n). Kharaghani's matrices exist for every Hadamard order n, so such a graph exists for every n=4m≥8, for example srg(1600,741,344,342) and srg(1936,903,422,420). A second source, found by analysing the search hits, is the rule (a,b)∼(c,d) iff a≠ c, b≠ d and H_abH_bcH_cdH_da=1 for a symmetric Hadamard matrix H. Together the two sources give at least 5, 7, 5 and 6 pairwise non-isomorphic graphs on 400, 576, 784 and 1296 vertices. None of the graphs we tested on these four vertex numbers is a Latin square graph, so they say nothing about the orthogonal arrays OA(n,n/2-1) named in the table. The graph on 306 vertices has a short description on the 300 non-square points of the parabolic quadric Q(4,5) together with the six points of a totally singular line; this line is a Delsarte clique. The graph has the parameters of the collinearity graph of a generalized quadrangle GQ(5,10) but is not geometric, and the same rule over 𝔽_3 gives the collinearity graph of Q(4,3). Strong regularity of every graph is also checked by an exact, standalone, standard-library Python program.

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 five graphs were found by a computer search over fusions of orbitals of transitive groups acting on two or three coset spaces, rebuilt independently in GAP, and verified with a standard-library Python program included in the data archive; the Hadamard constructions and the spread lemma were proved by hand and checked exactly. Each result was re-derived blind by a separate session of a different model (Claude Fable) with its own code, and the paper was refereed in two rounds by further independent sessions, which reproduced all canonical hashes and the clique and coclique counts; the referee reports are supplied as supplementary material. The LaTeX text was drafted by the agents and revised after the referee rounds. 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, https://doi.org/10.5281/zenodo.23296158, which is the citable record.
AI provenance filesAI_USE_STATEMENT.txt · 3 KBreferee_new_srgs_multiorbit_fable_2026_10_11.txt · 13 KBreferee_new_srgs_multiorbit_v2_fable_2026_10_12.txt · 30 KB

References

  1. A. E. Brouwer, Parameters of strongly regular graphs , online tables, r̆l https://aeb.win.tue.nl/graphs/srg/srgtab.html (pages for 301v400301 v 400, 551v600551 v 600, 751v800751 v 800 and 1251v13001251 v 1300 accessed 10 October 2026, re-read 11 October 2026).link
  2. A. Bonato, W. H. Holzmann and H. Kharaghani, Hadamard matrices and strongly regular graphs with the 3-e.c. adjacency property, Electron. J. Combin. 8 (2001), #R1.
  3. A. E. Brouwer and J. H. van Lint, Strongly regular graphs and partial geometries, in Enumeration and Design , Academic Press, 1984, 85--122.
  4. K. A. Bush, Unbalanced Hadamard matrices and finite projective planes of even order, J. Combin. Theory Ser. A 11 (1971), 38--44.
  5. 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
  6. R. Craigen and H. Kharaghani, Hadamard matrices and Hadamard designs, in C. J. Colbourn and J. H. Dinitz (eds.), Handbook of Combinatorial Designs , 2nd ed., Chapman & Hall/CRC, 2007, 273--280.
  7. D. Crnković, N. Mostarac and A. Švob, Distance-regular graphs obtained from the Mathieu groups, arXiv:2101.02790, 2021.arXiv
  8. D. Crnković, S. Rukavina and A. Švob, New strongly regular graphs from orthogonal groups O+(6,2)O^+(6,2) and O−(6,2)O^-(6,2), Discrete Math. 341 (2018), 2723--2728, doi:10.1016/j.disc.2018.06.029.DOI
  9. D. G. Fon-Der-Flaass, New prolific constructions of strongly regular graphs, Adv. Geom. 2 (2002), 301--306.
  10. The GAP Group, GAP -- Groups, Algorithms, and Programming , Version 4.12.1, 2022, r̆l https://www.gap-system.org .link
  11. J.-M. Goethals and J. J. Seidel, Strongly regular graphs derived from combinatorial designs, Canad. J. Math. 22 (1970), 597--614.
  12. C. J. Colbourn and J. H. Dinitz (eds.), Handbook of Combinatorial Designs , 2nd ed., Chapman & Hall/CRC, Boca Raton, 2007.
  13. W. H. Haemers and V. D. Tonchev, Spreads in strongly regular graphs, Des. Codes Cryptogr. 8 (1996), 145--157.
  14. Z. Janko, H. Kharaghani and V. D. Tonchev, The existence of a Bush-type Hadamard matrix of order 324324 and two new infinite classes of symmetric designs, Des. Codes Cryptogr. 24 (2001), 225--232.
  15. V. V. Kabanov, New versions of the Wallis--Fon-Der-Flaass construction to create divisible design graphs, arXiv:2111.10799, 2021.arXiv
  16. H. Kharaghani, New classes of weighing matrices, Ars Combin. 19 (1985), 69--72.
  17. A. Kovaľ, New strongly regular graphs on open parameter sets of Brouwer's table, preprint, Zenodo, 2026, doi:10.5281/zenodo.23210829.DOI
  18. A. Kovaľ, The regular two-graphs on 126126 and 176176 points are unique, preprint, Zenodo, 2026, doi:10.5281/zenodo.23279444.DOI
  19. B. D. McKay and E. Spence, Classification of regular two-graphs on 3636 and 3838 vertices, Australas. J. Combin. 24 (2001), 293--300.
  20. M. Muzychuk and Q. Xiang, Symmetric Bush-type Hadamard matrices of order 4m44m^4 exist for all odd mm, Proc. Amer. Math. Soc. 134 (2006), 2197--2204.
  21. M. Muzychuk, A generalization of Wallis--Fon-Der-Flaass construction of strongly regular graphs, J. Algebraic Combin. 25 (2007), 169--187.
  22. B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94--112; o̧de dreadnaut of nauty 2.8.8.
  23. L. Perron and F. Didier, CP-SAT , OR-Tools, Google, r̆l https://developers.google.com/optimization .link
  24. R. E. A. C. Paley, On orthogonal matrices, J. Math. Phys. 12 (1933), 311--320.
  25. J. J. Seidel, A survey of two-graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo I, Accad. Naz. Lincei, Rome, 1976, 481--511.
  26. T. Merkwitz, L. Naughton and G. Pfeiffer, TomLib, the GAP library of tables of marks , Version 1.2.11, GAP package.
  27. E. R. van Dam and K. Guo, Pseudo-geometric strongly regular graphs with a regular point, arXiv:2204.04755v3, 2026.arXiv
  28. W. D. Wallis, Construction of strongly regular graphs using affine designs, Bull. Austral. Math. Soc. 4 (1971), 41--49; corrigendum, Bull. Austral. Math. Soc. 5 (1971), 431.

Version history

  1. v1Submitted by Anton KovaľInitial depositSupersededOct 11, 2026
  2. v2Submitted by Anton KovaľSubmitted as a new versionCurrentOct 11, 2026