Problem of the Week #140 - February 2, 2015

[Euge]

Here's this week's problem!

__________________

Problem. Suppose $S$ is a partially ordered set such that for some positive integer $n$, every finite subset of $S$ is a union of $n$ chains. Prove that $S$ is itself the union of $n$ chains.

__________________
Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Euge]

This week's problem was correctly solved by Fallen Angel. You can view his solution below.

Spoiler

We can assume that $S$ is not finite and we will call $\leq$ the partial order relation.

Suppose $S$ can not be splitted into the union of $n$ chains. Then there exists

$c_{1,1}\leq c_{2,1} \leq \ldots \leq c_{i_{1},1}$
$c_{1,2}\leq c_{2,2} \leq \ldots \leq c_{i_{2},2}$
$\vdots \hspace{1cm} \vdots \hspace{2cm} \vdots$
$c_{1,n+1}\leq c_{2,n+1} \leq \ldots \leq c_{i_{n+1},n+1}$

$n+1$ chains (eventually trivial) with the following property:

$c_{i_{j},j}\nleq c_{1,k}$ for every distinct $k, j$ so by transitivity $c_{i_{j},j}\nleq c_{i_{k},k}$ for every distinct $k, j$.

Hence the set $\mathcal{C}=\{c_{i_{1},1},c_{i_{2},2},\ldots ,c_{i_{n+1},n+1}\}$ is a finite set with $n+1$ elements where the restriction of the order $\leq$ is trivial, so can't be splitted into $n$ ordered chains

Here is also my solution, which uses a graph theory approach.

Spoiler

Introduce a graph $G$ with vertices in $S$ and edges made by two incomparable vertices. Graph $G$ is $n$-colorable if and only if $S$ is a union of $n$ chains, and every finite subset of $S$ is the union of $n$ chains if and only if every finite subgraph of $G$ is $n$-colorable. Hence, by assumption on $S$, all finite subgraphs of $G$ are $n$-colorable, which implies $G$ is $n$-colorable. So $S$ is a union of $n$ chains.