2
$\begingroup$

I am trying to prove that every partial order of a finite set is an intersection of a finite number of linear orders of this set. Can this be proved using these observations:

  1. a partial order has a linear extension
  2. this partial order is an intersection of its linear extensions
  3. there is a finite number of linear extensions

Or is there a simpler proof?

$\endgroup$
  • $\begingroup$ Yes, it can. This is how I’d prove it; I don’t see anything simpler, and this isn’t really very hard. $\endgroup$ – Brian M. Scott Jan 20 '15 at 19:33
  • $\begingroup$ Related to the bullet point 3, the paper makes a claim that every partial order is an intersection of linear extensions but let the partial order to be infinite so the new question math.stackexchange.com/questions/1695566/… to find out whether there is a mistake or misunderstanding in the paper. $\endgroup$ – hhh Mar 13 '16 at 12:51
  • $\begingroup$ Part 1 and 2 proved here. $\endgroup$ – hhh Mar 13 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.