NICE LABELING PROBLEM FOR EVENT STRUCTURES: A COUNTEREXAMPLE
In this paper, we present a counterexample to a conjecture of Rozoy and Thiagarajan from 1991 (also called the nice labeling problem) asserting that any (coherent) event structure with finite degree admits a labeling with a finite number of labels or, equivalently, that there exists a function f : N bar right arrow N such that an event structure with degree <= n admits a labeling with at most f(n) labels. Our counterexample is based on Burling's construction from 1965 of 3-dimensional box hypergraphs with clique number 2 and arbitrarily large chromatic numbers and the bijection between domains of event structures and median graphs established by Barthelemy and Constantin in 1993.
nice labeling event structure box hypergraph domain median graph cat(0) cubical complex