Family of $r$-subsets, all pair-wise intersecting in $s$ elements

combinatorial-designscombinatoricsextremal-combinatoricsreference-requestterminology

Let $X$ be some $n$-element set and $\,\mathcal I\subseteq\mathcal P(X)$ a family of subsets with the following properties:

  • all $I\in\mathcal I$ are of size $r$
  • any two $I,J\in\mathcal I$ intersect in exactly $s$ elements.

In particular, I do not require that every element of $X$ appears in some subset of $\mathcal I$.

I am interested in the maximal size of $\mathcal I$. I wonder what are the key words for such type of questions? I know of Erdos-Ko-Rado typed problems, block designs, etc., but none of these fits well. This question is similar, but askes for intersections $\ge s$ instead of $=s$.


More concrete, I want to know how large $\mathcal I$ can be if $4s=2r=n$. If $\#(n)$ denotes this maximal size, then

$$\#(4)= 3, \qquad\#(8)\in\{7,8\}, \qquad\#(2^k)\ge 2^k-1. $$

What in general?

Best Answer

The Ray-Chaudhuri--Wilson theorem states that if $L$ is a finite set of $k$ non-negative integers and $\mathcal{I}$ is a collection of subsets of an $n$-element set, each of the same finite size, and such that $|A\cap B|\in L$ for any two distinct $A,B\in\mathcal{I}$, then $|\mathcal{I}\leq\binom{n}{k}$.

In your case $k=1$, so you get an upper bound of $|\mathcal{I}|\leq n$.

For more on Ray-Chaudhuri--Wilson and related theorems, see this paper of Alon, Babai and Suzuki.

Related Question