BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
Locally bipartite subgraphs via multicolor Ramsey numbers
Locally bipartite subgraphs via multicolor Ramsey numbers
Speaker
Raphael Steiner
Time
Tuesday, October 13, 2026 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
In this talk I will present and explain some recent results of mine motivated by the fundamental conjecture of Erdös and Hajnal (1969) on the existence of high-girth high-chromatic subgraphs. Formally, their conjecture states 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$. So far, 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 superlinear 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.
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.
Speaker Intro
Raphael Steiner is an Assistant Professor in the mathematics department of ETH Zurich. Previously, he was an ETH Postdoctoral Fellow and then an SNSF Ambizione Fellow at ETH. He received his PhD in mathematics from the Technical University of Berlin in 2021. Raphael's research interests span across several topics of combinatorics and related areas.