Partial Orders and Lattices

GATE CS previous year questions · 2 questions

GATE CS 2025 Set 2 | Question 42

MSQ · 2 marks

Let \(\mathcal{F}\) be the set of all functions from \(\{1, \ldots, n\}\) to \(\{0,1\}\). Define the binary relation \(\preccurlyeq\) on \(\mathcal{F}\) as follows:

\(\forall f, g \in \mathcal{F},\ f \preccurlyeq g\) if and only if \(\forall x \in \{1, \ldots, n\},\ f(x) \le g(x),\) where \(0 \le 1\).

Which of the following statement(s) is/are TRUE?

Options for GATE CS 2025 Set 2 | Question 42

Explanation

Answer: (B), (C)

Each \(f \in \mathcal{F}\) is an \(n\)-bit vector, and \(f \preccurlyeq g\) compares the vectors position by position.

  • Reflexive: \(f(x) \le f(x)\). Antisymmetric: \(f \preccurlyeq g\) and \(g \preccurlyeq f\) force \(f(x) = g(x)\) for every \(x\). Transitive, because \(\le\) is. So it is a partial order (B).
  • Any two functions have a greatest lower bound, the pointwise minimum, and a least upper bound, the pointwise maximum, so it is a lattice (C): the Boolean lattice of subsets of \(\{1, \ldots, n\}\).
  • It is not symmetric: the all-0 function is \(\preccurlyeq\) the all-1 function, but not the other way round. So A is false, and D is false because an equivalence relation must be symmetric.

Answer: B, C

GATE CS 2024 Set 2 | Question 34

NAT · 1 mark

Let \(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 \(P\) is __________

Explanation

Answer: 5

A total order that contains \(P\) is a linear extension of \(P\): an arrangement of 1, 2, 3, 4 in which 1 comes before 2, 3 comes before 2, and 3 comes before 4. Only the minimal elements 1 and 3 can come first.

  • First 1: among 2, 3, 4 the element 3 must lead, and 2 and 4 follow in either order: 1, 3, 2, 4 and 1, 3, 4, 2.
  • First 3: the remaining 1, 2, 4 only need 1 before 2, which half of their \(3! = 6\) orders satisfy: 3, 1, 2, 4; 3, 1, 4, 2; 3, 4, 1, 2.

So \(2 + 3 = 5\) total orders contain \(P\).

Answer: 5