The Zarankiewicz problem on tripartite graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916507617853440 |
|---|---|
| author | Di Braccio, Francesco Illingworth, Freddie |
| author_facet | Di Braccio, Francesco Illingworth, Freddie |
| contents | In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest $τ$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + τ$ must contain $K_{t, t, t}$, conjecturing that $τ= \mathcal{O}(n^{1/2})$ for $t = 2$. We prove that $τ= \mathcal{O}(n^{1 - 1/t})$ which confirms their conjecture and is best possible assuming the widely believed conjecture that $\operatorname{ex}(n, K_{t, t}) = Θ(n^{2 - 1/t})$. Our proof uses a density increment argument.
We also construct an infinite family of extremal graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03505 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Zarankiewicz problem on tripartite graphs Di Braccio, Francesco Illingworth, Freddie Combinatorics 05C35 In 1975, Bollobás, Erdős, and Szemerédi asked for the smallest $τ$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + τ$ must contain $K_{t, t, t}$, conjecturing that $τ= \mathcal{O}(n^{1/2})$ for $t = 2$. We prove that $τ= \mathcal{O}(n^{1 - 1/t})$ which confirms their conjecture and is best possible assuming the widely believed conjecture that $\operatorname{ex}(n, K_{t, t}) = Θ(n^{2 - 1/t})$. Our proof uses a density increment argument. We also construct an infinite family of extremal graphs. |
| title | The Zarankiewicz problem on tripartite graphs |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2412.03505 |