×

zbMATH — the first resource for mathematics

On the existence of triangulated spheres in 3-graphs, and related problems. (English) Zbl 0269.05111
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.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
57M20 Two-dimensional complexes (manifolds) (MSC2010)
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] W. G. Brown, On graphs that do not contain a Thomsen graph,Canad. Math. Bull. 9 (1966) 281–285. · Zbl 0178.27302
[2] P. Erdos andA. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc. 52 (1946), 1087–1091. · Zbl 0063.01277
[3] P. Erdos andT. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356. · Zbl 0090.39401
[4] P. Erdos, Extremal problems in graph theory,Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague, 1964, 29–36.
[5] P. Erdos, On extremal problems of graphs and generalized graphs,Israel J. Math. 2 (1964), 183–190. · Zbl 0129.39905
[6] P. Erdos, A. Rényi andV. T. Sós, On a problem of graph theory,Studia Sci. Math. Hungar. 1 (1966), 215–235.
[7] P. Erdos andM. Simonovits, A limit theorem in graph theory,Studia Sci. Math. Hungar. 1 (1966), 51–57.
[8] P. Erdos andM. Simonovits, Some extremal problems in graph theory,Combinatorial Theory and its Applications (Colloq. Math. J. Bolyai4), Amsterdam-London, 1970, 377–390.
[9] P. Erdos andD. J. Kleitman, On coloring graphs to maximize the proportion of multicolored k-edges,J. Combinatorial Theory 5 (1968) 164–169. · Zbl 0167.22302
[10] P. Erdos andV. T. Sós, Some remarks on Ramsey’s and Turán’s theorem,Combinatorial Theory and its Applications (Colloq. Math. J. Bolyai4), Amsterdam-London, 1970, 395–401.
[11] P. Erdos, On some extremal properties onr-graphs,Discrete Math. 1 (1971), 1–6. · Zbl 0211.27003
[12] M. K. Fort Jr. andG. A. Hedlund, Minimal coverings of pairs by triples,Pacific J. Math. 8 (1958) 709–719. · Zbl 0084.01401
[13] F. Harary,Graph Theory, Reading, Mass., 1969.
[14] Gy. Katona, T. Nemetz andM. Simonovits, Újabb bizonyítás a Turán-féle gráftételre és megjegyzések bizonyos általánosításaira,Mat. Lapok 15 (1964), 228–238.
[15] T. Kovári, V. T. Sós andP. Turán, On a problem of K. Zarankiewicz,Colloq. Math. 3 (1955), 50–57.
[16] G. Ringel, Extremal problems in the theory of graphs,Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague, 1964, 85–90.
[17] H. Ryser,Combinatorial Mathematics, New York, 1963. · Zbl 0112.24806
[18] M. Simonovits, Extremal graph problems with conditions,Combinatorial Theory and its Appl. (Colloq. Math. J. Bolyai4), Amsterdam-London, 1970, 999–1011.
[19] J. Singer, A theorem in finite projective geometry and some applications to number theory,Trans. Amer. Math. Soc. 43 (1938), 377–385. · Zbl 0019.00502
[20] P. Turán, Egy gráfelméleti szélsoérték-feladatról,Mat. Fiz. Lapok 48 (1941), 436–452.
[21] P. Turán, On the theory of graphs,Colloq. Math. 3 (1954), 19–30. · Zbl 0055.17004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.