2
$\begingroup$

Can someone explain the concept of partial order in relation to this problem? (Source: Putnam and Beyond)

Problem:

In some country all roads between cities are one-way and such that once you leave a city you cannot return to it again. Prove that there exists a city into which all roads enter and a city from which all roads exit.

Answer:

Consider the oriented graph of roads and cities. By hypothesis, the graph has no cycles. Define a partial order of the cities, saying that $A < B$ if one can travel from $A$ to $B$. A partial order on a finite set has maximal and minimal elements. In a maximal city all roads enter, and from a minimal city all roads exit

Thanks.

  • 0
    @Brian: Oh, right.2012-05-30

1 Answers 1

2

A partial order on a set $X$ is a binary relation $\le$ with the following properties:

  1. for all $x\in X$, $x\le x$ (the relation is reflexive);
  2. for all $x,y,z\in X$, if $x\le y$ and $y\le z$, then $x\le z$ (the relation is transitive); and
  3. for all $x,y\in X$, if $x\le y$ and $y\le x$, then $x=y$ (the relation is antisymmetric).

An example of a partial order is the subset relation $\subseteq$ on any collection of sets: if $A,B$, and $C$ are sets, then: (1) $A\subseteq A$; (2) if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$; and (3) if $A\subseteq B$ and $B\subseteq A$, then $A=B$.

Another example is the relation of divisibility on the positive integers. If $m$ and $n$ are positive integers, write $m\mid n$ to mean that $n$ is an integer multiple of $m$. Then for any positive integers $k,m$, and $n$: (1) $k\mid k$; (2) if $k\mid m$ and $m\mid n$, then $k\mid n$; and (3) if $k\mid m$ and $m\mid k$, then $k=m$.

Now let $X$ be the set of cities, and for $x,y\in X$ let $x\le y$ mean that either $x=y$, or one can travel by road from $x$ to $y$. Clearly this relation is reflexive by definition, and it’s pretty easy to see that it’s also transitive. Finally, if there were $x,y\in X$ such that $x\le y$, $y\le x$, and $x\ne y$, then one could travel by road from $x$ to $y$ and back to $x$ again; by hypothesis this is impossible, so if $x\le y$ and $y\le x$, it must be the case that $x=y$. Thus, $\le$ is antisymmetric, and we have a partial order.

For each city $x\in X$ let $P(x)$ be the set of cities from which you can reach $x$ (not counting $x$ itself); call these the predecessors of $x$. Let $n(x)=|P(x)|$, the number of predecessors of $x$. It’s a consequence of transitivity that if $x\le y$, then $P(x)\subseteq P(y)$. Thus, $n(x) whenever $x$ and $y$ are distinct cities with $x\le y$. There are only finitely many cities, so there must be one, say $x^-$, which has as few predecessors as possible. If $n(x^-)>0$, there is at least one city $y\in P(x^-)$, i.e., at least one predecessor of $x^-$. But then $n(y), i.e., $y$ has fewer predecessors than $x^-$, contradicting the choice of $x^-$ as a city with the smallest possible number of predecessors. Thus, $n(x^-)=0$, and there is therefore at least one city, $x^-$, with no predecessors. Thus, all roads at $x^-$ must lead out of $x^-$.

Similarly, there must be a city, say $x^+$, with the largest number of predecessors, and by similar reasoning it cannot be a predecessor to any other city; thus, all roads at $x^+$ must lead into $x^+$.

All of this can be done without knowing what minimal and maximal elements of a partial order are.

A minimal element of a partial order $\langle X,\le\rangle$ is an element $x^-\in X$ with no strictly smaller element: if $x\in X$, and $x\le x^-$, then $x=x^-$. Similarly, a maximal element is an element $x^+\in X$ with no strictly larger element: if $x\in X$, and $x^+\le x$, then $x^+=x$. A partial order can have more than one minimal (or maximal) element. For instance, let $X=\{2,3,4,6\}$, and let the partial ordering be the divisibility ordering $\mid$: the minimal elements of this ordering are $2$ and $3$, and the maximal elements are $4$ and $6$.

A finite partial order must have at least one minimal element, because you can’t keep going down forever when there are only finitely many ‘steps’ available. For essentially the same reason it must have at least one maximal element. A minimal element is one with no strict predecessors: it’s exactly like the $x^-$ that we chose above. A maximal element is one that isn’t a predecessor to anything else: it’s exactly like the $x^+$ that we chose above. In other words, those who know the technical terminology can say it all very quickly, but the idea doesn’t really require the terminology.