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 '20 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 '20 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 '20 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 '20 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 '20 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 '20 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 '20 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 '20 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 '20 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 at 23:16
  • $\begingroup$ Is there an existing way to obtain the Stanley lattice in Sage? $\endgroup$
    – Mare
    May 19 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 at 11:38
  • 1
    $\begingroup$ @Mare: Or "P = Partition(reversed([1..n])).cell_poset().order_ideals_lattice()" $\endgroup$ May 19 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 at 9:07
  • 1
    $\begingroup$ @F.C.: (strong) Bruhat is not a lattice, however, and the question asked specifically about lattices. $\endgroup$ May 19 at 13:03
  • $\begingroup$ oh, right. Missed that, sorry. $\endgroup$
    – F. C.
    May 19 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 '20 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 '20 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 '20 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 '20 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 '20 at 12:14
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$

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$

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$
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, privacy policy and cookie policy

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