11
$\begingroup$

I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs.

I am mosty interested in lattices defined on the objects of a fixed size.

To make later usage easier, I would like to combine all lattices defined on one set of objects into one answer, and identify sets of objects which are in bijection.

My motivation for creating this list is that I realized how limited my supply of examples of lattices is.

$\endgroup$
7
  • 2
    $\begingroup$ Here is a catalog of posets and lattices implemented in SageMath. $\endgroup$ Jun 20, 2020 at 12:23
  • 2
    $\begingroup$ (I've been noting when the lattices are distributive, because if your goal is to have a collection of interesting lattices, distributive lattices are in a sense very boring.) $\endgroup$ Jun 20, 2020 at 14:12
  • 1
    $\begingroup$ @SamHopkins, you are unstoppable :-) Noting distributivity is a great idea, but I must say that also distributive lattices may be very useful! $\endgroup$ Jun 20, 2020 at 14:18
  • 2
    $\begingroup$ Reverse plane partitions or semistandard tableaux of a given shape with entries from a given set also form distributive lattices with respect to entrywise comparison. More generally, this holds for P-partitions of any given labelled poset. $\endgroup$ Jun 20, 2020 at 18:06
  • 2
    $\begingroup$ The lattices I find most interesting are distributive! Specific distributive lattices are interesting when they can be naturally constructed on nice combinatorial objects (other than order ideals of a given poset). $\endgroup$ Jul 6, 2020 at 16:10

11 Answers 11

9
$\begingroup$

Lattices are prevalent when one deals with integer partitions. Let me give a few examples with pictures, that I hope you will enjoy despite the poor quality due to bitmap conversion.

The dominance order, that you already cited, is a lattice; it is not distributive and not graded, but it has nice self-similar properties. Here is a picture of its Hasse diagrams for $n=7$ and $n=20$:

                                    Dominance ordering over partitions of 7

   Dominance ordering over partitions of 20

The reachable configurations of the linear Sand Pile Model (SPM), where one starts with a pile of $n$ grains, and they may fall under the condition that the sequence of piles remains decreasing, is also a lattice. It is a sub-order of the lattice above. It is not distributive either, but it is graded, and has nice self-similar features too. Here is the Hasse diagram for $n=40$.

                             configuration lattice of the SPM with n=40

Ice Pile Models (IPM) are generalizations of the two above cases, where the grains may slip from one column to another under some conditions. The induced orders are non-graded lattices, and one may obtain not only partitions but also compositions of a given integer.

The examples above are partitions of a given integer; one may also consider integer partitions of given maximal part and/or number of parts.

This leads to finite distributive sub-lattices of the Young Lattice, strongly related to Dyck paths, already cited in previous answers. For instance, if we consider partitions in at most $3$ parts of value at most $3$, we obtain the following representations (the rightmost one is the lattice of Dyck paths with three steps in each direction):

    Ferrer diagrams        tuples partitions        Dyck paths

These can be generalized to plane partitions (or piles of cubes), solid partitions and actually generalized integer partitions on graphs introduced, I think, by Stanley in his seminal book "Ordered Structures and Partitions". Again, we obtain distributive lattices, and here is the case of planar partitions contained in a 3x3x2 volume:

                                       hexagon tilings - lattice

As you may see above, these partitions are equivalent to tilings of an hexagon with lozenges, with the order induced by flips of three tiles. In higher dimensions, we obtain tilings of 2D-gons, with the same flip ordering. They are not always lattices, but they are disjoint unions of distributive lattices, because of their relation to generalized integer partitions. For instance, here is the set of all tilings of a unit decagon:

                       tilings of a decagon with lozenges, and flips

Other kinds of tilings with flips induce distributive lattices, like tilings by dominoes, and generalized tilings with height functions.

Let me add a last example, because I love its drawing. If one considers, for a given $b$, the different ways to write a given number $n$ as a sum of powers of $b$, then one obtains a self-similar distributive lattice. For instance, for $n=80$ and $b=2$:

partitions of 80 into powers of 2

$\endgroup$
3
$\begingroup$

Set partitions, https://oeis.org/A000110

$\endgroup$
4
  • $\begingroup$ And I recall being told that every lattice is isomorphic to a partition lattice? Or was that just for finite lattices? $\endgroup$
    – bof
    Jun 20, 2020 at 11:43
  • 1
    $\begingroup$ @bof: No, there are many examples of finite lattices that are not partition lattices. Already a 3-element chain (totally ordered set) isn't. $\endgroup$ Jun 22, 2020 at 20:32
  • $\begingroup$ @NathanReading Huh? There is a $3$-element chain in the lattice of partitions of a $3$-element set. $\endgroup$
    – bof
    Jun 22, 2020 at 20:50
  • 2
    $\begingroup$ So do you mean every lattice is isomorphic to a sublattice or subposet of a partition lattice? Your original comment would seem to say that the 3 element chain should be a partition lattice, and that's certainly not true. (I hope none of this sounds disagreeable... just looking for the math. If there is some true sentence that says "Every finite lattice ... partition lattice", I'm interested.) $\endgroup$ Jun 23, 2020 at 0:35
