Almost-Fisher families

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:138

Article

Das, Shagnik¹  Sudakov, Benny¹  Vieira, Pedro¹ 

[1] ETH, Dept Math, CH-8092 Zurich, Switzerland

关键词: Design theory;    Fisher's inequality;    Extremal set theory;    Extremal combinatorics;    Hadamard matrices;   

DOI  :  10.1016/j.jcta.2015.10.003

来源: Elsevier

【 摘 要 】

A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family F of subsets of [n] with all pairwise intersections of size lambda can have at most n non-empty sets. One may weaken the condition by requiring that for every set in F, all but at most k of its pairwise intersections have size lambda. We call such families k-almost lambda-Fisher. Vu was the first to study the maximum size of such families, proving that for k = 1 the largest family has 2n - 2 sets, and characterising when equality is attained. We substantially refine his result, showing how the size of the maximum family depends on lambda. In particular we prove that for small lambda one essentially recovers Fisher's bound. We also solve the next open case of k = 2 and obtain the first non-trivial upper bound for general k. (C) 2015 Elsevier Inc. All rights reserved.

【 授权许可】

Free