1

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.

flag
Nisan–Wigderson combinatorial designs are also relevant. – Emil Jeřábek Nov 20 at 11:34
@Emil: Thanks for your comment. I will look into these designs. – Phanindra Nov 21 at 6:20

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.