Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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$. –  TMM Sep 27 '11 at 19:57
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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