I am playing with a problem (that's part of a much bigger problem) and trying to understand the best way to approach it and also if there are existing names for this or similar problems.
If I have a set say $\{b_0,b_1,...,b_{25}\}$ with a strict partial order (transitive reduction done):
$b_0 > b_1, b_0 > b_2, b_1 > b_3, b_2 > b_3, b_4 > b_5, b_6 > b_7, b_6 > b_8$, $b_7 > b_9, b_8 > b_9, b_{10} > b_{11}, b_{10} > b_{12}, b_{11} > b_{13}, b_{12} > b_{13}$, $b_{14} > b_{15}, b_{16} > b_{17}, b_{16} > b_{18}, b_{17} > b_{19}, b_{18} > b_{19}$, $b_{20} > b_{21}, b_{22} > b_{23}, b_{22} > b_{24}, b_{23} > b_{25}, b_{24} > b_{25}$
Could the following values be assigned to $b_0,...,b_{25}$ so that we continue to satisfy the partial order with $>$ taking it's usual meaning for integers:
3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,0
In this case the answer is no. The Hasse diagram of the partial order has 8 top points that must all take the value 3. Below them are only 13 vertices that could take the value 2 but the assignment set contains 14. So one 2 would have to be below another 2 which will not work.
I have a computer program generating millions of these problems. I will use Gecode (constraint satisfaction) to find cases that are not possible. That will give me something to play with. Thanks for any pointers.