کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655163 | 1632934 | 2016 | 33 صفحه PDF | دانلود رایگان |
A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family FF of subsets of [n][n] with all pairwise intersections of size λ can have at most n non-empty sets. One may weaken the condition by requiring that for every set in FF, all but at most k of its pairwise intersections have size λ. We call such families k-almost λ -Fisher. Vu was the first to study the maximum size of such families, proving that for k=1k=1 the largest family has 2n−22n−2 sets, and characterising when equality is attained. We substantially refine his result, showing how the size of the maximum family depends on λ. In particular we prove that for small λ one essentially recovers Fisher's bound. We also solve the next open case of k=2k=2 and obtain the first non-trivial upper bound for general k.
Journal: Journal of Combinatorial Theory, Series A - Volume 138, February 2016, Pages 175–207