×

Some extremal problems on infinite graphs. (English) Zbl 0114.01301

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.

MSC:

05C35 Extremal problems in graph theory
05C63 Infinite graphs
PDFBibTeX XMLCite