On the Turán properties of infinite graphs
type: Item
instance of: scholarly article
title: On the Turán properties of infinite graphs
zbMATH Open document ID: 1181.05054
author: Andrzej Dudek
author: Vojtěch Rödl
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/117234
full work available at URL: v15i1r47.html
review text: Summary: Let \(G^{(\infty)}\) be an infinite graph with the vertex set corresponding to the set of positive integers \({\mathbb N}\). Denote by \(G^{(l)}\) a subgraph of \(G^{(\infty)}\) which is spanned by the vertices \(\{1,\dots,l\}\). As a possible extension of Turán's theorem to infinite graphs, in this paper we will examine how large \(\lim \text{inf}_{l\rightarrow \infty} \frac{|E(G^{(l)})|}{l^2}\) can be for an infinite graph \(G^{(\infty)}\), which does not contain an increasing path \(I_k\) with \(k+1\) vertices. We will show that for sufficiently large \(k\) there are \(I_k\)--free infinite graphs with \(\frac{1}{4}+\frac{1}{200} < \lim \text{inf}_{l\rightarrow \infty}\frac{|E(G^{(l)})|}{l^2}\). This disproves a conjecture of J.Czipszer, P.Erdős and A.Hajnal. On the other hand, we will show that \(\liminf_{l\rightarrow \infty}\frac{|E(G^{(l)}|}{l^2} \leq \text{1}{3}\) for any \(k\) and such \(G^{(\infty)}\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5540952
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540952