3
$\begingroup$

Catalan objects, http://oeis.org/A000108

  • noncrossing partition lattice (also known as Kreweras lattice)
  • Tamari lattice - this lattice is not distributive but it is semidistributive
  • Dyck paths ordered by containment (also known as Stanley lattice) - this lattice is distributive

Bernardi, Olivier; Bonichon, Nicolas, Intervals in Catalan lattices and realizers of triangulations, J. Comb. Theory, Ser. A 116, No. 1, 55-75 (2009). ZBL1161.06001.

$\endgroup$
4
  • $\begingroup$ There's another weirder one which is the lattice of nonnesting partitions (where a partition is nonnesting if whenever $a < b < c < d$ and $a,d$ are consecutive elements of a block, then $b$ and $c$ do not belong to the same block). $\endgroup$ Mar 19, 2021 at 23:16
  • $\begingroup$ Is there an existing way to obtain the Stanley lattice in Sage? $\endgroup$
    – Mare
    May 19, 2021 at 10:41
  • 1
    $\begingroup$ P = lambda n: Poset([DyckWords(n), lambda D1, D2: all(h1 <= h2 for h1, h2 in zip(D1.heights(), D2.heights()))]) $\endgroup$ May 19, 2021 at 11:38
  • 1
    $\begingroup$ @Mare: Or "P = Partition(reversed([1..n])).cell_poset().order_ideals_lattice()" $\endgroup$ May 19, 2021 at 13:06
3
$\begingroup$

Permutations, http://oeis.org/A000142

  • weak (Bruhat) order - this lattice is not distributive, but it is semidistributive
  • shard intersection order
  • the ``bubble-sort'' order or more generally any of the sorting orders of Armstrong - this lattice (which sits between weak and strong order) is distributive

Reading, Nathan, Noncrossing partitions and the shard intersection order, Krattenthaler, Christian (ed.) et al., Proceedings of the 21st annual international conference on formal power series and algebraic combinatorics, FPSAC 2009, Hagenberg, Austria, July 20–24, 2009. Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS). Discrete Mathematics and Theoretical Computer Science. Proceedings, 745-756 (2009). ZBL1391.05283.

$\endgroup$
3
  • $\begingroup$ Of course, there is also the classical (strong) Bruhat order. More confidential is the parabolic support order, introduced by Bergeron, Hohlweg and Zabrocki. $\endgroup$
    – F. C.
    May 19, 2021 at 9:07
  • 1
    $\begingroup$ @F.C.: (strong) Bruhat is not a lattice, however, and the question asked specifically about lattices. $\endgroup$ May 19, 2021 at 13:03
  • $\begingroup$ oh, right. Missed that, sorry. $\endgroup$
    – F. C.
    May 19, 2021 at 18:11
2
$\begingroup$

Alternating Sign Matrices, https://oeis.org/A005130

  • distributive lattice of monotone triangles ordered componentwise, which is the MacNeille completion of (strong) Bruhat order on the symmetric group.
$\endgroup$
2
$\begingroup$

$n^{n-2}$ objects (labeled trees or parking functions)

  • the Cartesian product of $n-2$ chains of length $n$ can be interpreted as a (distributive) lattice on the Prüfer codes of labeled trees on $n$ vertices.
$\endgroup$
10
  • $\begingroup$ @RichardStanley: if we consider the poset of regions of the Shi arrangement where $\hat{0}$ is the region containing $(1,2,3,...,n)$, does this form a lattice? The poset on parking functions you mention is related to the Shi arrangement via the Pak-Stanley labeling; the one I am talking about is more related to the Athanasiadis-Linusson bijection (arxiv.org/abs/math/9702224). $\endgroup$ Jun 22, 2020 at 15:18
  • 1
    $\begingroup$ @RichardStanley: If I remember correctly, whether the "weak order" on a hyperplane arrangement is a lattice has something to do with whether the regions are simplicial? I'm not sure if this property holds for the Shi arrangement with this choice of base region; but I checked it in the case $n=3$. $\endgroup$ Jun 22, 2020 at 15:25
  • $\begingroup$ I checked (using SageMath) the case $A_4$, in which the poset of regions (with an element adjoined so it has a top and a bottom element) is not a lattice, apparently. $\endgroup$ Jun 23, 2020 at 12:39
  • 1
    $\begingroup$ @Sam Hopkins: In your second comment from the top, I believe you might be referring to a result of Björner, Edelman and Ziegler regarding when the poset of regions is a lattice given a choice of base region. For supersolvable arrangements, I recall that such a region can always be chosen. $\endgroup$
    – user35313
    Jun 24, 2020 at 21:03
  • 1
    $\begingroup$ @Sam Hopkins: You are indeed correct! I thought I would mention the supersolvable case simply to highlight a class where one obtains lattices. Should've stated it wasn't relevant in the Shi case. $\endgroup$
    – user35313
    Jun 25, 2020 at 12:14
