Hyunwoo Lee (이현우), A super-exponential lower bound construction for the multicolor triangle Ramsey problem discovered by OpenAI

Let $R_k(3)$ denote the smallest integer $N$ such that every $k$-edge-coloring of the complete graph $K_N$ contains a monochromatic triangle. A simple inductive argument gives the classical factorial upper bound $R_k(3)\leq k!=k^{O(k)}$, whereas the best previously known lower bound was only exponential in $k$, namely, $R_k(3)\geq 2^{\Omega(k)}$. It was a longstanding open problem of Erd\H{o}s whether $R_k(3)$ grows exponentially or super-exponentially in $k$.

On August 1, 2026, OpenAI, using an internal AI model, discovered a construction establishing the super-exponential lower bound $R_k(3)\geq k^{\Omega(k)}$, thereby resolving Erdős’ longstanding question. In this talk, I will explain the construction and discuss possible directions for further research, some of which may already have been explored by other researchers.