MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
see also… – Nathann Cohen May 11 '11 at 12:50
up vote 5 down vote accepted

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

share|cite|improve this answer
Thanks very much for that nice proof. Concerning question 2, i'd reckon the inequality isn't that strong though. – Martin Bächer May 12 '11 at 13:18
Indeed, I believe that question 2 is interesting for $m>k+1$. – Roland Bacher May 12 '11 at 13:21
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$. – Daniel Soltész Jan 14 '15 at 16:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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