OMA Foros

Sea [math]n\geq 2 un entero. Diremos que un conjunto de [math]k personas es amigable de orden [math]n si para toda persona del conjunto, si se excluye a esa persona, hay otras [math]n personas tales que en el grupo de las [math]n personas son todas amigas entre si. Hallar el máximo valor de [math]k tal que todo conjunto de [math]k personas que sea amigable de orden [math]n contenga necesariamente un grupo de [math]n+1 personas que son todas amigas entre sí.

Casi un paper.

Spoiler: mostrar

Primero veamos que [math]k\le 2n-1. Para ello, basta notar que el grafo de [math]2n vértices formado por dos componente que son [math]n-cliqués cada una satisface la condición del enunciado, pero no tiene ningún [math]n+1-cliqué.

Ahora veamos que todo grafo de [math]2n-1 vértices con la propiedad del enunciado debe tener un [math]n+1-cliqué. Para ello, supongamos a modo de contradicción que existe un grafo [math]G con la propiedad del enunciado de [math]2n-1 vértices pero que no tiene un [math]n+1-cliqué, y lleguemos a un absurdo.

Le demostración que sigue de basa fuertemente del uso de notación la cual nos va a permitir entender un poco mejor el grafo que tenemos. Después hay varias igualdades asquerosas que intimidan y que necesitamos usar para ser rigurosos, pero viendo los ejemplitos mostrados queda clara la idea de lo que estamos haciendo.

Obviamente [math]G contiene al menos dos [math]n-cliqués. Más aún, [math]G contiene al menos tres [math]n-cliqués: si hubiera a los sumo dos [math]n-cliqués los podemos reventar sacándoles un vértice en común. Supongamos entonces que [math]G contiene exactamente [math]m\ge 3 [math]n-cliqués, los cuales denotamos [math]C_1,C_2,\dots,C_m. Sea [math]M=\{1,2,\dots,m\}. Vamos a particionar al conjunto [math]V de los vértices de [math]G en varios subconjuntos, cada uno indexado por un subconjunto de [math]M. Lo hacemos de la siguiente forma: Para cada subconjunto [math]S=\{a_1,a_2,\dots,a_t\} (posiblemente vacío) de [math]M, [math]V_S es el conjunto de aquellos vértices de [math]G que pertenecen exactamente a los [math]n-cliqués [math]C_{a_1},C_{a_2},\dots,C_{a_t}. Más precisamente,

[math]V_S=\{v\in V|v\in C_i\iff i\in S\}.

Es inmediato verificar las siguientes observaciones:

[math]\bullet [math]V=\bigcup_{S\subset M} V_S es una partición de [math]V como una unión de subconjuntos disjuntos. En particular,

[math]\sum_{S\subset M}|V_S|=2n-1\ \ (1)

[math]\bullet [math]V_S es un cliqué para cada [math]S\subset M.
[math]\bullet [math]|V_M|=0, pues en caso contrario al retirar un vértice de [math]V_M se destruyen todos los [math]n-cliqués, contradiciendo la hipótesis del enunciado.
[math]\bullet Para cada [math]1\le i\le m, se tiene que [math]C_i=\bigcup_{i\in S\subset M} V_S. En particular,

[math]\sum_{i\in S\subset M}|V_S|=n\ \ (2)

Más aún, sumando sobre estas [math]m igualdades, cada término [math]|V_S| se suma una vez por cada [math]i\in S, y entonces es fácil ver que obtenemos

[math]\sum_{S\subset M}|S||V_S|=mn\ \ (3)

[math]\bullet Sea [math]F una familia de subconjuntos de [math]M tal que [math]I\cap J\neq \phi para cada [math]I,J\subset F. Entonces [math]\bigcup_{S\in F}V_S es un cliqué. Esta es una observación crucial a la que recurriremos como (*).

Al hacer la resta [math](3)-(1) nos queda que

[math]\sum_{S\subset M}(|S|-1)|V_S|=(m-2)n+1\ \ (4)

Ahora viene la idea principal, que va a ser la siguiente: Construiremos inductivamente subconjuntos [math]D_1,D_2,\dots,D_{m-2} de vértices de [math]V con las dos siguientes propiedades:
i. Cada [math]D_i es un cliqué.
ii.

