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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page