On the solution to the Erdős–Hajnal problem on high-girth high-chromatic subgraphs

27^th October 2026, 13:00 Ashton Lecture Theatre
Tung Nguyen
University of Oxford

Abstract

A well-known problem of Erdős and Hajnal from the 1960s asks whether every graph with huge chromatic number contains a subgraph with large girth and large chromatic number. Very recently, Kohlmeyer and Kruer, by means of AI tools, provided a strong negative solution to this problem. The talk aims to explain the construction method and relate it to relevant literature. Joint work with Bartosz Walczak.

Biography

Tung Nguyen is currently working at the University of Oxford as a Titchmarsh Research Fellow at the Mathematical Institute and a Postdoctoral Research Fellow at Christ Church. He obtained a PhD from Princeton University where he was supervised by Paul Seymour. Before Princeton, he earned a Bachelor of Science from KAIST. He is interested in discrete mathematics, mostly structural and extremal problems in graph theory.

Additional Materials

• https://arxiv.org/pdf/2609.40192