Raphael Steiner (ETH), Locally bipartite subgraphs via multicolor Ramsey numbers, 28 Oct 2026

Special joint Kraków-Oxford seminar Speaker: Raphael Steiner (ETH) Title: Locally bipartite subgraphs via multicolor Ramsey numbers Abstract: In this talk I will present and explain some recent results motivated by the fundamental conjecture of Erdős and Hajnal (1969) on the existence of high-girth high-chromatic subgraphs. Formally, their conjecture was that for every positive integer g there is a (smallest) function f_g such that every graph of chromatic number at least f_g(k) has a subgraph of girth at least g and chromatic number at least k. This has only been proved for the smallest case g=4 by Rödl, whose proof yields a bound on f_4(k) which is a tower of height \Theta(k^2\log k). In this talk I will present a surprising connection between the problem of finding subgraphs of large odd girth and multicolor Ramsey numbers of odd cycles. Using this connection and at the same time extending the recent first superexponential lower bound on the multicolor Ramey numbers of triangles due to OpenAI to fixed odd cycles, we prove that for every odd g\ge 5 there exists 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 odd girth at least g and chromatic number at least k. This proves a conjecture of Mohar and Wu (2018), addresses a problem of Erdős and Hajnal (1975) and in the g=5 case reduces the tower-type bound for f_4(k) to a single exponential. We then present a much more general meta theorem, which establishes that for a rich family of graph parameters f, including the fractional chromatic number, the Hall ratio and the strict vector chromatic number (a.k.a. Lovász Theta function of the complement), every graph G with f(G) sufficiently large has a subgraph G' of large odd girth with f(G') still large. Along the way, I will also explain OpenAI's construction for the multicolor Ramsey lower bound for triangles. Comment: The conjecture of Erdős and Hajnal has recently been disproved using AI, but the first paper with this result was not put on arXiv and appeared on a problem-bounty website. Recently, Ngyuen and Walczak wrote the first readable exposition of this disproof. I will not present the disproof in my talk and just briefly mention it along the way.