On the existence of triangulated spheres in 3-graphs, and related problems (Q2563170)

The problem described in the title represents an analogue of the well known property of graphs that any graph on \(n\) vertices and having at least \(n\) edges contains a polygon. That result could be restated, in topological terms, as saying that any simplicial 1-complex with at least as many 1-simplexes as 0-simplexes must contain a triangulation of the 1-sphere. In Theorem 3 we shall determine asymptotically the maximum number of 2-simplexes a simplicial 2-complex may contain without containing a subcomplex which is a triangulation of the 2-sphere. More precisely, we shall prove that there exist constants \(c_1\) and \(c_2\) such that every 3-graph on \(n\) vertices having \(c_2n^{3/2}\) edges or more contains a double pyramid; but that there exists a 3-graph on \(n\) vertices having \(c_1n^{3/2}\) edges containing no triangulation of the sphere. Also, we discuss several related results.