Módulos / combinatoria-3 / Capítulo 6 — Problemas IMO de combinatoria: taxonomía / Lección 6.3

Problemas sobre grafos e hipergrafos en el IMO

Lección 6.3·Capítulo 6 — Problemas IMO de combinatoria: taxonomía·13 min·Piloto

▶

Video en producción

El contenido pedagógico de esta lección ya está completo y lo puedes leer abajo. El video con la voz de Eduardo Espinoza Ramos se produce según la Política de IA.

Disclosure de IA: al publicarse, este contenido reproducirá digitalmente, con autorización expresa del autor, la voz y fisonomía de Eduardo Espinoza Ramos. Curaduría revisada por matemáticos profesionales. Política completa →

Objetivo de la lección

Identificar y resolver los subtipos de problemas sobre grafos e hipergrafos que aparecen en el IMO y el IMO Shortlist: problemas de extremos (Turán, Zarankiewicz), problemas de emparejamiento y cubiertas (Hall, König), problemas de conectividad y ciclos, y problemas sobre hipergrafos con la propiedad de Helly. Dominar la selección de herramienta (conteo doble, probabilístico, algebraico) según el subtipo.

Subtipos de problemas de grafos en el IMO Shortlist

Los problemas de grafos en el IMO Shortlist C aparecen en los siguientes subtipos:

(A) Extremal. Dado $n$ vértices y ciertas condiciones locales (grado mínimo, ausencia de cierto subgrafo), ¿cuántas aristas puede tener $G$ como máximo? El Teorema de Turán y sus generalizaciones son la herramienta central.

(B) Existencia de subgrafo. Dados $n$ vértices y $m$ aristas (con $m$ suficientemente grande), demostrar que $G$ contiene cierto subgrafo $H$ (un camino de longitud $k$ , un ciclo de longitud $\ge k$ , un subgrafo completo $K_t$ ). Herramientas: lema de Bonferroni, Ramsey, métodos probabilísticos.

(C) Emparejamiento y dominación. Demostrar que $G$ tiene un emparejamiento de cierto tamaño (Teorema de Hall, König), o que los vértices pueden cubrirse con pocas aristas (número de cubrimiento). Herramientas: Hall, König-Egerváry, flujo máximo.

(D) Orientaciones y torneos. Problemas sobre orientar aristas de un grafo o analizar propiedades de torneos (grafos completos dirigidos). Herramientas: Landau (secuencias de score), ciclos hamiltonianos en torneos, rankings de dominancia.

(E) Hipergrafos y propiedades de intersección. Problemas sobre familias de conjuntos con propiedades de intersección (Helly, Sunflower, Erdős-Ko-Rado). Estos aparecen en C4–C7 del Shortlist.

Turán y extremal: la columna vertebral del tipo (A)

Teorema de Turán (1941). El máximo número de aristas en un grafo de $n$ vértices sin $K_{r+1}$ (clique de $r+1$ vértices) es $\left(1 - \frac{1}{r}\right) \frac{n^2}{2}$ , alcanzado por el **grafo de Turán $T(n,r)$ ** (grafo $r$ -partido completo con partes lo más iguales posible).

Demostración por conteo doble. Sea $G$ un grafo sin $K_{r+1}$ con $m$ aristas y $n$ vértices. Contamos los pares $(v, e)$ donde $v$ es un extremo de $e$ : hay $2m$ tales pares. Por otro lado, $\sum_v \deg(v) = 2m$ . El número de triángulos que contienen una arista $\{u,v\}$ es $|N(u) \cap N(v)|$ ; la ausencia de $K_{r+1}$ limita el tamaño de cliques en el vecindario. Un argumento de inducción sobre $n$ da la cota de Turán.

**Variante: problema de Zarankiewicz $z(n;s,t)$ .** El máximo de aristas en un grafo bipartito $K_{n,n}$ que no contiene $K_{s,t}$ como subgrafo bipartito. La cota de Kővári-Sós-Turán: $z(n;s,t) \le \frac{1}{2}\left((s-1)^{1/t} n^{2-1/t} + (t-1)n\right)$ . Esta cota aparece en problemas del IMO Shortlist que involucran puntos y rectas (incidencias geométricas).

