Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "On the Tur´n Properties of Infinite Graphs a"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the Tur´n Properties of Infinite Graphs a. | On the Turan Properties of Infinite Graphs Andrzej Dudek and Vojtech Rodl Department of Mathematics and Computer Science Emory University Atlanta USA adudek rodl @mathcs.emory.edu Submitted Dec 9 2006 Accepted Mar 16 2008 Published Mar 20 2008 Mathematics Subject Classifications 05C35 05C38 Abstract Let G 1 be an infinite graph with the vertex set corresponding to the set of positive integers N. Denote by G l a subgraph of G l which is spanned by the vertices 1 . l . As a possible extension of Turan s theorem to infinite graphs in this paper we will examine how large liminf 1 1 ET j can be for an infinite graph G l which does not contain an increasing path Ik with k 1 vertices. We will show that for sufficiently large k there are Ife-free infinite graphs with 4 200 liminf 1 1 IE G2 j. This disproves a conjecture of J. Czipszer P. Erdos and A. Hajnal. On the other hand we will show that liminf 1 1 lE G d 1 for any k and such G l . 1 Introduction 1.1 Preliminaries Let G l y G 1 E G l be an infinite graph with the vertex set corresponding to the set of natural numbers i.e. y G l N and the set of edges E G l . Denote by G l the subgraph of G l induced on the set 1 . l . Let G l be a Kk 1- free graph. Then by Turan s theorem for finite graphs we get that liminf 1 1 cppll limsupz 1 E G I 2 1 D. On the other hand a Kk 1-free graph G l with edges i j 2 E G 1 if j i 0 mod k achieves this bound. Hence the Turan density for finite and infinite Kk 1-free graphs is the same. In this paper we study the edge density of graphs without an increasing path of length k. We say that Ik i1 i2 . ik 1 is an increasing path of G l if ii i2 ik 1 and ij ij 1 2 E G l . One can easily see that for any fixed l there exists a graph G l not containing Ik such that E G l I equals to the Turan number for Kk 1-free graphs. Hence for finite graphs forbidding Ik leads to the same restriction on number of edges THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R47 1 as forbidding Kk 1. While the maximum