GATE CS Partial Orders and Lattices questions

Practise Partial Orders and Lattices questions for GATE CS. Explore official PYQs and original topic-wise quizzes, check answers and view available solutions. Free, no sign-in.

12 on this page

SubjectTopicYearType

Let

\text{P}

be the partial order defined on the set

\{1,2,3,4\}

as follows

P=\{(x, x) \mid x \in\{1,2,3,4\}\} \cup\{(1,2),(3,2),(3,4)\}

The number of total orders on

\{1,2,3,4\}

that contain

\text{P}

is __________.

Consider the set

X=\{a, b, c, d, e\}

under partial ordering

R=\{(a,a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e) \}

The Hasse diagram of the partial order

(X, R)

is shown below. The minimum number of ordered pairs that need to be added to

R

to make

(X, R)

a lattice is ______

Suppose

L = \left\{ p, q, r, s, t\right\}

is a lattice represented by the following Hasse diagram: For any

x, y \in L

, not necessarily distinct ,

x \vee y

and

x \wedge y

are join and meet of

x, y

, respectively. Let

L^3 = \left\{\left(x, y, z\right): x, y, z \in L\right\}

be the set of all ordered triplets of the elements of

L

. Let …

Consider the set

S =\{ a , b , c , d\}.

Consider the following

4

partitions

π_1,π_2,π_3,π_4

S : π_1 =\{\overline{abcd}\},\quad π_2 =\{\overline{ab}, \overline{cd}\},

\quad π_3 = \{\overline{abc}, \overline{d}\},\quad π_4 =\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\}

. Let

\prec

be the partial order on the set of partitions …

The following is the Hasse diagram of the poset

\left[\{a,b,c,d,e\},≺\right]

The poset is :

The inclusion of which of the following sets into

S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3, 4, 5\right\} \right\}

is necessary and sufficient to make

S

a complete lattice under the partial order defined by set containment?

A partial order

≤

is defined on the set

S=\left \{ x, a_1, a_2, \ldots, a_n, y \right \}

x

\leq _{i}

a_{i}

for all

i

and

a_{i}\leq y

for all

i

, where

n ≥ 1

. The number of total orders on the set S which contain the partial order

≤

In the lattice defined by the Hasse diagram given in following figure, how many complements does the element ‘

e

’ have?

Let

X = \{2, 3, 6, 12, 24\}

, Let

\leq

be the partial order defined by

X \leq Y

x

divides

y

. Number of edges in the Hasse diagram of

(X, \leq)

The Hasse diagrams of all the lattices with up to four elements are ________ (write all the relevant Hasse diagrams)

The less-than relation,

<,

on real number is

Consider the set of integers

\{1,2,3,4,6,8,12,24\}

together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?