Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |