Combinatorics and Algebra of Geometric Subdivision Operations

NEW

Problem: For a finite abstract simplicial complex $\Delta$ of dimension $d-1$, let $sd^r(\Delta)$ be the $r$-fold barycentric subdivision and define

The reconstructed problem is: give an explicit computable integer $R(\Delta)$, depending on standard invariants of $\Delta$, such that for every integer $r\ge R(\Delta)$, $\mathfrak h^{sd^r(\Delta)}(t)$ has only real zeros. Constant polynomials are regarded as vacuously real-rooted.

Result: The full $f$-vector gives such a bound.

Let $F=(f_{-1},f_0,\dots,f_{d-1})^T$, with $f_{-1}=1$. For $d\le1$, take $R(\Delta)=0$, since the $h$-polynomial has degree at most $1$.

Assume $d\ge2$. Define the barycentric subdivision matrix $B_d$ by

where $\left\{\begin{matrix}j\\ i\end{matrix}\right\}$ is a Stirling number of the second kind. Thus

Let $L_d$ be the $h$-transform matrix

For $m=1,\dots,d$, let $u_m$ be the eigenvector of $B_d$ with eigenvalue $m!$, supported in coordinates $\le m$, normalized by $(u_m)_m=1$. Let $u_0=e_0$, and set

Write

Since $(u_d)_d=1$ and $u_m$ has zero $d$-coordinate for $m<d$, one has $c_d=f_{d-1}>0$. Hence

By Brenti–Welker, $P_d$ has degree $d-1$ and has $d-1$ simple real roots. Let these roots be

Choose

with the inner minimum omitted if $d=2$. Put $a_i=\alpha_i-\eta$, $b_i=\alpha_i+\eta$, and define

Finally set

where $\|Q\|_{\mathrm{coeff}}$ is the maximum absolute value of a coefficient of $Q$, and take

Equivalently, if $C_\Delta>\varepsilon_d$,

and otherwise $R(\Delta)=0$.

For $r\ge R(\Delta)$,

Therefore at each pair $a_i,b_i$, the normalized polynomial has the same signs as $P_d$. Since $P_d(a_i)$ and $P_d(b_i)$ have opposite signs, the intermediate value theorem gives one real zero in each interval $(a_i,b_i)$. Thus there are $d-1$ distinct real zeros. The polynomial has degree at most $d$, so any remaining factor has degree at most $1$, hence also has only real zeros. Multiplication by $f_{d-1}(d!)^r>0$ does not change zeros. Therefore $\mathfrak h^{sd^r(\Delta)}(t)$ is real-rooted for all $r\ge R(\Delta)$.

This bound depends only on the $f$-vector of $\Delta$ and on universal constants determined by $d$.

Citation: The subdivision matrix and the fact that the dominant eigenpolynomial $P_d$ has simple real roots are from F. Brenti and V. Welker, “$f$-vectors of barycentric subdivisions,” Math. Z. 259 (2008), 849–865. The explicit bound above is obtained by making their spectral convergence quantitative.