Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.19773 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916804462379008 |
|---|---|
| author | Chen, Yihan He, Jialin Lo, Allan Luo, Cong Ma, Jie Zhao, Yi |
| author_facet | Chen, Yihan He, Jialin Lo, Allan Luo, Cong Ma, Jie Zhao, Yi |
| contents | In 1975 Bollobás, Erdős, and Szemerédi asked what minimum degree guarantees an octahedral subgraph $K_3(2)$ in any tripartite graph $G$ with $n$ vertices in each vertex class. We show that $δ(G)\geq n+2n^{\frac{5}{6}}$ suffices thus improving the bound $n+(1+o(1))n^{\frac{11}{12}}$ of Bhalkikar and Zhao obtained by following their approach. Bollobás, Erdős, and Szemerédi conjectured that $n+cn^{\frac{1}{2}}$ suffices and there are many $K_3(2)$-free tripartite graphs $G$ with $δ(G)\geq n+cn^{\frac{1}{2}}$. We confirm this conjecture under the additional assumption that every vertex in $G$ is adjacent to at least $(1/5+\varepsilon)n$ vertices in any other vertex class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree Chen, Yihan He, Jialin Lo, Allan Luo, Cong Ma, Jie Zhao, Yi Combinatorics In 1975 Bollobás, Erdős, and Szemerédi asked what minimum degree guarantees an octahedral subgraph $K_3(2)$ in any tripartite graph $G$ with $n$ vertices in each vertex class. We show that $δ(G)\geq n+2n^{\frac{5}{6}}$ suffices thus improving the bound $n+(1+o(1))n^{\frac{11}{12}}$ of Bhalkikar and Zhao obtained by following their approach. Bollobás, Erdős, and Szemerédi conjectured that $n+cn^{\frac{1}{2}}$ suffices and there are many $K_3(2)$-free tripartite graphs $G$ with $δ(G)\geq n+cn^{\frac{1}{2}}$. We confirm this conjecture under the additional assumption that every vertex in $G$ is adjacent to at least $(1/5+\varepsilon)n$ vertices in any other vertex class. |
| title | Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.19773 |