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 (ij,ij+1) is an edge for j = 1,2,...,k, then we say G(k) contains an Ik path. An Ioo 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 > n0 an \epsilon > 0 g(n) > (1/4 - 1/4 k-1+\epsilon)n2 where k = 2 or k = 3. Then G(oo) contains infinitely many Ik-paths.
Theorem II. Let G(oo) be a graph for which

g(n) > 1/8 n2+( 1/32 +\epsilon )n2/ log2 n if n > n0.

Then G(oo) contains infinitely many I2-paths. The result is the best possible since there exists a G(oo) for which g(n) > 1/8 n2+ 1/32 n2/ log2n+o(n2/ log2n) and which does not contain any I2-path.
Theorem III. Let G(oo) be such that g(n) \geq 1/4 n2-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) /n2] > {1 \over 4} which does not contain an Ioo-path. But there exists a constant \alpha > 0 such that every G(oo) with liminf [g(n)/n2] > 1/2 -\alpha contains an Ioo-path. Theorem V. If g(n) > 1/2 n2-Cn for infinitely many n then G(oo) contains an infinite complete subgraph. But if we only assume that g(n) > 1/2 n2 -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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page