On some polytopes attached to preorders¶

Frédéric Chapoton

C.N.R.S. and Université de Strasbourg 🇫🇷

joint work with

Christos A. Athanasiadis

National and Kapodistrian University of Athens 🇬🇷

Algebraic Combinatorics and Finite Groups IV ; July 2026

drawing drawing

About some partial orders contained in $\mathbb{N}^n$ for the component-wise partial order.

Their elements are lattice points in some lattice polytopes.

An amusing duality between the poset aspect and the polytopal aspect.

The original motivation came from a close relation with combinatorics of cluster algebras and noncrossing partitions.

Preorders¶

The starting data is a finite preorder :

a finite set $I$, endowed with a relation $\leq$ which is transitive and reflexive.

For example : any total order on $I$, any partial order on $I$, or the relation where any element is smaller than any other.

One has an equivalence relation $a \simeq b$ when $a \leq b$ and $b \leq a$. Then the quotient by $\simeq$ becomes a partial order.

Our viewpoint : Hasse diagrams where every "vertex" contains at least one and maybe several elements.

Here is a random example on $I=\{a,b,c,d,e,f,g\}$ :

 ╭──{a,c}──╮ {g}
 │         │  │
{b}       {f}─╯
 │         │ 
{d}       {e}

where the preorder is increasing from bottom to top.

💎 The Polytope¶

Let us consider a preorder $t$ on the finite set $I$.

Recall that a lower ideal $L$ in a preorder $t$ is a subset of elements closed under adding smaller elements. In particular, $L$ is the union of some vertices.

We define a polytope by inequalities. Consider $\mathbb{R}^I$ with coordinates $x_i$ for $i \in I$.

Let us define the polytope $Q_t$ by the conditions $x_i \geq 0$ for all $i \in I$ and

$$\sum_{i \in L} x_i \leq |L|$$

for every lower ideal $L$.

Proposition : This defines a lattice polytope (vertices are lattice points) which is empty (no lattice point inside). This sends disjoint union to Cartesian product.

Note : Here lattice point means point with integer coordinates.

An example of polytope¶

Let us consider the preorder

 ╭{a}╮
 │   │
{b} {c,d}

Then the defining inequalities are

$$x_a \geq 0,\quad x_b \geq 0,\quad x_c \geq 0,\quad x_d \geq 0$$

and

$$x_a+x_b+x_c+x_d \leq 4,\quad x_b+x_c+x_d \leq 3 ,\quad x_b \leq 1 \quad \text{and}\quad x_c+x_d \leq 2.$$

In this case, the second inequality is superflous, as the lower ideal $\{b,c,d\}$ is not connected.

Note : for the full lower ideal, one always gets that the sum of all coordinates $\leq n$. So this is a polytope.

The Poset¶

Once the polytope $Q_t$ is defined, the poset $P_t$ is very simple :

  • its elements are all lattice points in the polytope $Q_t$,

  • the order relation is termwise comparison : $a\leq b$ if and only if $a_i \leq b_i$ for all $i \in I$.

The posets $P_t$ are graded posets, where grading is the sum of coordinates, with one unique minimum $(0,0,\ldots,0)$ and usually several maxima.

They are visually very cubical, the union of cubical cells. Cover relations = one coordinate is increased by $1$.

See the pictures at the beginning.

🕵️ Perché ?¶

The story started with a discovery in the "Catalan" case or type $\mathbb{A}$ case, to be presented soon.

Then there was a similar type $\mathbb{B}$ case, even simpler, almost too simple.

And then, investigating type $\mathbb{D}$ failed but not completely, and revealed a connexion with halohedra !

And then came a connexion with Hochschild polytopes. And then a connexion with some Stokes polytopes.

This leads to a first general theory about arbor polytopes, that unified all the previous cases.

And then came the further extension to preorder polytopes, that supersedes and widely extends the case of arbors.

The special case named "Catalan"¶

We consider the preorders which are total orders $1 \leq 2 \leq \cdots \leq n$.

If the coordinates are $x_1, \ldots, x_n$, then

the inequalities are $x_1 \leq 1$, $x_1+x_2 \leq 2$, ..., $x_1+x_2+ \cdots+x_n \leq n$.

Looking at integer solutions, one can recognize the usual definition of non-decreasing parking functions.

So the cardinality of the set of lattice points is indeed a Catalan number.

The polytope is the famous Pitman-Stanley polytope.

These posets have not been studied much.

They belong to the family of "Avalanche posets" introduced by Combe-Giraudo.

Here is the poset for $n=3$ :

drawing

M-triangles¶

Recall the definition of $M$-triangle, a polynomial built using Möbius numbers, that generalizes the characteristic polynomial.

Let $P$ be a graded poset, then the $M$-triangle of $P$ is the two-variables polynomial

$$M_P(X,Y) = \sum_{a\ \leq b} \mu_P(a,b) X^{|a|} Y^{|b|},$$

