Let rₖ (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 os and Hajnal introduced the study of this Ramsey number in 1972 and conjectured that for fixed s>k 3, there is a well defined value hₖ (s) such that rₖ (s, hₖ (s) -1; t) is polynomial in t, while rₖ (s, hₖ (s) ; t) is exponential in a power of t. Erd 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 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án-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.
Building similarity graph...
Analyzing shared references across papers
Loading...
Ruben Ascoli
Xiaoyu He
Hung-Hsun Hans Yu
Building similarity graph...
Analyzing shared references across papers
Loading...
Ascoli et al. (Sun,) studied this question.
www.synapsesocial.com/papers/68de5da283cbc991d0a208a3 — DOI: https://doi.org/10.48550/arxiv.2507.09434