3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – coffeemath Jun 26 '13 at 20:14
  • $\begingroup$ no - I mean count the number of pairs which intersect. I've edited above. $\endgroup$ – mathaholic Jun 26 '13 at 20:34
  • $\begingroup$ This edit clears it up, and makes it an interesting question, IMO. +1 $\endgroup$ – coffeemath Jun 26 '13 at 22:46
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree that lexicographic order looks like the correct answer. Unfortunately, I'm not sure how to prove this either once $k \geq n$. $\endgroup$ – mathaholic Jun 27 '13 at 0:29
1
$\begingroup$

Imagine you have n nodes - each corresponding to a number. A set in your case is an edge and an intersection is said to occur if two edges share a common vertex. Thus the number of interaectiona because of vertex v is degree(v) choose 2. The total number of intersections is the sum of degrees choose 2 (which is a convex function) whereas the sum of the degrees is 2*#edges = 2k. This proves user Ross Milikan's answer.

Sorry for the bad formatting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.