Structural Obstruction at K43 Evidence That R(5, 5) = 43 SAT Constraint Propagation, Exhaustive Enumeration, and the Distributed Obstruction Hypothesis

Read full text Summarise with VIRAT
Authors: Bryan Daugherty, Gregory Ward, Shawn Ryan
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We present exact combinatorial evidence that the diagonal Ramsey number R(5,5)=43R(5,5) = 43R(5,5) = 43 , complementing our companion paper that established the lower bound R(5,5)≥43R(5,5) \geq 43R(5,5) \geq 43 .Starting from a two-coloring of K43K_{43}K_{43} with exactly two monochromatic K5K_5K_5 subgraphs, we prove four structural results that demonstrate it is impossible to eliminate both violations: Exhaustive enumeration of all 214=16,3842^{14} = 16,3842^{14} = 16,384 assignments to the 14 violating edges shows that the minimum violation count is 2, with no solutions achieving zero violations. Systematic search over all 7,433 edge pairs confirms that no double edge flip reduces the violation count. All (143)+(144)=1,365\binom{14}{3} + \binom{14}{4} = 1,365\binom{14}{3} + \binom{14}{4} = 1,365 multi-flips on violating edges return to exactly two violations after greedy local search. We encode the full Ramsey constraints as 1,925,196 CNF clauses. After fixing the 889 non-violating edges, Boolean constraint propagation (BCP) derives a contradiction, proving that the “good” edges are incompatible with a zero-violation coloring. We introduce the Distributed Obstruction Hypothesis: the two-violation floor on K43K_{43}K_{43} is not a local defect, but a global property of the constraint structure, where edges far from the violations contribute to the obstruction through long-range constraint propagation.Independent two-violation colorings generated from different Galois fields exhibit the same structural pattern (two monochromatic K5K_5K_5 sharing four vertices), providing cross-algebraic confirmation of the result.

Fields of Study & Subjects

Limits and Structures in Graph Theory Advanced Combinatorial Mathematics Advanced Graph Theory Research

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
26 March 2026
Language
EN
Document type
Preprint