Yuval Roichman: Gallai colorings, transitivity and Schur-positivity

Abstract: A Gallai coloring of the complete graph is an edge-coloring with no rainbow triangle. This concept first appeared in the study of comparability graphs and anti-Ramsey theory. We introduce a transitive analogue for acyclic directed graphs and generalize these notions to Coxeter systems, loopless matroids and commutative algebras.

First, it is shown that the number of Gallai and transitive colorings in \(k\) colors is always a polynomial in \(k\). It is further shown that for any representable matroid the maximal number of colors is equal to the rank, generalizing a result of Erdös-Simonovits-Sós for complete graphs.

We count Gallai and transitive colorings of the root system of type \(A\) with a maximal number of colors, and show that, when equipped with a natural descent set map, the resulting quasisymmetric function is Schur-positive. The transitive commutative algebra of a Coxeter group will be presented. Open problems and conjectures regarding Hilbert series involve Stirling permutations and variants of Catalan numbers.

Based on Joint works with Ron Adin, Arkady Berenstein, Jacob Greenstein, Jianrong Li and Avichai Marmor.