in Graph Theory
1,525 views
0 votes
0 votes

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

in Graph Theory
1.5k views

30 Comments

is it 248 ?
0
0
Answer is 40. According to ME solution.
0
0
can you post their solution ?
0
0
Total topological sorts possible for this hasse diagrams.
0
0
topological sorts are 40, ok !

but what is the relation between the question and topological sort ?
0
0
That is what I wanted to ask.. is there any relationship between totally ordered set and topological sort?
 Because a-b-d should also be a TOSET
0
0

@Shaik Masthan topological sort is not possible for this graph. How 40 ?

0
0

@Ashutosh Khare 6 Why not brother?

 

0
0

@Shivam Kasat yeah sorry..its possible..i was thinking that its undirected graph..then realized that its a poset

1
1
@ashutosh

what will be the answer to this question brother! because i don't know if there is any relationship between being toset and topological sort
0
0

@Shivam Kasat yes answer will be 40 only..if that is the number of topological order..because TOSET is a order in which EVERY pair of element is comparable..so by topological ordering we are just writing various orders(starting with "a") in which every element will be related to one of the next element in order same as in given poset.

0
0

yeah! That's what I thought @Ashutosh Khare 6 Thanks

0
0
But asking about Sets !

Note that sets are not ordered. i mean to say {1,2,3}  = {3,2,1}
0
0

what should one conclude @Shaik Masthan

0
0

@Shaik Masthan didnt got you sir..what do you mean by "sets are not ordered" ?

0
0

can you list some of those 40 @Ashutosh Khare 6

0
0

@Shaik Masthan 1)a b c d e f g h i j k

2)a c b d f e h g j i k

0
0

these are sets ( due to question asked about sets ) , right ?

following sets are equal, {1,2,3}={1,3,2}={2,3,1} due to in the sets, elements can present in any order.

So all your 40 sets going to represent only one set !

 

@Shivam Kasat

as per me, we have to calculated all the sub lattices to the given lattice

0
0

A poset is called toset if every pair of element in that set are comparable(related),
ain't {a,b,d} a Toest? @Shaik Masthan 

0
0
yes, it is also a sublattice of the given lattice, right ?
0
0

@Shaik Masthan yes it is asked about sets..but it says ORDERED set..and element cant be written in any order in ORDERED set..thats why they are called Partially ordered set or totally ordered set..therefore all 40 will be different ordered sets..correct me if im wrong

1
1

correct @Ashutosh Khare 6 this the difference between totally ordered set and POSET.

0
0

@Shivam Kasat @Shaik Masthan {a,b,d} cant be a toset because every element of poset is not present in it

0
0

@Ashutosh Khare 6 {a,b,d} is a toset but it wont be counted here as the questions says Toset which are compatible to the given poset ! M I right

That why we counted topological sorts.

0
0
@Shivam Kasat see tosets are nothing but the posets in which every pair of elements are comparable..so by saying {a,b,d} is a toset..first it should be a poset..which its not(why?)..so it cant be a toset
0
0

@Ashutosh Khare 6 why {a,b,d} is not a poset?

0
0

@Shivam Kasat because its violating the simple partial ordering relation property i.e reflexiveness

0
0
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