Title: Gallai and transitive colorings
Abstract:
An edge-coloring of the complete graph K_n is called *Gallai* if it contains no rainbow triangle, namely a triangle with edges of (three) different colors. This concept was applied in a seminal paper of Gallai (1967) to characterize comparability graphs, and has been extensively studied since then. For example, the anti-Ramsey problem posed by Erd\H{o}s, Simonovits and S\'{o}s (1975) asks for the maximal number of colors in an edge-coloring of K_n with no rainbow subgraph isomorphic to a given graph H. For H = K_3 they showed that the number is n-1.
An analogue of this notion for directed graphs was introduced by Berenstein, Greenstein and Li (2017), in their study of monomial braidings. Consider the transitive tournament tK_n, with vertices 1, ..., n and a directed edge (i,j) for any i < j. A coloring f of the edges of tK_n is called *transitive* if $f(i,k) \in \{f(i,j), f(j,k)\}$, for all i < j < k. Clearly, a transitive coloring of tK_n induces a Gallai coloring of the underlying K_n, but not conversely.
We plan to describe various enumerative, structural and algebraic aspects of Gallai and transitive colorings, as well as extensions far beyond complete graphs. For example, the number of *maximal* (namely, using exactly n-1 colors) Gallai colorings of K_n is the double factorial (2n-3)!!, while the number of maximal transitive colorings of tK_n is the Catalan number C_{n-1}. On the structural side, every maximal Gallai coloring (and every maximal transitive coloring) contains a rainbow hamiltonian path, and also an edge with a unique color. On the algebraic side, corresponding quasisymmetric functions are in fact symmetric and Schur-positive, and there are connections to Orlik-Terao algebras of hyperplane arrangements.
The talk is based on joint works with Arkady Berenstein, Jacob Greenstein, Jianrong Li, Avichai Marmor and Yuval Roichman.