Strongly regular graphs with parameters ( 85 , 14 , 3 , 2 ) (85,14,3,2) do not exist

Sergey Shpectorov, Tianxiao Zhao · 2025

Read Strongly regular graphs with parameters ( 85 , 14 , 3 , 2 ) (85,14,3,2) do not exist by Sergey Shpectorov, Tianxiao Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-02449.txt.

Description

Sergey Shpectorov and Tianxiao Zhao close a decades-old question in graph theory by proving a certain graph cannot exist. Strongly regular graphs are networks where every counting rule about neighbors comes out constant. One long-unresolved parameter set describes a graph on eighty-five vertices where each vertex has fourteen neighbors, with three shared neighbors for adjacent pairs and two for non-adjacent pairs.

The authors first use the catalogue of small cubic graphs to restrict what the neighborhood of any vertex could look like. Then they list every possible neighborhood around a largest three-clique and test each against the counting rules and against geometric embedding conditions. Every case ends in contradiction. The empty result matters because feasible parameter sets that no graph realizes are as informative as new graphs: they mark the true borders of the theory.

Catalog record

CREATORSergey Shpectorov, Tianxiao Zhao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-02449

Browse the full library · About the Tower of Babel