1,446 views
0 votes
0 votes

The number of totally ordered sets compatible to the given POSET are ________.

1 Answer

3 votes
3 votes

The word $\textrm{ "partial" }$ in the names $\textrm{ "partial order" }$or $\textrm{ "partial ordered set " }$ is used as an indication that not every pair of elements needs to be comparable.

So to make this $\textrm{ "partial order" }$ a $\textrm{ "total order" }$, we need the relation to hold for every two element of the $\textrm{ "partial order" }$such that the properties that is shown by the given $POSET$ is also maintained after adding relations.

Currently between the set ${i,g,e}$ and ${j,h,f}$ there is no relation but there is some relation between ${i,g,e}$ ( since ${i,g,e}$ set and ${j,h,f}$ set are at same level in the given hasse diagram )

similarly we have no relation between $b$ and $c$.( since  they are at different level in the given hasse diagram. )

for eg:-

let the $POSET$ be defined by the binary relation $\leq$

this means  i$\leq$g$\leq$e and j$\leq$h$\leq$f  but we don't know any relation between i and h.


So the question is asking that in how many ways we can add some relation in the  POSET such that the properties shown in the given hasse daigram holds between the nodes after adding the new relations also.

for eg :- we can add the relation i$\leq$j  or g$\leq$j but not g$\leq$e because e$\leq$g in the given POSET.


In how many ways we can add relation e,f,g,h,i,j such that i$\leq$g$\leq$e and j$\leq$h$\leq$f always holds = $\frac{6!}{3! * 3!}$

similarly for b and c we can add b$\geq$c or b$\leq$c i.e. $2$ ways.

So total ways = $2*\frac{6!}{3! * 3!}$ = 40 ways.

Related questions

0 votes
0 votes
1 answer
1
Ramayya asked Jan 7
173 views
Maximum number of Simple graphs possible with $n$ vertices$2^{n(n-1)/2}$$2^{(n-1)/2}$$2^{n(n+1)/2}$$2^{n(n+1)}$
0 votes
0 votes
1 answer
4
Anand67222 asked Oct 14, 2023
300 views
How many simple directed (unweighted) graphs on the set of vertices {v0,v1,…v5} are there that have at most one edge between any pair of vertices? (That is, for two ver...