Acyclic Dichromatic Number of Tournaments: these are the Champions

Resumen Técnico: Número Dicromático Acíclico de Torneos

Planteamiento del Problema
Este artículo investiga el número dicromático acíclico ($\vec{\chi}_a$) de grafos orientados, específicamente dentro del contexto de los torneos. Una $k$-dicoloración acíclica es una partición de vértices en $k$ conjuntos tal que el subdigrafo inducido por cualquier parte individual es acíclico, y el grafo bipartito orientado entre cualquier par de partes también es acíclico. El número dicromático acíclico es el mínimo $k$ requerido para tal partición.

Los autores abordan dos conjeturas planteadas por Bang-Jensen, Picasarri-Arrieta y Yeo [4]:

1. Caracterización de Campeones: Identificar qué torneos $H$ son "campeones" (análogos a "héroes" en la teoría estándar del número dicromático), es decir, que todo torneo libre de $H$ tiene un número dicromático acíclico acotado.
2. Propiedad Local-a-Global: Determinar si el número dicromático acíclico de un torneo está acotado por una función del número dicromático acíclico máximo de las vecindades de salida de sus vértices.

Metodología
El artículo emplea la teoría estructural de grafos y argumentos de tipo Ramsey para establecer cotas sobre el número dicromático acíclico.

• Dimatchings (Parejas de emparejamientos): Una herramienta central introducida es el dimatching, definido como un conjunto de arcos disjuntos por pares $\{a_1b_1, \dots, a_kb_k\}$ tales que $a_i \to b_j$ si $i=j$ y $a_i \leftarrow b_j$ si $i \neq j$. Los autores aprovechan un resultado de Bang-Jensen et al. [4] que establece que la existencia de un dimatching grande implica un alto número dicromático acíclico.
• Teoría de Ramsey: La demostración utiliza el teorema de Erdős-Moser [8] relativo a la existencia de subtorneos transitivos en torneos grandes para localizar configuraciones estructurales específicas (específicamente, el torneo $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) dentro de torneos que contienen dimatchings grandes.
• Reducción a Grafos Bipartitos: Para probar la existencia de dimatchings grandes en torneos con un alto número dicromático acíclico, los autores reducen el problema a propiedades de grafos bipartitos. Utilizan un resultado de Atminas [2] referente a emparejamientos inducidos y co-emparejamientos en grafos bipartitos. Específicamente, relacionan el número dicromático acíclico de un torneo bipartito con la ausencia de $2K_2$ inducido (emparejamientos inducidos de tamaño 2) en el grafo bipartito no dirigido subyacente.
• Partición Recursiva: Las demostraciones implican la descomposición de torneos en conjuntos transitivos y el análisis de las interacciones entre estos conjuntos utilizando corolarios derivados del Lema 9, que acota el número dicromático acíclico de un digrafo basado en sus subdigrafos inducidos.

Contribuciones Clave y Resultados

1. Confirmación de la Conjetura de los Campeones (Teorema 3):
   Los autores prueban que un torneo $H$ es un campeón si y solo si es isomorfo a un subtorneo de $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ para algún entero $k \ge 1$.

   • Mecanismo: Demuestran que cualquier torneo con un dimatching suficientemente grande debe contener un subtorneo isomorfo a $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$. Dado que los dimatchings grandes fuerzan un alto número dicromático acíclico, cualquier torneo que evite esta estructura específica debe tener un número dicromático acíclico acotado.

2. Existencia de Dimatchings (Teorema 4):
   El artículo establece una función $f: \mathbb{N} \to \mathbb{N}$ tal que cada torneo con un número dicromático acíclico al menos de $f(k)$ contiene un dimatching de tamaño $k$.

   • Mecanismo: Este resultado se apoya en el teorema de Atminas [2] sobre grafos bipartitos. Al mostrar que si un torneo carece de un dimatching grande, su estructura puede particionarse en un número acotado de conjuntos transitivos con interacciones bipartitas específicas, los autores acotan el número dicromático acíclico.

3. Confirmación de la Propiedad Local-a-Global (Teorema 5):
   Los autores prueban la existencia de una función $g: \mathbb{N} \to \mathbb{N}$ tal que para cualquier torneo $T$, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$.

   • Mecanismo: Esto se deriva como una consecuencia del Teorema 4. Si un torneo tiene un número dicromático acíclico grande, contiene un dimatching grande. La estructura de este dimatching asegura que la vecindad de salida de ciertos vértices contenga un dimatching grande, forzando así un alto número dicromático acíclico en la vecindad local.

Significancia y Reivindicaciones
El artículo confirma dos conjeturas de Bang-Jensen, Picasarri-Arrieta y Yeo [4], completando así la caracterización de los "campeones" para el número dicromático acíclico y estableciendo su propiedad local-a-global.

Los autores señalan que, si bien la implicación directa de la caracterización de campeones (que los campeones deben tener la forma específica) era conocida previamente, la inversa (que los torneos de esta forma son efectivamente campeones) es la contribución novedosa de este trabajo. Además, el artículo proporciona una prueba alternativa para el Teorema 3 en el apéndice que no depende del Teorema 4 ni del resultado de Atminas, lo cual los autores sugieren que produce cotas superiores mejores y puede ser de interés independiente para investigaciones futuras.

El trabajo cierra la brecha entre el número dicromático bien comprendido (donde los "héroes" se caracterizan por una estructura recursiva específica) y el más restrictivo número dicromático acíclico, mostrando que, aunque las estructuras difieren, las propiedades fundamentales de acotación y localidad se mantienen para ambos parámetros en torneos.