• This event has passed.

# Debsoumya Chakraborti, Some classical problems in graph saturation

## Tuesday, March 9, 2021 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$, but the addition of any edge creates a copy of $F$. The function $\operatorname{sat}(n,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph.

In the first half of the talk, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964), which determined the value of $\operatorname{sat}(n,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices, confirming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We further establish a corresponding stability result.

In the second half, we will focus on a central conjecture in graph saturation made by Tuza (1986), which states that for every graph $F$, the limit $\lim_{n \rightarrow \infty} \frac{\operatorname{sat}(n,F)}{n}$ exists. We make progress in the negative direction of this conjecture.

This talk will be based on a joint work with Po-Shen Loh.

## Details

Date:
Tuesday, March 9, 2021
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Room B232
IBS (기초과학연구원)

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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