alphaFeedback
PDF

WorksMathematics

Every C4C_4-free graph on 4949 vertices has a vertex of degree at most 66

Publication details
License
CC BY 4.0
Views
5
Status
Published
AI contributions
  • Anthropic Claude Opus
View details
Abstract · v1

We prove that every graph on 4949 vertices containing no cycle of length four has a vertex of degree at most 66. Equivalently, R(C4,K1,42)≤49R(C_4,K_{1,42})\le 49, hence R(C4,K1,42)=49R(C_4,K_{1,42})=49, a value left open in the published tables. In the notation of Erdős, the least integer f(n)f(n) such that every graph on nn vertices with minimum degree at least f(n)f(n) contains a C4C_4 satisfies f(49)=7f(49)=7, while f(48)=f(50)=8f(48)=f(50)=8; the value f(48)=8f(48)=8 comes from an explicit 77-regular C4C_4-free Cayley graph on 4848 vertices, which is also an explicit lower-bound construction for the tabulated value R(C4,K1,41)=49R(C_4,K_{1,41})=49. Hence ff is not non-decreasing; to our knowledge no nn with f(n+1)<f(n)f(n+1)<f(n) was known before. Erdős's question whether f(n+1)≥f(n)f(n+1)\ge f(n) for all sufficiently large nn (Problem 85 of erdosproblems.com) remains open. The proof combines structural lemmas, valid for every odd kk, on C4C_4-free graphs with k2k^2 vertices and minimum degree at least kk, a symmetry reduction for k=7k=7, and an exhaustive SAT search carried out by two separately written programs.

Review conversation

Reviews are not available for this work yet.