ON GENERALIZATIONS OF THE DEBRUIJN-ERDOS THEOREM

Let L = {l1, l2, ..., l(k)} be a collection of k positive intergers, l et A be a family of subsets of an n-element set and let C = {A(i) is-a n-element-of A : \A(i)\ is-an-element-of L}. We show that if \A(i) and A(j)\ is-an-element-of L for all A(i), A(j) is-an-element-of A and if Absolute value of C = 0 or if and(Ai is-and-element-of C)A(i) not-equ al 0 then Absolute value of A [GRAPHICS]. This result is used to prove that if 1 less-than-or-equal-to \A(i) and A(j)\ less-than-or-equal-to 2 for all A(i), A(j) is-an-element-of A then Absolute value of A less -than-or-equal-to (n-1/0) + (n-1/1) + (n-1/2) and this is best possibl e. We also prove that the following conjecture is true when n is suffi ciently large. Conjecture. Let L = {l1, l2..., l(k)} be a collection o f k positive integers. If \A(i) and A(j)\ is-an-element-of L for all A (i), A(j) is-an-element-of A, then Absolute value of A less-than-or-eq ual-to [GRAPHICS] (n-1/i). Finally, a modular version of the above the orem is proved and is used to partially confirm a conjecture of alon, babai, and Suzuki. These results generalize earlier results of deBruij n and Erdos, Bose, Ryser, Frankl and Furedi, and others. (C) 1994 Acad emic Press, Inc.