Structural Obstruction at K43 Evidence That R(5, 5) = 43 SAT Constraint Propagation, Exhaustive Enumeration, and the Distributed Obstruction Hypothesis
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