A Möbius function computing \(h\)-polynomials of nestohedra
Rafael S. González D'León
Department of Mathematics and Statistics · Loyola University Chicago
Joint work with Nicolas Avila Ramirez · Université du Québec à Montréal
Sergio A. Carrillo · Universidad Nacional de Colombia
Oct 11, 2026 · 2026 Fall Southeastern Sectional Meeting · Kennesaw State University, Kennesaw, GA
Outline
Building sets (De Concini–Procesi 1995)
Definition
A building set on a ground set \(V\) is a collection \(\B \subseteq \mathcal{P}(V)\) of nonempty subsets of \(V\) such that
  • (B1) if \(I, J \in \B\) and \(I \cap J \neq \emptyset\), then \(I \cup J \in \B\)
  • (B2) \(\B\) contains the singleton \(\{v\}\) for all \(v \in V\).
Example
\[ \B_0 = \bigl\{\{1\},\{2\},\{3\},\{4\},\{1,3\},\{2,3\},\{1,2,3\},\{1,2,4\},\{1,2,3,4\}\bigr\}, \]
Graphical building sets

For a graph \(G = (V,E)\), the family \(\B(G)\) of subsets \(I \subseteq V\) such that the induced subgraph of \(G\) on \(I\) is connected is a building set.

\[ \B(P_3) = \bigl\{\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,2,3\}\bigr\} \]
Every building set is "hypergraphical"

For a hypergraph \(H = (V,E)\), the family \(\B(H)\) of subsets \(I \subseteq V\) such that the induced subhypergraph of \(H\) on \(I\) is connected is a building set.

For every building set \(\B\), there exist many hypergraphs \(H\) such that \(\B = \B(H)\).

In fact \(H=\B\) works!

And there is a minimal choice: \(H=E(\B)\)

\(\B_0\)
Definition
For a building set \(\B\) we denote by \(E(\B)\subset \B\) the set of nonsingleton blocks \(S\in \B\), such that whenever \(S=I\cup J\) for some \(I,J\in \B\) with \(I\cap J\neq \emptyset\), we have \(I=S\) or \(J=S\). We call \(E(\B)\) the struts of \(\B\).

Došen–Petrić (2011) call \(E(\B)\) a bare hypergraph.

The \(\mathcal{B}\)-nestohedron
Definition (Postnikov 2005)
The \(\mathcal{B}\)-nestohedron is the convex polytope \(P_{\B}\) in \(\R^{V}\) defined by the Minkowski sum \[ P_{\B} := \sum_{I \in \B} \Delta_I, \] where \(\Delta_I \subseteq \R^{V}\) is the convex hull of the standard basis vectors \(\{\mathbf{e}_v : v \in I\}\) — known as a standard simplex.
\[ P_{\B_0} = \Delta_{1}+\Delta_{2}+\Delta_{3}+\Delta_{4}+\Delta_{13} +\Delta_{23}+\Delta_{123}+\Delta_{124}+\Delta_{1234}, \]
\(f\) and \(h\)-polynomials
To any polytope \(P\) one can associate two polynomials.
Definition
The \(f\)-polynomial is defined as \[ f_P(t) := \sum_{k \ge 0} f_k t^k, \] where \(f_i = f_i(P)\) is the number of \(i\)-dimensional faces of \(P\).
Definition
The \(h\)-polynomial is the translation \[ h_P(t) := f_P(t-1). \]
\[f_{P_{\B_0}}(t) = 12 + 18 t + 8 t^2 + t^3\]
\[f_{\B_0}(t) = 12 + 18 t + 8 t^2 + t^3\]
\[h_{\B_0}(t) = 12 + 18 (t-1) + 8 (t-1)^2 + (t-1)^3\]
\[h_{\B_0}(t) = 1 + 5 t + 5 t^2 + t^3\]
How can we compute these polynomials?
Computing \(h\)-polynomials recursively
Proposition (Postnikov 2005)
The \(h\)-polynomials associated to building sets are determined by the following recurrence relations:
  1. If \(\B\) is the unique building set on a singleton, \(h_{\B}(t) = 1\).
  2. If \(\B\) has connected components \(\B_1, \dots, \B_k\), then \[ h_{\B}(t) = h_{\B_1}(t) \cdots h_{\B_k}(t). \]
  3. If \(\B\) is connected, then \[ h_{\B}(t) = \sum_{I \subsetneq V} (t-1)^{|V|-|I|-1} h_{\B|_I}(t), \] where \(\B|_I := \{J \in \B \mid J \subseteq I\}\) is the restriction of \(\B\) to \(I\).
