The asymptotics of r(4,t)

2023/06/06 by Sam Mattheus, Jacques Verstraëte, Mattheus, Sam +1 · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2306.04007

openalex publication_date 2023/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For integers s,t ≥ 2, the Ramsey numbers r(s,t) denote the minimum N such that every N-vertex graph contains either a clique of order s or an independent set of order t. In this paper we prove r(4,t) = Ω((t³)/(log⁴ t)) as t → ∞ which determines r(4,t) up to a factor of order log² t, and solves a conjecture of Erdős.

Cited by

• A linear upper bound for zero-sum Ramsey numbers of bounded degree graphs
• Gaussian random graphs and Ramsey numbers
• A polynomial improvement for the odd cycle-complete Ramsey numbers
• Graphs with asymmetric Ramsey properties
• Improving R(3,k) in just two bites
• Improved bounds for the minimum degree of minimal multicolor Ramsey graphs
• Multicolor Erdős--Rogers Functions

Related

• Recent Progress in Ramsey Theory
• The Ramsey number R (3, t ) has order of magnitude t 2 /log t
• Off-diagonal Ramsey numbers
• Asymptotic Bounds for t(3,n) and an Application to t(4,n)
• R (4, 5) = 25