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.


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$).

| cite | improve this answer | |
  • $\begingroup$ Thanks very much for that nice proof. Concerning question 2, i'd reckon the inequality isn't that strong though. $\endgroup$ – Martin Bächer May 12 '11 at 13:18
  • $\begingroup$ Indeed, I believe that question 2 is interesting for $m>k+1$. $\endgroup$ – Roland Bacher May 12 '11 at 13:21
  • $\begingroup$ An other proof would be by the Sauer-Shelah lemma. If we have more sets thean the above mentioned sum, the set system would shatter a set of size $k+2$. Thus it would have a (actually k+1) pair of sets that has intersection of size at least $k+1$. $\endgroup$ – Daniel Soltész Jan 14 '15 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.