## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 30, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Pedro Vieira

## Almost-Fisher Families

A classic theorem in combinatorial design theory is Fisher's inequality, which states that a family $F$ of subsets of $\{1,2,...,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,\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 characterizing when equality is attained. In this talk we present a refined version of these results, showing how the size of the maximum family depends on the parameter $\lambda$. In particular we show 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$.

Information for students and suggested topics for student talks