tailieunhanh - Báo cáo toán học: "A multipartite version of the Tur´n problem a density conditions and eigenvalues"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A multipartite version of the Tur´n problem a density conditions and eigenvalues. | A multipartite version of the Turan problem -density conditions and eigenvalues Zoltán Lóránt Nagy Department of Computer Science Eotvos Lorand University Budapest Hungary nagyzoltanlorant@ Submitted Apr 16 2010 Accepted Feb 14 2011 Published Feb 21 2011 Mathematics Subject Classification 05C32 05C42 To the memory of Andras Gacs and Mate Salat Abstract In this paper we propose a multipartite version of the classical Turan problem of determining the minimum number of edges needed for an arbitrary graph to contain a given subgraph. As it turns out here the non-trivial problem is the determination of the minimal edge density between two classes that implies the existence of a given subgraph. We determine the critical edge density for trees and cycles as forbidden subgraphs and give the extremal structure. Surprisingly this critical edge density is strongly connected to the maximal eigenvalue of the graph. Furthermore we give a sharp upper and lower bound in general in terms of the maximum degree of the forbidden graph. 1 Introduction A Turan type problem is generally formulated in the following way one fixes some graph properties and tries to determine the maximum or minimum number of edges a graph on n vertices with the prescribed properties can have and furthermore describe the extremal structure. This paper deals with the following multipartite variant of the Turan problem inspired by previous research by Balazs Montagh. Fix a graph G on r labeled vertices. Consider all r-partite graphs with labeled partition classes of bounded cardinality satisfying the property that G is not a subgraph in such a way that the ith vertex of G is in the ith The author was supported by OTKA grant K 81310 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P46 1 partition class. The most natural question one can ask here is to determine the maximum number of edges such a multipartite graph can have. This question was mentioned in 1 in a bit specific form and turned out to be .