Question

Let $S \subset 2^M$ be a family of subsets of a set $M$ with $|M| = n$. Call $S$ min-k-intersecting if for each pair of subsets the intersection has at most $k$ elements: $\forall A,B \in S: |A \cap B | \leq k$.

Question 1: What is the maximal $N(n,k) = |S|$ of such a min-k-intersecting family of subsets of a set with cardinality $n$?

Question 2: What is the maximal $N(n,k,m) = |S|$ if additionally $|A| = m \quad \forall A \in S$?

I'd be glad if someone could point me to an argument (e.g. of Erdos-Rado type) that would be applicable.

Thanks a lot.

Answer 1

The answer (to question 1) is $\sum_{j=0}^{k+1}{n\choose j}$ and is realised by all subsets containing at most $k+1$ elements of $M$. Two such distinct subsets have indeed at most $k$ elements in common.

Let now $\mathcal S$ be a set of subsets in $M$ satisfying your requirement.

Suppose $A\in S$ is a subset of cardinality $>k+1$ intersecting a set $B\in S\setminus A$ in $j\leq k$ elements. Suppose $j$ maximal, ie $\sharp (A\cap C)\leq j$ for all $C\in S\setminus A$. Replace $A$ by $\tilde A=A\cap B\cup \lbrace a_1,\dots,a_{k+1-j}\rbrace\subset A$ with $a_1, \dots,a_{k+1-j}\in A\setminus B$. The map $A\longmapsto \tilde A$ replaces $A$ by a subset containing $k+1$ elements which does not belong to $S$. Moreover, $\tilde S=(S\cup \tilde A)\setminus A$ satisfies your requirements. Iterating this construction leads to a set $S$ of the same cardinality consisting only of subsets with at most $k+1$ elements.

Concerning question 2, the above proof gives the inequality $N(n,k,m)\leq {n\choose k+1}$ if $m>k+1$ (and $N(n,k,m)={n\choose m}$ if $m\leq k+1$).