ON GENERALIZATIONS OF THE DEBRUIJN-ERDOS THEOREM

[摘要] Let L = {l1, l2, ..., l(k)} be a collection of k positive intergers, let A be a family of subsets of an n-element set and let C = {A(i) is-an-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-equal 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 possible. We also prove that the following conjecture is true when n is sufficiently large. Conjecture. Let L = {l1, l2..., l(k)} be a collection of 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-equal-to [GRAPHICS] (n-1/i). Finally, a modular version of the above theorem is proved and is used to partially confirm a conjecture of alon, babai, and Suzuki. These results generalize earlier results of deBruijn and Erdos, Bose, Ryser, Frankl and Furedi, and others. (C) 1994 Academic Press, Inc.

[发布日期] 1994-10-01