2020/05/25 by Thomas Jenrich, Jenrich, Thomas
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Metric Geometry (math.MG) #graph theory and CDMA systems #math.CO #math.MG
paper · pdf · doi:10.48550/arxiv.2005.12025
11 pages, 9 additional files (program sources and scripts); v2: precised wording, one minor correction; v3: extensions and minor corrections of article and GAP script; v4: few minor corrections; v5: many changes
openalex publication_date 2020/05/25 · arxiv created 2021/06/26 · arxiv updated 2021/06/29 · openalex created_date 2021/07/05 · openalex updated_date 2026/07/28
In 2013 Andriy V. Bondarenko showed how to construct a two-distance counterexample to Borsuk's conjecture from any strongly regular graph whose vertex set is not the union of at most f+1 cliques (sets of pairwise adjacent vertices) where f is the multiplicity of the second-largest eigenvalue of its adjacency matrix. He applied that construction to those two graphs that he had been able to prove to fulfill the condition: From the G2(4) graph (on 416 vertices) he got a 65-dimensional two-distance counterexample. From the Fi23 graph (on 31671 vertices) he got a 782-dimensional one and, by considering certain induced subgraphs, counterexamples in dimensions 781, 780 and 779. This article presents two other strongly regular graphs fulfilling the condition, on 28431 and on 2401, resp., vertices. It gives dedicated counterexamples in dimensions from 781 down to 764 derived from the bigger graph (that turned out to be an induced subgraph of the Fi23 graph) and a 240-dimensional counterexample derived from the smaller graph. Several contained propositions rely on the results of (often extensive) computations, mainly within the computer algebra system GAP. The source package contains (almost) all used source files.