Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 269.05111
Autor: Sos, V.T.; Erdös, Paul; Brown, William G.
Title: On the existence of triangulated spheres in 3-graphs, and related problems. (In English)
Source: Period. Math. Hung. 3, 221-228 (1973).
Review: 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 c1 and c2 such that every 3-graph on n vertices having c2n3/2 edges or more contains a double pyramid; but that there exists a 3-graph on n vertices having c1n3/2 edges containing no triangulation of the sphere. Also, we discuss several related results.
Classif.: * 05C10 Topological graph theory
57M20 Two-dimensional complexes
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag