Consider the following Hasse diagrams. (i) a 4-element diamond: a bottom, two incomparable middle elements, and a top. (ii) a 5-element diagram in which two elements at the upper level share two common lower covers (a non-unique meet/join shape). (iii) a 6-element diagram with crossing edges in which a pair of elements has two incomparable upper bounds (and a pair has two incomparable lower bounds). (iv) a 5-element pentagon (N5): a bottom, a top, one side a 2-element chain and the other side a single element. Which all of the above represent a lattice? A. (i) and (iv) only B. (ii) and (iii) only C. (iii) only D. (i), (ii) and (iv) only
GATE 2008 · Discrete Mathematics · Lattice · medium
Answer: Only the diamond (i) and the pentagon (iv) have a unique join and meet for every pair, so the lattices are (i) and (iv) only: option A.
State and apply the lattice criterion: Scan each diagram for any pair of elements that has two incomparable minimal upper bounds (then the join is undefined) or two incomparable maximal lower bounds (then the meet is undefined). One such pair is enough to disqualify a diagram.
Classify the four diagrams: (i) The diamond's two middle elements meet uniquely at the bottom and join uniquely at the top: lattice. (iv) The pentagon N5 has a single top and bottom and every pair has a unique join and meet (it is a lattice, just non-modular): lattice. (ii) and (iii) each contain a pair whose upper (or lower) bounds are two incomparable elements, so the join (or meet) is not unique: NOT lattices. Therefore exactly (i) and (iv) are lattices, which is option A.