MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $X=\{1,2,\cdots,n\}$ and $\mathcal{F} \subset 2^X$ so that $\mathcal{F}$ contains sets of given cardinality $k_1,k_2,\cdots, k_N$ (here $|\mathcal{F}| = N)$. Let $\delta(\mathcal{F})$ be the maximum value of the intersection of elements in $\mathcal{F}$, i.e. $\delta (\mathcal{F}) = max_{i,j} |S_i \cap S_j|, S_i, S_j \in \mathcal{F}$. The problem is to find $\mathcal{F}$ for given $k_1,k_2,\cdots,k_N$ so that $\delta(\mathcal{F})$ is minimal.

I wanted to know if this problem is hard (NP hard, etc) and whether such problems have been researched before. I am aware of the Erdos-Ko-Rado, Sperner's theorems and have browsed some literature by N. Alon in Extremal finite set theory but did not come across something that can be used here.

Thanks for any help.

share|cite|improve this question
Nisan–Wigderson combinatorial designs are also relevant. – Emil Jeřábek Nov 20 '12 at 11:34
@Emil: Thanks for your comment. I will look into these designs. – Phanindra Nov 21 '12 at 6:20

Your Answer


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

Browse other questions tagged or ask your own question.