×

On complete topological subgraphs of certain graphs. (English) Zbl 0125.40501

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

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory

Keywords:

topology
PDFBibTeX XMLCite