Chapter 9 Directed graphs & Partial Orders256
Corollary 9.10.11.Every partially ordered set withnelements has a chain of size
greater than
p
nor an antichain of size at least
p
n.
Proof. SettD
p
nin Lemma 9.10.10.
Example9.10.12.In the dressing partially ordered set,nD 10.
TrytD 3. There is a chain of size 4.
TrytD 4. There is no chain of size 5 , but there is an antichain of size 4 10=4.
Example9.10.13.Suppose we have a class of 101 students. Then using the product
partial order,Y, from Example 9.9.2, we can apply Dilworth’s Lemma to conclude
that there is a chain of 11 students who get taller as they get older, or an antichain of
11 students who get taller as they get younger, which makes for an amusing in-class
demo.
9.11 Equivalence Relations
A relation is anequivalence relationif it is reflexive, symmetric, and transitive.
Congruence modulonis an excellent example of an equivalence relation:
It is reflexive becausexx .modn/.
It is symmetric becausexy .modn/impliesyx .modn/.
It is transitive becausexy .modn/andyz .modn/imply thatxz
.modn/.
There is an even more well-known example of an equivalence relation: equality
itself. Thus, an equivalence relation is a relation that shares some key properties
with “D”.
9.11.1 Partitions
There is another way to think about equivalence relations, but we’ll need a couple
of definitions to understand this alternative perspective.
Definition 9.11.1. Given an equivalence relationR WA! A, theequivalence
classof an elementx 2 Ais the set of all elements ofArelated toxbyR. The
equivalence class ofxis denotedŒxçR. Thus, in symbols:
ŒxçRWWDfyjx R yg:
