Segment Orders (2008)

Originators: Csaba Biró and William T. Trotter    (presented by Csaba Biro - REGS 2010)

Definitions: Consider the euclidean plane with the standard (x,y)- coordinate system. Say that a line segment s is regular if one endpoint is on the negative x-axis and the slope is positive. Equivalently, a regular segment s is a triple (s1,s2,s3) of real numbers with s2>0>s1 and s3>0 such that the endpoints are (s1,0) and (s2,s3).

Farhad Shahrokhi introduced two partial orders P1 and P2 on a family of regular segments. Given regular segments s and t, put s>t in P1 if

  1. s1<t1;
  2. s2>t2; and
  3. Any vertical line intersecting both s and t intersects s above t.

We put s>t in P2 when conditions (1), (2') and (3) are satisfied, where conditions (1) and (3) are the same as before, but (2') is s2<t2. Let P1 denote the class of posets that arise as P1 for some family of regular segments. Similarly, let P1 denote the class of posets that arise as P2.

Conjecture (Biró and Trotter [BT]): P1 ≠ P2.

Comments: It is surprising that this question is open. The two families of posets have many common properties. Both contain all posets of dimension at most 3. For k>3, each family contains infinitely many posets with dimension at least k but only a vanishing fraction all posets of dimension at least k. Both contain all interval orders.

The problem seems to be strongly related to stretchability questions about pseudoline arrangements; see [Go]. Basic knowledge about pseudoline arrangements may be relevant, see [Go].The stretchability question is NP-hard; see [Sh].

References:
[BT] Csaba Biró and William T. Trotter, Segment orders, Discrete Comput. Geom. 43, (2010), 680-704.
[Go] Jacob E. Goodman, Pseudoline arrangements, Handbook of discrete and computational geometry, 1997, pp. 83-109.
[Sh] Peter W. Shor, Stretchability of pseudolines is NP-hard, Applied geometry and discrete mathematics, 1991, pp. 531-554.