The thing I find the most difficult is the transitive part. The only way that I know of is to see if the relation is transitive, but I have to do check if it is transitive for every relation possible on a given matrices. It gets quite cumbersome when you have a matrix of 5 elements or more. So is there some sort of shortcut?
How do you find the smallest partial order?
-2
$\begingroup$
discrete-mathematics
-
1What are you actually trying to do? – 2012-12-09
-
0Finding the smallest partial order for S={(1,5) (2,3) (2,4) (3,3) (4,3) (5,1)} – 2012-12-09
-
0What on earth does that mean? – 2012-12-09
-
0If you are trying to find the smallest partial order containing some relation, look at [closure operations](http://en.wikipedia.org/wiki/Reflexive_transitive_closure). – 2012-12-09
-
0it defines a relation matrix – 2012-12-09
-
0@Chris: I suspect that xeonphi wants to find the reflexive, transitive closure of $S$. – 2012-12-09
-
0I know what to do, but I want a quick way of doing it. – 2012-12-09
-
0@xeonphi How do you define the smallest partial order for $S$? – 2012-12-09
-
0@dtldarek: No kidding! Clearly I’ve been answering too many questions about equivalence relations lately. Thanks. However, I note that there’s going to be a problem with antisymmetry ... – 2012-12-09
-
0@dtldarek: Start by telling us what "smallest partial order for S" means. Like I asked already. – 2012-12-09
-
0Xeonphi, are you sure that there **is** a partial order containing $S$? Note that $S$ contains both $(1,5)$ and $(5,1)$, but a partial order is antisymmetric. – 2012-12-09
-
0@ChrisEagle Yep, but you were misunderstood ("What on earth does $S = \{\ldots\}$ mean?") and your question has been answered ("It defines a relation matrix."). ;-) – 2012-12-09
-
0@dtldarek: that doesn't answer my question at all. The smallest partial order for S is a relation matrix. Ok, WHICH RELATION MATRIX IS IT? – 2012-12-09
-
0@Chris: I no longer have any clear idea of what your point is. Are you very indirectly noting that this $S$ cannot be extended to a partial order on $\{1,2,3,4,5\}$, or what? – 2012-12-09
-
0My point is that I have no idea what question is being asked. There seems to be an opinion developing that the question is "what's the smallest partial order extending $S$". But I can't find anything from the OP to support that, and I would rather find out what they actually want rather than guess wildly. – 2012-12-09
-
0@Chris: It may prove to be wrong, but it’s not a wild guess: the original question and the OP’s comment defining $S$ tend to support that interpretation. – 2012-12-09