Number of subsets with no pairwise intersection of cardinality 2?

83 Views Asked by At

Consider $[n] = \{1,2,\dots,n\}$ and let $\mathcal{F}$ be a family of subsets of $[n]$ , each subset having cardinality $k$, such that

$\forall x,y \in \mathcal{F}, |x \cap y | \not = \frac{k}{2}.$

Is there any known result or technique to find a (non-trivial) upper bound on the maximal cardinality of $\mathcal{F}$?

The actual problem I care about is in fact more specific, with $k=4$. Then the question becomes: What is an upper bound on the number of 4-subsets of $[n]$ such that no two subsets have an intersection of cardinality 2?

1

There are 1 best solutions below

3
On

You can formulate the problem as finding a maximum independent set in a graph $G=(N,E)$ with one node per $k$-subset and an edge for each pair of $k$-subsets that intersect in exactly $k/2$ elements. Let binary decision variable $x_i$ indicate whether node $i$ is part of the independent set. The problem is to maximize $\sum_{i\in N} x_i$ subject to linear constraints $x_i + x_j \le 1$ for all edges $(i,j)\in E$. Summing these constraints yields $$\sum_{(i,j)\in E} (x_i+x_j) \le |E|.\tag1\label1$$ Because the graph is regular of degree $\Delta = 2|E|/|N|$, \eqref{1} reduces to $$\Delta \sum_{i\in N} x_i \le |E|,$$ yielding upper bound $$\sum_{i\in N} x_i \le \frac{|E|}{\Delta} = \frac{|N|}{2}.$$

For $n\in\{1,\dots,15\}$, the actual maximum values $a_{n,4}$ are much smaller: $$0, 0, 0, 1, 5, 5, 5, 10, 11, 12, 18, 20, 22, 29, 32.$$

By considering subsets that do not contain a particular element, we obtain the recurrence relation $$a_{n,k} \le \frac{n}{n-k} a_{n-1,k}.$$