Exploramos cómo construir y hacer crecer secuencias de gráficos subcúbicos evitando menores repetidos. Veremos por qué su longitud máxima puede dispararse según las reglas de ocultación y los límites de grado.

Arrancamos con lo esencial. Un gráfico simple tiene nodos unidos por aristas sin bucles ni paralelas. Llamamos subcúbico al que limita el grado de cada nodo a como mucho tres. La ocultación aparece cuando un gráfico vive dentro de otro como menor, es decir, lo obtenemos quitando o contrayendo partes. El juego consiste en formar una secuencia donde cada elemento tiene más nodos que el anterior y ninguno contiene a los anteriores como menores.

¿Por qué crecen tanto estas secuencias? Porque al añadir nodos y mantener el grado acotado se multiplican las opciones estructurales, y cada elección puede escapar a los menores ya prohibidos. El teorema de los menores de grafos asegura que en cualquier colección infinita hay dos con relación de menor, así que si queremos una lista larga y libre de repeticiones, debemos hilar fino con las construcciones.

Veamos cifras ilustrativas en lenguaje llano. Con un punto de partida de un nodo se logra una longitud de dos siguiendo con un gráfico vacío. Si comenzamos con dos nodos, la longitud máxima alcanza cinco. Al aumentar las restricciones y arrancar con tres nodos, los resultados despegan y superan con holgura diez elevado a veintiocho. Sí, no necesitamos una pizarra infinita, pero casi.

Si relajamos las reglas y permitimos bucles y aristas paralelas, la película cambia aún más. El primer valor notable con bucles aparece en seis, y otras configuraciones se disparan hasta magnitudes que dejan muy atrás al famoso número de Graham. Abrir la puerta a bucles y paralelas aumenta la densidad local sin romper el tope de grado, y eso multiplica las formas de evitar menores ya vistos.

Para orientarnos, pensemos en tres ideas prácticas. Primera, crecer con paciencia: añadir un nodo y probar conexiones que no violen el grado máximo, comprobando que no introduce un menor prohibido. Segunda, usar invariantes sencillos como contar ciclos cortos, detectar puentes o mirar la arboricidad para intuir qué contracciones podrían aparecer. Tercera, cuando algo falla, retroceder y explorar ramificaciones cercanas en lugar de reiniciar desde cero.

Reto en modo juego, luego aprendemos. En parejas, partimos de un triángulo y añadimos un nodo por turno con como mucho tres conexiones, apuntando en una tarjeta qué menor evitamos cada vez; gana quien alcance la cadena más larga sin repetir menores.

Si te gusta convertir ideas complejas en retos jugables y fáciles de entender, te invitamos a visitar JeiJoLand.