Kurt Gödel Research Center

2017 seminar talk: Cycle Reversions and Dichromatic Number in (Infinite) Tournaments

Talk held by Paul Ellis (Manhattanville College, New York, USA) at the KGRC seminar on 2017-11-16.

Abstract

The dichomatic number for a digraph is the least number of acyclic subgraphs needed to cover the graph. In 2005, Pierre Charbit showed that by iterating the operation $\{\{$select a directed cycle, and reverse the direction of each arc in it$\}\}$ that the dichromatic number in any finite digraph can be lowered to 2. This is optimal, as a single directed cycle will always have dichromatic number 2. Recently, Daniel Soukup and I showed that the same is true for infinite tournaments of any cardinality, and in fact, we proved this by induction. Along the way to proving this, we uncovered some nice structural facts about infinite digraphs that we think are of more general interest. While this talk will be mostly graph theoretic in flavor, we did need to put on our set theory glasses to distinguish between the singular and regular cases in the induction. I should note that the question remains open for arbitrary inifinite digraphs, even those of countable cardinality.