Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2410.04744 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917841165352960 |
|---|---|
| author | Chao, Ting-Wei Dong, Zichao Shen, Zijun Yang, Ningyuan |
| author_facet | Chao, Ting-Wei Dong, Zichao Shen, Zijun Yang, Ningyuan |
| contents | Suppose $0 < p \le \infty$. For a simple graph $G$ with a vertex-degree sequence $d_1, \dots, d_n$ satisfying $(d_1^p + \dots + d_n^p)^{1/p} \le C$, we prove asymptotically sharp upper bounds on the number of $t$-cliques in $G$. This result bridges the $p = 1$ case, which is the notable Kruskal--Katona theorem, and the $p = \infty$ case, known as the Gan--Loh--Sudakov conjecture, and resolved by Chase. In particular, we demonstrate that the extremal construction exhibits a dichotomy between a single clique and multiple cliques at $p_0 = t - 1$. Our proof employs the entropy method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Many cliques with small degree powers Chao, Ting-Wei Dong, Zichao Shen, Zijun Yang, Ningyuan Combinatorics Suppose $0 < p \le \infty$. For a simple graph $G$ with a vertex-degree sequence $d_1, \dots, d_n$ satisfying $(d_1^p + \dots + d_n^p)^{1/p} \le C$, we prove asymptotically sharp upper bounds on the number of $t$-cliques in $G$. This result bridges the $p = 1$ case, which is the notable Kruskal--Katona theorem, and the $p = \infty$ case, known as the Gan--Loh--Sudakov conjecture, and resolved by Chase. In particular, we demonstrate that the extremal construction exhibits a dichotomy between a single clique and multiple cliques at $p_0 = t - 1$. Our proof employs the entropy method. |
| title | Many cliques with small degree powers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.04744 |