Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A note on graphs without short even cycles. | A note on graphs without short even cycles Thomas Lam Jacques Verstraete t Submitted Apr 6 2004 Accepted Mar 25 2005 Published Apr 6 2005 Mathematics Subject Classifications 05C35 05C38 Abstract In this note we show that any n-vertex graph without even cycles of length at most 2k has at most 2n1 1 k O n edges and polarity graphs of generalized polygons show that this is asymptotically tight when k 2 2 3 5 . 1 Introduction In this note we study graphs without cycles of prescribed even lengths. For a finite or infinite set C of cycles define ex n C to be the maximum possible number of edges in an n-vertex graph which does not contain any of the cycles in C. The asymptotic behaviour of the function ex n C is particularly interesting when at least one of the cycles in C is of even length and was initiated by Erdos 5 . In general it is the lower bounds for ex n C - that is the construction of dense graphs without certain even cycles - which are hard to come by. The best known lower bounds are based on finite geometries such as polarity graphs of generalized polygons 9 and the algebraic constructions given by Lazebnik Ustimenko and Woldar 8 and Ramanujan graphs of Lubotsky Phillips and Sarnak 11 see also 10 . In the direction of upper bounds the first major result is known as the even circuit theorem due to Bondy and Simonovits 3 who proved that ex n C2k 100kn1 k. A more extensive study of ex n C was carried out by Erdos and Simonovits 6 . Our point of departure is the study of ex n C when C consists only of the even cycles of length at most 2k. The main result of this article is the following Theorem 1 Let k 2 be an integer. Then for all n ex n C4 C6 . C2k 2 n1 k 2k2 n. Furthermore when k 2 2 3 5 the n-vertex polarity graphs of generalized k 1 -gons in 9 have 1 n1 1 k O n edges and no even cycles of length at most 2k. Department of Mathematics Massachusetts Institute of Technology 77 Massachusetts Ave. Cambridge MA 02139 USA. E-mail thomasl@ Faculty of .