Computing \(h\)-polynomials recursively
Proposition (Zelevinsky 2006)
We have that \[ \left( n - \kappa(\B) - (t-1)\frac{d}{dt} \right) h_{\B}(t) = \sum_{I \in \B \setminus \B_{\max}} h_{\B|_I}(t)\, h_{{}_I \backslash \B}(t), \] where \(\B_{\max}\) is the set of maximal blocks of \(\B\), and \({}_I\backslash\B = \{J \subseteq V \setminus I \mid J \in \B \text{ or } J \cup I \in \B\}\).
A combinatorial formula with \(\B\)-forests
Proposition (Postnikov–Reiner–Williams 2007)
If \(\B\) is a building set on \(V\), then \[ h_{\B}(t) = \sum_{F \text{ a } \B\text{-forest}} t^{\des(F)}. \]
We work in the generality of (multi)hypergraphs
(Multi)hypergraphs
Definition
A (multi)hypergraph \(H\) on \(V =: V(H)\) is a collection of pairs \(\mathsf{I} = (I, i) \in H\), called hyperedges, where \(\emptyset \neq I = V(\mathsf{I}) \subseteq V\) and \(i\) is any label that makes the pair unique in \(H\).

Building sets \(\B\), bare hypergraphs, and simple hypergraphs are all (multi)hypergraphs!

