컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0261 |
|---|---|
| 분류(Section) | Contributed Talk |
| 분과(Session) | (DM) Discrete Mathematics (DM) |
| 발표시간(Time) | 19th-A-10:20 -- 10:40 |
| 영문제목 (Title(Eng.)) |
Generalized Ramsey-Tur\'an density for cliques |
| 저자(Author(s)) |
Jun Gao1, Suyun Jiang2, Hong Liu1, Maya Sankar3 IBS-ECOPRO1, Jianghan University / IBS-ECOPRO2, Stanford University3 |
| 초록본문(Abstract) | We study the generalized Ramsey--Tur\'an function $\mathrm{RT}(n,K_s,K_t,o(n))$, which is the maximum possible number of copies of $K_s$ in an $n$-vertex $K_t$-free graph with independence number $o(n)$. The case when $s=2$ was settled by Erd{\H{o}}s, S{\'o}s, Bollob{\'a}s, Hajnal, and Szemer\'{e}di in the 1980s. We combinatorially resolve the general case for all $s\ge 3$, showing that the (asymptotic) extremal graphs for this problem have simple (bounded) structures. In particular, it implies that the extremal structures follow a periodic pattern when $t$ is much larger than $s$. Our results disprove a conjecture of Balogh, Liu, and Sharifzadeh and show that a relaxed version does hold. |
| 분류기호 (MSC number(s)) |
05C35 |
| 키워드(Keyword(s)) | Generalized Ramsey-Tur\'an function, cliques, independence number |
| 강연 형태 (Language of Session (Talk)) |
English |