# Maximum number of pairwise intersections

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.

• By "pairwise intersections" do you mean that any two of the subsets of size 2 ("2-sets") must have a nonempty intersection? If so, and the 2-sets do not have a common element, and e.g. $1$ happens to lie in the intersection of some two of the 2-sets, then you'd have e.g. $\{1,2\},\{1,3\},\{a,b\}$ where neither of $a,b$ are $1$, which forces them to be $2,3$ and you have only 3 sets possible in the list. – coffeemath Jun 26 '13 at 20:14
• no - I mean count the number of pairs which intersect. I've edited above. – mathaholic Jun 26 '13 at 20:34
• This edit clears it up, and makes it an interesting question, IMO. +1 – coffeemath Jun 26 '13 at 22:46

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.
• I agree that lexicographic order looks like the correct answer. Unfortunately, I'm not sure how to prove this either once $k \geq n$. – mathaholic Jun 27 '13 at 0:29