Subhypergraphs and contraction
Definition
We say that a hypergraph \(H'\) is a spanning subhypergraph of a hypergraph \(H\) if \(V(H') = V(H) = V\) and \(H' \subseteq H\). This relation defines an order \(H' \leq H\) on the set of hypergraphs on \(V\).
Definition
Given \(H' \leq H\) we define the contraction \(H/_{H'}\) as the hypergraph on vertex set \(V(H/_{H'}) = H'_{\max}\) and hyperedges given by \[ H/_{H'} = \Big\{ \big( \{I \in H'_{\max} \mid I \cap V(\mathsf{J}) \neq \emptyset\},\, \mathsf{J} \big) \ \Big|\ \mathsf{J} \in H \setminus H' \Big\}. \] In particular, \(|H/_{H'}| = |H| - |H'|\).
What are sub-building sets?
Sub-building sets
Definition
We say that a building set \(\A\) is a spanning sub-building set of \(\B\) if \(E(\A)\) is a spanning subhypergraph of \(E(\B)\), i.e. if \(V(\A) = V(\B)\) and \(E(\A) \subseteq E(\B)\).
Remark
A less strict, and perhaps more natural, notion of a spanning sub-building set can be defined whenever \(\A\subseteq \B\).
\(\mathbb{B}_{E(\B_0)}\)
The poset of weighted hypergraphs \(\WH(V)\)
Weighted hypergraphs
Definition
A weighted hypergraph on \(V\) is a pair \(\pmb{H} = (H, w_{\pmb{H}})\) where \(H\) is a hypergraph on \(V\) and \(w_{\pmb{H}} : H_{\max} \to \N\) is a weight function that assigns a value \(0 \le w_{\pmb{H}}(I) < |I|\), for every \(I \in H_{\max}\).
The poset of weighted hypergraphs \(\WH(V)\)
Definition
The poset of weighted hypergraphs \(\WH(V)\) is defined by relations \(\pmb{H'} \le \pmb{H}\) whenever \(H' \le H\) and, for every \(J \in H_{\max}\) of the form \(J = I_1 \cup \cdots \cup I_k\) where \(I_1, \dots, I_k \in H'_{\max}\), we have \[ w_{\pmb{H}}(J) = \nu + \sum_{j=1}^{k} w_{\pmb{H'}}(I_j), \qquad 0 \le \nu < k. \]
The order ideal \(\WH(H)\) in \(\WH(V)\)
The poset of weighted hypergraphs \(\WH(V)\)
Lemma
Given \(\pmb{H'} \in \WH(H)\), we have the isomorphisms of posets \[ \begin{aligned} U_H(\pmb{H'}) &\cong \WH(H/_{H'}), \\ \left[\pmb{\hat 0}, \pmb{H'}\right] &\cong \prod_{I \in H'_{\max}} \left[\pmb{\hat 0},\, H'|_{I}^{\,w_{\pmb{H'}}(I)}\right], \end{aligned} \] where \(U_H(\pmb{H'})\) is the principal filter — or principal upper order ideal — defined by \(\pmb{H'}\) in \(\WH(H)\), and \([\pmb{\hat 0}, \pmb{H'}]\) indicates the closed interval between \(\pmb{\hat 0}\) and \(\pmb{H'}\) in \(\WH(H)\).
The Möbius function
Definition
The Möbius function of a poset \(P\), denoted \(\mu_P(x,y)\) (or \(\mu(x,y)\) when the poset is understood), is defined recursively on the set \(\mathrm{Int}(P)\) of closed intervals \([x,y]\) in \(P\) by \(\mu(x,x) = 1\) and, for all \(x < y\), either one of the following two equivalent recursions: \[ \begin{aligned} \mu(x,y) &= -\sum_{x \le z < y} \mu(x,z), \quad \text{or} \\ \mu(x,y) &= -\sum_{x < z \le y} \mu(z,y). \end{aligned} \]
The Möbius function of the poset of weighted hypergraphs \(\WH(V)\)
Our results
Computing \(h\)-polynomials with Möbius functions
Theorem (Avila Ramirez–Carrillo–González D'León 2026)
Let \(H\) be a hypergraph on \(V\). Then \[ h_H(t) = (-1)^{|H|} \sum_{\pmb{H} \in \WH(V)} \mu(\pmb{\hat 0}, \pmb{H})\, t^{w_{\pmb{H}}}, \] where the sum is taken over all weighted hypergraphs \(\pmb{H} = (H, w_{\pmb{H}})\) supported on \(H\) and \(t^{w_{\pmb{H}}} := \prod_{I \in H_{\max}} t^{w_{\pmb{H}}(I)}\), with \(H_{\max}\) the set of maximal subsets of \(V\) connected by \(H\).
In particular, \[ h_{\B}(t) = (-1)^{|E(\B)|} \sum_{\pmb{E(\B)} \in \WH(V)} \mu(\pmb{\hat 0}, \pmb{E(\B)})\, t^{w_{\pmb{E(\B)}}}. \]
New recursions for the \(h\)-polynomials
Theorem (Avila Ramirez–Carrillo–González D'León 2026)
The \(h\)-polynomials associated to hypergraphs are determined by the following recurrence relations:
  1. If \(H = \emptyset\), \(h_H(t) = 1\).
  2. If \(H\) has connected components \(H_1, \dots, H_k\), then \(h_H(t) = h_{H_1}(t) \cdots h_{H_k}(t)\).
  3. If \(H\) is a connected hypergraph with \(|V(H)| > 1\), then \(h_H(t)\) satisfies the two recurrences: \[ h_H(t) = \sum_{H' < H} (-1)^{|H| - |H'| - 1} [\kappa(H')]_t \, h_{H'}(t) \] and \[ h_H(t) = \sum_{\emptyset \neq H' \le H} (-1)^{|H'| - 1} h_{H/_{H'}}(t) \prod_{I \in H'_{\max}} [\,|I|\,]_t, \] where \([n]_t := 1 + t + \cdots + t^{n-1}\).
Theorem (Avila Ramirez–Carrillo–González D'León 2026)
The \(h\)-polynomials associated to building sets are determined by the following recurrence relations:
  1. If \(\B\) consists of a singleton, \(h_{\B}(t) = 1\).
  2. If \(\B\) has connected components \(\B_1, \dots, \B_k\), then \(h_{\B}(t) = h_{\B_1}(t) \cdots h_{\B_k}(t)\).
  3. If \(\B\) is a connected building set with \(|V(\B)| > 1\), then \(h_{\B}(t)\) satisfies the two recurrences: \[ h_{\B}(t) = \sum_{\A < \B} (-1)^{|E(\B)| - |E(\A)| - 1} [\kappa(\A)]_t \, h_{\A}(t) \] and \[ h_{\B}(t) = \sum_{\substack{\A \le \B \\ E(\A) \neq \emptyset}} (-1)^{|E(\A)| - 1} h_{\B/_{\A}}(t) \prod_{I \in \A_{\max}} [\,|I|\,]_t, \] where \(\B/_{\A}\) is the contraction of the building set \(\B\) by \(\A\) and \([n]_t := 1 + t + \cdots + t^{n-1}\).
Proof idea
A Möbius polynomial

To establish the formula \( h_H(t) = (-1)^{|H|} \sum_{\pmb{H}} \mu(\pmb{\hat 0}, \pmb{H})\, t^{w_{\pmb{H}}} \) for a given hypergraph \(H\) on \(V\), we introduce the auxiliary polynomial

\[ M_H(t) := \sum_{\pmb{H} \in \WH(V)} \mu(\pmb{\hat 0}, \pmb{H})\, t^{w_{\pmb{H}}}, \] where the sum is taken over all weighted hypergraphs \(\pmb{H} = (H, w_{\pmb{H}})\) supported on \(H\) and \(t^{w_{\pmb{H}}} := \prod_{I \in H_{\max}} t^{w_{\pmb{H}}(I)}\).

Our main theorem states that

\[ h_{\B(H)}(t) = (-1)^{|H|} M_H(t) \]

for any hypergraph \(H\), and in particular for \(H = E(\B)\).

Recursions for the \(M\)-polynomials

Exploiting the recursive nature of the Möbius function we obtain the following proposition.

Proposition
Let \(H\) be a hypergraph on \(V\).
  1. If \(H = \emptyset\), then \(M_H(t) = 1\).
  2. If \(H\) has connected components \(H_1, \dots, H_k\), then \(M_H(t) = M_{H_1}(t) \cdots M_{H_k}(t)\).
  3. If \(H\) is connected and \(|V(H)| > 1\), then \[ \begin{aligned} \sum_{H' \le H} [\kappa(H')]_t \, M_{H'}(t) &= 0, \\ \sum_{H' \le H} M_{H/_{H'}}(t) \prod_{I \in H'_{\max}} [\,|I|\,]_t &= 0. \end{aligned} \]
A similar recursion for the \(h\)-polynomials
Proposition
Let \(H\) be a connected hypergraph such that \(|V(H)| > 1\). Then \[ \sum_{H' \le H} [\kappa(H')]_t \, (-1)^{|H'|} h_{H'}(t) = 0. \]

We use the following facts:

  • \( h_{H'}(t) = \sum_{F \text{ an } H'\text{-forest}} t^{\des(F)} \) (Postnikov–Reiner–Williams)
  • \( [\kappa(H')]_t = 1 + t + \cdots + t^{\kappa(H')-1} \) is modeled by choosing one of the roots of an \(H'\)-forest \(F\) after being ordered \(r_0 < r_1 < \cdots < r_{\kappa(H')-1}\). We then set \(\sigma_F(r_i) := i\).





Roots of \(F'\): \(1 < 6 < 7\), so \(\sigma_{F'} = 0, 1, 2\) and \(t^{\sigma_{F'}(1)} + t^{\sigma_{F'}(6)} + t^{\sigma_{F'}(7)} = 1 + t + t^2 = [\kappa(H')]_t\).

Taking these observations into account, we define the set

\[ \Omega_H := \left\{ (H', F, r) \mid H' \le H,\ F \text{ an } H'\text{-forest, and } r \text{ a root of } F \right\}. \]

and the weight function \(\omega\) on it:

\[ \omega : \Omega_H \to \mathbb{Z}[t], \qquad \omega(H', F, r) = (-1)^{|H'|}\, t^{\des(F) + \sigma_F(r)}. \]

The equation in the above proposition can be rewritten as

\[ \sum_{(H', F, r) \in \Omega_H} \omega(H', F, r) = 0. \]
A sign-reversing involution
A sign-reversing involution

To every \(r \in V\) we assign a unique hyperedge \(\mathsf{I}_r\) of \(H\) (\(H\) is connected). The sign-reversing involution adds \(\mathsf{I}_r\) to, or removes it from, \(H'\), changing the forest and the sign but preserving the power of \(t\).

\(\overset{+\,\mathsf{I}_1}{\underset{-\,\mathsf{I}_1}{\rightleftarrows}}\)
\( \omega(H', F', 1) = (-1)^{|H'|}\, t^{2 + 0} \)
\( \omega(H'', F'', 1) = (-1)^{|H'| + 1}\, t^{2 + 0} \)
A very direct example
The simplex
Example
Consider the building set \[ \B_n := \{\{i\} \mid i \in [n]\} \cup \{[n]\}, \] with ground set \([n]\) and only strut \([n]\), so \(P_{\B_n}\) is an \((n-1)\)-simplex.

If \(\A < \B_n\), then \(E(\A) = \emptyset\) and \(\kappa(\A) = n\).

The first recurrence gives directly

\[ h_{\B_n}(t) = (-1)^{1-0-1}\, [n]_t \cdot 1 = [n]_t = 1 + t + \cdots + t^{n-1}, \]

a short proof of this well-known result (Postnikov–Reiner–Williams 2007, Example 6.11).

¡Gracias!
arXiv: 2609.15784