2
$\begingroup$

Given an $n$-element set $S$, the problem is to find the size of the largest possible family of subsets $\{S_1, \dots, S_m\}, S_i \subseteq S$ with constraints $|S_i| = 3, |S_i \cap S_j| \neq 1$. My thoughts on it are below - I think I'm on the right way to the solution, but have no idea how to proceed.

For 3-element sets intersection $\neq 1$ means they don't intersect, or intersect by 2 elements. An intuitively obvious way to build the required subsets is to split all the $n$ elements into groups of four, and in each group make subsets like $\{1,2,3\}, \{2,3,4\}, \{1,2,4\}, \{1,3,4\}$ - this way there will be exactly $n$ subsets for $n$ divisible by 4. This family is maximal by inclusion, i.e. no other subset can be added to it, but how to prove it's the largest one (as is it, actually?)? In case 4 doesn't divide $n$, subsets can look like $\{1,2,3\}, \{2,3,4\}, \{2,3,5\}, \dots$ - but again, is it the largest family?

Also it's interesting, if there is some general method to solve this, when $|S_i| = k, |S_i \cap S_j| \neq l$? I couldn't apply similar intuition here...

$\endgroup$
1
$\begingroup$

If each element is required to occur in a triple, the best you can do is $n$ triples if $4|n$, and $n-2$ triples otherwise. If you allow "unused" elements you can do $n-1$ triples if $n\equiv 1\pmod 4$.

The reason is that there are only two nontrivial kinds of "connected components" you can have (that is, connected components in the graph joining two elements by an edge iff they both occur in some triple). One possible component is the complete graph $K_4$ involving four triples $abc$, $abd$, $acd$, and $bcd$. There's really only one other thing that can happen: suppose you have two triples which intersect; they must intersect in two elements, so we have $abc$ and $abd$. If a third triple intersects either of these and involves a fifth element $e$, it's easy to see that the only possibility is $abe$. So the triples in the connected component must be $abc$, $abd$, $abe$, $abf$, and so on; we'll call this a bouquet. A bouquet involving $m$ elements contains $m-2$ triples. So the optimal configurations look like a disjoint union of $K_4$'s, together with at most one bouquet if $n$ is not divisible by $4$.

Finally, if you allow unused elements, you can achieve $n-1$ triples if $n\equiv 1\pmod 4$ by grouping all but one element into $K_4$'s.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's actually not quite correct - if $n = 4k + 1$, one can get $n-1 = 4k$ triples, just using the same ones as for $n = 4k$. $\endgroup$ – aplavin Oct 7 '15 at 14:04
  • $\begingroup$ I see - I'd assumed all the elements had to be used. I've updated the solution accordingly. $\endgroup$ – Tad Oct 8 '15 at 2:06

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.