[math]\sum_{1\le i\le m-2}|D_i|=\left(\sum_{S\subset M,S\neq \phi,M}(|S|-1)|V_S|\right)+(m-2)|V_M|.

En tal caso habremos terminado porque tendremos que, como [math]|V_M|=0 y [math]-|V_{\phi}| solo resta,

[math]\sum_{1\le i\le m-2}|D_i|=\left(\sum_{S\subset M,S\neq \phi,M}(|S|-1)|V_S|\right)+(m-2)|V_M|\ge

[math]\sum_{S\subset M}(|S|-1)|V_S|=(m-2)n+1

y entonces por Principio del Palomar alguno de los cliqués [math]D_i tendrá al menos [math]\left\lceil \frac{(m-2)n+1}{m-2}\right\rceil=n+1 elementos, una contradicción a la suposición de que no hay [math]n+1-cliqués.

Vamos a los ejemplos de la construcción para entender lo que haremos. Escribimos por comodidad [math]V_S=(s:s\in S). Entonces, por ejemplo [math]V_{\{1,3,4\}}=(1,3,4).

Para [math]m=3, podemos considerar simplemente [math]D_1=(1,2)\cup(1,3)\cup(2,3)\cup(1,2,3). Por (*), [math]D_1 es un cliqué, y encima verifica la igualdad ii.

Para [math]m=4, tomamos el [math]D_1 que teníamos antes y le agregamos los mismos subconjuntos pero agregandoles el número [math]4. Nos quedaría

[math]D_1=(1,2)\cup(1,3)\cup(2,3)\cup(1,2,3)\cup(1,2,4)\cup(1,3,4)\cup(2,3,4)\cup(1,2,3,4)

que trivialmente sigue cumpliendo (*) entonces [math]D_1 es un cliqué. Definimos [math]D_2 como sigue: [math]D_2 es la unión de todos los [math]V_S con [math]S\subset \{1,2,3,4\} tales que [math]4\in S pero [math]S\neq \{4\}, y además le agregamos al final el [math](1,2,3). Nos quedaría

[math]D_2=(1,4)\cup(2,4)\cup(3,4)\cup(1,2,4)\cup(1,3,4)\cup(2,3,4)\cup(1,2,3,4)\cup(1,2,3)

Notar a ojo en este caso chico que [math]D_2 resulta un cliqué (después lo demostraremos en el paso inductivo, por ahora solo veamos la idea). Y además se verifica fácilmente a mano la igualdad ii.

Para [math]m=5, hacemos con [math]D_1 y [math]D_2 lo que para [math]m=4 hicimos sólo con [math]D_1, y definimos [math]D_3 en forma análoga a como definimos [math]D_2 para [math]m=4. Nos quedaría

[math]D_1=(1,2)\cup(1,3)\cup(2,3)\cup(1,2,3)\cup(1,2,4)\cup(1,3,4)\cup(2,3,4)\cup(1,2,3,4)\cup
[math](1,2,5)\cup(1,3,5)\cup(2,3,5)\cup(1,2,3,5)\cup(1,2,4,5)\cup(1,3,4,5)\cup(2,3,4,5)\cup(1,2,3,4,5)
[math]D_2=(1,4)\cup(2,4)\cup(3,4)\cup(1,2,4)\cup(1,3,4)\cup(2,3,4)\cup(1,2,3,4)\cup(1,2,3)\cup
[math](1,4,5)\cup(2,4,5)\cup(3,4,5)\cup(1,2,4,5)\cup(1,3,4,5)\cup(2,3,4,5)\cup(1,2,3,4,5)\cup(1,2,3,5)
[math]D_3=(1,5)\cup(2,5)\cup(3,5)\cup(4,5)\cup(1,2,5)\cup(1,3,5)\cup(1,4,5)\cup(2,3,5)\cup(2,4,5)\cup
[math](3,4,5)\cup(1,2,3,5)\cup(1,2,4,5)\cup(1,3,4,5)\cup(2,3,4,5)\cup(1,2,3,4,5)\cup(1,2,3,4)

Si se fijan estos subconjuntos cumplen con i y también la cuenta de ii (se puede ver a mano).

