Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Why do you say that "a partial order on a finite set has maximal and minimal elements"? –  Weltschmerz May 30 '12 at 4:05
    
Indeed, it is rather easy to construct counterexamples to the stated claim by exhibiting countries whose directed graph consists of two or more connected components. There are two ways to fix this: rephrase to instead claim that there exist cities such that all roads are either into it, or that all roads are out of it; alternatively, assume further that between any two cities there is a possible road trip (one or the other direction), so that a total order is defined. Total orders on finite sets have maximal and minimal elements. –  anon May 30 '12 at 4:10
    
@Weltschmerz: Because (in ZF) on non-void finite sets, every partial order does have a minimal and a maximal element. –  Cameron Buie May 30 '12 at 4:36
    
@anon: Excellent point. Connectedness is crucial, or else a rephrasing such as you offer is necessary (though I would further refine it to say "either all roads connected to it are into it, or all such roads are out of it"). One further clarification: total orders on finite sets have greatest and least elements--which are, of course, maximal and minimal, respectively--but even if not total, the maximality and minimality conditions are attained. –  Cameron Buie May 30 '12 at 4:40
1  
@anon: The claim is simply that there is at least one source and at least one sink; this is true whether or not the graph is connected. The problem could be stated better, but it clearly does not mean that there is a city from which every road leaves. –  Brian M. Scott May 30 '12 at 4:43

1 Answer 1

up vote 2 down vote accepted

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)<n(y)$ 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)<n(x^-)$, 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.

share|improve this answer
    
Thanks, great answer. –  Mat.S May 30 '12 at 13:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.