Turán problems for simplicial complexes

Abstract

An abstract simplicial complex $\mathbf{F}$ is a non-uniform hypergraph without isolated vertices, whose edge set is closed under taking subsets. The extremal number $\mathrm{ex}(n,\mathbf{F})$ is defined as the maximum number of edges in an $n$-vertex $\mathbf{F}$-free simplicial complex. Although Turán-type problems for simplicial complexes have long appeared in extremal set theory, a systematic study of $\mathrm{ex}(n,\mathbf{F})$ was initiated only recently by Conlon, Piga, and Schülke. In contrast to uniform hypergraphs, even the order of magnitude of $\mathrm{ex}(n,\mathbf{F})$ remains unknown for most simplicial complexes. In this paper, we present a general framework for estimating $\mathrm{ex}(n,\mathbf{F})$ via generalised Turán numbers of associated hypergraphs. Using this approach, we determine the asymptotic behaviour, and in some cases the exact value, of $\mathrm{ex}(n,\mathbf{F})$ for broad classes of simplicial complexes, extending a result of Conlon, Piga, and Schülke. We also exhibit simplicial complexes whose extremal numbers are not governed by the corresponding generalised Turán numbers, and determine their extremal numbers asymptotically. In addition, we study how the extremal number changes when a new edge is added to the forbidden simplicial complex, and obtain a tight bound for this behaviour.

18 pages, comments are welcome