tailieunhanh - Báo cáo toán học: "An Extremal Characterization of Projective Planes"

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: An Extremal Characterization of Projective Planes. | An Extremal Characterization of Projective Planes Stefaan De Winter Department of Mathematics and Computer Algebra Ghent University 9000 Gent Belgium sgdwinte@ Felix Lazebniky Department of Mathematical Sciences University of Delaware Newark DE 19716 USA lazebnik@ Jacques Verstraetez Department of Mathematics University of California San Diego 9500 Gilman Drive La Jolla California 92093-0112 USA jacques@ Submitted Jul 22 2008 Accepted Nov 20 2008 Published Nov 30 2008 Mathematics Subject Classihcation 05B25 05C35 05C38 51E14 90C30 Abstract In this article we prove that amongst all n by n bipartite graphs of girth at least six where n q2 q 1 157 the incidence graph of a projective plane of order q when it exists has the maximum number of cycles of length eight. This characterizes projective planes as the partial planes with the maximum number of quadrilaterals. 1 Introduction The problem of maximizing the number of copies of a graph H in an F-free graph has been investigated at length by numerous researchers see for example Fisher 9 and Gyori Pach and Simonovits 13 Fiorini and Lazebnik 7 8 . The Turán problem is the most familiar instance of this problem where H K2 and is discussed in detail in Bollobás 2 Furedi 10 Simonovits 18 . To mention another example Erdos 5 conjectured that the The author is a Postdoctoral Fellow of the Research Foundation Flanders. yThis research was partially supported by the NSA Grant H98230-08-1-0041. zThis research was supported by an Alfred P. Sloan Research Fellowship and the NSF Grant DMS 0800704. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R143 1 maximum number of cycles of length five in an n-vertex triangle-free graph is achieved by the blowup of a pentagon see Gyori 12 for details . In order to present our results we will need the following definitions and notations. Any graph-theoretic notion not defined here may be found in Bollobas 3 . All our graphs are finite simple and undirected. If G