pith. sign in

arxiv: 2507.09434 · v1 · pith:JHBLZ4A2new · submitted 2025-07-13 · 🧮 math.CO

Polynomial-to-exponential transition in 3-uniform Ramsey numbers

classification 🧮 math.CO
keywords problemuniformblueconjectureedgeedgeshypergraphnumber
0
0 comments X
read the original abstract

Let $r_k(s, e; t)$ denote the smallest $N$ such that any red/blue edge coloring of the complete $k$-uniform hypergraph on $N$ vertices contains either $e$ red edges among some $s$ vertices, or a blue clique of size $t$. Erd\H os and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that for fixed $s>k\geq 3$, there is a well defined value $h_k(s)$ such that $r_k(s, h_k(s)-1; t)$ is polynomial in $t$, while $r_k(s, h_k(s); t)$ is exponential in a power of $t$. Erd\H os later offered \$500 for a proof. Conlon, Fox, and Sudakov proved the conjecture for $k=3$ and $3$-adically special values of $s$, and Mubayi and Razborov proved it for $s > k \geq 4$. We prove the conjecture for $k=3$ and all $s$, settling all remaining cases of the problem. We do this by solving a novel Tur\'an-type problem: what is the maximum number of edges in an $n$-vertex $3$-uniform hypergraph in which all tight components are tripartite? We show that the balanced iterated blowup of an edge is an exact extremizer for this problem for all $n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.