Locally bipartite subgraphs via multicolor Ramsey numbers
演讲者
Raphael Steiner
时间
2026年10月13日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.
演讲者介绍
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.