A hypergraph extension of the bipartite Turan problem

摘要

Let t,n be integers with n greater than or equal to 3t. For t greater than or equal to 3, we prove that in any family of at least t(4)((n)(2)) triples from an n-element set X, there exist 2t triples A(1), B-1, A(2), B-2,..., A(t), B-t and distinct elements a, b is an element of X such that A(i) boolean AND A(j) = {a} and B-i boolean AND B-j = {b}, for all i not equal j, and[GRAPHICS]When t = 2, we improve the upper bound t(4) ((n)(2)) to 3 ((n)(2)) + 6n. This improves upon the previous best known bound of 3.5((n)(2)) due to Furedi. Some results concerning more general configurations of triples are also presented. (C) 2004 Elsevier Inc. All rights reserved.