pith. sign in

arxiv: 1806.00783 · v1 · pith:UXGLIJE7new · submitted 2018-06-03 · 🧮 math.CO · math.LO

Chromatic numbers of directed hypergraphs with no "bad" cycles

classification 🧮 math.CO math.LO
keywords chromaticcyclecyclesdigraphdirectionedgesproofrule
0
0 comments X
read the original abstract

Imagine that you are handed a rule for determining whether a cycle in a digraph is "good" or "bad", based on which edges of the cycle are traversed in the forward direction and which edges are traversed in the backward direction. Can you then construct a digraph which avoids having any "bad" cycles, but has arbitrarily large chromatic number? We answer this question when the rule is described in terms of a finite state machine. The proof relies on Nesetril and Rodl's structural Ramsey theory of posets with a linear extension. As an application, we give a new proof of the Loop Lemma of Barto, Kozik, and Niven in the special case of bounded width algebras.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.