Acyclic Dichromatic Number of Tournaments: these are the Champions

Resumo Técnico: Número Dicromático Acíclico de Torneios

Enunciado do Problema
Este artigo investiga o número dicromático acíclico ($\vec{\chi}_a$) de grafos orientados, especificamente no contexto de torneios. Uma $k$-dicoragem acíclica é uma partição de vértices em $k$ conjuntos, tal que o subdigrafo induzido por qualquer parte individual seja acíclico, e o grafo bipartido orientado entre quaisquer duas partes também seja acíclico. O número dicromático acíclico é o $k$ mínimo necessário para tal partição.

Os autores abordam duas conjecturas específicas propostas por Bang-Jensen, Picasarri-Arrieta e Yeo [4]:

1. Caracterização de Campeões: Identificar quais torneios $H$ são "campeões" (análogos a "heróis" na teoria do número dicromático padrão), ou seja, todo torneio livre de $H$ possui um número dicromático acíclico limitado.
2. Propriedade Local-para-Global: Determinar se o número dicromático acíclico de um torneio é limitado por uma função do número dicromático acíclico máximo das vizinhanças de saída de seus vértices.

Metodologia
O artigo emprega teoria de grafos estruturais e argumentos do tipo Ramsey para estabelecer limites no número dicromático acíclico.

• Dimatchings (Dimotivos): Uma ferramenta central introduzida é o dimatching, definido como um conjunto de arcos disjuntos entre si $\{a_1b_1, \dots, a_kb_k\}$ tal que $a_i \to b_j$ se $i=j$ e $a_i \leftarrow b_j$ se $i \neq j$. Os autores aproveitam um resultado de Bang-Jensen et al. [4] afirmando que a existência de um dimatching grande implica um alto número dicromático acíclico.
• Teoria de Ramsey: A prova utiliza o teorema de Erdős-Moser [8] referente à existência de subtorneios transitivos em grandes torneios para localizar configurações estruturais específicas (especificamente, o torneio $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) dentro de torneios contendo grandes dimatchings.
• Redução a Grafos Bipartidos: Para provar a existência de grandes dimatchings em torneios com alto número dicromático acíclico, os autores reduzem o problema às propriedades de grafos bipartidos. Eles utilizam um resultado de Atminas [2] sobre emparelhamentos induzidos e co-emparelhamentos em grafos bipartidos. Especificamente, eles relacionam o número dicromático acíclico de um torneio bipartido com a ausência de $2K_2$ induzido (emparelhamentos induzidos de tamanho 2) no grafo bipartido não direcionado subjacente.
• Particionamento Recursivo: As provas envolvem a decomposição de torneios em conjuntos transitivos e a análise das interações entre esses conjuntos usando corolários derivados do Lema 9, que limita o número dicromático acíclico de um digrafo com base em seus subdigrafos induzidos.

Principais Contribuições e Resultados

1. Confirmação da Conjectura dos Campeões (Teorema 3):
   Os autores provam que um torneio $H$ é um campeão se, e somente se, for isomorfo a um subtorneio de $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ para algum inteiro $k \ge 1$.

   • Mecanismo: Eles demonstram que qualquer torneio com um dimatching suficientemente grande deve conter um subtorneio isomorfo a $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$. Como grandes dimatchings forçam um alto número dicromático acíclico, qualquer torneio que evite essa estrutura específica deve possuir um número dicromático acíclico limitado.

2. Existência de Dimatchings (Teorema 4):
   O artigo estabelece uma função $f: \mathbb{N} \to \mathbb{N}$ tal que todo torneio com um número dicromático acíclico pelo menos $f(k)$ contém um dimatching de tamanho $k$.

   • Mecanismo: Este resultado baseia-se no teorema de Atminas [2] sobre grafos bipartidos. Ao mostrar que, se um torneio carece de um grande dimatching, sua estrutura pode ser particionada em um número limitado de conjuntos transitivos com interações bipartidas específicas, os autores limitam o número dicromático acíclico.

3. Confirmação da Propriedade Local-para-Global (Teorema 5):
   Os autores provam a existência de uma função $g: \mathbb{N} \to \mathbb{N}$ tal que, para qualquer torneio $T$, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$.

   • Mecanismo: Isto é derivado como uma consequência do Teorema 4. Se um torneio possui um grande número dicromático acíclico, ele contém um grande dimatching. A estrutura deste dimatching garante que a vizinhança de saída de certos vértices contenha um grande dimatching, forçando, assim, um alto número dicromático acíclico na vizinhança local.

Significância e Alegações
O artigo confirma duas conjecturas de Bang-Jensen, Picasarri-Arrieta e Yeo [4], completando assim a caracterização de "campeões" para o número dicromático acíclico e estabelecendo sua propriedade local-para-global.

Os autores observam que, embora a implicação direta da caracterização dos campeões (que campeões devem ter a forma específica) já fosse conhecida, a recíproca (que torneios desta forma são de fato campeões) é a contribuição inédita deste trabalho. Além disso, o artigo fornece uma prova alternativa para o Teorema 3 no apêndice que não depende do Teorema 4 ou do resultado de Atminas, o que os autores sugerem que produz melhores limites superiores e pode ser de interesse independente para pesquisas futuras.

O trabalho preenche a lacuna entre o número dicromático bem compreendido (onde os "heróis" são caracterizados por uma estrutura recursiva específica) e o número dicromático acíclico, mais restritivo, mostrando que, embora as estruturas difiram, as propriedades fundamentais de limitação e localidade mantêm-se para ambos os parâmetros em torneios.