Loading Events

« All Events

  • 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.


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


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


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.