Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
see also mathoverflow.net/questions/33763/… –  Nathann Cohen May 11 '11 at 12:50

1 Answer 1

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|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

Your Answer

 
discard

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.