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
- Anton Koval
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