Ahora al paso inductivo. Supongamos que para algún [math]m\ge 3 hemos conseguido subconjuntos [math]D_1,D_2,\dots,D_{m-2}
con las propiedades de arriba. Hallemos una tal familia para [math]m+1. Consideremos los conjuntos [math]D_i'=D_i\cup(D_i+(m+1)) donde abusando un poco de notación, [math]D_i+(m+1)=\{d_i\cup\{m+1\}|d_i\in D_i\}. Es fácil ver que los [math]D_i' son cliques porque si [math]D_i cumple (*) entonces se verifica también fácilmente para [math]D_i'. Definimos el conjunto [math]D_{m-1}' como sigue: [math]D_{m-1}' es la unión de todos los [math]V_S tales que [math]S\subset \{1,2,\dots,m+1\}, [math]m+1\in S, [math]S\neq \{m+1\}, y encima agregamos por último el conjunto [math](1,2,\dots,m). [math]D_{m-1}' cumple con (*) porque: si [math]V_S,{V_S'}\in D_{m-1}' y [math]m+1\in S,S' ya está ([math]V_S y [math]V_{S'} tendrían intersección no vacía). El único caso a considerar es entonces el que involucra al conjunto [math]\{1,2,\dots,m\}, pero este se interseca trivialmente con cualquier otro [math]S que aparece en [math]D_{m-1}' porque [math]|S|\ge 2 (acá es donde usamos que no estamos incluyendo el [math]S=\{m+1\}) Ahora verifiquemos la cuenta monstruosa en ii. Usando la hipótesis inductiva, miremos la suma

[math]\sum_{1\le i\le m-1}|D_i'|=\sum_{1\le i\le m-2}|D_i|+\sum_{1\le i\le m-2}|D_i\cup(m+1)|+|D_{m-1}'|

que queremos ver que es igual a

[math]\left(\sum_{S\subset M+1,S\neq \phi,M+1}(|S|-1)|V_S|\right)+((m+1)-2)|V_{M+1}|.

Pero usando la hipótesis inductiva,

[math]\bullet \sum_{1\le i\le m-2}|D_i|=\left(\sum_{S\subset M,S\neq \phi,M}(|S|-1)|V_S|\right)+(m-2)|V_M|,

[math]\bullet \sum_{1\le i\le m-2}|D_i\cup(m+1)|=\left(\sum_{S\subset M,S\neq \phi,M}(|S|-1)|V_{S\cup\{m+1\}}|\right)+(m-2)|V_{M\cup\{m+1\}}|=

[math]\left(\sum_{m+1\in S\subset M+1,S\neq M+1}(|S|-2)|V_S|\right)+((m+1)-3)|V_{M+1}|.

[math]\bullet |D_{m-1}'|=\left(\sum_{m+1\in S\subset M+1,S\neq\{m+1\}}|V_S|\right)+|V_M|.

