Intersection statements for systems of sets

[摘要] A Family of r sets is called a Delta-system if any two sets have the same intersection. Denote by F(n, r) the most number of subsets of an n-element set which do not contain a Delta-system consisting of r sets. Constructive new lower bounds for F(n,r) are given which improve known probabilistic results, and a new upper bound is given by employing an argument due to Erdos and Szemeredi. Another construction is given which shows that for certain n, F(n, 3)greater than or equal to 1.551(n-2). We also show a relationship between the upper bound for F(n, 3) and the Erdos-Rado conjecture on the largest uniform family of sets not containing a Delta-system. (C) 1997 Academic Press.

[发布日期] 1997-07-01