Locally bipartite subgraphs via multicolor Ramsey numbers

Abstract

A famous conjecture of Erdős and Hajnal (1969) states that for every integer $g\ge 4$ there is a smallest function $f_g:\mathbb{N}\to \mathbb{N}$ such that every graph of chromatic number at least $f_g(k)$ contains a subgraph of chromatic number $k$ and girth at least $g$. So far, this has only been proved for $g=4$ by Rödl (1977), with $f_4(k)$ bounded by a tower of height $\Theta (k^2\log k)$. We exhibit a surprising connection between finding high-chromatic subgraphs of large odd-girth (avoiding short odd cycles) and lower-bounding multicolor Ramsey numbers of odd cycles. Using this connection, we prove that for every odd $g\ge 5$ there is a function $h_g:\mathbb{N}\to \mathbb{N}$ growing as a power tower of height $\frac{g-3}{2}$ such that every graph of chromatic number at least $h_g(k)$ contains a subgraph of chromatic number at least $k$ and odd-girth at least $g$. This proves a conjecture of Mohar and Wu (2018), addresses a question of Erdős and Hajnal (1975), and for $g=5$ improves Rödl's bound on $f_4(k)$ to a single-exponential. We extend this to a much more general meta-theorem which applies to many graph parameters: if $f$ is the fractional chromatic number, the Hall ratio, or the strict vector chromatic number (Lovász-Theta-function of the complement), then for every $k,g\in \mathbb{N}$, every graph $G$ with sufficiently large $f(G)$ contains a subgraph $G^{\prime }$ of odd-girth at least $g$ with $f(G^{\prime })\ge k$. The key Ramsey-theoretic ingredient is a new lower bound on Ramsey numbers of odd cycles. For $p\ge 1$, let ${\mathcal{O}}_p=\{C_3,C_5,\dots ,C_{2p+1}\}$. We show that $R_k({\mathcal{O}}_p)\ge ({\log }^{(p-1)}k{)}^{k/3-o(k)}$ for every fixed $p$, where ${\log }^{(p-1)}$ denotes the $(p-1)$-fold iterated logarithm. This yields the first superexponential lower bound on multicolor Ramsey numbers of fixed odd cycles, and extends the recent breakthrough by OpenAI for triangles.

28 pages, supersedes v1s of arXiv:2608.02522 and arXiv:2608.02537 and adds several new results