Supersaturation beyond color-critical graphs

时   间：  2023-04-16 16:00 — 17:00

A fundamental theorem of Rademacher from 1941 led to the study of supersaturation problems of graphs, which aim to count the minimum number of copies of a given graph $F$ among all graphs with $n$ vertices and $m$ edges. This is closely related to a central concept in Extremal Graph Theory -- the Tur\'an number of $F$, which denotes the maximum number of edges in an $n$-vertex graph which does not contain $F$ as a subgraph. Famous results of Erd\H{o}s, and Lov\'asz and Simonovits determine the minimum number of cliques $K_r$ in graphs whose number of edges exceed the Tur\'an number of $K_r$. Subsequent works of Mubayi as well as Pikhurko and Yilma extend these classical results from cliques to color-critical graphs, a rich family playing important roles in extremal problems. In this talk, we will discuss supersaturation problems beyond color-critical graphs and investigate natural enumerative parameters.

Our results go beyond the previous results and show that supersaturation problems for general graphs can be rather complicate. Among others, we disprove a conjecture of Mubayi. Joint work with Long-Tu Yuan.