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

Question

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?

Answer 1

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.

Answer 2

Based on the comment of jpvee, here is a construction for the case $4s=2r=n=2^k,k\ge 2$ with $|\mathcal I|=n-1$ subsets.

---

Denote bei $\Bbb F_2$ the finite field with two elements. Let $X=\Bbb F_2^k$ be our ground set from which we choose the family $\mathcal I\subseteq\mathcal P(X)$. This is the $k$-dimensional vector space over $\Bbb F_2$, hence has $n=|X|=2^k$ elements. Further, we define

$$\mathcal I:=\{ U\subseteq\Bbb F_2^k \mid \text{$U$ is a $(k-1)$-dimensional subspace of $\Bbb F_2^k$}\},$$

Each of these subspaces is isomorphic to $\Bbb F_2^{k-1}$, hence has $r=2^{k-1}=n/2$ elements. Any two distinct $(k-1)$-dimensional subspaces of a $k$-dimensional vector space intersect in a subspace of dimension

$$(k-1)+(k-1)-k=k-2.$$

Thus, the intersections are isomorphic to $\Bbb F_2^{k-2}$ and contain $s=2^{k-2}=n/4$ elements. So the family $\mathcal I$ satisfies all the conditions of the question for $4s=2r=n=2^k$.

By the $q$-binomial coefficient formula (taken from here), $\Bbb F_2^k$ has

$$\frac{(2^k-1)\cdots(2^k-2^{k-2})}{(2^{k-1}-1)\cdots (2^{k-1}-2^{k-2})}=2^k-1=n-1$$

$(k-1)$-dimensional subspaces. Hence $|\mathcal I|=n-1$.