Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "More Constructions for Tur´n’s (3, 4)-Conjecture a"

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: More Constructions for Tur´n’s (3, 4)-Conjecture a. | More Constructions for Turan s 3 4 -Conjecture Andrew Frohmader Department of Mathematics 581 Malott Hall Cornell University Ithaca NY 14853-4201 froh@math.cornell.edu Submitted Jan 29 2008 Accepted Oct 24 2008 Published Nov 14 2008 Mathematics Subject Classification 05C65 Abstract For Turan s 3 4 -conjecture in the case of n 3k 1 vertices 26k-1 nonisomorphic hypergraphs are constructed that attain the conjecture. In the case of n 3k 2 vertices 6k-1 non-isomorphic hypergraphs are constructed that attain the conjecture. 1 Introduction Turán 8 posed the following problem about edges of hypergraphs. Suppose that an muniform hypergraph has exactly n vertices. Given r m if every possible subset of r vertices contains some m that do not form an edge how many edges can the hypergraph have as a function of n m and r Let tm n r be the greatest number of edges that the hypergraph can have. Turán 7 solved the case where m 2. The next simplest case is when m 3 and r 4. Turan had a conjecture for this case which we call Turán 3 4 -conjecture. Conjecture 1.1 Let H be a 3-uniform hypergraph in which every set of four vertices contains at most three edges. Let the number of vertices of H be n. Then the number of edges of H is at most 8 2 k3 - 3k2 if n 3k 2k3 k2 21 k if n 3k 1 2k3 7k2 k if n 3k 2. If all possible sets of m vertices formed an edge there would be m edges. Hence tm n r m is the fraction of the potential edges. If a hypergraph on n 1 vertices attains tm n 1 r then removing one vertex and all edges containing it leaves a hypergraph THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R137 1 with n vertices and at most tm n r edges. Average over all the ways to remove a vertex and we get tm n 1 r tm n r n 1 Zn m m Much work has since been done on the following problem. Problem 1.2 Fix r m. Let H be an m-uniform hypergraph on n vertices. Suppose further that every possible subset of r vertices contains some m that do not form an edge. Let tm n r denote the greatest number of .