1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
\noindent {\bf Q4)}
C1: f, d, j, k
C2: b, h, c, l, e, m, o
C3: g, n, a, i
Width = w = 3.
Antichain: $\{f,b,g\}$
\noindent {\bf Q5)}
1. If vertex A has vertex B in its down set, then vertex B has vertex A in its up set. Therefore, any vertex in the "difference" between two adjacent up sets in the "subset chain" outlined in the text must have a unique down set to any of the other "differences" and the same as every other vertex within the same "difference." If it didn't have the same down set as the other vertices, then a vertex which is in one down set but not the other could not have one of the original vertices in its up set (meaning they wouldn't be in the same difference, which is a contradiction). Similarly, if it had the same up set as a vertex within a different "difference," the vertex appearing "later" in the sequence should have appeared "earlier." The bijection establishes a similarity in size.
2. For all $x \in X$, $i \leq j$ in R because the largest (least) up set it could have must be smaller than the up sets of anything in its down set. As described in part 1, the subset sequence means that if there are i-1 lesser down sets, the vertices behind those downsets must define at least i-1 lesser up sets, so $j \geq i$.
3. If $x < y$ in P, x is in the down set of y and y is in the up set of x. All of the lesser (larger) up sets than x's also have lesser (smaller) down sets than y's. As a subposet, $|D|=|U|$ and with the addition of x's down set, k (number of y down sets) $>$ j (number of x up sets) in all cases.
4. For every up and down set, at least one vertex has that up or down set. This means that every integer is used at least once as a left endpoint and as a right endpoint in the final interval representation. If the interval representation could be made on [d-1], this would force two previously comparable intervals to be incomparable (a right endpoint that was one away from a left endpoint is now on the same integer). It is also unique because none of the endpoints could be moved w/o similar dilemma.
\noindent {\bf Q6)}
a. If each of the linear orders are "flipped" so that if $a < b$, $a' > b'$, then the intersection of those linear orders is the dual of P. The number of linear orders defining an intersection stays the same.
b. Let Q=(Y,Q) be a superset of P=(X,P) --- that is, $X \subset Y$ and $P = Q \cap (X \times X)$. Each linear order used to define Q can be stripped of elements in Y but not in X to create a set of linear orders defining P, so $dim(Q) \geq dim(P)$.
c. When a point is removed, all of its comparisons are removed, so it can just be "taken out" of each linear order. Once removed, there are two possible cases. Either all remaining linear orders are non-identical or more than one are the same. In the first case, the dimension stays the same. In the second, it can only decrease by one because if there were more than 2 identical orders, one of the orders would've been originally non-minimal (if point 'a' is removed and 3+ orders are removed, the one with 'a' positioned between its other two locations is redundant because any comparisons it defines are covered by one of the other two)
d. 3, for all.
e. Dillworth's theorem states that there is a maximal partition of size width=w into chains. The order of each chain must be preserved in every linear order by definition, so each element can be referred to by its chain without loss of generality. A first "basic order" can be created, containing all comparisons. It takes at most w-1 orders to distinctly label the invalid comparisons in that list (moving vertices from one chain along the line until all valid comparisons still exist creates one order without invalidating any proper relations).
f. A poset like the example on the left (complete bipartite except incomparability between opposites) with 2n vertices clearly has a width equal to n because all points from one independent set makes the maximum antichain. Its dimension is equal to n because it can only define one of the partner incomparabilities per linear order. In general, set 1 $<$ set 2, so a linear order has to look like "$2 < 4 ... 9 < 10 < 7 ...$" Within n linear orders, incomparability within independent sets can be easily defined.
\bye
|