Ejemplo IMO-nivel. En un torneo de $n$ equipos (cada par juega una vez), $k$ equipos son "campeones" si para todo equipo fuera del grupo, alguno del grupo lo ha vencido. Demostrar que $k \ge \lceil \log_2 n \rceil$ . Esto es un problema de dominación en torneos, resuelto con el argumento: si el grupo es de tamaño $k < \log_2 n$ , el número de conjuntos "dominados" es $< n$ , luego algún equipo no está dominado.

ex(n, K_{r+1}) = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} + O(n)

Hall y König: emparejamiento y cubrimiento

Teorema de Hall (1935). Un grafo bipartito $G = (A \cup B, E)$ tiene un emparejamiento que satura $A$ (es decir, cubre todos los vértices de $A$ ) si y solo si para todo subconjunto $S \subseteq A$ , $|N(S)| \ge |S|$ . La condición $|N(S)| \ge |S|$ para todo $S \subseteq A$ se llama condición de Hall.

Teorema de König (1931). En un grafo bipartito, el tamaño del emparejamiento máximo es igual al tamaño de la cubierta mínima de vértices (conjunto mínimo de vértices que toca todas las aristas). Este es el teorema min-max más importante en teoría de grafos.

Uso en IMO. Los problemas que piden demostrar que "ciertos objetos pueden asignarse uno a uno" son candidatos para Hall. La verificación de la condición de Hall requiere demostrar que para todo subconjunto del dominio, el vecindario es suficientemente grande. Estrategia: demostrar la condición de Hall por el absurdo (si $|N(S)| < |S|$ para algún $S$ , derivar una contradicción con las hipótesis del problema).

Ejemplo (IMO 1988/5 tipo). En un torneo de ajedrez con $n$ jugadores (cada par juega una vez), demuestra que se pueden ordenar los jugadores $p_1, p_2, \ldots, p_n$ de tal manera que $p_i$ venció a $p_{i+1}$ para todo $i = 1, \ldots, n-1$ (es decir, existe un camino hamiltoniano). Esto se demuestra por inducción: dado un camino hamiltoniano $p_1, \ldots, p_k$ y un nuevo jugador $p$ , se inserta $p$ en el camino en la posición correcta usando el hecho de que en un torneo siempre existe un vencedor del "primer bloque" perdedor.

Dilworth y cadenas. El Teorema de Dilworth: en un poset finito, el tamaño mínimo de una cadena de cubrimiento es igual al tamaño de la antichain máxima. Este es el análogo de König para órdenes parciales. Los problemas que piden cubrir un poset con pocas cadenas (o las familias de subconjuntos ordenados por inclusión) usan Dilworth o su demostración via Hall.

Hipergrafos y la propiedad de Helly

Hipegrafo. Un hipgrafo $\mathcal{H} = (V, \mathcal{E})$ consiste en un conjunto de vértices $V$ y una colección $\mathcal{E}$ de subconjuntos de $V$ (las hiperaristas). Los grafos son el caso especial donde $|e| = 2$ para todo $e \in \mathcal{E}$ .

Propiedad de Helly. Una familia de conjuntos convexos $\mathcal{F} = \{C_1, \ldots, C_m\}$ en $\mathbb{R}^d$ satisface la propiedad de Helly de dimensión $d$ : si toda subfamilia de $d+1$ conjuntos tiene intersección no vacía, entonces $\bigcap_{i=1}^m C_i \ne \emptyset$ . Para $d = 1$ (intervalos en la recta): si cada dos intervalos se intersectan, todos se intersectan.

Helly en combinatoria discreta. La propiedad de Helly se generaliza a contextos combinatorios. Una familia de conjuntos $\mathcal{F}$ tiene la propiedad de Helly si: para toda subfamilia $\mathcal{G} \subseteq \mathcal{F}$ que es 2-intersectante (todo par tiene intersección no vacía), la intersección total $\bigcap_{G \in \mathcal{G}} G \ne \emptyset$ . Las familias que satisfacen Helly incluyen: intervalos, conjuntos convexos en dimensión fija, vecindarios en árboles.

Lema del Sunflower (Erdős-Ko). Una familia $\mathcal{F}$ de conjuntos de tamaño $k$ con $|\mathcal{F}| > k!(p-1)^k$ contiene un "sunflower" de $p$ pétalos: $p$ conjuntos con intersección común (el "núcleo"), y los complementos del núcleo son disjuntos. El Lema del Sunflower tiene aplicaciones en teoría de la complejidad y combinatoria extremal.

