##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 114.01301

**Autor: ** Czipszer, J.; Erdös, Pál; Hajnal, András

**Title: ** Some extremal problems on infinite graphs (In English)

**Source: ** Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 441-457 (1962).

**Review: ** Let the vertices of the infinite graph G^{(oo)} be the integers 1,2,...,n.... Let G^{(n)} be the subgraph of G^{(oo)} consisting of the vertices 1,2,...,n and the edges joining them, and let g(n) denote the number of edges in G^{(n)}. If G^{(n)} contains k vertices such that (i_{j},i_{j+1}) is an edge for j = 1,2,...,k, then we say G^{(k)} contains an I_{k} path. An I_{oo} path may be defined in similar manner. The authors proved in this paper the following theorems:

Theorem I: Let G^{(oo)} be a graph and assume for all n > n_{0} an \epsilon > 0 g(n) > (^{1}/_{4} - ^{1}/_{4} k^{-1}+\epsilon)n^{2} where k = 2 or k = 3. Then G^{(oo)} contains infinitely many I_{k}-paths.

Theorem II. Let G^{(oo)} be a graph for which g(n) > ^{1}/_{8} n^{2}+**(** ^{1}/_{32} +\epsilon **)**n^{2}/ log^{2} n if n > n_{0}. Then G^{(oo)} contains infinitely many I_{2}-paths. The result is the best possible since there exists a G^{(oo)} for which g(n) > ^{1}/_{8} n^{2}+ ^{1}/_{32} n^{2}/ log^{2}n+o(n^{2}/ log^{2}n) and which does not contain any I_{2}-path.

Theorem III. Let G^{(oo)} be such that g(n) \geq ^{1}/_{4} n^{2}-Cn. Then G^{(oo)} contains an infinite path. This result is best possible in the sense that C can not be replaced by A(n) where A(n) ––> oo.

Theorem IV. There exists a G^{(oo)} with **liminf** [g(n) /n^{2}] > {1 \over 4} which does not contain an I_{oo}-path. But there exists a constant \alpha > 0 such that every G^{(oo)} with **liminf** [g(n)/n^{2}] > ^{1}/_{2} -\alpha contains an I_{oo}-path. Theorem V. If g(n) > ^{1}/_{2} n^{2}-Cn for infinitely many n then G^{(oo)} contains an infinite complete subgraph. But if we only assume that g(n) > ^{1}/_{2} n^{2} -f(n) n for all n where f(n) tends to infinity as slowly as we please then G^{(oo)} does not have to contain an infinite complete graph.

**Reviewer: ** J.Dénes

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Index Words: ** combinatorics

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag