Speaker: Debsoumya Chakraborti (University of Warwick)
Host: Niranjan Balachandran
Title: Results in Extremal Combinatorics
Time, day and date: 4:30:00 PM, Tuesday, March 11
Venue: Online talk only (https://tel.meet/hqy-hswu-jho?hs=5)
Abstract: A key objective of extremal combinatorics is to investigate various conditions on combinatorial structures (such as graphs, set systems, and simplicial complexes) that guarantee the existence of specific substructures. In this talk, I will concentrate on two central topics within this theme of extremal combinatorics:
1. Tur\'an problems and
2. Embedding spanning subgraphs.
I will begin with a gentle introduction to the first topic, highlighting a few fundamental questions in the field. In this context, I will introduce the Erd\H{o}s--Sauer problem that asks for the maximum possible number of edges that an $n$-vertex graph can have without containing an $r$-regular subgraph. The problem
had seen no progress since Pyber's work in 1985 until recently when Janzer and Sudakov resolved this problem up to a multiplicative constant depending on $r$. We resolve the Erd\H{o}s--Sauer problem up to an absolute constant factor (not depending on $r$) as follows. There exists an absolute constant $C$ such that for
each positive integer $r$, every $n$-vertex graph with at least $Cr^2n\log \log n$ edges contain an $r$-regular subgraph. Moreover, we show this to be tight up to the value of $C$ for all $r\geq 3$ and $n\geq n(r)$.
Next, I will transition to the second topic, starting with two classical results on embedding the Hamilton cycle (a cycle that visits every vertex exactly once):
(i) Dirac's theorem, which establishes a sharp minimum degree condition on a graph to ensure the existence of a Hamilton cycle, and
(ii) Theorems on various orientations of Hamilton cycles in tournaments.
In the last decade, extending subgraph embedding problems to the setting of transversals over a collection of graphs has sparked significant interest in the literature. I will introduce this concept and then discuss the transversal generalizations of (i) and (ii). Some of these include results from my own work in various papers.