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í toán học quốc tế đề tài: On Hypergraphs of Girth Five | On Hypergraphs of Girth Five Felix Lazebnik Department of Mathematical Sciences University of Delaware Newark De 19716 USA lazebnik@ Jacques Verstraete Theory Group Microsoft Research Building 113 2105 Redmond WA 98052 USA jbav@ Submitted Oct 9 2002 Accepted May 8 2003 Published May 30 2003 MR Subject Classifications 05D05 05D40 05D99 To the memory of Dom de Caen Abstract In this paper we study r-uniform hypergraphs H without cycles of length less than five employing the definition of a hypergraph cycle due to Berge. In particular for r 3 we show that if H has n vertices and a maximum number of edges then H 1 n3 2 o n3 2 . 6 This also asymptotically determines the generalized Turan number T3 n 8 4 . Some results are based on our bounds for the maximum size of Sidon-type sets in Zn. 1 Definitions In this paper a hypergraph H is a family of distinct subsets of a finite set. The members of H are called edges and the elements of V H uE-H E are called vertices. If all edges in H have size r then H is called an r-uniform hypergraph or simply r-graph. For example a 2-graph is a graph in the usual sense. A vertex v and an edge E are called incident if v E E. The degree of a vertex v of H denoted d v is the number of edges This work was initiated and continued at Microsoft Research during the author s visits and we are thankful the hosts for the opportunity and support. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R25 1 of H incident with V. An r-graph H is r-partite if its vertex set V H can be colored in r colors in such a way that no edge of H contains two vertices of the same color. In such a coloring the color classes of V H - the sets of all vertices of the same color - are called parts of H. We refer the reader to Berge 3 or 4 for additional background on hypergraphs. For k 2 a cycle in a hypergraph H is an alternating sequence of vertices and edges of the form v1 E1 v2 E2 . Vk Ek v1 such that i V1 v2 . vk are distinct vertices of H ii E1
