zbMATH — the first resource for mathematics

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
topology