Jump To中央區塊/Main Content :::
:::

Seminars

Seminar on Combinatorics

Chromatic threshold via combinatorial convexity, and beyond

2025/06/09 (Mon.) 15:30~16:30
  • Date : 2025/06/09 (Mon.) 15:30~16:30
  • Location : Seminar Room 617, Institute of Mathematics (NTU Campus)
  • Speaker : Jozef Skokan (London School of Economics and Political Science)
  • Organizer : Bruce Reed (AS)
  • Abstract : Determining the chromatic number of a graph is an important but difficult problem. A natural variety of this problem is to find meaningful upper bounds for the chromatic number of certain families of graphs. One type of graph family that received considerable attention is the family of graphs G which do not contain a given graph H as subgraph (H-free graphs). Erdős showed that the chromatic number of H-free graphs G can be arbitrarily large (when H is not a forest). In 1973 Erdős and Simonovits asked what happens if we additionally impose a minimum degree condition for G. This initiated the study of the so-called chromatic threshold of a graph H and opened several important directions of research.
    In the talk I will provide all necessary background and discuss the relations between the chromatic threshold and other important concepts such as the chromatic profile and the homomorphism threshold. I will also talk about recent work with Liu, Shangguan and Xu in which we establish a novel connection between the chromatic threshold problem in extremal combinatorics and the celebrated (p,q)-theorem in discrete geometry.
:::