Agrupar el $n$ elementos en bloques de $4$ . Cada bloque de $4$ admite una colección de cuatro $3$ -conjuntos de elementos con $2$ -Intersecciones de elementos. Si $n=4m+k$ con $k\in\{0,1,2\}$ puedes conseguir al menos $4m$ conjuntos que satisfacen la condición, y si $n=4m+3$ puedes conseguir al menos $4m+1$ . Esto no es peor que formar el conjunto de todos los $3$ -que contienen un par fijo de elementos, y es mejor cuando $k$ es $0$ o $1$ .
Añadido: Podemos pensar en esto en términos de gráficos $G$ en $n$ vértices. Dos vértices están conectados por una arista si pertenecen a algún miembro de $\mathbf M$ . La exigencia de $\mathbf M$ se traduce en la exigencia de que dos $3$ -cliques en $G$ deben ser disjuntos o compartir una arista.
Supongamos que $\{u,v\}$ es una arista compartida por $m>2$ $3$ -cliques cuyos terceros vértices son $w_1,w_2,\dots,w_m$ . Está claro que no hay dos de los $w_i$ pueden ser adyacentes; por ejemplo, si $\{w_1,w_2\}$ fuera un borde, el $3$ -cliques $\{u,w_1,w_2\}$ y $\{u,v,w_3\}$ compartirían un solo vértice. También está claro que si $z$ es un vértice diferente de $u,v$ y el $w_i$ No. $\{z,w_i\}$ puede ser una arista: cualquier $3$ -clique que contiene $z$ y $w_i$ tendría que contener $u$ o $v$ para evitar tener un solo vértice en común con $\{u,v,w_i\}$ pero entonces sólo tendría un vértice en común con $\{u,v,w_j\}$ para $j\ne i$ . El subgrafo de $G$ generado por $\{u,v\}\cup \{w_i:1\le i\le m\}$ es, por tanto, un componente de $G$ con $m+2$ vértices y $m$ $3$ -cliques.
Supongamos ahora que $\{u,v\}$ es una arista compartida por sólo dos $3$ -cliques, cuyos terceros vértices son $w_1$ y $w_2$ . Supongamos que $\{w_1,y,z\}$ es un $3$ -clique, donde $y$ es un vértice distinto de $u,v$ y $w_2$ . El $3$ -clique $\{u,v,w_1\}$ fuerzas $z$ para ser $u$ o $v$ pero luego $\{u,v,w_2\}$ sólo tiene un vértice en común con $\{w_1,y,z\}$ , lo cual es imposible. De la misma manera, $w_2$ no puede formar parte de un $3$ -con un vértice diferente de $u,v$ y $w_1$ . Supongamos a continuación que $\{u,y,z\}$ es un borde para algunos $y$ diferente de $v,w_1$ y $w_2$ . Es fácil ver que $z$ no puede ser $w_1$ o $w_2$ pero tampoco puede ser $v$ ya que $\{u,v\}$ pertenece sólo a dos $3$ -cliques. De la misma manera, $v$ no puede ser adyacente a ningún vértice diferente de $u,w_1$ y $w_2$ . Por último, si $\{w_1,w_2,z\}$ es un $3$ -clique, $z$ debe ser $u$ o $v$ . Así, el subgrafo generado por $\{u,v,w_1,w_2\}$ es un componente de $G$ con $4$ vértices y $2,3$ o $4$ $3$ -cliques.
Por último, supongamos que $\{u,v\}$ pertenece sólo a la $3$ -clique $\{u,v,w\}$ . Si una de las otras dos aristas del $3$ -clique pertenece al menos a otra $3$ -estos tres vértices pertenecen a un componente de uno de los dos tipos ya discutidos; si no, el subgrafo generado por $\{u,v,w\}$ es un componente de $G$ con $3$ vértices y uno $3$ -clique.
Cualquier otro componente de $G$ deben ser vértices aislados.
De ello se deduce que la estrategia de agrupar los elementos en bloques de $4$ (y un bloque impar de $3$ , si es posible) es óptimo.
