The maximum number of triangles in $K_{1,s,t}$-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916899071197184 |
|---|---|
| author | Calbet, Asier Goenka, Ritesh |
| author_facet | Calbet, Asier Goenka, Ritesh |
| contents | We consider the following generalized Turán problem: For $2 \le s \le t$, what is the maximum number of triangles in a $K_{1,s,t}$-free graph on $n$ vertices? The previously best known lower and upper bounds are $Ω(n^2)$ and $o(n^{3-1/s})$, respectively. To the best of our knowledge, all known proofs of the upper bound use the triangle removal lemma. We give a new elementary proof that avoids the use of the triangle removal lemma and improves the upper bound to $O\left(n^{3-1/s}(\log n)^{-1+1/s}\right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The maximum number of triangles in $K_{1,s,t}$-free graphs Calbet, Asier Goenka, Ritesh Combinatorics 05C35 We consider the following generalized Turán problem: For $2 \le s \le t$, what is the maximum number of triangles in a $K_{1,s,t}$-free graph on $n$ vertices? The previously best known lower and upper bounds are $Ω(n^2)$ and $o(n^{3-1/s})$, respectively. To the best of our knowledge, all known proofs of the upper bound use the triangle removal lemma. We give a new elementary proof that avoids the use of the triangle removal lemma and improves the upper bound to $O\left(n^{3-1/s}(\log n)^{-1+1/s}\right)$. |
| title | The maximum number of triangles in $K_{1,s,t}$-free graphs |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2508.10611 |