A strongly regular graph with parameters (833,416,207,208)

We construct a strongly regular graph with parameters (833,416,207,208), a conference graph. The parameter set was marked "?" (existence unknown) in Brouwer's online table on 29 October 2026; equivalently, no regular two-graph on 834 points and no symmetric conference matrix of order 834 was known. The vertex set is Z17 × F49; the 17 fibres are Paley graphs Paley(49), and two fibres are joined by a "line incidence" block [ℓ_a(u) − ℓ_b(v) ∈ T], where ℓ_a, ℓ_b are F7-linear forms on F49 and T ⊂ F7 is the set of non-zero squares or its complement according to the Paley graph Paley(17) on the fibres. The combinatorial input is a partition of the 136 edges of K17 into 34 four-cycles, each containing an odd number of edges of Paley(17), with a balanced choice of a bipartition class in each cycle. Strong regularity is proved by hand by a Fourier computation over F49: on each eigenspace of the fibres the Seidel matrix splits into 34 blocks of size 4, and the four-cycle condition is exactly the condition that each block squares to 17I. The first graph found has automorphism group of order 3; covers invariant under Z17 give further, non-isomorphic graphs with automorphism groups of order 51 (24 pairwise non-isomorphic graphs in all; any union of four parallel classes of AG(2,7) may replace Paley(49) in each fibre). The same construction with Paley(p²) fibres over a conference graph on q = 2p+3 vertices, p ≡ 3 (mod 4), gives conference graphs on p²q vertices whenever a signed four-cycle cover exists, and such covers exist for every prime power q ≡ 1 (mod 16) (by computer for q < 321, by a Jacobi-sum estimate for q ≥ 321). Hence for every prime p ≡ 7 (mod 8) such that 2p+3 is a prime power there is a conference graph on p²(2p+3) vertices; the first new cases give symmetric conference matrices of orders 25922, 214274, 4145154 and 9398594. With five incidences per direction instead of two, a computer search gives a conference graph on 2009 = 7²·41 vertices, hence a symmetric conference matrix of order 2010. The construction was proposed by an AI system as a generalisation of a construction of J. Yip; the cover was then found by a short depth-first search. The data archive contains the LaTeX source, the graphs in graph6 format (the first graph, the 16 graphs from translation-invariant covers and 3 from further direction seeds), the cover, a standard-library program that rebuilds the first graph from its definition and checks it (byte-identical graph6 output), a program that checks the hypotheses of the hand proof, the programs that find translation-invariant covers (q = 17, 49, 97, 257) and the resulting graphs, a standalone SRG verifier, the auditing session's search and verification programs, the blind-audit record, the proposing session's report, the referee report and the build log.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-29
DOI
https://doi.org/10.5281/zenodo.23771334
Primary Topic
Finite Group Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A strongly regular graph with parameters (833,416,207,208)

Anton Koval
5 links
Zenodo (CERN European Organization for Nuclear Research)
Finite Group Theory Research
preprint

A strongly regular graph with parameters (833,416,207,208)

Anton Koval
preprint en

Abstract

We construct a strongly regular graph with parameters (833,416,207,208), a conference graph. The parameter set was marked "?" (existence unknown) in Brouwer's online table on 29 October 2026; equivalently, no regular two-graph on 834 points and no symmetric conference matrix of order 834 was known. The vertex set is Z17 × F49; the 17 fibres are Paley graphs Paley(49), and two fibres are joined by a "line incidence" block [ℓ_a(u) − ℓ_b(v) ∈ T], where ℓ_a, ℓ_b are F7-linear forms on F49 and T ⊂ F7 is the set of non-zero squares or its complement according to the Paley graph Paley(17) on the fibres. The combinatorial input is a partition of the 136 edges of K17 into 34 four-cycles, each containing an odd number of edges of Paley(17), with a balanced choice of a bipartition class in each cycle. Strong regularity is proved by hand by a Fourier computation over F49: on each eigenspace of the fibres the Seidel matrix splits into 34 blocks of size 4, and the four-cycle condition is exactly the condition that each block squares to 17I. The first graph found has automorphism group of order 3; covers invariant under Z17 give further, non-isomorphic graphs with automorphism groups of order 51 (24 pairwise non-isomorphic graphs in all; any union of four parallel classes of AG(2,7) may replace Paley(49) in each fibre). The same construction with Paley(p²) fibres over a conference graph on q = 2p+3 vertices, p ≡ 3 (mod 4), gives conference graphs on p²q vertices whenever a signed four-cycle cover exists, and such covers exist for every prime power q ≡ 1 (mod 16) (by computer for q < 321, by a Jacobi-sum estimate for q ≥ 321). Hence for every prime p ≡ 7 (mod 8) such that 2p+3 is a prime power there is a conference graph on p²(2p+3) vertices; the first new cases give symmetric conference matrices of orders 25922, 214274, 4145154 and 9398594. With five incidences per direction instead of two, a computer search gives a conference graph on 2009 = 7²·41 vertices, hence a symmetric conference matrix of order 2010. The construction was proposed by an AI system as a generalisation of a construction of J. Yip; the cover was then found by a short depth-first search. The data archive contains the LaTeX source, the graphs in graph6 format (the first graph, the 16 graphs from translation-invariant covers and 3 from further direction seeds), the cover, a standard-library program that rebuilds the first graph from its definition and checks it (byte-identical graph6 output), a program that checks the hypotheses of the hand proof, the programs that find translation-invariant covers (q = 17, 49, 97, 257) and the resulting graphs, a standalone SRG verifier, the auditing session's search and verification programs, the blind-audit record, the proposing session's report, the referee report and the build log.

Zenodo (CERN European Organization for Nuclear Research)
Finite Group Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon