Redirected
in Graph Theory
1,443 views
0 votes
0 votes

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

in Graph Theory
1.4k views

4 Comments

In a Hasse diagram we don't show reflexive and transitive relations!
0
0
@Shivam Kasat because it is by default reflexive and transitive..that is why it is a poset(hasse diagram) in the first place..right?..what you are saying that {a,b,d} is a poset cant be true because it is not reflexive..
0
0

finally found what they want to be ask https://gateoverflow.in/2257/gate1997-6-1#4308

0
0

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.

1 comment

yes $^{6}C_{3}$
1
1

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true