2017/07/25 by Boyadzhiyska, Simona, Isaak, Garth, Trenk, Ann N
#05-C75 #06-A06 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1707.08093
A poset P = (X,\prec) has an interval representation if each x ∈ X can be assigned a real interval Ix so that x \prec y in P if and only if Ix lies completely to the left of Iy. Such orders are called interval orders. In this paper we give a surprisingly simple forbidden poset characterization of those posets that have an interval representation in which each interval length is either 0 or 1. In addition, for posets (X,\prec) with a weight of 1 or 2 assigned to each point, we characterize those that have an interval representation in which for each x ∈ X the length of the interval assigned to x equals the weight assigned to x. For both these problems we can determine in polynomial time whether the desired interval representation is possible and in the affirmative case, produce such a representation.