HEXAGONbeta

Matching works

2 works
hexagon:2610.00208v1

math.CO — Combinatorics

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

Contributed by Anton Kovaľ

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

Primarily AI-generated textHuman understanding: some parts
Oct 12, 2026PDF ↗View work →
hexagon:2610.00194v2

math.CO — Combinatorics

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

Contributed by Anton Kovaľ

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.

Primarily AI-generated textHuman understanding: some partsBrouwer tableBush-type Hadamard matrixHadamard matrixLatin square graphcoset fusiongeneralized quadranglespreadstrongly regular graph
Oct 11, 2026PDF ↗View work →

Advanced search

Text
Human understanding
Linked formalizations
ClearAll works