11
$\begingroup$

A finite lattice is planar if it admits a Hasse diagram which is a planar graph (we want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element respects the order).

Remark: See the paper Planar lattices and planar graphs (1976) by C. R. Platt :
It is shown that a finite lattice is planar if and only if the (undirected) graph obtained from its (Hasse) diagram by adding an edge between its least and greatest elements is a planar graph.

The $B_3$ lattice (below) is not planar.
enter image description here

Question: Is a finite distributive lattice planar iff it admits no sublattice isomorphic to $B_3$?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ As a graph it is planar. You need to specify if you want an orientation of the plane and an order preserving map from the lattice to the plane of representation with additional properties for the induced edges. $\endgroup$
    – The Masked Avenger
    Commented Feb 21, 2015 at 19:37
  • 1
    $\begingroup$ You might ask what is the smallest distributive lattice that contains a subgraph homeomorphic (or appropriately morphic) to K5 or K3,3. $\endgroup$
    – The Masked Avenger
    Commented Feb 21, 2015 at 19:43
  • 1
    $\begingroup$ Are the lattices meant to be finite? If not, what is your generalization of Hasse diagrams to infinite lattices? $\endgroup$
    – Emil Jeřábek
    Commented Feb 21, 2015 at 20:07
  • 3
    $\begingroup$ Pursuant to The Masked Avenger's first comment, maybe you want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element is its rank in the lattice. $\endgroup$
    – Todd Trimble
    Commented Feb 21, 2015 at 20:14
  • $\begingroup$ @TheMaskedAvenger: you're right, thank you. I've edited an additional assumption. See also the paper Planar lattices and planar graphs $\endgroup$
    – Sebastien Palcoux
    Commented Feb 21, 2015 at 22:45

3 Answers 3

Reset to default
16
$\begingroup$

A stronger result is due to R. Wille. See for instance page 3 of http://www.math.uh.edu/~hjm/1973_Lattice/p00512-p00518.pdf.

Improve this answer
$\endgroup$
9
$\begingroup$

If I may be permitted to extract Wille's theorem ("On modular lattices of order dimension two") to which Professor Stanley refers (remember, this is 1973!):

Theorem: A modular lattice $\mathfrak{M}$ is planar iff $\mathfrak{M} - \{ d \in \mathfrak{M} \mid d \text{ is doubly irreducible} \}$ is a planar distributive lattice iff $\mathfrak{M}$ does not contain any of the posets of figures 1 and 2 as a subposet.

    Figs1&2

Improve this answer
$\endgroup$
1
  • $\begingroup$ (Thanks for the improvement, @senshin.) $\endgroup$
    – Joseph O'Rourke
    Commented Feb 22, 2015 at 1:44
9
$\begingroup$

It's already been answered positively, but here's another argument that shows something a little stronger: every finite distributive lattice either contains a B3 (and is not planar) or it can be drawn as a planar grid graph.

By Birkhoff's representation theorem, every finite distributive lattice is isomorphic to the lattice of lower sets of a finite partially ordered set. If this partial order has width three or more, (that is, if it has an antichain of three elements), then they generate a B3 and the lattice is not planar. And if the partial order has width two, then by Dilworth's theorem it can be decomposed into two chains. This decomposition can be used to embed the lattice as a grid graph, by setting the two coordinates of each lower set to be the numbers of elements it has in each of the two chains (and then rotating the whole thing by 45 degrees to make it an upward drawing).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .