Turán number of complete multipartite graphs in multipartite graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917991168344064 |
|---|---|
| author | Han, Jie Zhao, Yi |
| author_facet | Han, Jie Zhao, Yi |
| contents | In this paper we study a multi-partite version of the Erdős--Stone theorem. Given integers $r<k$ and $t\ge 1$, let $\text{ex}_k(n, K_{r+1}(t))$ be the maximum number of edges of $K_{r+1}(t)$-free $k$-partite graphs with $n$ vertices in each part, where $K_{r+1}(t)$ is the complete $(r+1)$-partite graph with $t$ vertices in each part. We determine the exact value of $\text{ex}_k(n, K_{r+1}(t))$ for $t\le 3$, $r<k\le 2r$ and sufficiently large $n$. We also characterize all extremal graphs for $r, k$ such that $r$ divides $k$, analogous to a result of Erd\H os and Simonovits on forbidding $K_{r+1}(t)$ in general graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16561 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Turán number of complete multipartite graphs in multipartite graphs Han, Jie Zhao, Yi Combinatorics In this paper we study a multi-partite version of the Erdős--Stone theorem. Given integers $r<k$ and $t\ge 1$, let $\text{ex}_k(n, K_{r+1}(t))$ be the maximum number of edges of $K_{r+1}(t)$-free $k$-partite graphs with $n$ vertices in each part, where $K_{r+1}(t)$ is the complete $(r+1)$-partite graph with $t$ vertices in each part. We determine the exact value of $\text{ex}_k(n, K_{r+1}(t))$ for $t\le 3$, $r<k\le 2r$ and sufficiently large $n$. We also characterize all extremal graphs for $r, k$ such that $r$ divides $k$, analogous to a result of Erd\H os and Simonovits on forbidding $K_{r+1}(t)$ in general graphs. |
| title | Turán number of complete multipartite graphs in multipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.16561 |