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
| CREATOR | Sergey Shpectorov, Tianxiao Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-02449