where $\mu_P$ is the Möbius function and $|\cdot|$ is the grading.

Note that the power $Y$ is at least that of $X$ in every monomial in the sum. Hence the name.

For example, for the poset of noncrossing partitions of $4$ points on a circle, ordered by refinment, one finds $$ \left(\begin{array}{rrrr} -5 & 10 & -6 & 1 \\ 10 & -16 & 6 & . \\ -6 & 6 & . & . \\ 1 & . & . & . \end{array}\right) $$ with the constant term on the bottom left.

The diagonal just count elements according to the grading.

The leftmost column is the characteristic polynomial.

Transmutation 🪄 of $M$-triangles¶

Let us introduce a bizarre operation on $M$-triangles, called transmutation :

$$ \overline{m}(X,Y) = m\left(\frac{1-Y}{1-XY},1-XY\right).$$

This is still a polynomial. One easily checks that this is an involution.

Here is the $M$-triangle of the poset $P_t$ for the "Catalan" type of dimension $3$ : $$ \left(\begin{array}{rrrr} -1 & 6 & -10 & 5 \\ 3 & -8 & 5 & . \\ -3 & 3 & . & . \\ 1 & . & . & . \end{array}\right) \quad\text{whose transmutation is}\quad \left(\begin{array}{rrrr} -5 & 10 & -6 & 1 \\ 10 & -16 & 6 & . \\ -6 & 6 & . & . \\ 1 & . & . & . \end{array}\right) $$

Do you recognize something on the right ?

Transmutation with noncrossing partitions¶

This is a general statement, discovered by chance :

Proposition : The $M$-triangle of the poset $P_t$ of "Catalan" type in dimension $n$ is the transmutation of the $M$-triangle of the poset of noncrossing partitions of $n+1$ elements.

The proof is a computation, that does not explain anything.

Besides, these two posets share the same Zêta polynomial, that factorizes completely over $\mathbb{Q}$.

The proof is also a computation.

Recall : The Zêta polynomial of a poset, evaluated at the integer $N \geq 2$ is the number of chains $a_{1} \leq \cdots \leq a_{N-1}$.

Type $\mathbb{B}$¶

Here we consider preorders with just one vertex that contains the elements $\{1,2,\ldots,n\}$.

The polytope $Q_t$ is very simple, just one inequality $x_1 + x_2 + \cdots + x_n \leq n$, besides the conditions $x_i \geq 0$, so it is a simplex.

The poset $P_t$ is also very simple.

Proposition : The $M$-triangle of the poset $P_t$ of type $\mathbb{B}$ in dimension $n$ is the transmutation of the $M$-triangle of the poset of noncrossing partitions of type $\mathbb{B}_n$.

Besides, these two posets share the same Zêta polynomial, that factorizes completely over $\mathbb{Q}$.

Once again, the proof is not enlightening.

Other Coxeter types ?¶

A natural idea would be to extend to other finite Coxeter groups.

This does not work well. I could do something for $\mathbb{I}_2$, but not within the setting of preorders.

Nothing corresponds exactly to type $\mathbb{D}$ by transmutation. But something is very close to match.

Looking among preorders for those where the Zêta polynomial of $P_t$ factorizes completely over $\mathbb{Q}$, we see $3$ infinite families :

"Catalan" or type $\mathbb{A}$, type $\mathbb{B}$ and "halohedra" type.

Halohedra¶

This is a sequence of polytopes, closed cousins of associahedra and cyclohedra, less well-known.

They do not come from cluster theory.

One simple polytope in each dimension $n \geq 2$, first one is a pentagon.

The number of vertices are $5, 16, 55, 196, 714, 2640, 9867, \ldots$

with formula $c_{n-1} \times (3n-1)$ where $c_n$ is a Catalan number, see OEIS A051960.

  • a geometric meaning as compactification of a moduli space (Devadoss-Heath-Vipismakul)

  • a combinatorial definition : design-tubings of cycle graphs (Graph cubeahedra of cycle graphs)

This is a variation on the classical theory of graph-associahedra (tubes and tubings). One of the facets is a cyclohedra.

Two families of Halohedra type¶

On the side of preorders, on can consider two families :

  • a top vertex containing $n-1$ elements + a bottom vertex with $1$ element
  • a top vertex containing $1$ element + a bottom vertex with $n-1$ elements

Proposition : for both families, the poset $P_t$ in dimension $n$ has as many elements as vertices in the halohedra of dimension $n$.

Proof is an easy computation. There is also a finer equality of $h$-vectors.

But why is there such a coincidence between different preorders ?

☯ Ehrhart-Zêta duality¶

Let $t$ be a preorder.

One can define the opposite preorder $t'$ by the reversed relation. This is clearly an involution.

The polytopes $Q_t$ and $Q_{t'}$ are usually very different, not isomorphic in any sense. The same for the posets $P_t$ and $P_{t'}$.

Then, nevertheless, we have a surprising relationship between $t$ and $t'$.

