Let $[n]=\{1,2,\ldots,n\}$ and let $S$ consist of subsets of $[n]$ of cardinality $2$. I would like to find the maximum number of pairwise intersections that $k$ distinct elements from $S$ can have. That is, I would like to find $k$ sets from $S$ such that the number of pairs of intersecting sets is the largest.
For example, the collection $\{1,2\},\{2,3\},\{3,4\}$ has 2 pairs of intersecting sets. The collection $\{1,2\},\{1,3\},\{1,4\}$ has 3 pairs of intersecting sets.
When $k \leq (n-1)$, I know that the answer is $\binom{k}{2}$ obtained by taking $\{1,2\},\{1,3\},\{1,4\},\ldots,\{1,k+1\}$.
Thanks.
Best Answer
I think the greedy algorithm works. Sort the two element subsets in lexicographic order, then take the first $k$ of them. As you say, up to $n-1$ of them you get $k \choose 2$ intersecting pairs, which is all of them. Now you start with $\{2,i\}$ with $i$ ranging from $3$ to $n$. Each new one will intersect two of the first $n-1$ and all the new ones. I don't see how to prove it, though.