i + 1.
Let F(t) be the largest integer h for which there is an -sequence (S0;::: ;Sh) with
Si f1;::: tg for all i.
Proposition 1.2.8. The following example is the longest -sequence with the subsets of
f1;2;3;4g.
(;;f1g;f2g;f3g;f4g;f2; 4g;f1;4g;f1; 3g;f1;2;3g;f2;3; 4g)
Corollary 1.2.9. F(4) = 9
Theorem 1.2.10 (Felsner and Trotter [10]). For every t 1
C(t) = F(t):
14
Consider the Boolean lattice of subsets of f1;::: ;ng. The Hasse diagram of this lattice
is isomorphic to the n-dimensional hypercube. We mentioned previously that this graph is
Hamiltonian. Let fS1;::: ;S2ng be a Hamiltonian path. We say it is monotone, if for every
i, either (a) every subset of Si appears among the sets S1;::: ;Si 1, or (b) only one (say S)
does not, furthermore Si+1 = S.
It is not known if the diagram of the subset lattice of f1;::: ;ng is Hamiltonian for all
n.
Felsner and Trotter also showed the following theorem.
Theorem 1.2.11.
F(t) 2t 1 +
t 1
2
with equality holding if and only if there is a monotone Hamiltonian path in the subset lattice
of f1;::: ;tg.
15
CHAPTER II
HEIGHT-SEQUENCE OF PARTIALLY ORDERED SETS
2.1 Introduction
In the following, we will study the height-sequence of a partially ordered set. We will use
the following notation.
De nition 2.1.1. Let x be an element of the partially ordered set P. Then hi(x) is the
number of linear extensions of P in which x is in the ith lowest position, in other words,
those linear extensions L, for which
jfy 2 P : y L xgj = i:
By this de nition, hi = 0 if i 0 or i > jPj. If it is clear from the context, we will
frequently omit x, simply writing hi.
Stanley proved in [23] that for any partially ordered set, the height-sequence is log
concave. More precisely
Theorem 2.1.2. Let P be a partially ordered set and x 2 P an element. Then
hihi+2 h2i+1:
for all i 2 Z.
In his argument, he used the Aleksandrov{Fenchel inequalities from the theory of mixed
volumes. The proof is short and elegant, however it does not provide any information about
the di erence of the two sides of the inequality. In particular, it is not known when equality
holds.
In the following, we will provide a fully combinatorial argument to prove a special case
of the inequality. We hope, that the techniques used here are deep enough that they can
provide a proof the theorem in whole generality.
16
Theorem 2.1.3. Let P be a partially ordered set such that the height sequence has at most
3 nonzero elements. Then
hi(x)hi+2(x) h2i+1(x)
for all i 2 Z.
Before we provide a proof, we explain an another motivation why it would be important
to know more about the error term in the inequality.
De nition 2.1.4. The average height of x 2 P is
h(x) =
Pn
i=1 ihi(x)Pn
i=1 hi(x)
Kahn conjectured the following.
Conjecture 2.1.5. Let x;y 2 P. Let n = jPj and m = jD[x] [ D[y]j. Then
maxfh(x);h(y)g m 1
Kahn observed that log-concavity of the height sequence implies the conjecture when
n = m, i.e. when x and y are the only two maximal elements. Applying the same technique
for the general conjecture, one can only derive a weaker result.
Proposition 2.1.6. Let x;y 2. Let n = jPj and m = jD[x] [ D[y]j. Then
maxfh(x);h(y)g mln2 0:7m
If we could understand the behavior of the di erence of the two sides in Staley?s inequal-
ity we may have a chance to prove the general conjecture, or at least something stronger
than the proposition above.
2.2 Proof of Theorem 2.1.3
First we discuss the case when y1 and y2 are comparable. Without loss of generality we
may assume y1 < y2.
We will use the following theorem by Ahlswede and Daykin (see [1]).
17
Theorem 2.2.1. Let L be a distributive lattice. For sets X;Y L and a function f : L !
R, let
f(X) =
X
x2X
f(x)
X ^ Y = fx ^ y : x 2 X;y 2 Yg
X _ Y = fx _ y : x 2 X;y 2 Yg
Let , , and four functions mapping L to the non-negative reals. If
(x) (y) (x _ y) (x ^ y)
for all x;y 2 L, then
(X) (Y ) (X _ Y ) (X ^ Y )
for all X;Y L.
In this proof, some of the ideas are similar to that are used in [21] and [22]. We will
de ne a distributive lattice whose elements are 4-tuples of order-preserving functions from
P to a long chain. When the chain is very long, these functions will almost look like linear
extensions of P.
As promised, let us de ne a distributive lattice L. The elements of the ground set are
4-tuples of functions (f1;f2;f3;f4) such that
fi : P [fug ! f0;::: ;k 1g
are order preserving functions, where k is some xed positive integer (parameter of L) and
u is an arti cial element that is not in the ground set of P. Also, when we require order
preserving functions, we consider u to be incomparable with all other elements of P, so in
e ect, fi(u) can be assigned freely.
To complete the de nition of the lattice, we have to de ne the lattice operations.
(f1;f2;f3;f4) ^ (g1;g2;g3;g4) = (f1 ^g1;f2 ^ g2;f3 ^ g3;f4 ^ g4)
(f1;f2;f3;f4) _ (g1;g2;g3;g4) = (f1 _g1;f2 _ g2;f3 _ g3;f4 _ g4)
18
where
(f ^ g)(u) =maxff(u);g(u)g
(f ^ g)(x) =maxff(u);g(u)g+ (2)
+ minff(x) f(u);g(x) g(u)g for all x 2 P;
and similarly,
(f _ g)(u) =minff(u);g(u)g
(f _ g)(x) =minff(u);g(u)g+ (3)
+ maxff(x) f(u);g(x) g(u)g for all x 2 P:
Intuitively, the meet operation pushes u up, and everything else is down, relative to u. The
join operation pushes u down, and everything else is up, relative to u.
Lemma 2.2.2. L is a distributive lattice.
Proof. Observe that L = L0 L0 L0 L0, with L0 having order preserving functions
P [fug ! f0;::: ;k 1g as elements, and operations are as described in (2) and (3). It is
su cient to prove that L0 is a distributive lattice, because products of distributive lattices
are distributive lattices.
First we show L0 is a lattice. For this, note that L0 is closed under the lattice operations.
Then note that the operations are trivially commutative. Associativity and absorption
follow from simple calculations.
Now we show that the operations are distributive. For this, note that for any three real
numbers a, b and c
maxfa;minfb;cgg = minfmaxfa;bg;maxfa;cgg (4)
and dually
minfa;maxfb;cgg = maxfminfa;bg;minfa;cgg: (5)
19
Then
f ^(g _h)(x) = maxff(u);minfg(u);h(u)g + minff(x) f(u);
minfg(u);h(u)g + maxfg(x) g(u);h(x) h(u)g minfg(u);h(u)gg =
= maxff(u);minfg(u);h(u)g + minff(x) f(u);
maxfg(x) g(u);h(x) h(u)gg
(f ^ g) _ (f ^h)(x) = minfmaxff(u);g(u)g;maxff(u);h(u)gg+
+ maxfmaxff(u);g(u)g + minff(x) f(u);g(x) g(u)g maxff(u);g(u)g;
maxff(u);h(u)g + minff(x) f(u);h(x) h(u)g maxff(u);h(u)gg =
minfmaxff(u);g(u)g;maxff(u);h(u)gg+
+ maxfminff(x) f(u);g(x) g(u)g;
minff(x) f(u);h(x) h(u)gg
Applying (4) and (5) we get that the two expressions above are equal.
We de ne X;Y L formally. The de nitions are illustrated on Figure 2. In the
following de nitions, A denotes the the upset of x and B denotes the downset of x in P.
X = f(f1;f2;f3;f4) :
f1(u) = f1(y1);
f1(B) = f2(B) = f2(y1) = f2(y2) = 0;
f2(u) < f2(x) for all x 2 A;
f3(A) = f4(A) = f3(y1) = f3(y2) = k 1;
f3(u) > f3(x) for all x 2 B;
f4(u) = f4(y1) = f4(y2);
fi(x) 6= fi(y) 8x;y 2 P;i = 1;2;3;4;
other than when required by the aboveg
20
PSfrag
replacemen
ts
x y z
w
X
Y
f
1
f
2
f
3
f
4
g
1
g
2
g
3
g
4
f
_
g
f
^
g
u
u
u
u
u
u
u
u
u
u
u
u
u
u
u
y
1
y
1
y
1
y
1
y
1
y
1
y
1
y
1
y
2
y
2
y
2
y
2
y
2
y
2
y
2
y
2
Figure 2: Subsets X, Y , X _ Y and X ^ Y
21
Y = f(f1;f2;f3;f4) :
f4(u) = f4(y2);
f4(A) = f3(A) = f3(y1) = f3(y2) = k 1;
f3(u) > f3(x) for all x 2 B;
f1(B) = f2(B) = f2(y1) = f2(y2) = 0;
f2(u) < f2(x) for all x 2 A;
f1(u) = f1(y1) = f1(y2);
fi(x) 6= fi(y) 8x;y 2 P;i = 1;2;3;4;
other than when required by the aboveg
To apply Theorem 2.2.1, we need to determine the cardinality of jXj, jY j, jX _ Y j and
jX ^ Y j. This is relatively easy. In the following, a = jAj and b = jBj. Also e will denote
the number of linear extensions of the poset A [ B, in which the relation is inherited from
P.
jXj = hie
k
a + 2
k
b + 1
k
a + 1
k
b + 1
jY j = hi+2e
k
a + 1
k
a + 1
k
b + 1
k
b + 2
We can not exactly count jX _Yj and jX ^Yj with our method. However, the following
is clear:
jX _ Y j = h i+1e
k
a + 2
k
a + 1
k
b + 1
k
b + 1
+ R_;
where h i+1 is the number of linear extensions of P such that x is in the ith lowest position
and y2 is in a position where y1 could also go. Clearly h i+1 hi+1.
R_ is the number of elements of X _ Y in which \collision" happens. This is when
fi(x) 6= fi(y) or gi(x) 6= gi(y), but (fi _ gi)(x) = (fi _ gi)(y) for some i. Clearly, these case
are not included in the rst term, that is why we need the adjustment.
Using a similar counting method and notation
jX ^ Y j = h i+1e
k
a + 1
k
a + 1
k
b + 1
k
b + 2
+ R^:
22
with h i+1 hi+1.
Now apply Theorem 2.2.1 with all four functions being constant 1. Then simplify by e
and the binomial coe cients. We have
hihi+2 h i+1 + r_ h i+1 + r^
where r_ = R_e( k
a+2)(
k
a+1)(
k
b+1)(
k
b+1)
and r^ = R^e( k
a+1)(
k
a+1)(
k
b+1)(
k
b+2)
.
Now let k ! 1. The probability of a collision tends to zero, more precisely r_ ! 0 and
r^ ! 0. Then applying hi+1 h i+1 and hi+1 h i+1 implies the inequality.
It remains to discuss the case when y1ky2.
Let the number of linear extensions in which x is in the ith position and y1 < y2 be
denoted by hi(y1 < y2), and the number of linear extensions in which y2 < y1 be denoted
by hi(y2 < y1).The inequality we need to show is
[hi(y1 < y2) + hi(y2 < y1)][hi+2(y1 < y2) + hi+2(y2 < y1)]
[hi+1(y1 < y2) + hi+1(y2 < y1)]2:
Since hi(y1 < y2)hi+2(y1 < y2) hi+1(y1 < y2)2 and hi(y2 < y1)hi+2(y2 < y1) hi+1(y2 <
y1)2 by the rst case, we only need to show hi(y2 < y1)hi+2(y1 < y2)+hi(y1 < y2)hi+2(y2 <
y1) 2hi+1(y1 < y2)hi+1(y2 < y1). This can be done by showing hi(y2 < y1)hi+2(y1 <
y2) hi+1(y2 < y1)hi+1(y1 < y2) and hi(y1 < y2)hi+2(y2 < y1) hi+1(y1 < y2)hi+1(y2 <
y1) similarly to the rst case.
23
CHAPTER III
SEGMENT ORDERS
3.1 Introduction
The containment order of closed intervals on the real line is a very natural partially ordered
set that one wants to investigate. Interval I is less than interval J, if and only if I J. It
is easy to show the following.
Proposition 3.1.1. A partially ordered set is a containment order of real intervals if and
only its dimension is at most 2.
Farhad Shahrokhi proposed a de nition of two families of partially ordered sets. These
came up for him with relation of a graph theory problem. He originally asked if the families
contain an arbitrary large dimensional partially ordered sets. It is not di cult to show that
the answer is \yes". However, the classes turned out to be interesting on their own right.
In particular, Shahrokhi, Trotter and his students realized that it is not clear if the two
families are actually the same or not. This inspired this line of research, in which we will
de ne Shahrokhi?s two families and we propose the de nition of two other families. They
are all very similar, and actually they all might be the same (though it seems unlikely).
First we will de ne two kinds of partial orders between certain closed line segments of a
two-dimensional Cartesian coordinate system. The segments subject to this order have an
endpoint (x1;0) on the x-axis, and the other endpoint (x2;x3) satis es x1 < x2 and x3 > 0.
First we de ne the partial order of the rst kind. We say, the line segment x (whose
endpoints are (x1;0) and (x2;x3)) is greater than the line segment y (whose endpoints are
(y1;0) and (y2;y3)), if x1 < y1, x2 > y2 and every vertical line that intersects both x and y
intersects x strictly above y. In particular, if x \y 6= ; then they are incomparable.
For the partial order of the second kind, we say, the line segment x is greater than the
line segment y, if x1 < y1, x2 < y2 and every vertical line that intersects both x and y
intersects x strictly above y. In other words, we reverse the ordering rule on the right end
24
of the line segment.
Let P be a poset. If there is a function l1 such that for x;y 2 P, x < y if and only is
l1(x) is less than l2(x) in the rst kind of line segment ordering, then we say P is a segment
order of the rst kind. We denote the class of segment orders of the st kind by P1. We can
also say P is a P1-order, and the set of corresponding line segment is a P1-representation
of P. We use similar de nitions to de ne the class P2, the class of segment orders of the
second kind.
Shahrokhi?s two families were not these two. He added another restriction to both
classes producing subfamilies of these families.
Let P 2 P1 a poset. If P has a P1-representation L, such that every line segment in
L intersects the y-axis, we say P is a central segment order of the rst kind. We use p1
to denote this class. Similarly, we can de ne p2, the class of central segment orders of the
second kind.
It is clear that p1 P1 and p2 P2, but it is not at all clear if these are proper
containments or not.
Every interval containment order is in P1. This is trivial, because one can easily turn an
interval containment representation into a P1-representation by adding 1 to the y-coordinate
to the right endpoint of each interval. In this sense, P1 is a natural generalization of interval
containment orders.
Using a similar analogy, P2 is a natural generalization of interval orders. Again, just
lifting the right endpoints of the intervals by 1 will produce a P2-representation from any
interval representation of an interval order. Interval orders and interval containment orders
are two very di erent classes, nevertheless, it is not clear how di erent P1 and P2 are.
Theorem 3.1.2. Every interval containment order is both in p1 and in p2.
Proof. To see that every interval containment order is in p1, consider an interval represen-
tation L = f[a1;b1];::: ;[an;bn]g of the order P. There exists an m 2 R such that the set of
intervals L0 = f[ai m;bi+m] : [ai;bi] 2 Lg is pairwise intersecting. Observe, that L0 is still
a representation of P. Now let L00 = fline segments from (ai;0) to (bi;1) : [ai;bi] 2 L0g.
25
Then L00 is a p1-representation of P. The second part of the proof is quite similar to the
rst, so we omit it.
We will prove a more general statement later, namely, that every 3-dimensional poset,
as well as every interval order is both in p1 and p2. On the other hand, the fraction of
4 and higher dimensional posets that are in the classes is very small (we will make this
statement rigorous later). This makes these classes even more interesting: as we know that
the Removable Pair Conjecture holds for 3-dimensional posets and interval orders, p1 and
p2 seem to be the next ideal choices to test the conjecture.
We will show many other small results about the classes p1, p2 and P1, P2. For a
substantial part of the chapter, statements are equally true for both centered and regular
classes of segment orders, and depending on the statement, we will claim and prove the
form that is stronger. The main question of this discussion (which will appear even more
natural after understanding these classes a little better) is if p1 = p2. We conjecture that
the answer is negative and we will be able to prove a statement that says that there is no
continuous function of line segments to line segments that turns a P1 order into a P2 order.
This statement has a corollary on the central classes. Though these results might seem to
be weak, they are surprisingly di cult to prove. The discretization of these proofs are also
beyond our understanding at this point.
Since our ultimate goal is to prove p1 6= p2, the reader might think that eventually
somebody will draw a p1 poset with less than a hundred lines and will show it is not in
p2. While we can?t rule out the possibility completely, the following discussion will show
that it is indeed very improbable. It seems very likely the deep techniques are required to
construct such a poset, and it will contain at least several billion points.
3.1.1 A note about tied endpoints
Suppose we want to rede ne the de nition of P1 or P2 by allowing equality in the x-
coordinates of the endpoints. Or similarly, if x is the segment from (0;0) to (1;1) and y is
the segment from ( 1;0) to (3;1), why don?t we de ne x < y in P1?
Observe, that if we make any or all of these changes, we actually don?t change the class.
26
For example, if a nite number of line segments in a P1-representation have a the same
x-coordinate for their right endpoints, the segments are pairwise incomparable. One can
make the ith segment (ordering them increasingly according their y-coordinates) "=i longer
to the right, using an " so small that this addition will not a ect the relationship of the
tied segments with the others. If we modify the de nition making the above mentioned line
segments pairwise comparable, add "=i to their lengths in reverse order.
Similarly, one can break all the ties that arise in any of the four classes. Therefore no
matter how we de ne the classes in terms of ties, we get equivalent de nitions. We will
extensively use this fact by changing our de nition of the classes at will, depending of what
de nition is the easiest to use.
3.2 Basic properties of regular and central segment orders
The following proposition answers Shahrohki?s question.
Proposition 3.2.1. For every positive integer n, the \standard examples" Sn are in both
p1 and p2.
Proof. Let C be the quarter circle whose equation is (x 1)2 + y2 = 4 with x 1 and
y 0. Let p1;p2;::: ;pn be the points on C, such that the x-coordinate of pi is i=(n + 1).
For each i = 1;::: ;n, let ai be a line segment whose left endpoint is of the form (x;0) with
1 < x < 0 and right endpoint is pi. Let bi be a segment of the tangent of C at point
pi, such that its left endpoint lies on the x-axis and its right endpoint has x-coordinate 2.
Then fa1;::: ;an;b1;::: ;bng is a p1-representation of Sn, hence Sn 2 p1. (See Figure 3.)
To show that Sn 2 p2 is very similar, but the choice of C is slightly more complicated.
Let C be the arc y = ex with x 2 [0;1]. Let p1;p2;::: ;pn be the points on C, such that
the x-coordinate of pi is i=(n + 1). For each i = 1;::: ;n, let bi be a line segment whose
left endpoint is of the form (x;0) with x < 1 and right endpoint is pi. Let ai be a
segment of the tangent of C at point pi, such that its left endpoint lies on the x-axis and
its right endpoint has x-coordinate 2. Then fa1;::: ;an;b1;::: ;bng is a p2-representation of
Sn, hence Sn 2 p2. (See Figure 4.)
27
PSfrag replacements
x
y
z
w
ai
bi
C
Figure 3: p1-representation of Sn
PSfrag replacements
x
y
z
w
ai
bi
C
Figure 4: p2-representation of Sn
28
Theorem 3.2.2. Every poset of dimension at most 3 is in both p1 and p2.
Proof. Let P be a three-dimensional poset. Let L1, L2 and L3 be linear extensions such
that L1 \ L2 \ L3 = P. For each x 2 P, let xi be the position of x in Li, counting from
low to high. For each x 2 P, draw a line segment from ( x1;0) to (0;x2). There is an
" > 0 such that if we change the x-coordinate of the right endpoint of every line segment
to any number between 0 and " (from the original 0), then the intersection properties will
not change, in other words, two line segments will intersect, if and only if they intersected
before.
Then change the right endpoint of line segment x to "x3jPj. Clearly line segment x is
greater than line segment y in p2 if and only if x < y in L1;L2;L3. So P 2 p2.
To prove that P 2 p1, we can start with the same line segments and " as above. Then
change the right endpoint of line segment x to " "(x3 1)jPj . Now line segment x is greater
than line segment y in p1 if and only if x < y in L1;L2;L3. Therefore P 2 p1.
Before we start to think that maybe p1 and p2 are universal, we discover the following
theorem:
Theorem 3.2.3. For every d > 3, there is a d-dimensional poset that is neither in P1 nor
in P2. Furthermore, for every 0 < p < 1 there is a positive integer n, such that out of all
d-dimensional posets on n elements, at most their p-fraction is in P1 or P2.
Before we discuss the proof, we need a few de nitions and a theorem.
De nition 3.2.4. Let F be a family of sets. Let P be a poset. We say P is an F-order, if
there is a function f : P ! F such that f(x) f(y) if and only if x y in P.
De nition 3.2.5. A family of sets F has k degrees of freedom, if there is an injec-
tive function f : F ! Rk, such that there exist polynomials p1;::: ;pt of 2k variables
such that for two sets S;T 2 F, the question if S T can be decided by the signs of
pi(f1(S);::: ;fk(S);f1(T);::: ;fk(T)) for i = 1;::: ;t.
29
Theorem 3.2.6 (Alon and Scheinerman [2]). Let F be any family of sets. If F has at
most k degrees of freedom, there is some k + 1-dimensional poset which is not an F-order.
Proof. We will de ne F1 (or F2) to be an in nite family of sets that represents the P1 (or
P2) ordering. For P1 this can be done as the following: to a line segment (a;0) to (b;c),
assign the closed triangle with vertices (a;0), (b;0), (b;c). Containment of these triangles
will result in an ordering that is not quite the same as in the original de nition of P1, but
it de nes an equivalent class (see Section 3.1.1). For P2 the assignment is the following:
to a segment (a;0), (b;c), assign the union of the closed triangle with vertices (a;0), (b;0),
(b;c), and the set f(x;y) : x b;y 0g. Similar remark applies as in the previous case.
So every poset of P1 (P2) is an F1-order (F2-order). Then we show that F1 (F2) has at
most 3 degrees of freedom by providing nitely many (that will be 3) polynomials, whose
sign pattern will determine the relationship between two sets of F1 (F2). We will provide
the polynomials for F1 here as an example and leave the polynomials for F2 as an exercise.
Let a line segment have the endpoints (x;0), (y;z). Then we will assign the triple
(x;y;z) to the set of F1 that was assigned to the line segment. Let two line segments have
the endpoints (x1;0), (y1;z1) and (x2;0), (y2;z2).
p1(x1;y1;z1;x2;y2;z2) = x2 x1
p2(x1;y1;z1;x2;y2;z2) = y1 y2
p3(x1;y1;z1;x2;y2;z2) = z1x2 + z1y2 z2y1 + x2z2
The rst line segments is less than the second if and only if all three polynomials are negative.
Observe, that p1 and p2 determines the ordering of the projections of the endpoints to
the x-axis, and p3 determines if the endpoint of the second line segment stays under line
determined by the rst line segment.
This shows that F1 has at most 3 degrees of freedom. Therefore, by Theorem 3.2.6,
there is a 4-dimensional poset that is not an F1-order, hence it not in P1.
The statement of the theorem is stronger than this, but this is not a problem. The proof
of Theorem 3.2.6 in [2] implies a stronger statement than the theorem, and that is exactly
what we need to deduce the stronger statement of our theorem.
30
Corollary 3.2.7. For every d > 3, there is a d-dimensional poset that is neither in p1 nor
in p2. Furthermore, for every 0 < p < 1 there is a positive integer n, such that out of all
d-dimensional posets on n elements, at most their p-fraction is in p1 or p2.
Theorems 3.2.2 and 3.2.7 suggest that p1 and p2 strongly overlap with the low dimen-
sional posets. Perhaps with the exception of a few obscure examples, these classes contain
exactly the low-dimensional posets. In that case, the classes are not very interesting. For-
tunately it turns out that it is very far from being true.
As Proposition 3.2.1 shows, there is no bound for the dimension of posets in either
classes. However, one may wonder, if the standard examples are the only high dimensional
examples in p1 or p2. The following theorem shows that this is not the case.
Theorem 3.2.8. Every interval order is in both p1 and p2.
Proof. It is clearly su cient to prove that In = f[a;b] : a = 1;::: ;n; b = 1;::: ;ng is both
in p1 and p2. We will rst show that In 2 p1.
Draw a quarter of a circle with radius 1 and center (1;0). For every interval of In, place
a point to the circle, in the way it is shown on the left of Figure 5. For every point [i;j],
if i 3, draw a half-line from the point representing [i;j] so that it intersects the circle
between the point representing [i 2;i 1] and the next point up on the circle. Drop the
portion of this half-line that is under the x-axis to create a line segment. This line segment
will be assigned to the interval [i;j].
If i 2 draw a line segment from (0;") to the point representing [i;j], where " is a small
positive real, such that (0;") will be the point closest to the origin on the x-axis of all the
endpoints of the segments.
It is clear that the p1 ordering among these segments is the same as the interval ordering
among the intervals.
If we change the quarter circle as it is shown on the right of Figure 5, then the same
argument gives a proof that every interval order is a p2 order.
31
PSfrag replacementsx
yz
w
[1;2]
[1;3]
[2;3]
[1;4]
[2;4]
[3;4]
[1;5]
[2;5]
[3;5] [4;5]
PSfrag replacementsx
yz
w
[1;2][1;3]
[2;3] [1;4]
[2;4]
[3;4]
[1;5]
[2;5]
[3;5]
[4;5]
Figure 5: Right endpoints of segments and the segment assigned to [4;5]
3.3 Goals and motivations
We were not able to nd a p1 poset that is not p2 or vice versa. The previous discussion
shows that if there is one, it is of dimension at least 4, not an interval order and not a
standard example. If the two classes are the same, one would expect that there is short
proof, which would be something like a nice, bijective function from the line segments of R2
to itself that maps the line segments of a p1 poset to another set of line segments, so that
it will be a p2-representation of the same poset. Or maybe its is even true for P1 and P2.
Momentarily, we will show, that at least the latter statement is false.
From now on we will focus on the question whether p1 = p2.
De nition 3.3.1. A universal function is a function f : R3 ! R3 such that for every L p1-
representation of a poset P, the set of line segments ff(l) : l 2 Lg forms a p2-representation
of P.
Remark: f(l) denotes the line segment, whose left endpoint is de ned by the rst coor-
dinate of f(l) and right endpoint de ned by the third and forth coordinates of f(l); f(l) is
computed by transforming the line segment l to a triple using the x coordinate of the left
endpoint of l and the x and y coordinates of the right endpoint of l, in order.
De nition 3.3.2. A shift insensitive universal function is a function f : R3 ! R3 such
that for every L p1-representation of a poset P and for every s 2 R, there exists an s0, such
32
that the set of line segments ff(l + s) : l 2 Lg + s0 forms a p2-representation of P.
Remark: for a line segment l from (x;0) to (y;z), l + s denotes the line segment from
(x + s;0) to (y + s;z). For a set of line segments L0 and s0 2 R, L0 + s0 = fl0 + s0 : l0 2 L0g.
Clearly, not every universal function is shift insensitive universal, but also, not every
shift insensitive universal function is universal.
The partial result that we achieved is the following.
Theorem 3.3.3. There is no continuous shift insensitive universal function.
This is one reason why we make the following conjecture.
Conjecture 3.3.4. p1 6= p2. Furthermore, p1 6 p2 and p2 6 p1.
In this whole section we will assume that the intersection of two line segments never
occurs in the endpoint of any of them. We can do this because of the remarks we made in
Section 3.1.1.
De nition 3.3.5. Let P be a poset in p1 with a representation P1. We say, L is the left
linear extension of P (de ned by P1), if L is de ned by the regular ordering of the absolute
values of the x-coordinates of the left endpoints of the line segments of P1. Similarly, we say,
R is the right linear extension of P (de ned by P1), if R is de ned by the regular ordering
of the absolute values of the x-coordinates of the right endpoints of the line segments of P1.
The following lemma will allow us to make strong assumptions about how a poset is
represented.
Lemma 3.3.6. Let P1 be a p1-representation of a poset P. Then there exists a Q1 P1
p1-representation of a poset Q, such that for any Q2 p2-representation of Q, there exists
P2 Q2 such that P2 is a p2-representation of P 1, and additionally the following is true:
L1 is the left linear extension of P (de ned by P1), R1 is the right linear extension of
P (de ned by P1). Similarly, L2 is the left linear extension of P (de ned by P2), R2 is the
right linear extension of P (de ned by P2).
1This far, the statement is totally trivial, as P2 can be chosen to be set of line segments corresponding to
the line segments in P1. The question is, if we can force this to behave as it is described in the second part
of the statement. In fact, probably we can not, and in the proof, P2 will be slightly di erent than just the
image of P1.
33
Then
i) L1 = Rd2
ii) L2 = R1.
Let P1 be a p1-representation of a poset and l and m be two line segments. Let l1 be
the absolute value of the x-coordinate of the left endpoint of l and de ne l2 similarly for
the right endpoint. Similarly de ne m1 and m2. Assume further that l1 > m1 and l2 > m2.
Now try to represent the poset in p2. Do we know anything about the order of the
projections of the endpoints of the line segments corresponding to l and m? If in P1, l and
m are comparable (then l > m), then yes, these orders are xed. However, l and m may
very well be incomparable in P1 in which case there is no restriction how the endpoints are
ordered in the p2-representation. The power of the lemma, is that we can actually force
some order on the endpoints, by building a set of \helper" lines above P1 rst to form Q1,
then nd the the representation of Q1 in p2, and nd the correct subset. This will essentially
tie our hands how to create p2-representations.
3.4 Proof of Lemma 3.3.6
The idea of the proof is the following. First we will provide a construction of Q1 that
only proves i). Then we start over and provide another construction of Q1 that proves ii),
but then we assume that i) already holds. So in reality, if one wants to force the desired
behavior, he has build the helper segments that force ii), then above that he builds the
helpers that force i).
We will dedicate a section to each part of the proof.
3.4.1 First part
In this section we will construct Q1 that forces i).
Let the elements of P = fp1;p2;::: ;pjPjg. Let n = 2jPj+1. We will add two sets of line
segments to P1:
A = fa1;::: ;ang; B = fb1;::: ;bng:
34
PSfrag replacements
x
y
z
w
A [ G
B
Segments of P start here Segments of P end here
Figure 6: Arrangement of Q1
They form a standard example, like in Figure 3. Specially, the elements of B are con ned
to a narrow space: each of them starts after the last element of P (i.e. the left endpoints
of the elements of P are left from the left endpoints of the elements of B), and each of the
ends before the rst ending element of P. Also, pi \ aj = ; for all i;j.
Additionally, we construct a set of line segments G.
G = fgS : S is a set of consecutive integers not greater than ng:
We de ne G so that GkA, and for each S for which gS 2 G, it holds that gSkfb 2 B : b 2 Sg
but gS > fb 2 B : b 62 Sg. Note, that this does not de ne how to draw the line segments
of G, but clearly, it is easy to do it (\intermix" the segments with the elements of A). See
Figure 6.
Suppose that the x-coordinates of the right endpoints of the elements of p1;::: ;pjPj are
pR1 ;::: ;pRjPj. Without loss of generality, pR1 < < pRjPj. Note, this is equivalent to the
statement R1 = (p1;::: ;pn). Then the x-coordinates of the right endpoints of the elements
of A, call them aR1 ;::: ;aRn will follow the following rule:
aRi = p
Rj + pRj+1
2 if i =
k 12
2j for some k: (6)
Some aRi are not de ned by this rule (namely, i ij2jPj); they will be such that aRi > pRj for
all j, but otherwise arbitrary.
35
PSfrag replacements
x
y
z
w
Figure 7: p2-representation of Sn
Now we will show that Q2 has to attain a very speci c form, and so does P2. From now
on, we change the notation, and pi, ai, bi denote line segments of the p2-representation,
and we use again aLi , aRi for the absolute values of the x-coordinates of the left and right
endpoints of the segments. However, we maintain the indices, so in this way ai is the image
of the original ai2.
In the following, we will study the structure of A [ B in the p2-representation. Since
this will be useful later, too, we state it as a separate lemma.
Lemma 3.4.1. Every p2-representation of Sn (standard example) has the arrangement as
in Figure 7, with the exception of at most two pairs of line segments.
Proof. The sets A and B are the maximum antichains in Sn. A = fa1;::: ;ang, B =
fb1;::: ;bng and ai > bj if and only if i 6= j.
Hence in the representation,
aLi > bLj
for all i;j except maybe for one pair. Let us ignore that pair now and concentrate on the
remaining. Now let ak be such that aRk is maximal. Then each bi < ak with i 6= k, so each
bRi > aRk with i 6= k. If we ignore ak and bk now, too, then the remaining
faRi < bRj g for all i;j, except for the ignored.
2We believe that the confusion this might cause is less than the confusion that would be caused by the
hordes of indices.
36
Still, for every i, aikbi somehow: the only way this can be if, ai \ bi 6= ;. So the p2-
representation must look like Figure 7.
We can specify an ordering on B with the aid of the left linear extension (de ned by
Q2), call it L2(Q2)jB. Also, denote the linear order speci ed by the left linear extension
(de ned by Q1) by L1(Q1)jB. We claim that if we keep ignoring the pairs in the previous
paragraph, then either
L1(Q1)jB = L2(Q2)jB or L1(Q1)jB = (L2(Q2)jB)d: (7)
To see this, pick bx and by consecutive elements in L1(Q1)jB. We know that y = x + 1
unless some elements were ignored between them, in which case every i : x < i < y is an
index of an ignored element. Let S = fx;::: ;yg a set of (at least two) integers, and consider
the image of gS, call it g . Now g > bi for all i except for the images of bx and by (and the
ignored elements of course). This is only possible if the images of bx and by are consecutive
line segments on Figure 7, or more rigorously, the images of bx and by are consecutive in
L2(Q2)jB. So we deduced that the consecutivity property is preserved between L1(Q1)jB
and L2(Q2)jB, which implies (7)3.
Note that the proposition above has no consequence to the right linear extension of B.
However, it immediately implies a similar statement on the right linear extension of A. Let
L2(Q2)jA be the right linear extension (de ned by Q2). Then
L2(Q2)jA = (a1;::: ;an) or (an;::: ;a1): (8)
(Again, recall that we may have missing elements from these sets, but that will not a ect
our argument.)
Recall that R1 = (p1;::: ;pjPj), so we need to show that L2 = (p1;::: ;pjPj).
Now recall the de nition of Q1, speci cally that all ai had its left endpoint left from all
pi, and the ordering of their right endpoints by (6). In particular it implies that p1 < ai for
all i. Therefore it must be that p1 g, a
contradiction. So rR < bR.
3.4.2.3 Case 3
rR < bR and r \ b 6= ; in Q1
40
PSfrag replacementsx
yz
w
r
b
l g
y-axis
PSfrag replacementsx
yz
w b r g
Figure 11: Case 3
PSfrag replacements
x
y
z
w
r
g
b
Figure 12: Case 4
Add two line segments, g and l, so that in Q1
g

rL by the rst part of the lemma. Suppose that bR < rR. Then b and r must
intersect in Q2 in order to be incomparable. gL < rL, g

rR by the Case 1 construction. Then it should happen that l

Q b and g and r are in the same relation as b and r in
Case 3. In Q2, gR < bR, because g >Q b. If bR < rR, then gR < rR, contradicting Case 3.
This concludes the proof of the main lemma.
Although we worked out the proof for p1 and p2, observe that position of the y-axis did
not really play any role in the proof. In the points when it came up in the discussion it only
made the proofs harder, so if we drop the assumption that every line segments intersects
the y-axis, the proof still stands. Therefore we can also conclude the following:
Lemma 3.4.2. The statement of Lemma 3.3.6 holds for P1 and P2, too.
3.5 Connections with pseudoline arrangements
In this section, unless otherwise noted, we will work on on the real projective plane P2.
De nition 3.5.1. A pseudoline is a simple closed curve whose removal does not disconnect
the plane.
Consider a set of pseudolines on the plane. Maybe we are not interested the exact paths
the pseudolines describe, or they analytical properties. If we are only interested how they
connect certain points of the plane, then we talk about graph theory. In this case, we de ne
abstract object|graphs|that contain only these properties of the lines. If we are also
interested the intersection properties of these lines, then we will de ne a di erent kind of
abstract object: a pseudoline arrangement.
De nition 3.5.2. An arrangement of pseudolines is a set of pseudolines such that any two
intersects at exactly one point, and not all of them intersect in the same point.
De nition 3.5.3. Consider the sphere model of P2, in which the points are pairs of an-
tipodal points, and the lines are the great circles. Let a and b be two points in P2, and
(a1;a2), (b1;b2) be the corresponding pairs of antipodal points. The distance of a and b is
minfd(a1;b1);d(a1;b2);d(a2;b1);d(a2;b2)g, where d(ai;bj) is the length of the shortest arc
42
PSfrag replacements
x
y
z
w
a1
a2
a3
b1 b2 b3
Figure 13: Non-stretchable arrangement with 9 pseudolines
between ai and bj on the surface of the sphere. A function P2 ! P2 is continuous, if it is
continuous with respect to the metric de ned by the distance above. A function P2 ! P2 is
a homeomorphism, if it is bijective, continuous and its inverse is also continuous.
De nition 3.5.4. Two pseudoline arrangements are isomorphic, if there is a homeomor-
phism that maps one to the other.
De nition 3.5.5. A pseudoline arrangement is stretchable if it is isomorphic to a pseu-
doline arrangement, in which every pseudoline is a straight line.
Not every pseudoline arrangement is stretchable. To show a counterexample, recall the
classical geometrical theorem by Pappus.
Theorem 3.5.6 (Pappus). Let a1, a2, a3 be collinear points, and b1, b2, b3 be another set
of collinear points. Let (ai;bj) denote the straight line that passes through the points ai and
bj. Then the points (a1;b2) \(a2;b1), (a1;b3) \ (a3;b1), (a2;b3) \(a3;b2) are collinear.
Corollary 3.5.7. The pseudoline arrangement on Figure 13 is not stretchable.
Desargues? Theorem can be used to produce a non-stretchable con guration on 10 lines.
There are several other famous examples. Bokowski and Sturmfels provided a \minor-
minimal" in nite family of non-stretchable arrangements. This already suggests that that
it is di cult to determine if a pseudoline arrangement is stretchable. Indeed, Mn ev proved
that the problem determining if a pseudoline arrangement is stretchable is NP-complete.
43
PSfrag replacements
x
y
z
w
a1
a2
a3
b1
b2
b3
Figure 14: Non-stretchable simple arrangement with 9 pseudolines
De nition 3.5.8. A pseudoline-arrangement is simple, if no three pseudolines cross in the
same point.
Simple pseudoline arrangements will be central points of interest to us, because the
method that we will develop will produce arrangements that are simple, or close to simple.
It is easy to transform the non-Pappus arrangement into a simple pseudoline arrangement, as
shown on Figure 14. We encourage the reader to reconstruct the proof that the arrangement
is non-stretchable using Pappus?s Theorem.
For more information on pseudoline arrangements, see [15], or for more detailed expo-
sition from the point of view of oriented matroids, see [3].
In the following, we will see how Conjecture 3.3.4 is related to stretchability of pseudoline
arrangements. We will de ne a sequence of posets Un 2 p1 for every positive integer n. We
will assign a family of pseudoline arrangements to each Un, and we will ask if it is true that
there is a stretchable arrangement in each family.
Let ^Un = f1;::: ;ng3, the set of ordered triples of positive integers not greater than n.
To every element (l;r;u) of ^Un, assign the line segment from ( l;0) to (r;u). Consider
these line segments as a p1-representation of a poset. Call this poset Un.
If there is an n such that Un 62 p2, then p1 6 p2, speci cally, Conjecture 3.3.4 is true.
On the other hand, if Un 2 p2 for every n positive integer, then p1 p2. Indeed, every
poset in p1 can be represented as a subset of ^Un for some large n.
44
The subsets of ^Un that is determined by the triples
P(r;u) = f(i;r;u) : i 2 f1;::: ;ngg
are called pencils.
We say a pencil P(r1;u1) dominates a di erent pencil P(r2;u2) at level i, if
r1 r2 and u1 u2, or
r1 > r2 and u1 > u2 and the line segment ( i;0) to (r1;u1) passes above the point
(r2;u2), or
r1 < r2 and u1 < u2 and the line segment ( i;0) to (r2;u2) passes below the point
(r1;u1).
The following proposition is a straightforward consequence of the de nition.
Proposition 3.5.9. The domination relation of pencils at a xed level i is a total order on
the pencils.
In the following, we describe a pseudoline arrangement, that is associated with the
poset Un. For simplicity, we we will use a Cartesian coordinate system, and we add the
ideal line. We will only specify ordered sequences of points in the coordinate system that
the pseudoline passes through, in the prescribed order. Doing so, we actually do not fully
specify the arrangement, but we do specify many (intersection) properties of it. Then
we consider all pseudoline arrangements that satisfy these properties to get our family of
arrangement.
Start with straight lines v1;::: ;vn, such that vi is the straight line passing through (i;0)
and (i;1). Add a new pseudoline pr;u for each pencil P(r;u). Let li(r;u) be the position
of the pencil P(r;u) at level i in the total order de ned by domination, so that li(r;u) is 1
for the smallest pencil and n2 for the largest. Let the pseudoline pr;u pass through ( r;0),
then for i = 1;::: ;n, (i;li(r;u)). See Figure 15.
Observe, that we did not specify how the pseudolines intersect left from v1, but it is
very strictly de ned how they intersect between any vi and vi+1. This way, taking every
45
PSfrag replacements
x
y
z
w
v1 v2 v3 v4p1; p2; p3; p4;
Figure 15: Pseudoline representation of U4
46
possible arrangement (up to isomorphism), we have de ned a family of arrangements. Call
it Fn.
Proposition 3.5.10. If there exists an n 2 N such that no pseudoline arrangement in Fn
is stretchable, then p1 6 p2.
Proof. Consider ^Un, a p1-representation of Un. It is clear that we can break the ties with the
endpoint coordinates in ^Un without changing the underlying poset. Also, we can move the
line segments so that no line segment endpoint lies on another line segment, still without
changing the underlying poset.
For each set of line segment that used to be pencils, create two other identical \pencils"
(these are not really pencils any more after the tiebreaking), overlapping the original. Now
move one replica?s right endpoints to left, and move the other?s right endpoints to the right.
Do this so that the replicas have the same relationship with every other line segments
that are not in any copy on this pencil. Also, do this for every pencil, and call this new
p1-representation ~Un.
We will apply Lemma 3.3.6 on ~Un; recall that this involves building a huge helper poset
above ~Un.
In ^Un, there were only n values attained by x-coordinates of left endpoints of line seg-
ments (namely 1;::: ; n). In ~Un, the x-coordinates of the left endpoints of the correspond-
ing segments are grouped to n disjoint intervals. By Lemma 3.3.6, this property is preserved
in the p2-representation of the poset. A similar property holds for the x-coordinates of the
right endpoints.
Also by the lemma, the image of a pencil in the p2-representation resembles a ray (a
half-line). It is so that
the left endpoints are con ned to an interval in which no other line segments start,
except the ones with identical x-coordinates of right endpoints,
the right endpoints hit the groups mentioned in the previous paragraph: each segment
hits exactly one group, and the order is also preserved,
47
the \shorter" line segments do not intersect any line segments that the \longer" ones
do not.4
For each pencil, concentrate only the \longest" line segments. We know where these
start on the x-axis (recall how they are con ned into disjoint intervals).
We will add vertical lines to this p2-representation. First consider the replicas of pencils
P(i;u) for a xed i that were moved to the left. These are con ned to an interval ILi in the
p2-representation. The replicas that were moved to the right are con ned to the interval
IRi . Similar holds to the original copies of pencils, call their interval Ii.
ILi , Ii and IRi are pairwise disjoint, and Ii is the one in the middle. So there is a real
number ri strictly between ILi and IRi .
In the stripe ILi R there is a pseudoline, and we know the order it intersects the
\longest" line segments de ned above. This order is li, the total order de ned by pencil
domination. There is a similar pseudoline in the stripe IRi R, on which the intersection
order is the same. So the order must still be same on the vertical line with x = ri. Keep
only these vertical lines along with the \longest" line segments, and turn the \longest" line
segments into lines by continuing them to in nity at both ends.
What we got is a straight line arrangement that adhere to all the de ning requirements
of the members of Fn, contradicting the assumption that no pseudoline arrangement in Fn
is stretchable.
3.6 Properties of continuous universal functions
In this section, we will again heavily use Lemma 3.3.6. We will frequently make statements
that will imply that certain arrangements of line segments must hold in a p2-representation
of a certain poset. What we mean in these cases, is that we may assume that the segments
are arranged in the speci ed way, because by Lemma 3.3.6 there exists a superposet of the
current poset that forces the current posets arrangement in the speci ed way. In other
4The \shorter" segments here are those, whose right endpoint has smaller x-coordinate, although their
\arc length" can technically be longer.
48
words, we assume the statement of Lemma 3.3.6 in these cases. It would be really cumber-
some to make the precise statement every time in each argument, so we chose to use this
\shortcut".
Lemma 3.6.1. Let f be a continuous universal function function and r, b two line segments
with rL > bL.
i) If the right endpoint of r lies on the line de ned by b, then the right endpoint of f(b)
lies on the line de ned by f(r).
ii) If the right endpoint of b lies on the line de ned by r, then the right endpoint of f(r)
lies on the line de ned by f(r) (speci cally in the interior of f(r)).
The proof of this lemma relies on a sequence of basic statements that do not require
continuity and are somewhat similar to Lemma 3.3.6. The proof of these are very technical,
but not hard. The lemma will be a relatively straightforward consequence of these. The
statements are claimed together in the following lemma.
Lemma 3.6.2. Let r1 and b1 two line segments of a representation of a p1 poset P such
that rL1 > bL1. Let b and r be the corresponding elements of P. Find a p2-representation of
P. In this, the line segment corresponding to r1 and b1 will be called r2 and b2 respectively.
Let the lines de ned by ri be called Ri and the lines de ned by li be called Li respectively.
Then
1. (bR1 < rR1 ) ^ (r1 \ b1 6= ;) =) (r2 \ b2 6= ;).
2. (bR1 < rR1 ) ^ (r1 \ b1 = ;) ^ (r1 \ B1 6= ;) =) (r2 \ b2 = ;) ^ (R2 \b2 6= ;).
3. (bR1 < rR1 ) ^ (r1 \ b1 = ;) ^ (r1 \ B1 = ;) =) (r2 \ b2 = ;) ^ (R2 \b2 = ;).
4. (rR1 < bR1 ) ^ (r1 \ b1 6= ;) =) (r2 \ b2 = ;) ^(R2 \ b2 = ;).
5. (rR1 < bR1 ) ^ (r1 \ b1 = ;) ^ (R1 \ b1 6= ;) =) (r2 \ b2 = ;) ^ (R2 \ b2 6= ;).
6. (rR1 < bR1 ) ^ (r1 \ b1 = ;) ^ (R1 \ b1 = ;) =) (r2 \ b2 6= ;).
49
Proof. 1) is trivial, because if r2 \ b2 = ;, then r > b would follow, while rkb.
In 2), the part that r2 \ b2 = ; is trivial for similar reasons: we must have r > b. To
prove the other part, add a new line segment g1 such that bL1 < gL1 < rL1 , bR1 < gR1 < rR1
and g1 \ b1 6= ; and g1 \ r1 6= ;. Lemma 3.3.6 implies bL2 < gL2 < rL2 and rR2 < gR2 < bR2 .
Then g2 \r2 6= ;, because we need gkr, and g2 \b2 6= ;, because we need gkb. This implies
R2 \b2 6= ;.
3) will be proven at the end of the proof.
To prove 4), add a new line segment g1 such that gL1 < bL1 < rR1 , gR1 < rR1 < bR1 and
g1 \ r1 6= ;. Lemma 3.3.6 implies gL2 < rL2 < bL2 and rR2 < bR2 < gR2 . Since g < b, we have
g2 \ b2 = ;. Since rkg, we must have r2 \ g2 6= ;. Therefore the right endpoint of r2 in Q2
can not stay in the triangle de ned by the left endpoints of b2 and r2 and the right endpoint
of b2. This implies both statements.
To prove 5, add two new line segments g1 and w1 in the following way.
gL1 < bL1 < rL1 < wL1
rR1 < gR1 < wR1 < bR1
g1 \ b1 6= ;, w1 \ r1 6= ; and w1 \ b1 6= ;
w1 \ g1 = ;
By Lemma 3.3.6 we may assume that rL2 < gL2 < wL2 < bL2 and wR2 < rR2 < bR2 < gR2 . Since
gkb, we have g2 \ b2 6= ;. Similarly, r2 \ w2 6= ;. But w > g, therefore r2 \ g2 6= ;. This
implies the statement of the lemma.
To show 6, add g1 so that bL1 < rL1 < gL1 , rR1 < bR1 < gR1 and g1 \r1 6= ; and g1 \b1 = ;.
By Lemma 3.3.6 rL2 < bL2 < gL2 and gR2 < rR2 < bR2 . Since gkr it follows that g2 \ r2 6= ;.
Since g > b it follows that g2 \ b2 = ;. This implies the statement.
Now let us return to 3). We get the rst part trivially form r > g. To see the second
part, add a new line segment g1 such that gL1 < bL1 < rL1 , bR1 < rR1 < gR1 and g1 \b1 6= ; and
g1 \R1 = ;. Lemma 3.3.6 implies bL2 < rL2 < gL2 and rR2 < bR2 < gR2 . Because of the already
proven part 4, g2 \b2 = ;. Because of part 6, g2 \r2 6= ;. This implies the second part.
50
PSfrag replacementsx
yz
w r
b
g
PSfrag replacementsx
yz
w r
b
g
Figure 16: Proof of Lemma 3.6.2 case 4
PSfrag replacementsx
yz
w
r
b
gw
PSfrag replacementsx
yz
w
r
b
g
w
Figure 17: Proof of Lemma 3.6.2 case 5
Now we are ready to prove Lemma 3.6.1.
Proof. The lemma contains four statements altogether. Part i) has two statements enclosed:
one if the right endpoint of r lies in the interior of b, and the other, if it lies outside of b.
Similarly, part ii) includes two statements. All four statements have very similar proofs,
so we only include the proof of the case of part i) when the right endpoint of r lies in the
interior of b. The other statements are proven similarly.
Consider a sequence of segments frig1i=1 such that all ri have their left endpoints at the
left endpoint of r, and their right endpoints converge to the right endpoint of r, but the
relation of ri and b is such as r and b in part 4 of Lemma 3.6.2. Also consider another
sequence of segments fRig1i=1 such that their left endpoints are also at the left endpoint of
r, their right endpoints also converge to the right endpoint of r, however, the relation of Ri
and b is such as r and b in part 5 of Lemma 3.6.2.
Let T be the triangle determined by the line segment f(b) as a side and the left endpoint
of f(r) as opposite vertex. The images f(ri) all lie outside of T (left endpoints being at
a vertex), and the images f(Ri) lie inside of T (left endpoints being at the same vertex).
51
The right endpoints of these segments converge to the right endpoint of f(r). So the right
endpoint of f(r) must lie on the boundary of T, which implies the statement of lemma.
Nothing that has been done in this section depends on the position of the y-axis. Since
Lemma 3.3.6 works also in the absence of the y-axis, and we didn?t use the y-axis in
Lemma 3.6.2, it follows that Lemma 3.6.1 works also for shift insensitive universal functions.
We emphasize this in the following corollary.
Corollary 3.6.3. Let f be a continuous shift insensitive universal function function and
r, b two line segments with rL > bL.
i) If the right endpoint of r lies on the line de ned by b, then the right endpoint of f(b)
lies on the line de ned by f(r).
ii) If the right endpoint of b lies on the line de ned by r, then the right endpoint of f(r)
lies on the line de ned by f(r) (speci cally in the interior of f(r)).
3.7 Proof of Theorem 3.3.3
Lemma 3.7.1. Let r be a line segment from ( x;0) to (y;z) and b be a segment from ( x;0)
to (y;w) with x;y;z;w > 0 and z > w. Let f be a continuous universal function. Then f(r)
and f(b) has a common left endpoint and their right endpoints have equal x-coordinate, but
di erent y-coordinates.
Proof. Lemma 3.3.6 with the continuity of f imply that the x-coordinates of the left end-
points of f(r) and f(b) are equal, therefore the left endpoints are identical. Also, for similar
reasons, the x-coordinates of the right endpoints are equal. So unless f(r) = f(b), the
statement is true. Suppose f(r) = f(b).
Let g be a line segment starting at ( x 1;0) passing through (y;z) ending at (y +
1;z(x+y+2)=(x+y+1)). Due to Lemma 3.6.1, the right endpoint of f(z) lies on f(r) = f(b).
Considering Lemma 3.3.6, it is clear that the right endpoint of f(z) must lie in the interior
of f(b). This makes z and b incomparable in the underlying poset, when the construction
of b and g implies g > b.
52
Corollary 3.7.2. Let r be a line segment from (x;0) to (y;z) and b be a segment from (x;0)
to (y;w) with z > w. Let f be a continuous shift insensitive universal function. Then f(r)
and f(b) has a common left endpoint and their right endpoints have equal x-coordinate, but
di erent y-coordinates.
Proof. The argument is the same as for the previous lemma. Instead of using Lemma 3.3.6
and Lemma 3.6.1, we have to use their shift insensitive versions, and the argument can be
repeated without change.
Now we are ready to prove Theorem 3.3.3.
Consider two non-intersecting line segments in a P1 or P2-representation of a poset.
Let d(x0) is the distance between the points that are de ned by the intersection of the line
segments with the horizontal line y = x0. The function d(x) is de ned on at least on some
interval [0;"] for some " > 0. If d(x) is monotonously increasing, then we say they diverge.
Similarly, if d(x) is decreasing, we say they converge. If they neither diverge nor converge,
we say they are parallel (actually this is not our de nition).
Let r be the line segment (0;0) to (1;2). Let b be the line segment (0;0) to (1;1). For
" > 0 de ne b" to be the segment from (0;0) to (1;1 ").
Because of Lemma 3.7.2, f(r) and f(b) diverge. Since f is continuous, there exists " > 0
such that f(r) and f(b") diverge. Let r0 = f(r) and b0 = f(b").
De ne a new line segment l such that it passes through the points (1;2) and (1;1 ")
and its left endpoint is on the x-axis. This does not de ne l0 completely, because it does
not describe the right endpoint, but that is in fact not necessary: the location of the right
endpoint does not matter. Let l0 = f(l).
Applying Lemma 3.6.1 to r and l we conclude that the right endpoint of l0 lies on the
line de ned by r0. Similarly, looking at b" and l, we conclude that the right endpoint of
l0 lies on the line de ned by b0. Hence the lines de ned by r0 and b0 intersect at the right
endpoint of l0. This contradicts the fact that they diverge. Q.E.D.
53
3.8 Some known con gurations
Naturally we attempted to nd an integer n, such that no pseudoline arrangement of Fn is
stretchable. This actually would imply that for all m > n, no pseudoline arrangement of
Fm is stretchable, because ^Un ^Um. So we do not need to nd the smallest n, and it is
certainly more natural to try to prove the statement, that for n large enough, no pseudoline
arrangement of Fn is stretchable.
We know that the problem of stretchability is di cult is general. However, we may be
able to nd a subset of ^Un for large n, that is a known example of a non-stretchable arrange-
ment. The simplest known non-stretchable arrangement is the non-Pappus arrangement.
Unfortunately we can come to the following conclusion.
Theorem 3.8.1. The non-Pappus pseudoline arrangement is not a subset of ^Un for any
n.
This theorem is actually quite hard to prove, but since it is not closely related to the
topic, we omit the proof.
Two more attempts to nd the so called bad pentagon (see [15]) and the the Desargues
con guration also resulted in failures.
All we can really do here is to describe certain arrangements whose image under a
hypothetical continuous universal function is very restricted. They provide some hope that
a contradiction will arise from them.
Fix the positive real numbers x6 < x3 and y6 < y5. We will de ne 8 points in R2:
P 1( 1;0)
P0(0;0)
P6(x6;y6)
P5(x6;y5)
P4
x3; x3y5x6
P3
x3; (x3+1)y6x6+1
54
PSfrag replacements
x
y
z
w
P0P 1
P1
P2
P3
P4
P5
P6
Figure 18: p1 poset whose image is the Pappus con guration
P2 is the intersection of the line determined by the points P 1 and P5 and the line
determined by the points P0 and P3.
P1 is the intersection of the line determined by the points P 1 and P4 and the line
determined by the points P0 and P6.
An easy calculation gives that the x-coordinates of P1 and P2 are both
x3y5
x3y6 x3y5 + y6 :
Now let the line segment li;j connect points Pi and Pj for i = 1;::: ;6 and j = 1;0. See
Figure 18. Since this representation is full of ties, we can not directly apply Lemma 3.3.6 to
it. However, it is fairly intuitive, that the lemma can be applied to representations that are
\close" to this one, and therefore get a strong conclusion about the image of ^P0. Therefore,
its is easy to show the following.
Proposition 3.8.2. Let f be a continuous universal function. Then f maps Figure 18 into
a Pappus-like con guration, shown on Figure 19.
55
PSfrag replacements
x
y
z
w
f(l1;
)
f(l2; ) f
(l3; )
f(
l4;
)
f
(l
5
;
)
f(
l6;
)
Figure 19: The Pappus p2 poset
56
CHAPTER IV
MONOTONE HAMILTONIAN PATHS IN THE BOOLEAN LATTICE
OF SUBSETS
4.1 Introduction
The n-dimensional hypercube, as a graph is one of the rst standard examples of a Hamil-
tonian graph in college graph theory classes; a simple induction shows that a Hamiltonian
cycle exists for every n 2. However, if we follow any cycle like this, we will nd, that the
sizes of the sets along the cycle goes up and down and does not show any kind of monotone
property. The question occurs: if we give up having a cycle, and we just want a Hamiltonian
path, can we nd such a path, for which every time we cover a set, we will have covered all
the subsets of this set? This kind of path would start from the empty set, end in the set
f1;::: ;ng, and it would traverse the diagram of the subset lattice \from bottom to top".
It is immediately clear that this is impossible even for n = 2. So we relax the conditions
even more. For this, we change our point of view, and from this point on, we consider the
subset lattice of the set f1;::: ;ng. The diagram of this lattice, as a graph, is isomorphic to
the n-dimensional hypercube. We are searching for a Hamiltonian path fS1;::: ;S2ng such
that for every i, either
every subset of Si appears among the sets S1;::: ;Si 1, or
only one (say S) does not; in this case Si+1 = S.
If a Hamiltonian path has the above properties, we call it a monotone Hamiltonian path.
If a path is not Hamiltonian, but it starts at the empty set and has the above properties,
we call it a monotone stub or simply stub of a monotone Hamiltonian path. If a stub covers
all the sets of at most size k, we call is a k-stub. Obviously, the existence of an n-stub is
equivalent to the existence of a monotone Hamiltonian path. The answer for the following
questions is not known:
57
1. Is there a monotone Hamiltonian path for every n in the n-cube?
2. If the answer is no, what is the largest k such that a k-stub of a monotone Hamiltonian
path exists?
Trotter and Felsner [10] found some striking combinatorial connections related to these
questions. Without going into much details, let us just mention the results. For basic
de nitions on interval orders and partial orders, see [25], and on graph theory, see [5].
De nition 4.1.1. C(t) is the largest integer h so that whenever P is an interval order of
height h, the chromatic number of the diagram of P is at most t.
De nition 4.1.2. A sequence (S0;S1;::: ;Sh) of sets is an -sequence if
S0 6 S1, and
Sj 6 Si [ Si+1 when j > i + 1
F(t) is the largest h for which there exists an -sequence of subsets of f1;::: ;tg.
Theorem 4.1.3. For every t 1
C(t) = F(t) 2t 1 +
t 1
2
;
with equality holding if and only there is monotone Hamiltonian path in the t-cube.
Another closely related problem is the famous \middle two level" conjecture posed
by Ivan Havel. That problem is almost solved, see [17]. We do not know any speci c
connections, but both problems deal with the same kind of objects, so we can hope that
solving one might help solving the other.
Trotter conjectured, that if n is su ciently large, there is no monotone Hamiltonian
path in the n-cube. He also conjectured that if n is su ciently large, there is no 3-stub in
the n-cube.
The existence of a k-stub for k = 0;1 is absolutely trivial, and it is really easy to show
that 2-stubs exist. The number of 2-stubs is enormous, but not all of them are pre xes of
3-stubs. In our construction, we have to be really careful how we cover the 2-sets, so that
we can continue it to construct a 3-stub.
58
4.2 The existence of 3-stubs
Theorem 4.2.1. For every n positive integer, a 3-stub exists in the subset lattice of
f1;::: ;ng.
The existence of a monotone Hamiltonian path for n 10 was checked with computers
by Trotter and it has been rechecked by the authors. So in the following, we may assume
that n 9.
4.2.1 Construction of a 2-stub
Start the path with the following sequence: ;, f1g, f1;2g, f2g, f2;3g, f3g, . .. , fng. So far,
this is a 1-stub.
Now we will use a table to demonstrate how to cover the remaining 2-sets. In the table,
we just list the 2-sets that are not covered so far without curly braces and commas to
save space. When we connect two 2-sets in this table, say fa;bg and fb;cg (which will be
denoted by ab and bc), we mean that the path goes from fa;bg to fa;b;cg and then to
fb;cg. Observe, that this is only possible if the set fa;cg has been covered. We will be
careful to only connect subsets, if that is allowed. Here is our table:
13
14 24
15 25 35
...
1n 2n 3n ... n-2 n
Later we will refer to the rows of this table. When we refer to the rst, second, etc.
row, we will call them row 3, row 4, etc. respectively. So row k is the row that contains the
2-sets, whose largest element is k.
Observe, that if two sets are next to each other (up-down or left-right), it is always
possible to connect them, because the missing 2-set that must have been covered is of the
form f ; + 1g, and these were covered in the 1-stub. Additional opportunities to connect
sets arise as we go along the path. It is now fairly obvious, that we can construct 2-stubs
59
13
14
15
16
17
...
27 37 47 57
26 36 46
25 35
24
1C 2C 3C 4C 5C 6C 7C 8C 9C
1B 2B 3B 5B 6B 7B 8B
AC
9B4B
PSfrag replacements
x
y
z
w
Figure 20: Construction of a 2-stub
in many ways. We will do it as demonstrated in Figure 20. In this gure we used n = 12
and we used the letters A, B and C in place of the numbers 10, 11 and 12.
In general, the demonstrated path is the following: after the set fng, we cover f3;ng,
f2;3;ng, f2;ng, f1;2;ng, f1;ng, f1;3;ng (it is allowed, because f3;ng has been covered),
f1;3g, f1;3;4g, f1;4g and so on as demonstrated in Figure 20. After f2;7g, we do the
following. We cover the table row-by-row, going down to the next row only after we covered
every 2-set in a given row. The order of the 2-sets within a row is arbitrary, with the
following restrictions (k 7, the sign denotes an arbitrary element):
If a row ends with the sets fa;kg, f ;kg, fb;kg, then the next row starts with the sets
fb;k + 1g, fa;k + 1g.
The row before the last one ends with the sets f5;n 1g, f ;n 1g, f4;n 1g.
The last row ends with f6;ng.
When we cover row k, every row of index less than k has been covered, and this makes
it possible that every jump within the row is allowed. So just by this fact, each row could
be covered in an arbitrary order. The restrictions given above are important though in the
construction of the 3-stub.
It is clear, that for large n there are still exponentially many ways to build a 2-stub
that satis es the requirements. For clarity, let us list the 2-sets covered in order for n = 12
in the lexicographically rst stub. We will omit the curly braces, commas and we will not
mention the implied 3-sets. We will use the letters A, B, C as before.
60
3C, 2C, 1C, 13, 14, 24, 25, 35, 15, 16, 26, 36, 46, 47, 27, 17, 37, 57, 58,
18, 28, 38, 48, 68, 69, 39, 19, 29, 49, 59, 79, 7A, 4A, 1A, 2A, 3A, 6A, 5A, 8A,
8B, 6B, 1B, 2B, 3B, 6B, 5B, 7B, 4B, 4C, 5C, 7C, 8C, 9C, AC, 6C
4.2.2 Construction of a 3-stub
The idea of this construction is the following. We will partition the non-covered 3-sets into
\tables". Table k contains the set of non-covered 3-sets, whose largest element is k. So
Table 3 contains only one element: f1;2;3g, Table 4 contains one again (f2;3;4g { the sets
f1;2;4g and f1;3;4g were covered during the beginning of the 2-stub), Table 5 consists of
f1;2;5g, f1;4;5g and f3;4;5g. We will traverse the tables one by one and in an increasing
order.
Of course one problem is that the last 2-set is f6;ng, so we can not make a jump
to f1;2;3g. This is how we go back: f1;6;ng, f1;2;6;ng, f2;6;ng, f2;3;6;ng, f3;6;ng,
f1;3;6;ng, f1;3;6g, f1;2;3;6g, f1;2;3g. We encourage the reader to check that every step
is valid. Note, that this is basically a \greedy" path; we swap out the elements of the set
f6;ng to the elements of the set f1;2;3g as fast as possible.
Another important thing to observe that we only used some elements of Table n and
one element of Table 6, so tables from 7 to n 1 are una ected.
Here is how we cover the 3-sets from Table 3 to Table 6. We will omit the the 4-sets
between each pair of 3-sets for simplicity. The reader is encouraged to check the validity.
f1;2;3g, f2;3;4g, f3;4;5g, f1;4;5g, f1;2;5g, f2;5;6g, f3;5;6g, f4;5;6g, f1;4;6g, f2;4;6g
Now we will show how to cover tables from 7 to n 1. In order to do this, we will
introduce a nice, compact way to write down the element of a table in an actual table.
When we consider Table k, each element will contain k, so we will omit that element. In
e ect we will just write down 2-sets, without curly braces and commas.
We will use custom row and column indices. An element is row i and column j will be
the element ij, denoting the set fi;j;kg.
Consider the way we covered row k in the construction of the 2-stub. Say the order of
the 2-sets in that row is f 1;kg;f 2;kg;::: ;f k 2;kg. Index the columns in order with
61
62
61
63
65
41
43
45
23
25 15
PSfrag replacementsx
yz
w
71
72
73
74
76
52
53
54
56
13
14
16
24
26 36
PSfrag replacementsx
yz
w
Figure 21: Table 7 on the left and Table 8 on the right
83
81
82
84
85
87
61
62
64
65
67
32
34
35
37
14
15
17
25
27 47
PSfrag replacementsx
yz
w
94
91
92
93
96
95
98
71
72
73
76
75
78
42
43
46
45
48
13
16
15
18
26
25
28
35
38 68
PSfrag replacementsx
yz
w
Figure 22: Table 9 on the left and Table 10 on the right
k 1, 1, 2, .. ., k 4. Index the rows in order with 2, 3, .. ., k 2. This way we get
a k 3 k 3 table. Obviously, due to symmetry, only half of the table, say the lower
triangle (including the diagonal) is necessary to consider. Observe, that in the beginning,
the valid moves are exactly the moves between up-down or left-right neighbors in the table.
However, while covering a table, new valid moves appear.
We need two di erent constructions to cover the tables: one kind for even indexed tables
and one for odd. Instead of writing down how to cover the tables in an abstract way, let us
just show the examples of Tables 7 to 10 for the case of n = 12 and the lexicographically rst
2-stub. The examples will clearly show the pattern and how to generalize it. See Figures 21
and 22.
One can check that every step is valid inside a table. Also, we start to cover Table 7
with the set f2;6;7g, and this is possible, because the last element of Table 6 was f2;4;6g
and it is valid to move to f2;4;6;7g and then to f2;6;7g, because f2;4;7g and f4;6;7g
were covered during the 2-stub. This is true in general, i.e. it is always possible to move
from one table to the next one. We end Table k with the element fa;b;kg, where row k
(covering the 2-stub) ended with the sets fa;kg, f ;kg, fb;kg (lower right corner of the
table). We start Table k + 1 with the element fa;k;k + 1g (upper left corner of the table).
The implied 4-set between them is fa;b;k;k + 1g. The 3-sets that have to be covered to
62
make this a valid step, are fa;b;k + 1g and fb;k;k + 1g. The former was covered in the
beginning of row k +1, which started as fb;k +1g, fa;k +1g implying the missing set. The
latter was covered between row k and row k +1; row k ended with fb;kg, row k +1 started
with fb;k + 1g, implying the missing set.
It remains to be shown how to traverse Table n. Remember that the table is special for
two reasons: rst row n was covered irregularly in the 2-stub, and second, because when
we started to cover the 3-sets, and we had to \go back" to the set f1;2;3g, we used some
entries of Table n.
The beauty of the construction is that these two forces neutralize each other. Remember,
that the rst three sets covered in row n were f3;ng, f2;ng and f1;ng. Let us ignore these
for a moment, and concentrate on the order the remaining sets were covered. Say this
order is f 1;ng, . .. , f n 5;ng = f6;ng. Index the columns of Table n with n 1, 1,
.. ., n 5 = 6, 1, and index the rows with 2, .. ., n 5 = 6, 1, 2, 3.
When we draw the lower triangular n 3 n 3 table now, it is not completely \accurate"
for the following reasons:
The moves between column 6 and column 1 are not valid.
The set f1;6;ng is missing from the table. This is not an actual di erence, because
this set was covered in the beginning on the 3-stub.
The sets f1;3;ng, f2;6;ng and f3;6;ng are present on the table, but they are in fact
covered in the beginning of the 3-stub.
We can easily take care of the last problem by dropping the corresponding elements from
the table. As we mentioned, the second problem does not cause di culty. Now look at the
rst problem. After we drop the elements mentioned in the third problem, the separated
columns on the right are dropped, so the problem resolved itself.
Now it is really easy to traverse Table n, because we can use the exact same techniques
that we used to traverse the previous tables. Let us just illustrate how to cover the table
for n = 12 on Figure 23. The construction needs to be changed for di erent parity in the
same way as it was for the smaller tables. We use the letters A and B as before.
63
B5
B7
B8
B9
BA
B6
B1
B2
B3
47
48
49
4A
46
41
42
43
58
59
5A
56
51
52
53
79
7A
76
71
72
73
8A
86
81
82
83
96
91
92
93
A1
A2
A3
62
63 13
PSfrag replacements
x
y
z
w
Figure 23: Table 12
4.3 The general problem
Of course the immediate question arises if this technique exhibited here is useful for solving
the general problem. If nothing else, maybe for constructing a 4-stub. In our opinion, with
hard work, it is probably possible to construct a 4-stub using the same ideas, but it is at
least questionable if the gained insight would be enough to solve the general question.
This argument has several points that are very special for 3-stubs. The basic idea, that
we cover the 2-sets \row by row" and then the 3-sets \table by table" does not work without
modi cation. This is why we needed to do special things in the beginning of covering the
2-sets and even more special things in the beginning of covering the 3-sets. The fact that
the two \tweaks" t together perfectly, almost seems to be lucky.
We hope that this construction, or a simpli cation of this, can provide a general pattern,
that will help answer the question if there is monotone Hamiltonian path of every subset
lattice.
64
REFERENCES
[1] Ahlswede, R. and Daykin, D. E., \An inequality for the weights of two families
of sets, their unions and intersections," Z. Wahrsch. Verw. Gebiete, vol. 43, no. 3,
pp. 183{185, 1978.
[2] Alon, N. and Scheinerman, E. R., \Degrees of freedom versus dimension for con-
tainment orders," Order, vol. 5, no. 1, pp. 11{16, 1988.
[3] Bj orner, A., Las Vergnas, M., Sturmfels, B., White, N., and Ziegler, G. M.,
Oriented Matroids, vol. 46 of Encyclopedia of Mathematics and its Applications. Cam-
bridge University Press, 2 ed., 1999.
[4] Bogart, K. P. and Trotter, W. T., \Maximal dimensional partially ordered sets.
II. Characterization of 2n-element posets with dimension n," Discrete Math., vol. 5,
pp. 33{43, 1973.
[5] Bollob as, B., Modern Graph Theory. Springer, 2002.
[6] Brightwell, G. R., Felsner, S., and Trotter, W. T., \Balancing pairs and the
cross product conjecture," Order, vol. 12, pp. 327{349, 1995.
[7] Brightwell, G. R. and Trotter, W. T., \A combinatorial approach to correlation
ineqialities," Discrete Math., vol. 257, pp. 311{327, 2002.
[8] Dilworth, R. P., \A decomposition theorem for partially ordered sets," Ann. of
Math. (2), vol. 51, pp. 161{166, 1950.
[9] Felsner, S., Fishburn, P. C., and Trotter, W. T., \Finite three-dimensional
partial orders which are not sphere orders," Discrete Math., vol. 201, no. 1-3, pp. 101{
132, 1999.
[10] Felsner, S. and Trotter, W. T., \Colorings of diagrams of interval orders and
-sequences of sets," Discrete Math., vol. 144, no. 1-3, pp. 23{31, 1995. Combinatorics
of ordered sets (Oberwolfach, 1991).
[11] Fishburn, P. C., \Intransitive indi erence with unequal indi erence intervals," J.
Math. Psych., vol. 7, pp. 144{149, 1970.
[12] Fishburn, P. C., \A correlational inequality for linear extensions of a poset," Order,
vol. 1, no. 2, pp. 127{137, 1984.
[13] Fishburn, P. C. and Trotter, W. T., \Angle orders," Order, vol. 1, pp. 333{343,
1985.
[14] F uredi, Z., Hajnal, P., R odl, V., and Trotter, W. T., \Interval orders and shift
graphs," in Sets, graphs and numbers (Hajnal, A. and S os, V. T., eds.), vol. 60 of
Colloq. Math. Soc. J anos Bolyai, pp. 297{313, Amsterdam: North-Holland, 1992.
65
[15] Goodman, J. E., \Pseudoline arrangements," in Handbook of Discrete and Computa-
tional Geometry (Goodman, J. E. and O?Rourke, J., eds.), ch. 5, pp. 83{109, CRC
Press LLC, 1997.
[16] Hiraguchi, T., \On the dimension of orders," Sci. Rep. Kanazawa Univ., vol. 4, no. 1,
pp. 1{20, 1955.
[17] Johnson, R. J., \Long cycles in the middle two layers of the discrete cube," J. Combin.
Theory Ser. A, vol. 105, no. 2, pp. 255{271, 2004.
[18] Kahn, J. N. and Saks, M., \Balancing poset extensions," Order, vol. 1, no. 2, pp. 113{
126, 1984.
[19] Ne set ril, J. and R odl, V., \A short proof of the existence of highly chromatic
hypergraphs without short cycles," J. Combin. Theory Ser. B, vol. 27, no. 2, pp. 225{
227, 1979.
[20] Scheinerman, E. R. and Wierman, J. C., \On circle containment orders," Order,
vol. 4, no. 4, pp. 315{318, 1988.
[21] Shepp, L. A., \The FKG inequality and some monotonicity properties of partial
orders," SIAM J. Algebraic Discrete Methods, vol. 1, pp. 295{299, September 1980.
[22] Shepp, L. A., \The XYZ conjecture and the FKG inequality," Ann. Probability,
vol. 10, pp. 824{827, August 1982.
[23] Stanley, R. P., \Two combinatorial applications of the Aleksandrov{Fenchel inequal-
ities," J. Combin. Theory Ser. A, vol. 31, pp. 56{65, 1981.
[24] Szpilrajn, E., \Sur l?extension de l?ordre partiel," Fund. Math., vol. 16, pp. 386{389,
1930.
[25] Trotter, W. T., Combinatorics and Partially Ordered Sets. The Johns Hopkins
University Press, 1992.
66