For $t$ and $t'$ opposite preorders :

Theorem :

If $Z_t$ is the Zêta polynomial of the poset $P_t$ and $E_{t'}$ is the Ehrhart polynomial of the polytope $Q_{t'}$,

then $Z_t(u) = E_{t'}(u - 1)$.

Recall : the Ehrhart polynomial evaluated at an integer $N \geq 1$ counts lattice points in the polytope dilated by $N$.

Note : In particular, this implies that $P_t$ and $P_{t'}$ have the same cardinality (formula at $u=2$). Comparing leading coefficients gives an equality between the number of maximal chains in the poset $P_t$ and the normalized volume of the polytope $Q_{t'}$.

☯ A small example¶

In dimension 3, consider the two preorders of halohedra type. See the pictures at the beginning. Both have cardinality $16$.

Consider first $t$ with a top vertex of size $2$ and a bottom vertex of size $1$.

Then $E_t(u) = \frac{1}{6} \cdot (u + 1) \cdot (19 u^2 + 23 u + 6)$ and so $E_t(u-1) = \frac{1}{6} \cdot u \cdot (19 u^2 - 15 u + 2)$.

We also have $Z_t(u) = \frac{1}{3} \cdot u \cdot (2 u - 1) \cdot (5u - 2)$.

Consider now $t'$ with a top vertex of size $1$ and a bottom vertex of size $2$.

Then $E_{t'}(u)=\frac{1}{3} \cdot (u + 1) \cdot (2 u + 1) \cdot (5 u + 3)$ and so $E_{t'}(u-1)=\frac{1}{3} \cdot u \cdot (2 u - 1) \cdot (5 u - 2)$.

We also have $Z_{t'}(u) = \frac{1}{6} \cdot u \cdot (19 u^2 - 15 u + 2)$.

💎 Minkowski description¶

There is a natural alternative description of the polytope $Q_t$ as a Minkowski sum of simplices.

In $\mathbb{R}^I$, for every subset $U$ of $I$, let $\Delta_U$ be the simplex with vertices $0$ and the basis vectors indexed by $U$.

Then

Proposition : The polytope $Q_t$ is the Minkowski sum of $\Delta_U$ over all principal upper ideals of the preorder $t$.

For example, for the poset $a \leq b$ on the set $\{a, b\}$, This is the sum $\Delta_{b} + \Delta_{a,b}$.

This places our polytopes in the general framework of generalized permutohedra as introduced by Postnikov in 2009.

Associated reflexive polytope¶

As said before, the polytope $P_t$ has no interior lattice point. One can "fix" this by adding one more factor in the Minkowski sum.

Let $R_t$ be the sum of $P_t$ and the simplex $\Delta_I$.

Proposition : The polytope $R_t$ (once translated) is a reflexive polytope. Its polar polytope is a terminal reflexive polytope.

Recall that a reflexive polytope is a lattice polytope with $0$ in its interior, whose polar polytope is also a lattice polytope.

Being terminal means that the only lattice points are $0$ and the vertices.

This opens an interesting connexion with Calabi-Yau manifolds, Fano varieties and mirror symmetry, through Laurent polynomials.

Summary¶

On one side, a rich landscape of rather well-known and interesting things (Coxeter-Catalan combinatorics and more) :

  • noncrossing partitions, clusters and cambrian lattices, semi-distributive lattices, simple polytopes and exchange graphs, fans.

After transmutation, something like a "new world" :

  • preorders, very-cubical posets, lattice polytopes with no interior lattice points, Ehrhart-Zêta duality for opposite preorders.

Several examples of correspondences between the classical landscape and the new one : type $\mathbb{A}$, type $\mathbb{B}$, halohedra, Hochschild lattices, bubble lattices, pellytopes, etc.

A large family of correspondences still to be explored and understood : some planar preorders and Stokes polytopes associated with some quadrangulations. This opens an intriguing connexion with gentle algebras and tau-tilting theory.

🦊 Ma perché ?¶

So there are two different worlds and unexplained coincidences between numbers and polynomials on each side.

How could we try to explain all this ?

Hope : define for every preorder a polytopal semidistributive lattice (alla Tamari)

One would want this lattice to have the correct cardinality, and that $M$-triangles of polytopes also match.

One could then ask moreover that the Zêta polynomial of the associated core-label-order should match.

🎁 Many omitted things¶

(with no explanations of terminology)

Transmutation is just transposition when acting on $H$-triangles.

The $M$-triangle of the preorder poset $P_t$ looks very much like the $F$-triangle of the cluster complex.

It seems that the $\Gamma$-triangle after transmutation is always positive : look for a flag simplicial sphere.

For Hochschild lattices, everything seems to work well : transmutation of $M$-triangles and equality of Zêta polynomials.

For halohedra, the polytope is known, but not the semi-distributive lattice.

Besides the $M$-triangle and the Zeta polynomial, there is also coincidence for leading coefficients of $q$-Zêta polynomials.