Ahora solo hay que verificar que cada cosa está en su lugar: Si [math]S es un subconjunto propio de [math]\{1,2,\dots,m\}=M, entonces [math]|V_S| aparece sumado [math]|S|-1 veces en la primer suma. Si [math]S=M entonces [math]|V_M| aparece sumado [math]m-2 veces en la primera suma y una última vez en la tercera (la aparición que nos da [math]D_{m-1}'), o sea en total [math]m-1. Los [math]|V_S| con [math]S\subset \{1,2,\dots,m+1\} propios que contienen al [math]m+1 pero no son [math]S=\{m+1\} aparecen sumados [math]|S|-2 veces en la segunda suma, mas una última vez en la tercer suma, dándonos [math]|S|-1 apariciones en total. Por último, para [math]S=\{1,2,\dots,m+1\}=M+1, [math]|V_{M+1}| aparece sumado [math]((m+1)-3) veces en la segunda suma, y una última en la tercera, es decir en total [math]((m+1)-2) veces. O sea que todo está en su lugar y el paso inductivo se completa.

Con esto hecho, ahora en nuestro problema podemos construir [math]D_1,D_2,\dots D_{m-2} con las propiedades i y ii, llevándonos a la existencia de un [math]n+1-cliqué, contradicción!

Se cumplen 10 años desde que empecé a pensar este problema. Finalmente creo que me salió. La solución es algo distinta a la de Prillo.

Spoiler: mostrar

Antes de empezar: llamo $G$ al grafo y asumo que la cantidad de vértices es a lo sumo $2n-1$ y lo que hay que probar es que tiene un $n+1$-clique. (Si el grafo tiene al menos $2n$ vértices puede no haber un $n+1$-clique, por ejemplo si hay dos $n$-cliques disjuntos.)

Sea $u_1$ un vértice, y sea $A_1$ un $n$-clique en $G \smallsetminus \{u_1\}$. Sea $u_2 \in A_1$, y sea $A_2$ un $n$-clique en $G \smallsetminus \{u_2\}$. Sea $u_3 \in A_1 \cap A_2$ (si no es vacío), y sea $A_3$ un $n$-clique en $G \smallsetminus \{u_3\}$. Continuando este proceso obtenemos $k$ $n$-cliques $A_1, \ldots, A_k$ tales que $A_1 \cap \cdots \cap A_k = \emptyset$ pero $A_1 \cap \cdots \cap A_{k-1} \neq \emptyset$. Notar que $k\geqq 3$, ya que $k\neq1$ porque $A_1 \neq \emptyset$, y $k\neq2$ porque si $A_1 \cap A_2 = \emptyset$, $|A_1 \cup A_2| = 2n$, pero hay a lo sumo $2n-1$ vértices.

Supongamos que $i\in\{1,\ldots,k\}$ cumple que $\bigcap_{j\neq i} A_j = \emptyset$. Sea $G'$ un grafo formado con los vértices de $G$ y las aristas de los cliques $A_j$ con $j\neq i$. Cumple la condición: si $u\in G'$, como $\bigcap_{j\neq i} A_j = \emptyset$ hay $j\neq i$ con $u\not\in A_j$, luego hay un $n$-clique en $G'\smallsetminus\{u\}$. Bastaría probar que hay un $n+1$-clique en $G'$, ya que también estará presente en $G$. Por lo tanto podemos asumir que, para todo $i$, $\bigcap_{j\neq i} A_j \neq \emptyset$. Es más, asumimos que las aristas de $G$ son sólo aquellas presentes en los cliques $A_i$; es decir, $u,v$ están conectados si y sólo si pertenecen a un mismo clique $A_i$.

Si $j=1,\ldots,k$ sea $\Gamma_j$ el conjunto de vértices de $G$ que están en exactamente $j$ de los $n$-cliques $A_i$, y sea $N_j = |\Gamma_j|$. Tenemos que $|A_1| + \cdots + |A_k| = kn$, y también es $N_1 + 2N_2 + \cdots + kN_k$, por lo que $\sum_{j=1}^k jN_j = kn$. Notar que por lo anterior $N_k=0$ y $N_{k-1} \geqq 1$.

Si $u\in\Gamma_r$ y $v\in\Gamma_s$ con $r+s\geqq k+1$ entonces $u$ y $v$ están conectados; en efecto, si $U$ es el conjunto de cliques en los que está $u$ y $V$ en los que está $v$, tenemos $|U \cap V| = r + s - |U \cup V| \geqq k + 1 - k = 1$, por lo que están en un clique común, y por lo tanto están conectados. En particular $\Gamma_{k-1}$ es un clique ya que $2(k-1) \geqq k+1$ pues $k\geqq 3$, y si $B \subset \Gamma_2 \cup \cdots \cup \Gamma_{k-2}$ es un clique, entonces $B \cup \Gamma_{k-1}$ también.

Vamos a probar el teorema por inducción. El caso $n=2$ es obvio. Suponemos que el teorema es cierto para $n-1$ y lo vamos a probar para $n$.

Supongamos que $N_1 \neq 0$. Sea pues $u \in \Gamma_1$, y sea $i$ con $u \in A_i$. Vimos que podemos asumir que $\bigcap_{j\neq i} A_j \neq \emptyset$, así que sea $v \in \bigcap_{j\neq i} A_j$. Veamos que $G' = G \smallsetminus \{u, v\}$ cumple las condiciones del teorema para $n-1$. En efecto, si $w$ es un vértice de $G'$, hay $j$ con $w\not\in A_j$; si $j=i$, como $v\not\in A_i$ tenemos que $A_i \smallsetminus \{u\}$ es un $n-1$-clique en $G' \smallsetminus \{w\}$; si $j\neq i$, como $u\not\in A_j$ tenemos que $A_i \smallsetminus \{u\}$ es un $n-1$-clique en $G' \smallsetminus \{w\}$; en ambos casos en $G' \smallsetminus \{w\}$ hay un $n-1$-clique. Por lo tanto, por hipótesis inductiva, hay un $n$-clique $B$ en $G \smallsetminus \{u, v\}$. Veamos que $B \cup \{v\}$ es un $n+1$-clique. Esto sólo podría no ocurrir si hay $w \in B$ que sólo está en $A_i$, ya que si está en $A_j$ con $j\neq i$, como $v\in A_j$, $u$ y $v$ están conectados. Ahora si hay $w\in B$ que sólo está en $A_i$, para que esté conectado al resto de los vértices de $B$ debe suceder que $B = A_i$, pero $u\not\in B$ ya que $B\subset G \smallsetminus \{u, v\}$. Probamos, pues, que si $N_1 \neq 0$ hay un $n+1$-clique, y terminamos.

Supongamos, para terminar, que $N_1 = 0$. Tenemos que $2N_2 + \cdots + (k-1)N_{k-1} = kn$. Veamos que en $C=\Gamma_2 \cup \cdots \cup \Gamma_{k-2}$ hay un clique de tamaño al menos $\left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil$. En efecto, si $a_i = |C \cap A_i|$ tenemos $a_1 + \cdots + a_k = 2N_2 + \cdots + (k-2)N_{k-2}$, por lo que hay $i$ con $a_i \geqq \left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil$. Esos vértices están en $C$ y en $A_i$, por lo que forman un clique $B$ de tamaño al menos $\left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil$, como dije. Como probé antes, $B \cup \Gamma_{k-1}$ es un clique, de tamaño al menos $\left\lceil \frac{2N_2 + \cdots + (k-2)N_{k-2}}k \right\rceil + N_{k-1} = \left\lceil \frac{2N_2 + \cdots + (k-1)N_{k-1}}k + \frac{N_{k-1}}k \right\rceil = n+1$, como queríamos.

Se me ocurrio una solucion mucho mas facil!

Spoiler: mostrar

Vamos a probar por induccion en $n$ que si un grafo no vacio es amigable de orden $n$ y no tiene $n+1$-cliques entonces tiene al menos $2n$ vertices. La cota no se puede mejorar porque podes tomar dos $n$-cliques separados. El caso $n = 0$ es trivial.

Sea $n \geq 1$, y considero un grafo no vacio amigable de orden $n$ sin $n+1$-cliques. Tomo un vertice y encuentro un $n$-clique $C_1$ que no lo contiene. Tomo un vertice en $C_1$ y encuentro un $n$-clique $C_2$ que no lo contiene. Tomo un vertice en $C_1 \cap C_2$ y encuentro un $n$-clique $C_3$ que no lo contiene. Sigo hasta obtener $n$-cliques $C_1, \ldots, C_l$ con $l\geq 2$ tales que $C_1 \cap \cdots \cap C_l = \varnothing$, pero $U := C_1 \cap \cdots \cap C_{l-1} \neq \varnothing$. Sea $V := C_1 \cup \cdots \cup C_{l-1} \smallsetminus U$. Tenemos que $U$ es un clique, $|U| \geq 1$, y si $u \in U$, $v \in V$ entonces $uv$ es una arista. Si $V$ contiene un $n - |U| + 1$-clique $W$ entonces $U \cup W$ es un $n+1$-clique, absurdo, luego $V$ no contiene $n - |U| + 1$-cliques. Ahora bien, notar que $V$ es amigable de orden $n - |U|$, ya que los $C_i \smallsetminus U$ son $n - |U|$-cliques con interseccion vacia. Por hipotesis inductiva tenemos que $|V| \geq 2(n - |U|)$.

Notar que $C_l \cap U = C_1 \cap \cdots \cap C_l = \varnothing$ y $C_l \cap V$ es un clique, asi que $|C_l \cap V| \leq n - |U|$. Entonces $|U \cup V \cup C_l| = |U| + |V| + |C_l| - |C_l \cap V| \geq |U| + 2(n - |U|) + n - (n - |U|) = 2n$, como queriamos.