A conditional lower bound for the Turán number of spheres
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_ | 1866908761868730368 |
|---|---|
| author | Newman, Andrew Pavelka, Marta |
| author_facet | Newman, Andrew Pavelka, Marta |
| contents | We consider the hypergraph Turán problem of determining $\mathrm{ex}(n, S^d)$, the maximum number of facets in a $d$-dimensional simplicial complex on $n$ vertices that does not contain a simplicial $d$-sphere (a homeomorph of $S^d$) as a subcomplex. We show that if there is an affirmative answer to a question of Gromov about sphere enumeration in high dimensions, then $\mathrm{ex}(n, S^d) \geq Ω(n^{d + 1 - (d + 1)/(2^{d + 1} - 2)})$. Furthermore, this lower bound holds unconditionally for 2-LC spheres, which includes all shellable spheres and therefore all polytopes. We also prove an upper bound on $\mathrm{ex}(n, S^d)$ of $O(n^{d + 1 - 1/2^{d - 1}})$ using a simple induction argument. We conjecture that the upper bound can be improved to match the conditional lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A conditional lower bound for the Turán number of spheres Newman, Andrew Pavelka, Marta Combinatorics Primary 05E45, Secondary 05C65, 05C35 We consider the hypergraph Turán problem of determining $\mathrm{ex}(n, S^d)$, the maximum number of facets in a $d$-dimensional simplicial complex on $n$ vertices that does not contain a simplicial $d$-sphere (a homeomorph of $S^d$) as a subcomplex. We show that if there is an affirmative answer to a question of Gromov about sphere enumeration in high dimensions, then $\mathrm{ex}(n, S^d) \geq Ω(n^{d + 1 - (d + 1)/(2^{d + 1} - 2)})$. Furthermore, this lower bound holds unconditionally for 2-LC spheres, which includes all shellable spheres and therefore all polytopes. We also prove an upper bound on $\mathrm{ex}(n, S^d)$ of $O(n^{d + 1 - 1/2^{d - 1}})$ using a simple induction argument. We conjecture that the upper bound can be improved to match the conditional lower bound. |
| title | A conditional lower bound for the Turán number of spheres |
| topic | Combinatorics Primary 05E45, Secondary 05C65, 05C35 |
| url | https://arxiv.org/abs/2403.05364 |