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

$$\mathfrak h^\Gamma(t)=\sum_{k=0}^d h_k(\Gamma)t^k,\qquad \sum_{k=0}^d h_k(\Gamma)t^k=\sum_{i=0}^d f_{i-1}(\Gamma)t^i(1-t)^{d-i}.$$

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

$$(B_d)_{ij}= \begin{cases} 1,&i=j=0,\\ i!\left\{\begin{matrix}j\\ i\end{matrix}\right\},&1\le i\le j\le d,\\ 0,&\text{otherwise}, \end{cases}$$

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

$$F(sd^r\Delta)=B_d^rF.$$

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

$$(L_d)_{ki}= \begin{cases} (-1)^{k-i}\binom{d-i}{k-i},&0\le i\le k\le d,\\ 0,&i>k. \end{cases}$$

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

$$P_m(t)=\sum_{k=0}^d (L_du_m)_k t^k.$$

Write

$$F=\sum_{m=0}^d c_mu_m.$$

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

$$\frac{\mathfrak h^{sd^r(\Delta)}(t)}{f_{d-1}(d!)^r} = P_d(t)+ \sum_{m=0}^{d-1}\frac{c_m}{f_{d-1}}\left(\frac{m!}{d!}\right)^rP_m(t).$$

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

$$\alpha_1<\cdots<\alpha_{d-1}.$$

Choose

$$\eta=\frac13\min\Bigl(1,\min_{i\ne j}|\alpha_i-\alpha_j|\Bigr),$$

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

$$\mu=\min_i\{|P_d(a_i)|,|P_d(b_i)|\}>0,$$ $$M=\max_i\sum_{k=0}^d \max(|a_i|,|b_i|)^k, \qquad \varepsilon_d=\frac{\mu}{2M}.$$

Finally set

$$C_\Delta=\sum_{m=0}^{d-1}\frac{|c_m|}{f_{d-1}}\|P_m\|_{\mathrm{coeff}},$$

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

$$R(\Delta)=\min\{r\in\mathbb N: C_\Delta d^{-r}\le\varepsilon_d\}.$$

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

$$R(\Delta)=\left\lceil \frac{\log(C_\Delta/\varepsilon_d)}{\log d}\right\rceil,$$

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

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

$$\left\| \frac{\mathfrak h^{sd^r(\Delta)}(t)}{f_{d-1}(d!)^r}-P_d(t) \right\|_{\mathrm{coeff}} \le C_\Delta d^{-r}\le\varepsilon_d.$$

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.