9
$\begingroup$

Let $\mathbf{M} = \{M_1, M_2, ..., M_s\}$ be a set of (some) 3-element subsets of an $n$-element set.

It is known that $\forall i,j:\quad 1 \leq i \leq j \leq s: \quad |M_i\cap M_j|\neq 1$.

I need to find a maximum $s$ which allows the previous condition to hold. The answer may be dependent on $n$.

I need to solve this task to proceed with my study, but my current math level isn't very good. (But of course I know basic combinatorics). Could you please give as "for dummies" explanation as possible!

Thank you!

  • 0
    For $n \geq 3$ the answer would be $\infty$ by taking $M_1 = M_2 = \ldots$, so I guess that you actually want the condition that $|M_i \cap M_j| \in \{0,2\}$ for $i \neq j$.2011-09-27

2 Answers 2

7

Group the $n$ elements in blocks of $4$. Each block of $4$ admits a collection of four $3$-element sets with $2$-element intersections. If $n=4m+k$ with $k\in\{0,1,2\}$ you can get at least $4m$ sets satisfying the condition, and if $n=4m+3$ you can get at least $4m+1$. This is never worse than forming the set of all $3$-element sets containing a fixed pair of elements, and it’s better when $k$ is $0$ or $1$.

Added: We can think of this in terms of graphs $G$ on $n$ vertices. Two vertices are connected by an edge iff they belong to some member of $\mathbf M$. The requirement on $\mathbf M$ translates to a requirement that any two $3$-cliques in $G$ must either be disjoint or share an edge.

Suppose that $\{u,v\}$ is an edge shared by $m>2$ $3$-cliques whose third vertices are $w_1,w_2,\dots,w_m$. Clearly no two of the $w_i$ can be adjacent; e.g., if $\{w_1,w_2\}$ were an edge, the $3$-cliques $\{u,w_1,w_2\}$ and $\{u,v,w_3\}$ would share only one vertex. It’s also clear that if $z$ is a vertex different from $u,v$, and the $w_i$, no $\{z,w_i\}$ can be an edge: any $3$-clique containing $z$ and $w_i$ would have to contain $u$ or $v$ to avoid having just one vertex in common with $\{u,v,w_i\}$ but would then have only one vertex in common with $\{u,v,w_j\}$ for $j\ne i$. The subgraph of $G$ generated by $\{u,v\}\cup \{w_i:1\le i\le m\}$ is therefore a component of $G$, with $m+2$ vertices and $m$ $3$-cliques.

Now suppose that $\{u,v\}$ is an edge shared by just two $3$-cliques, whose third vertices are $w_1$ and $w_2$. Suppose that $\{w_1,y,z\}$ is a $3$-clique, where $y$ is a vertex distinct from $u,v$, and $w_2$. The $3$-clique $\{u,v,w_1\}$ forces $z$ to be $u$ or $v$, but then $\{u,v,w_2\}$ has only one vertex in common with $\{w_1,y,z\}$, which is impossible. Similarly, $w_2$ cannot be part of a $3$-clique with a vertex different from $u,v$, and $w_1$. Suppose next that $\{u,y,z\}$ is an edge for some $y$ different from $v,w_1$, and $w_2$. It’s easy to see that $z$ can’t be $w_1$ or $w_2$, but it also can’t be $v$, since $\{u,v\}$ belongs to only two $3$-cliques. Similarly, $v$ can’t be adjacent to any vertex different from $u,w_1$, and $w_2$. Finally, if $\{w_1,w_2,z\}$ is a $3$-clique, $z$ must be $u$ or $v$. Thus, the the subgraph generated by $\{u,v,w_1,w_2\}$ is a component of $G$, with $4$ vertices and $2,3$, or $4$ $3$-cliques.

Finally, suppose that $\{u,v\}$ belongs only to the $3$-clique $\{u,v,w\}$. If one of the other two edges of the $3$-clique belongs to at least one other $3$-clique, these three vertices belong to a component of one of the two types already discussed; if not, the subgraph generated by $\{u,v,w\}$ is a component of $G$, with $3$ vertices and one $3$-clique.

Any other components of $G$ must be isolated vertices.

It follows that the strategy grouping the elements in blocks of $4$ (and one odd block of $3$, if possible) is optimal.

0

Note that a (not very good) lower bound is $\lfloor n/3 \rfloor$ by having none of the subsets sharing elements. But you may be able to do better with some of the subsets sharing two elements.

On the assumption this is homework:

  • What do you think the answer might be if $n=3$?

  • What do you think the answer might be if $n=4$?

  • What do you think the answer might be if $n=5$?

  • etc.