Erdős, Pál; Hajnal, András On complete topological subgraphs of certain graphs. (English) Zbl 0125.40501 Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 7, 143-149 (1964). Let \(G(n,l)\) a graph of \(n\) vertices and \(l\) edges. We say that \(G(n,l)\) contains a complete \(k\)-gon if there are \(k\) vertices of \(G(n,l)\) any two of which are connected by an edge, we say that it contains a complete topological \(k\)-gon if it contains \(k\) vertices any two of which are connected by paths no two of which have a common vertex (except of endpoints). Denote the complete \(k\)-gon by \(\langle k\rangle \), and the complete topological \(k\)-gon by \(\langle k\rangle \), and the complete topological \(k\)-gon by \(\langle k\rangle_t\). The first theorem of the paper is the following: If \(r \geq 2\) and \(c_3 \geq 1/(2r+2)\), then \(G(n,c_3n^2)\) contains \(\langle [c_4 n^{1/r} ]\rangle_t\), where \(c_4\) depends on \(c_3\). Denote by \(f(k,l)\) the smallest integer such that splitting the edges of an \(\langle f(k,l)\rangle \) into two classes in an arbitrary way, either the first contains a \(\langle k\rangle\) or the second an \(\langle l\rangle \). There are estimation for \(f(k,l).\) [P. Erdős and G. Szekeres, Zbl 0012.27010; C. Frasney, C. R. Acad. Sci., Paris 256, 2507-2510 (1963; Zbl 0211.02502); P. Erdős, Zbl 0032.19203; Zbl 0097.39102) Similarly, denote by \(f(k_t,l_t)\) the smallest integer such that splitting the edges of an \(\langle f(k_tl_t)\rangle\) into two classes in an arbitrary way, either the first contains a \(\langle k\rangle_t\) or the second an \(\langle l\rangle_t\). Moreover \(f(k,l_t)\) and \(f(k_t,l)\) have a self-explanatory meaning. Theorem 2. gives the estimations \[ c_1 k^2 < f(k_tl_t) < c_2k^2, \]\[ c_5l^{4/3}(\log l)^{-3/2} < f(3,l_t) \leq {l+1 \choose 2}, \]\[ c_6k^3(\log k)^{-1} < f(k,k_t). \] The symbol \(m \to \infty (m_t,m_t)^2\) denotes the statement that if we split the edges of a complete graph of power \(m\) into two classes in an arbitrary way, then there exists a complete topological subgraph of power \(m\) all whose edges belong to the same class. The third theorem states \(m \to (m_t,m_t)^2\) if \(m\) is an arbitrary cardinal. The paper contains further interesting results as collararies to the main theorems, and unsolved problems. Reviewer: Gy.Katona Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 5 Documents MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:topology Citations:Zbl 0012.27010; Zbl 0211.02502; Zbl 0032.19203; Zbl 0097.39102 PDFBibTeX XMLCite \textit{P. Erdős} and \textit{A. Hajnal}, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 7, 143--149 (1964; Zbl 0125.40501)