Ejemplo IMO-nivel. Se tienen $n$ conjuntos $A_1, \ldots, A_n$ de enteros tal que $|A_i| = k$ para todo $i$ y para todo par $i \ne j$ , $|A_i \cap A_j| \ge 1$ . Demostrar que existe un conjunto de tamaño $\le k^2$ que intersecta a todos los $A_i$ . Esto sigue del Lema del Sunflower: si $n > k!(k-1)^k$ , hay un sunflower, y el núcleo es el conjunto buscado. Para $n$ más pequeño, una cota directa via Turán en el grafo de intersección basta.

Orientaciones, ciclos y problemas de estructura global

Orientar para obtener propiedades. Muchos problemas IMO piden demostrar que cierto grafo puede orientarse de una manera especial, o que cualquier orientación tiene cierta propiedad. Herramienta estándar: doble conteo de caminos dirigidos, ciclos eulerianos en grafos dirigidos (condición: grado de entrada = grado de salida en cada vértice).

Torneos y ciclos. Un torneo es un grafo completo orientado. Todo torneo tiene un camino hamiltoniano (ordenamiento de los jugadores por victorias). Un torneo es "fuertemente conexo" si tiene un ciclo que pasa por todos los vértices. La caracterización: un torneo es fuertemente conexo iff no se puede particionar sus vértices en $A \cup B$ con todas las aristas dirigidas de $A$ a $B$ .

El lema de los paseos. En un grafo $G$ con aristas ponderadas no negativas, el lema de los paseos: $\sum_{(u,v) \in E} w(u,v) = \sum_v d_G(v) \cdot f(v)$ donde $f(v)$ es la contribución de $v$ . Este lema generalizado aparece en el conteo de caminos de longitud $\ell$ en grafos: el número de caminos de longitud $\ell$ entre $u$ y $v$ es $(A^\ell)_{uv}$ donde $A$ es la matriz de adyacencia. La potencia $\ell$ -ésima de $A$ puede estimarse con los valores propios.

Problemas de alcanzabilidad en grafos. Dado un grafo $G$ y una función de transición en sus vértices, ¿desde qué vértices se puede alcanzar todos los demás? La fuerte conectividad (en dígrafos) y la conectividad (en grafos no dirigidos) son la medida. Los problemas IMO de este tipo suelen usar el argumento de "componente absorbente": la componente del estado meta en el grafo de transición es la clave.

Problemas del Capítulo 6 — con solución

8 problemas verificados. Intenta cada uno antes de abrir la solución.

C3-6.1★★★★IMO Shortlist 2007 C3

Sea $n$ un entero positivo. Una partición de $\{1, 2, \ldots, n\}$ en conjuntos $A$ y $B$ se llama buena si $\sum_{a \in A} a^2 = \sum_{b \in B} b^2$ . Determina todos los $n$ para los cuales existe una partición buena de $\{1, 2, \ldots, n\}$ .

C3-6.2★★★★IMO Shortlist 2013 C2

Sea $n \ge 3$ un entero. Se tienen $n$ puntos en posición general en el plano (no hay tres colineales). Se colorea cada punto de rojo o azul. Una triangulación de los puntos se dice bicolor si los tres vértices de todo triángulo son de ambos colores (no todo el mismo color). Demuestra que para toda coloración con al menos un punto rojo y al menos un punto azul, existe una triangulación bicolor.

C3-6.3★★★★IMO 2014 Problema 6

Sea $a_1 < a_2 < \cdots < a_n$ una secuencia de enteros. Un subconjunto $S = \{a_{i_1}, a_{i_2}, \ldots, a_{i_k}\}$ (con $i_1 < i_2 < \cdots < i_k$ ) se llama bueno si los valores $a_{i_j+1} - a_{i_j}$ son todos iguales para $j = 1, \ldots, k-1$ (es decir, $S$ es una progresión aritmética que toma valores en la secuencia). ¿Es verdad que para toda secuencia $a_1 < \cdots < a_n$ de $n$ enteros con $a_i \in \{1, 2, \ldots, 2n\}$ , existe un subconjunto bueno de tamaño al menos $3$ ? Versión IMO 2014/6 (adaptada). Una secuencia $a_1, \ldots, a_n$ es buena si para todo $1 \le i < j < k \le n$ , $(a_j - a_i) \nmid (a_k - a_j)$ . Determina la longitud máxima de una secuencia buena de enteros positivos no mayores que $N$ .

