Locally bipartite subgraphs via multicolor Ramsey numbers
Abstract
A famous conjecture of Erdős and Hajnal (1969) states that for every integer g≥ 4 there is a smallest function fg:ℕ→ℕ such that every graph of chromatic number at least fg(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 f4(k) bounded by a tower of height Θ(k2log 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≥ 5 there is a function hg:ℕ→ℕ growing as a power tower of height (g−3)/2 such that every graph of chromatic number at least hg(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 f4(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∈ℕ, every graph G with sufficiently large f(G) contains a subgraph G' of odd-girth at least g with f(G')≥ k. The key Ramsey-theoretic ingredient is a new lower bound on Ramsey numbers of odd cycles. For p≥ 1, let 𝒪p={C3,C5,…,C2p+1}. We show that Rk(𝒪p)≥(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.
Related
BibTeX
@misc{steiner2026locally,
title = {{Locally bipartite subgraphs via multicolor Ramsey numbers}},
author = {Raphael Steiner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.02522},
eprint = {2608.02522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.02522},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Locally bipartite subgraphs via multicolor Ramsey numbers
AU - Raphael Steiner
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.02522
UR - https://arxiv.org/abs/2608.02522
AB - A famous conjecture of Erdős and Hajnal (1969) states that for every integer g≥ 4 there is a smallest function f_g:ℕ→ℕ 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 Θ(k^2log 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≥ 5 there is a function h_g:ℕ→ℕ growing as a power tower of height (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∈ℕ, every graph G with sufficiently large f(G) contains a subgraph G' of odd-girth at least g with f(G')≥ k. The key Ramsey-theoretic ingredient is a new lower bound on Ramsey numbers of odd cycles. For p≥ 1, let 𝒪_p={C_3,C_5,…,C_2p+1}. We show that R_k(𝒪_p)≥(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.
ER -