Acyclic Dichromatic Number of Tournaments: these are the Champions

Technische Samenvatting: Acyclische Dichromatische Getal van Toernooien

Probleemstelling
Dit artikel onderzoekt het acyclische dichromatische getal ($\vec{\chi}_a$) van georiënteerde grafen, specifiek binnen de context van toernooien. Een acyclische $k$-dicoloring is een vertex-partitie in $k$ verzamelingen waarvoor de door een enkele deelverzameling geïnduceerde subdigraaf acyclisch is, en de georiënteerde bipartiete graaf tussen twee deelverzamelingen eveneens acyclisch is. Het acyclische dichromatische getal is het minimum aantal $k$ dat vereist is voor een dergelijke partitie.

De auteurs behandelen twee specifieke vermoedens opgesteld door Bang-Jensen, Picasarri-Arrieta en Yeo [4]:

1. Karakterisering van Champions: Het identificeren van welke toernooien $H$ "champions" zijn (analoog aan "heroes" in de standaard dichromatische getaltheorie), wat betekent dat elk $H$-vrij toernooi een begrensde acyclische dichromatische getal heeft.
2. Local-to-Global Eigenschap: Bepalen of het acyclische dichromatische getal van een toernooi begrensd wordt door een functie van het maximale acyclische dichromatische getal van de uit-nabijheden van de vertices ervan.

Methodologie
Het artikel maakt gebruik van structurele graaftheorie en Ramsey-achtige argumenten om grenzen te stellen aan het acyclische dichromatische getal.

• Dimatchings: Een centraal instrument dat wordt geïntroduceerd is de dimatching, gedefinieerd als een verzameling evenwijdig disjuncte bogen $\{a_1b_1, \dots, a_kb_k\}$ zodanig dat $a_i \to b_j$ als $i=j$ en $a_i \leftarrow b_j$ als $i \neq j$. De auteurs maken gebruik van een resultaat van Bang-Jensen et al. [4] dat stelt dat de aanwezigheid van een grote dimatching een hoog acyclisch dichromatisch getal impliceert.
• Ramsey-theorie: Het bewijs maakt gebruik van de Erdős-Moser stelling [8] betreffende de aanwezigheid van transitieve subtornooien in grote toernooien om specifieke structurele configuraties (specifiek het toernooi $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) te lokaliseren binnen toernooien die grote dimatchings bevatten.
• Reductie naar Bipartiete Grafen: Om de aanwezigheid van grote dimatchings te bewijzen in toernooien met een hoog acyclisch dichromatisch getal, reduceren de auteurs het probleem tot eigenschappen van bipartiete grafen. Zij maken gebruik van een resultaat door Atminas [2] betreffende induced matchings en co-matchings in bipartiete grafen. Specifiek relateren zij het acyclische dichromatische getal van een bipartiete toernooi aan de afwezigheid van een induced $2K_2$ (induced matchings van grootte 2) in de onderliggende ongerichte bipartiete graaf.
• Recursieve Partitie: De bewijzen omvatten het decomponeren van toernooien in transitieve verzamelingen en het analyseren van de interacties tussen deze verzamelingen met behulp van corollaria afgeleid van Lemma 9, die het acyclische dichromatische getal van een digraaf begrenst op basis van zijn geïnduceerde subdigrafen.

Belangrijkste Bijdragen en Resultaten

1. Bevestiging van de Champion Conjecture (Theorem 3):
   De auteurs bewijzen dat een toernooi $H$ een champion is dan en slechts dan als het isomorf is aan een subtornooi van $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ voor een bepaalde integer $k \ge 1$.

   • Mechanisme: Zij demonstreren dat elk toernooi met een voldoende grote dimatching een subtornooi bevat dat isomorf is aan $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$. Aangezien grote dimatchings een hoog acyclisch dichromatisch getal afdwingen, heeft elk toernooi dat deze specifieke structuur vermijdt een begrensde acyclische dichromatische getal.

2. Bestaan van Dimatchings (Theorem 4):
   Het artikel stelt een functie $f: \mathbb{N} \to \mathbb{N}$ vast zodanig dat elk toernooi met een acyclisch dichromatisch getal van ten minste $f(k)$ een dimatching van grootte $k$ bevat.

   • Mechanisme: Dit resultaat berust op de stelling van Atminas [2] betreffende bipartiete grafen. Door aan te tonen dat indien een toernooi een grote dimatching mist, de structuur ervan kan worden gepartitioneerd in een begrens aantal transitieve verzamelingen met specifieke bipartiete interacties, begrenzen de auteurs het acyclische dichromatische getal.

3. Bevestiging van de Local-to-Global Eigenschap (Theorem 5):
   De auteurs bewijzen het bestaan van een functie $g: \mathbb{N} \to \mathbb{N}$ zodanig dat voor elk toernooi $T$, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$.

   • Mechanisme: Dit wordt afgeleid als een consequentie van Theorem 4. Indien een toernooi een groot acyclisch dichromatisch getal heeft, bevat het een grote dimatching. De structuur van deze dimatching zorgt ervoor dat de uit-nabijheid van bepaalde vertices een grote dimatching bevat, wat daarmee een hoog acyclisch dichromatisch getal in de lokale nabijheid afdwingt.

Betekenis en Claims
Het artikel bevestigt twee vermoedens van Bang-Jensen, Picasarri-Arrieta en Yeo [4], waarmee het de karakterisering van "champions" voor het acyclische dichromatische getal voltooit en de local-to-global eigenschap vaststelt.

De auteurs merken op dat hoewel de voorwaartse implicatie van de champion-karakterisering (dat champions de specifieke vorm moeten hebben) eerder bekend was, het omgekeerde (dat toernooien van deze vorm inderdaad champions zijn) de nieuwe bijdrage van dit werk is. Bovendien biedt het artikel in de appendix een alternatief bewijs voor Theorem 3 dat niet steunt op Theorem 4 of de resultaten van Atminas, wat volgens de auteurs betere bovengrenzen oplevert en mogelijk van onafhankelijk belang kan zijn voor toekomstig onderzoek.

Het werk overbrugt de kloof tussen het goed begrepen dichromatische getal (waarbij "heroes" worden gekarakteriseerd door een specifieke recursieve structuur) en het restrictievere acyclische dichromatische getal, waarbij wordt aangetoond dat hoewel de structuren verschillen, de fundamentele eigenschappen van begrensdheid en lokaliteit voor beide parameters in toernooien standhouden.