Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 125.40501
Autor: Erdös, Pál; Hajnal, András
Title: On complete topological subgraphs of certain graphs (In English)
Source: Ann. Univ. Sci. Budapest. Rolando Eötvös, Sect. Math. 7, 143-149 (1964).
Review: 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 < k> , and the complete topological k-gon by < k> , and the complete topological k-gon by < k>t. The first theorem of the paper is the following: If r \geq 2 and c3 \geq 1/(2r+2), then G(n,c3n2) contains < [c4 n1/r ]>t, where c4 depends on c3. Denote by f(k,l) the smallest integer such that splitting the edges of an < f(k,l)> into two classes in an arbitrary way, either the first contains a < k> or the second an < l> . There are estimation for f(k,l). [P. Erdös and G. Szekeres, Zbl 012.27010; C. Frasney, C. R. Acad. Sci., Paris 256, 2507-2510 (1963; Zbl 211.02502); P. Erdös, Zbl 032.19203; Zbl 097.39102) Similarly, denote by f(kt,lt) the smallest integer such that splitting the edges of an < f(ktlt)> into two classes in an arbitrary way, either the first contains a < k>t or the second an < l>t. Moreover f(k,lt) and f(kt,l) have a self-explanatory meaning. Theorem 2. gives the estimations c1 k2 < f(ktlt) < c2k2,
c5l4/3(log l)-3/2 < f(3,lt) \leq {l+1 \choose 2},
c6k3(log k)-1 < f(k,kt). The symbol m ––> oo (mt,mt)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 ––> (mt,mt)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
Classif.: * 05C10 Topological graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag