## Jaehyeon Seo (서재현) gave a talk on the rainbow Turán problem for color-critical graphs at the Discrete Math Seminar

On January 18, 2022, Jaehyeon Seo (서재현) from KAIST gave a talk at the Discrete Math Seminar on the rainbow Turán problem for color-critical graphs. The title of his talk was “A rainbow Turán problem for color-critical graphs“.

## Jaehyeon Seo (서재현), A rainbow Turán problem for color-critical graphs

For given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a ‘colorful’ copy of $H$, i.e. a copy of $H$ containing at most one edge from each $G_i$?

Keevash, Saks, Sudakov, and Verstraëte defined $\operatorname{ex}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,\dots, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, one of the two natural constructions is always the extremal construction. Moreover, they conjectured the same holds for every color-critical graphs and proved it for $3$-color-critical graphs.

We prove their conjecture for $4$-color-critical graphs and for almost all $r$-color-critical graphs when $r > 4$. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of $k$. This is a joint work with Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee, and Hong Liu.

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209