TAILIEUCHUNG - 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

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.