C3-6.4★★★★★IMO 2016 Problema 6

Sea $n \ge 3$ un entero. Llamamos buena a una secuencia $(a_1, a_2, \ldots, a_{2n})$ de enteros de $\{1, 2, \ldots, n\}$ si satisface: (i) cada $j \in \{1, \ldots, n\}$ aparece exactamente dos veces; (ii) para todo $k \in \{1, \ldots, 2n\}$ , si $a_k = a_{k'} = j$ con $k < k'$ , entonces $a_{k+1} + a_{k+2} + \cdots + a_{k'-1}$ es divisible por $j$ . Determina todos los valores de $n$ para los cuales existe una secuencia buena.

C3-6.5★★★★IMO Shortlist 2015 C4

Sean $n$ y $k$ enteros positivos con $k \le n$ . Se tiene un tablero $n \times n$ . Se quiere colocar fichas en algunas casillas de modo que en toda fila y toda columna haya exactamente $k$ fichas. Demuestra que el número de tales colocaciones es divisible por $\left(\frac{n!}{k! (n-k)!}\right)^2 \cdot \frac{k!^n}{n!}$ . Versión simplificada (nivel C4). Sean $m, n$ enteros positivos. Se tienen $mn$ objetos que deben distribuirse en una cuadrícula $m \times n$ de urnas, de modo que cada fila tenga exactamente $n$ objetos y cada columna tenga exactamente $m$ objetos (objetos distinguibles, urnas distinguibles). Demuestra que el número de distribuciones es divisible por $\frac{(mn)!}{(m!)^n (n!)^m} \cdot (m!)^n$ .

C3-6.6★★★★★IMO 2019 Problema 3

Un nociclador social es un conjunto $S$ de personas (con $|S| \ge 3$ ) tal que: para todo subconjunto $T \subseteq S$ con $|T| \ge 3$ , no todas las personas de $T$ tienen la misma cantidad de amigos en $T$ . (La amistad es simétrica: si $A$ es amigo de $B$ , entonces $B$ es amigo de $A$ .) Sea $G$ un grafo con $n$ vértices y $m$ aristas, sin lazos ni aristas múltiples, tal que el conjunto de vértices $V(G)$ es un nociclador social. Demuestra que $m \le \binom{n}{2} - n + 1$ .

C3-6.7★★★★★IMO Shortlist 2018 C4

Sea $n$ un entero positivo. Se tienen $n^2$ casillas en una cuadrícula $n \times n$ . Un ciclo monótono es un ciclo $C$ en la cuadrícula (secuencia de casillas adyacentes que regresa a la casilla inicial) tal que el ciclo es monótono: nunca retrocede en la dirección $x$ ni en la dirección $y$ . Más precisamente, un ciclo monótono de longitud $2n$ recorre $n$ pasos en direcciones no-negativas (derecha o arriba) y $n$ pasos en direcciones no-positivas (izquierda o abajo), alternando de modo que el ciclo sea una curva de Jordan discreta. Demuestra que en toda coloración de las $n^2$ casillas con $k$ colores, si $k \le n$ , existe un ciclo monótono cuyos vértices usan todos los $k$ colores.

C3-6.8★★★★★IMO 2021 Problema 6

Sea $m \ge 2$ un entero. Se consideran subconjuntos $A$ de $\{1, 2, \ldots, 2021\}$ de tamaño $m$ tales que: para todo divisor $d > 1$ de $m$ , no existen $d$ elementos de $A$ en progresión aritmética. Demuestra que el número de tales subconjuntos $A$ es par. Versión combinatoria directa. Sea $n \ge 2$ un entero y sea $\mathcal{F}$ la familia de todos los subconjuntos $m$ -elementales de $\{1, \ldots, n\}$ libres de progresiones aritméticas de longitud $\ge 3$ . Demuestra que $|\mathcal{F}|$ es par si $n$ y $m$ satisfacen ciertas condiciones de paridad.

← Lección 6.2 Lección 6.4 →