2
$\begingroup$

Fibonacci numbers: Two examples of distributive lattice structures

$\bullet$ Dominance Order on $\Bbb{YF}_n$: A fibonacci word is a string of the form $u = a_1 \cdots a_k$ with digits $a_i \in \{1, 2\}$. Define its length by $|u| := a_1 + \cdots + a_k$ and the let $\Bbb{YF}_n$ denote the set of all fibonacci words of length $|u|=n$. Clearly the cardinality of $\Bbb{YF}_n$ is $F_n$ where $F_n$ is the $n$-th fibonacci number. Given two fibonacci words $u= a_1 \cdots a_k$ and $v = b_1 \dots b_\ell$ of equal length declare $u \unlhd v$ if $a_1 + \cdots + a_i \leq b_1 + \cdots + b_i$ for $1 \leq i \leq \mathrm{min}(k,\ell)$. This is a distributive lattice.

$\bullet$ Ideals of the Zig-Zag Poset $\mathcal{Z}_n$: The Zig-Zag poset $\mathcal{Z}_n$ is the index set $[1, \dots, n]$ where all even numbers are maximal and incomparable, all odd numbers are minimal and incomparable, and $2i$ covers its odd neighbors $2i-1$ and $2i+1$ (whenever the latter is present). Clearly the number of (lower) ideals is $F_{n+1}$ and the set $\mathrm{J}\big( \mathcal{Z}_n \big)$ of all (lower) ideals ordered by inclusion will be a distributive lattice.

Maybe I'll add more later, ines.

$\endgroup$
9
  • $\begingroup$ Are these two distributive lattices on Fibonacci number objects not the same? $\endgroup$ Nov 15, 2021 at 21:40
  • 1
    $\begingroup$ They shouldn't be: When $n=3$ the dominance order is the total order $1111 \lhd 112 \lhd 121 \lhd 211 \lhd 22$ while the ideals $\{1 \}$ and $\{3 \}$ are incomparable with the respect to the inclusion order of $\mathrm{J}(\mathcal{Z}_3)$. $\endgroup$ Nov 16, 2021 at 19:31
  • 1
    $\begingroup$ Interesting. So what is the $P$ for which dominance order on fibonacci words is $J(P)$? $\endgroup$ Nov 16, 2021 at 19:33
  • 1
    $\begingroup$ I think I finally figured out the answer to my question in the comment above, thanks to a talk by Richard Stanley. It should be the "comb poset"; see page 57 of math.mit.edu/~rstan/transparencies/posets.pdf $\endgroup$ Sep 4, 2023 at 13:40
  • 1
    $\begingroup$ @SamHopkins Hi, the distributive lattice of order ideals of the comb poset (of size $2n$) has a unique maximal element which cover exactly $n$ elements. On the other hand, the dominance order on fibonacci words of size $2n$ has a unique maximal element which covers exactly one element. So I don't see how you can recover the $\Bbb{YF}_{2n}$ dominance order from the comb poset in this way. $\endgroup$ Sep 4, 2023 at 17:25
1
$\begingroup$

Integer partitions, http://oeis.org/A000041

$\endgroup$
1
$\begingroup$

$\binom{n}{k}$ objects, i.e., $k$-element subsets of $[n]$

$\endgroup$
1
  • $\begingroup$ I believe this is the same as dominance order on compositions of a fixed number into a fixed number of parts. $\endgroup$ Nov 15, 2021 at 15:28
1
$\begingroup$

All $2^n$ subsets of $[n]$

  • Boolean lattice - (distributive)
  • the interval $[\varnothing, (n,n-1,...,1)]$ of the shifted version of Young's lattice, this is the same as the dominance order on compositions of $n+1$ - (distributive)
$\endgroup$
1
$\begingroup$

Excerpt from "Distributive lattices, polyhedra, and generalized flows" by Stefan Felsner and Kolja Knauer:

Many researchers have constructed distributive lattices on sets of combinatorial objects, e.g.,

• domino and lozenge tilings of plane regions ([23] and others based on [27]).

• planar spanning trees ([11])

• planar bipartite perfect matchings ([16])

• planar bipartite d-factors ([8,22])

• Schnyder woods of planar 3-connected graphs ([4])

• Eulerian orientations of planar graphs ([8])

• α-orientations of planar graphs ([8,7])

• circular integer flows in planar graphs ([15])

• higher dimensional rhombic tilings ([18])

• c-orientations of graphs ([22]).



Perhaps you would find this answer by Vijay D to a MO-Q on dualities informative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.