Simplicial homeomorphs and trace-bounded hypergraphs

Abstract

Our first main result is a uniform bound, in every dimension $k\in \mathbb{N}$, on the topological Turán numbers of $k$-dimensional simplicial complexes: for each $k\in \mathbb{N}$, there is a ${\lambda }_k\ge k^{-2k^2}$ such that for any $k$-complex $\mathcal{S}$, every $k$-complex on $n\ge n_0(\mathcal{S})$ vertices with at least $n^{k+1-{\lambda }_k}$ facets contains a homeomorphic copy of $\mathcal{S}$. This was previously known only in dimensions one and two, both by highly dimension-specific arguments: the existence of ${\lambda }_1$ is a result of Mader from 1967, and the existence of ${\lambda }_2$ was suggested by Linial in 2006 and recently proved by Keevash-Long-Narayanan-Scott. We deduce this geometric fact from a purely combinatorial result about trace-bounded hypergraphs, where an $r$-partite $r$-graph $H$ with partite classes $V_1,V_2,\dots ,V_r$ is said to be $d$-trace-bounded if for each $2\le i\le r$, all the vertices of $V_i$ have degree at most $d$ in the trace of $H$ on $V_1\cup V_2\cup \cdots \cup V_i$. Our second main result is the following estimate for the Turán numbers of degenerate trace-bounded hypergraphs: for all $r\ge 2$ and $d\in \mathbb{N}$, there is an ${\alpha }_{r,d}\ge (5rd{)}^{1-r}$ such that for any $d$-trace-bounded $r$-partite $r$-graph $H$, every $r$-graph on $n\ge n_0(H)$ vertices with at least $n^{r-{\alpha }_{r,d}}$ edges contains a copy of $H$. This strengthens a result of Conlon-Fox-Sudakov from 2009 who showed that such a bound holds for $r$-partite $r$-graphs $H$ satisfying the stronger hypothesis that the vertex-degrees in all but one of its partite classes are bounded (in $H$, as opposed to in its traces).

12 pages

Cited by in corpus (1)

• Robust (rainbow) subdivisions and simplicial cycles