Acyclic Dichromatic Number of Tournaments: these are the Champions

Sintesi Tecnica: Numero Dicromatico Aciclico di Tornei

Enunciato del Problema
Questo articolo investiga il numero dicromatico aciclico ($\vec{\chi}_a$) di grafi orientati, specificamente nel contesto dei tornei. Un $k$-dicolorezza aciclica è una partizione dei vertici in $k$ insiemi tali che il sottografo indotto da ogni singolo insieme sia aciclico e il grafo bipartito orientato tra due qualsiasi insiemi sia anch'esso aciclico. Il numero dicromatico aciclico è il minimo $k$ richiesto per tale partizione.

Gli autori affrontano due congetture poste da Bang-Jensen, Picasarri-Arrieta e Yeo [4]:

1. Caratterizzazione dei Campioni: Identificare quali tornei $H$ sono "campioni" (analoghi agli "eroi" nella teoria standard del numero dicromatico), ovvero quei tornei tali che ogni torneo $H$-free ha un numero dicromatico aciclico limitato.
2. Proprietà Locale-Globale: Determinare se il numero dicromatico aciclico di un torneo sia limitato da una funzione del numero dicromatico aciclico massimo dei vicini uscenti dei suoi vertici.

Metodologia
Il lavoro impiega la teoria dei grafi strutturali e argomenti di tipo Ramsey per stabilire i limiti sul numero dicromatico aciclico.

• Dimatchings: Uno strumento centrale introdotto è il dimatching, definito come un insieme di archi disgiunti a coppie $\{a_1b_1, \dots, a_kb_k\}$ tali che $a_i \to b_j$ se $i=j$ e $a_i \leftarrow b_j$ se $i \neq j$. Gli autori sfruttano un risultato di Bang-Jensen et al. [4] secondo cui l'esistenza di un grande dimatching implica un alto numero dicromatico aciclico.
• Teoria di Ramsey: La dimostrazione utilizza il teorema di Erdős-Moser [8] riguardante l'esistenza di sottotornei transitivi in grandi tornei per localizzare specifiche configurazioni strutturali (specificamente, il torneo $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) all'interno di tornei contenenti grandi dimatchings.
• Riduzione a Grafi Bipartiti: Per dimostrare l'esistenza di grandi dimatchings in tornei con alto numero dicromatico aciclico, gli autori riducono il problema alle proprietà dei grafi bipartiti. Utilizzano un risultato di Atminas [2] riguardante i matchings indotti e i co-matchings in grafi bipartiti. Nello specifico, collegano il numero dicromatico aciclico di un torneo bipartito all'assenza di $2K_2$ indotto (matching indotto di dimensione 2) nel grafo bipartito non orientato sottostante.
• Partizione Ricorsiva: Le dimostrazioni comportano la decomposizione di tornei in insiemi transitivi e l'analisi delle interazioni tra questi insiemi utilizzando corollari derivati dal Lemma 9, che limita il numero dicromatico aciclico di un digrafo basandosi sui suoi sottodigrafi indotti.

Contributi Chiave e Risultati

1. Conferma della Congettura dei Campioni (Teorema 3):
   Gli autori dimostrano che un torneo $H$ è un campione se e solo se è isomorfo a un sottotorneo di $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ per qualche intero $k \ge 1$.

   • Meccanismo: Dimostrano che qualsiasi torneo con un dimatching sufficientemente grande deve contenere un sottotorneo isomorfo a $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$. Poiché i grandi dimatchings forzano un alto numero dicromatico aciclico, qualsiasi torneo che eviti questa specifica struttura deve avere un numero dicromatico aciclico limitato.

2. Esistenza di Dimatchings (Teorema 4):
   Il saggio stabilisce una funzione $f: \mathbb{N} \to \mathbb{N}$ tale che ogni torneo con un numero dicromatico aciclico almeno pari a $f(k)$ contenga un dimatching di dimensione $k$.

   • Meccanismo: Questo risultato si basa sul teorema di Atminas [2] riguardante i grafi bipartiti. Dimostrando che se un torneo manca di un grande dimatching, la sua struttura può essere partizionata in un numero limitato di insiemi transitivi con specifiche interazioni bipartite, gli autori limitano il numero dicromatico aciclico.

3. Conferma della Proprietà Locale-Globale (Teorema 5):
   Gli autori dimostrano l'esistenza di una funzione $g: \mathbb{N} \to \mathbb{N}$ tale che per ogni torneo $T$, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$.

   • Meccanismo: Ciò deriva come conseguenza del Teorema 4. Se un torneo ha un grande numero dicromatico aciclico, contiene un grande dimatching. La struttura di questo dimatching assicura che il vicinato uscente di certi vertici contenga un grande dimatching, forzando così un alto numero dicromatico aciclico nel vicinato locale.

Significato e Rivendicazioni
Il saggio conferma due congetture di Bang-Jensen, Picasarri-Arrieta e Yeo [4], completando così la caratterizzazione dei "campioni" per il numero dicromatico aciclico e stabilendo la sua proprietà locale-globale.

Gli autori osservano che, mentre l'implicazione diretta della caratterizzazione dei campioni (ovvero che i campioni debbano avere la specifica forma) era precedentemente nota, il inverso (ovvero che i tornei di questa forma siano effettivamente campioni) costituisce il contributo originale di questo lavoro. Inoltre, il saggio fornisce una prova alternativa per il Teorema 3 nell'appendice che non dipende dal Teorema 4 o dal risultato di Atminas, il che, secondo gli autori, produce limiti superiori migliori e potrebbe essere di interesse indipendente per la ricerca futura.

Il lavoro colma il divario tra il numero dicromatico ben compreso (dove gli "eroi" sono caratterizzati da una specifica struttura ricorsiva) e il numero dicromatico aciclico, più restrittivo, mostrando che, sebbene le strutture differiscano, le proprietà fondamentali di limitatezza e località valgono per entrambi i parametri nei tornei.