Czipszer, J.; Erdős, Pál; Hajnal, András Some extremal problems on infinite graphs. (English) Zbl 0114.01301 Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 441-457 (1962). Let the vertices of the infinite graph \(G^{(\infty)}\) be the integers \(1, 2, \ldots, n, \ldots\). Let \(G^{(n)}\) be the subgraph of \(G^{(\infty)}\) consisting of the vertices \(1,2, \ldots,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,\ldots,k\), then we say \(G^{(k)}\) contains an \(I_k\) path. An \(I_\infty\) path may be defined in similar manner. The authors proved in this paper the following theorems: Theorem I: Let \(G^{(\infty)}\) be a graph and assume for all \(n>n_0\) an \(\varepsilon > 0\) \(g(n)> (\frac{1 }{4} - \frac{1 }{4} k^{-1} + \varepsilon)n^2\) where \(k=2\) or \(k=3\). Then \(G^{(\infty)}\) contains infinitely many \(I_k\)-paths. Theorem II. Let \(G^{(\infty)}\) be a graph for which \[ g(n) > \frac{1 }{8} n^2 + \left (\frac{1 }{32} + \varepsilon \right )n^2/\log^2 n \text{ if } n > n_0. \] Then \(G^{(\infty)}\) contains infinitely many \(I_2\)-paths. The result is the best possible since there exists a \(G^{(\infty)}\) for which \(g(n) > \frac{1 }{8} n^2+ \frac{1}{32}n^2/\log^2n+o(n^2/\log^2n)\) and which does not contain any \(I_2\)-path. Theorem III. Let \(G^{(\infty)}\) be such that \(g(n) \geq \frac{1 }{4} n^2-Cn\). Then \(G^{(\infty)}\) contains an infinite path. This result is best possible in the sense that \(C\) can not be replaced by \(A(n)\) where \(A(n) \to \infty\). Theorem IV. There exists a \(G^{(\infty)}\) with \(\liminf [g(n) /n^2] > \frac{1 }{4}\) which does not contain an \(I_\infty\)-path. But there exists a constant \(\alpha >0\) such that every \(G^{(\infty)}\) with \(\liminf [g(n)/n^2] > \frac{1 }{2}-\alpha\) contains an \(I_\infty\)-path. Theorem V. If \(g(n) > \frac{1 }{2} n^2-Cn\) for infinitely many \(n\) then \(G^{(\infty)}\) contains an infinite complete subgraph. But if we only assume that \(g(n)> \frac{1 }{2} n^2 -f(n) n\) for all \(n\) where \(f(n)\) tends to infinity as slowly as we please then \(G^{(\infty)}\) does not have to contain an infinite complete graph. Reviewer: József Dénes (Budapest) Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 1 ReviewCited in 4 Documents MSC: 05C35 Extremal problems in graph theory 05C63 Infinite graphs Keywords:extremal problems; infinite graphs PDFBibTeX XMLCite \textit{J. Czipszer} et al., Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 441--457 (1962; Zbl 0114.01301)