Simplicial homeomorphs and trace-bounded hypergraphs

Simplicial homeomorphs and trace-bounded hypergraphs, Discrete Analysis 2022:6, 12 pp.

A well-known result of Mader from 1967 states that for every finite graph $H$ there exists a positive integer $d$ such that every graph of average degree at least $d$ contains a subdivision of $H$ – that is, a copy of $H$ where each edge may be replaced by a path (and the paths do not intersect). Of course, this follows from the special case where $H$ is a complete graph. The result was motivated by connections with a famous conjecture of Hadwiger, which states that if $G$ does not contain the complete graph $K_t$ as a minor, then the chromatic number of $G$ is less than $t$. Since no planar graph contains a $K_5$ minor, this is a generalization of the four-colour theorem.

This paper concerns generalizations of Mader’s theorem to $k$-dimensional simplicial complexes. It has been known for some time that for any such complex $K$ there exist $\lambda>0$ and $C$ such that every $k$-dimensional simplicial complex on $n$ vertices with at least $Cn^{k+1-\lambda})$ faces of dimension $k$ contains a complex homeomorphic to $K$. Note that each face of dimension $k$ is determined by $k+1$ vertices, so the trivial upper bound for the number of faces is $\binom n{k+1}$, and therefore this result is saying that the trivial upper bound can be beaten by a power of $n$.

Given a $k$-dimensional complex $K$, let us define $\lambda_K$ to be the supremum over all $\lambda$ such that every $k$-dimensional complex that contains no homeomorphic copy of $K$ has $O(n^{k+1-\lambda})$ faces of dimension $k$.

When $k=1$, Mader’s theorem tells us that $\lambda_K=1$ for every $K$. (In this case, $K$ is a graph.) In particular, $\lambda_K$ is independent of $K$ that one is trying to find. It is therefore natural to ask whether the same is true in higher dimensions. That is, is it true that for each $k$ there exists $\lambda_k>0$ such that $\lambda_K\geq\lambda_k$ for every $k$-dimensional complex $K$?

Before this paper it was shown by Peter Keevash, Alexander Scott and the first two authors of this paper that $\lambda_2$ exists and is at least $1/5$. The conjectured best possible value for $\lambda_2$ is 1/2, but this is still an open problem.

The main result of this paper is a proof that $\lambda_k\geq k^{-2k^2}$ for every $k$, so there is indeed a uniform bound for every fixed $k$. However, determining the correct dependence on $k$ (even asymptotically) remains a challenging open problem. It is probably possible to prove at least that $\lambda_k\to 0$, though this does not yet seem to have been done formally.

The proof of the result goes via a Turán-type statement. The basic idea is to take a complex $K$ and construct its “canonical subdivision”. This is the combinatorial version of the natural geometric subdivision one obtains by taking the centres of all the faces of every dimension as the vertices and joining $k+1$ of them whenever they form the centres of the faces of a $k$-dimensional “flag” (that is, sequence of faces $F_0\subset F_1\subset\dots\subset F_k$ where $F_i$ has dimension $i$).

One can check easily that the $k$-dimensional faces of a canonical subdivision $\tilde K$ of $K$ form a $(k+1)$-partite $(k+1)$-uniform hypergraph (the vertex sets corresponding to the dimensions of the faces of $K$ of which the vertices of $\tilde K$ are the centres). Furthermore, this hypergraph has the following property. If $i>0$ and we take a vertex $v_i$ from the $i$th vertex class $V_i$, then the number of ways of choosing a vertices $v_0,v_1,\dots,v_{i-1}$ from the vertex classes $V_0,V_1,\dots,V_{i-1}$ in such a way that $v_0,v_1,\dots,v_i$ is contained in one of the faces of the hypergraph is at most $(i+1)!$, since the $i$-dimensional face that contains $v_i$ has $i+1$ faces of dimension $i-1$. (For instance, a tetrahedron is 3-dimensional and has four 2-dimensional faces. Note that the authors denote the vertex sets by $V_1,\dots,V_{k+1}$ instead of $V_0,V_1,\dots,V_k$.) In particular, this number is at most $(k+1)!$. In the terminology of the paper, this means that the hypergraph is $(k+1)!$-trace bounded.

It therefore suffices to prove the Turán-type result that every $(k+1)$-uniform hypergraph that does not contain a subhypergraph isomorphic to some fixed $d$-trace bounded hypergraph has $O(n^{k+1-\lambda_k})$ hyperedges. Note that since a trace-bounded hypergraph is $(k+1)$-partite, it is reasonable to expect a power improvement on the trivial bound of $\binom n{k+1}$, just as in the graph case a graph that does not contain a fixed bipartite graph has $O(n^{2-\epsilon})$ edges for some positive $\epsilon$ (though with the difference that we are talking about an arbitrary member of a class of hypergraphs rather than a single hypergraph and we want a power that depends just on $d$).

The authors show that for every $r$ and $d$ there exists $\alpha>0$ such that if $H$ is a $d$-trace bounded $r$-partite $r$-uniform hypergraph, then for sufficiently large $n$, every $r$-uniform hypergraph that does not contain $H$ has at most $n^{r-\alpha}$ hyperedges. The bound they obtain for $\alpha$ is $(5rd)^{-(r-1)}$. This result generalizes an earlier result of Conlon, Fox and Sudakov, which uses a stronger hypothesis on $H$ than trace boundedness (and obtains a slightly better bound). For the purposes of this paper, it is essential that trace boundedness is sufficient.

Our first main result is the following basic fact about simplicial complexes: for each $k \in \N$, there exists an exponent $\lambda_k \ge k^{-2k^2}$ such that for any $k$-complex $\SS$, every $k$-complex on $n \ge n_0(\SS)$ vertices with at least $n^{k+1 - \lambda_k}$ facets contains a homeomorphic copy of $\SS$. The existence of these exponents was suggested by Linial in 2006 but 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 established by Keevash–Long–Narayanan–Scott in 2020. We deduce this geometric theorem 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 \dots \cup V_i$. Our second main result is the following fact about degenerate trace-bounded hypergraphs: for all $r \ge 2$ and $d\in\N$, there exists an exponent $\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 theorem of Conlon–Fox–Sudakov from 2009 who showed that a similar result 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).