# Elementary Proof of a Theorem of Hawkes, Isaacs and Özaydin

Matthé van der Lee

###### Abstract

We present an elementary proof of the theorem of Hawkes, Isaacs and Özaydin,
which states that $\Sigma\,\mu_{G}(H,K)\equiv 0$ mod $d$, where $\mu_{G}$
denotes the Möbius function for the subgroup lattice of a finite group $G$,
$H$ ranges over the conjugates of a given subgroup $F$ of $G$ with $[G:F]$
divisible by $d$, and $K$ over the supergroups of the $H$ for which $[K:H]$
divides $d$. We apply the theorem to obtain a result on the number of
solutions of $|\langle H,g\rangle|\mid n$, for said $H$ and a natural number
$n$. The present version of the article includes an additional result on a
quantity studied by K.S. Brown.

Keywords: Möbius function, arithmetic functions, subgroup lattice

2010 MSC: 05E15, 11A25, 20D30

##  1 Introduction

The purpose of this note is to present a simple proof for the theorem of
Hawkes, Isaacs and Özaydin, an important tool in the area of counting problems
in finite groups.

We refer to [3], where the result has appeared as Theorem 5.1, for background
information regarding the subject.

The exposition uses minimal group theory. The ingredients for the proof are
Burnside’s Lemma, the incidence algebra of a finite partially ordered set (of
which we use only the basic properties), and a feature of arithmetic
functions: Corollary 3.4.

Next, we derive a result on the number of solutions $g$ of $|\langle
H,g\rangle|\mid n$, for a finite group $G$, a subgroup $H\leq G$, and
$n\mid|G|$ (Theorem 6.1), and some results on a quantity studied by K.S. Brown
(Propositions 6.2 and 6.3).

##  2 A group action

For positive integers $m$ and $d$, we define the number
$\boldsymbol{b_{m}(d)}$ as the binomial coefficient

$b_{m}(d)={dm\scalebox{0.6}[0.75]{$-$}1\choose d\scalebox{0.6}[0.75]{$-$}1}.$

This function will play a pivotal role.

Let $t,m$ be positive integers, and $G$ a finite group of order $t\cdot m$.
$G$ acts on the set $X=\\{T\subseteq G\mid|T|=t\\}$ of its subsets of
cardinality $t$ in the natural way

$g\cdot T:=gT=\\{gx\mid x\in T\\}.$

This is in fact the group action used in Wielandt’s proof of Sylow’s theorem,
see [4], §1.7.

If $g\in G$ fixes an element $T\in X$, then $HT=T$ where $H=\langle g\rangle$
is the subgroup generated by $g$. So $T$ must be a union of right cosets of
$H$ in $G$. As $|H|$ equals the order $\boldsymbol{o(g)}$ of $g$ in $G$, this
means $o(g)$ divides $|T|=t$. Writing $t=o(g)\cdot d$, we find that $T$ is the
union of $d$ of the $d\cdot m$ right cosets of $H$. Conversely, any such union
is an element of $X$ and is fixed by $g$. It follows that the number of fixed
points in $X$ of an element $g\in G$ of order $t/d$ equals

${dm\choose d}={dm\scalebox{0.6}[0.75]{$-$}1\choose
d\scalebox{0.6}[0.75]{$-$}1}\cdot m=b_{m}(d)\cdot m.$

And, clearly, if $o(g)$ does not divide $t$, $g$ cannot have any fixed points
in $X$.

By Burnside’s Lemma, the number of orbits of $G$ in $X$ is equal to the
average number of fixed points of the elements of $G$. Denoting the number of
elements of order $n$ in $G$ by $\boldsymbol{\chi(n)}=\chi_{G}(n)$, the number
of orbits is therefore equal to

$(\Sigma_{d\mid t}\,b_{m}(d)\cdot m\cdot\chi(t/d))\,/\,(t\cdot m).$

Because this must be an integer, we have the following result.

######  Proposition 2.1.

If $m$ and $t$ are positive integers and $G$ is a group of order $tm$, one has

$\displaystyle\Sigma_{d\mid t}\,b_{m}(d)\,\chi_{G}(t/d)\equiv\,0\text{ mod }t$

##  3 Arithmetic functions modulo $n$

Let $n$ be a fixed positive integer, and consider the set
$\boldsymbol{Ar_{n}}=\\{f\mid f:\mathbb{N}\to\mathbb{Z}/n\\}$ of functions
from $\mathbb{N}$ to $\mathbb{Z}/n$. We can think of the standard arithmetic
functions such as the Euler $\varphi$ and Möbius $\mu$ functions as elements
of this set, taking their values modulo $n$.

The set $Ar_{n}$ is a commutative ring under the operations of point-wise
addition and convolution product multiplication

$\displaystyle f+h:a$ $\displaystyle\mapsto f(a)+h(a)$ $\displaystyle
f\,*\,h:a$ $\displaystyle\mapsto\Sigma_{d\mid a}\,f(d)\,h(a/d)$

Unity is the function $\boldsymbol{\varepsilon}$, given by $\varepsilon(1)=1$
and $\varepsilon(a)=0$ for $a>1$. The group of units of $Ar_{n}$ is:

$\displaystyle Ar_{n}^{*}=\\{f\in Ar_{n}\mid f(1)\in(\mathbb{Z}/n)^{*}\\}.$

Indeed, if $f*h=\varepsilon$, then $f(1)\,h(1)\equiv 1$ mod $n$ and
$\forall_{a\in\mathbb{N},\,a>1}\,\Sigma_{d\mid a}\,f(d)\,h(a/d)\equiv 0$ mod
$n$. So $h(1)$ must be the inverse of $f(1)$ in $(\mathbb{Z}/n)^{*}$, and the
value of $h(a)$ for $a>1$ can recursively be determined in $\mathbb{Z}/n$ from
the second congruence, in which it has coefficient $f(1)$.

By the well-known formula $\Sigma_{d\mid
a}\,\mu(d)=\delta_{1,a}=\varepsilon(a)$, the inverse
$\mu^{\scalebox{0.6}[0.75]{$-$}1}$ of the ordinary Möbius $\mu$ function in
the ring $Ar_{n}$ is the function $\boldsymbol{E}$ given by $E(a)=1$ for all
$a\in\mathbb{N}$. Thus,

$\mu=E^{\scalebox{0.6}[0.75]{$-$}1}$ (1)

We now discuss the set $\boldsymbol{R_{n}}=\\{f\in Ar_{n}\mid\forall_{t\mid
n}\,f(t)\equiv 0$ mod $t\\}$ of the arithmetic functions mod $n$ that are, to
give them a name, special.

######  Proposition 3.1.

$R_{n}$ is a unitary subring of $Ar_{n}$, and one has $R_{n}^{*}=R_{n}\cap
Ar_{n}^{*}$. That is, if $f\in R_{n}$ is a unit in $Ar_{n}$, it is a unit in
$R_{n}$.

###### Proof.

$R_{n}$ is closed under addition, and $\varepsilon\in R_{n}$. If $f$ and $h$
are special mod $n$ and $t$ is a divisor of $n$, each term in the sum
$(f*h)(t)=\Sigma_{d\mid t}\,f(d)\,h(t/d)$ is divisible by $d\cdot(t/d)=t$, and
$f*h$ is again special.

Finally, if $f\in R_{n}\cap Ar_{n}^{*}$, let $t\mid n$ with $t>1$. Then $f(1)$
is relatively prime to $n$, hence to $t$. Furthermore,
$f(1)\,f^{\scalebox{0.6}[0.75]{$-$}1}(t)\equiv\scalebox{0.6}[0.75]{$-$}\Sigma_{1<d\mid
t}\,f(d)\,f^{\scalebox{0.6}[0.75]{$-$}1}(t/d)$ mod $n$, so certainly modulo
$t$. By induction, all terms on the right-hand side can be assumed to be
multiples of $d\cdot(t/d)=t$. Hence $f(1)\,f^{\scalebox{0.6}[0.75]{$-$}1}(t)$
is a multiple of $t$, and therefore so is $f^{\scalebox{0.6}[0.75]{$-$}1}(t).$
∎

######  Corollary 3.2.

Let $f,h\in Ar_{n}$, and assume $f*E\in R_{n}$. Then

  1. _(a)_

$h*\mu\in R_{n}\Rightarrow h*f\in R_{n}$

If, moreover, $f\in Ar_{n}^{*}$, the following equivalences hold

  1. 2.

$h*\mu\in R_{n}\Leftrightarrow h*f\in R_{n}$

  2. 3.

$h*E\in R_{n}\Leftrightarrow h*f^{\scalebox{0.6}[0.75]{$-$}1}\in R_{n}$

###### Proof.

If $h*\mu\in R_{n}$, then since $f*E$ is also in $R_{n}$, so is their product
$h*\mu*f*E$. By equation (1), that is just $h*f$, giving (a).

Now if $f$ is a unit, so is $f*E$. As this function is in $R_{n}$, by
Proposition 3.1 its inverse $f^{\scalebox{0.6}[0.75]{$-$}1}*\mu$ is also in
$R_{n}$. So if $h*f\in R_{n}$, the product
$h*f*f^{\scalebox{0.6}[0.75]{$-$}1}*\mu=h*\mu$ is in $R_{n}$ too, establishing
(b).

For (c), note that $h*E\in R_{n}\Leftrightarrow
h*(f^{\scalebox{0.6}[0.75]{$-$}1}*f)*E\in R_{n}\Leftrightarrow
h*f^{\scalebox{0.6}[0.75]{$-$}1}\in R_{n}$, the latter equivalence because of
$f*E\in R_{n}^{*}$. ∎

Note that the Corollary applies in particular to $f=\varphi$. Indeed, as
$\Sigma_{d\mid a}\,\varphi(d)=a$, one has $\varphi*E=I\in R_{n}$, where
$\boldsymbol{I}$ denotes the identity function, $I(a)=a$ (taken modulo $n$).
And $\varphi\in Ar_{n}^{*}$ since $\varphi(1)=1$.

Viewing the binomial coefficient function
$b_{m}:d\mapsto{dm\scalebox{0.6}[0.75]{$-$}1\choose
d\scalebox{0.6}[0.75]{$-$}1}$ introduced in Section 2 as an element of
$Ar_{n}$, we now have

######  Proposition 3.3.

For $m\in\mathbb{N}$ and $h\in Ar_{n}$, the following are equivalent

  1. _(a)_

$h*E\in R_{n}$

  2. _(b)_

$h*b_{m}\in R_{n}$

###### Proof.

Let $t$ be a divisor of $n$. We apply Proposition 2.1 to the cyclic group
$G=\mathbb{Z}/tm$. It has $\chi_{G}(d)=\varphi(d)$ for every divisor $d$ of
$tm$, and hence we obtain $\Sigma_{d\mid t}\,b_{m}(d)\,\varphi(t/d)\equiv
0\,(t)$. Writing $b$ for $b_{m}$, it follows that $b*\varphi\in R_{n}$. By (b)
of Corollary 3.2, applied to $f=\varphi$ and $h=b$, we find $b*\mu\in R_{n}$.

As $b(1)=1$, the function $b$ is a unit in $Ar_{n}$. Taking inverses, we get
$b^{\scalebox{0.6}[0.75]{$-$}1}*E\in R_{n}$. Part (c) of the Corollary, for
$f:=b^{\scalebox{0.6}[0.75]{$-$}1}$, then gives the desired equivalence
$h*E\in R_{n}\Leftrightarrow h*b\in R_{n}$ for $h\in Ar_{n}$. ∎

A slightly stronger statement is:

######  Corollary 3.4.

For $h\in Ar_{n}$, the following are equivalent

  1. _(i)_

$\forall_{t\mid n}\,\Sigma_{d\mid t}\,h(d)\equiv\,0\>(t)$

  2. _(ii)_

$\forall_{t\mid n}\,\exists_{m\in\mathbb{N}}\,\Sigma_{d\mid
t}\,h(d)\,b_{m}(t/d)\equiv\,0\>(t)$

###### Proof.

(i) just paraphrases (a) of the Proposition, and (ii) is a trivial consequence
of (b). To see that (ii) implies (i), take a divisor $t$ of $n$, and suppose
one already knows that $\forall_{k\mid t,\,k<t}\,\Sigma_{d\mid k}\,h(d)\equiv
0\,(k)$. By the Proposition, $h*b_{m}\in R_{k}$ for all $m\in\mathbb{N}$ and
all $k\mid t$ with $k<t$. Using (ii), pick an $m$ such that $\Sigma_{d\mid
t}\,h(d)\,b_{m}(t/d)\equiv 0\,(t)$. Then clearly $h*b_{m}\in R_{t}$ for this
particular $m$. Applying Proposition 3.3 again, one finds that $h*E\in R_{t}$,
and so (i) holds for $t$ as well. ∎

##  4 The incidence algebra of a finite poset

Let $\langle P,\leq\rangle$ be a finite poset (partially ordered set), and $A$
a commutative ring. The incidence algebra of $P$ over $A$ is the set of
functions in two variables on $P$ with values in $A$, which can only assume
non-zero values when the arguments are comparable:

$\displaystyle\boldsymbol{W_{P,A}}=\\{f:P\times P\to
A\mid\forall_{x,\,y\,\in\,P}\,(x\nleq y\Rightarrow f(x,y)=0)\\}.$

The set $W_{P,A}$ is a, generally non-commutative unitary ring under point-
wise addition and convolution product multiplication

$\displaystyle(f+h)(x,y)\,$ $\displaystyle=\,f(x,y)+h(x,y)$
$\displaystyle(f*h)(x,y)\,$ $\displaystyle=\,\Sigma_{x\leq z\leq
y}\,f(x,z)\,h(z,y)$

Unity is Kronecker’s delta function, $\boldsymbol{\delta}(x,y)=1$ if $x=y$ and
$\delta(x,y)=0$ otherwise.

$W_{P,A}$ is an $A$-module, with $a\in A$ acting by $(a\cdot f)(x,y)=a\cdot
f(x,y)$. And $A\to W_{P,A},\,a\mapsto a\cdot\delta,$ is a ring homomorphism
making it an $A$-algebra. Its group of units is given by:

$\displaystyle W_{P,A}^{*}=\\{f\in W_{P,A}\mid\forall_{x\in P}\,f(x,x)\in
A^{*}\\}.$

For if $f(x,x)\in A^{*}$ for all $x\in P$, we may compute the values
$h(x,y)\in A$ of the right inverse $h$ of $f$ (the $h$ with $f*h=\delta$) for
a given $y\in P$ inductively for the $x\leq y$ by means of

$\displaystyle h(y,y)$ $\displaystyle=f(y,y)^{\scalebox{0.6}[0.75]{$-$}1}$
$\displaystyle h(x,y)$
$\displaystyle=\scalebox{0.6}[0.75]{$-$}f(x,x)^{\scalebox{0.6}[0.75]{$-$}1}\cdot\Sigma_{x<z\leq
y}\,f(x,z)\,h(z,y)$

(This works because $P$ is finite.) Similarly, the values of the left inverse
$g$ of $f$ are found, given $x$, using

$\displaystyle g(x,x)$ $\displaystyle=f(x,x)^{\scalebox{0.6}[0.75]{$-$}1}$
$\displaystyle g(x,y)$
$\displaystyle=\scalebox{0.6}[0.75]{$-$}f(y,y)^{\scalebox{0.6}[0.75]{$-$}1}\cdot\Sigma_{x\leq
z<y}\,g(x,z)\,f(z,y)$

By associativity, $g=g*\delta=g*f*h=\delta*h=h$ is the unique two-sided
inverse of $f$.

Key elements of $W_{P,A}$ are the following functions $\boldsymbol{\zeta}$,
$\boldsymbol{\eta}$ and $\boldsymbol{\mu}$:

$\displaystyle\zeta(x,y)=\begin{cases}\,1&\mbox{if }x\leq y\\\
\,0&\mbox{otherwise}\end{cases}$ $\displaystyle\mbox{the {zeta function} of
}P$ $\displaystyle\eta(x,y)=\begin{cases}\,1&\mbox{if }x<y\\\
\,0&\mbox{otherwise}\end{cases}$ $\displaystyle\mbox{the {chain function} of
}P$ $\displaystyle\mu=\zeta^{\scalebox{0.6}[0.75]{$-$}1}$
$\displaystyle\mbox{the {M\"{o}bius function} of }P$

The latter has the following properties, resulting from these definitions

$\left.\begin{aligned} &\mu(x,x)=1&&\quad\qquad\mbox{for all }x\in P\>\\\
&\mu(x,y)=\scalebox{0.6}[0.75]{$-$}\Sigma_{x<z\leq
y}\>\mu(z,y)=\scalebox{0.6}[0.75]{$-$}\Sigma_{x\leq
z<y}\>\mu(x,z)&&\quad\qquad\mbox{for }x<y\>\\\ &\Sigma_{x\leq z\leq
y}\>\mu(x,z)=0=\Sigma_{x\leq z\leq y}\>\mu(z,y)&&\quad\qquad\mbox{for }x\neq
y\>\end{aligned}\right\\}$ (2)

Many combinatorial aspects of the poset $\langle P,\leq\rangle$ are reflected
in the ring $W_{P,A}$. For instance, the number of elements of the interval
$[x,y]=\\{z\in P\mid x\leq z\leq y\\}$, and the number of chains of length
$k\geq 0$ from $x$ to $y$ are given by, respectively

$\displaystyle\zeta^{2}(x,y)$ $\displaystyle=|[x,y]|$
$\displaystyle\eta^{k}(x,y)$ $\displaystyle=|\\{(z_{0},\cdots,z_{k})\in
P^{k+1}\mid x=z_{0}<z_{1}<\cdots<z_{k}=y\\}|$

As $<$-chains of length $|P|$ cannot exist, we have $\eta^{|P|}=0$. And since
$\zeta=\delta+\eta$ and $\delta=1$, it follows that

$\mu=\zeta^{\scalebox{0.6}[0.75]{$-$}1}=(\delta+\eta)^{\scalebox{0.6}[0.75]{$-$}1}=\delta-\eta+\eta^{2}-\cdots\pm\eta^{|P|\scalebox{0.6}[0.75]{$-$}1}$

######  Remark 4.1.

By this formula, $\mu(x,y)$ is equal to (the image under $\mathbb{Z}\to A$ of)
the number of even-length chains from $x$ to $y$ in $P$ minus the number of
odd-length ones. (Here, $x=y$ is considered to form a $<$-chain of length
zero.) This result is due to P. Hall.

##  5 Proof of the Theorem

Let $G$ be a finite group of order $|G|=t\cdot m$, and let
$\boldsymbol{\mathcal{L}(G)}=\\{H\mid H\leq G\\}$ be its subgroup lattice. It
is partially ordered by the inclusion relation $\subseteq$, which we shall
denote as $\leq$. Using $A=\mathbb{Z}$ as base ring, we will write
$\boldsymbol{\mathcal{W}(G)}$ for the associated incidence algebra
$W_{\mathcal{L}(G),\mathbb{Z}}$.

We denote $\boldsymbol{\mu_{G}}$, the Möbius function of the poset
$\mathcal{L}(G)$, simply by $\mu$, and similarly write just $\zeta$ for the
zeta function.

We revisit the action of $G$ on $X=\\{T\subseteq G\mid|T|=t\\}$ discussed in
Section 2. For $K\leq G$, define:

$\displaystyle\Lambda(K)$ $\displaystyle=\\{T\in X\mid G_{T}=K\\}$
$\displaystyle\lambda(K)$ $\displaystyle=|\Lambda(K)|$

where $\boldsymbol{G_{T}}=\\{g\in G\mid g\cdot T=T\\}$ is the stabilizer of
$T\in X$. If $H=G_{T}$, then $T=HT$ is a union of right cosets of $H$ in $G$,
so $|H|$ divides $t$. Putting $d=t/|H|$, the size of the orbit $G\cdot T$
equals $[G:H]=dm$.

A point $gT$ in this orbit has stabilizer
$G_{gT}=gHg^{\scalebox{0.6}[0.75]{$-$}1}$, a conjugate of $H$. So if
$\mathcal{H}$ denotes the conjugacy class of $H$ in $G$, it follows that
$\bigcup_{L\in\mathcal{H}}\Lambda(L)$ is a union of orbits of $G$ in $X$, each
of length $dm$. As the $\Lambda(L)$ are disjoint, we obtain
$\Sigma_{L\in\mathcal{H}}\,\lambda(L)\equiv\,0\>(dm)$.

Hence if $d\mid t$ and $\mathcal{E}$ is any set of subgroups of order $t/d$ of
$G$ closed under conjugation, we have:

$\Sigma_{H\in\mathcal{E}}\>\lambda(H)\equiv\,0\>(dm)$ (3)

Now let $H\leq G$ fix $T\in X$. Then $H\leq G_{T}$, so $|H|$ again divides
$t$. With $d:=t/|H|$, $T$ must be a union of $d$ of the $d\cdot m$ right
cosets of $H$. As we saw earlier, the number of these unions equals
$b_{m}(d)\cdot m$, which is therefore the number of fixed points of $H$ in
$X$. It follows that for any $H\leq G$ with $|H|\mid t$

$b_{m}(t/|H|)\cdot m=\Sigma_{H\leq K\leq G,\,|K|\mid t}\,\lambda(K)$ (4)

Indeed, $T$ is a fixed point of $H$ iff $H\leq G_{T}$, and $|G_{T}|$ divides
$t$ for every $T\in X$.

Let $F$ be a subgroup of $G$, of order dividing $t$, and consider the
collection

$\mathcal{F}=\\{H\in\mathcal{L}(G)\mid H\,\text{contains a conjugate
of}\,F\\}.$

The remaining computations will take place in the incidence algebra
$\mathcal{W}_{\mathcal{F}}:=W_{\mathcal{F},\mathbb{Z}}$ of the poset
$\langle\mathcal{F},\leq\rangle$. As $\mathcal{F}$ is convex in
$\mathcal{L}(G)$, that is, for $H\leq L\leq K$ in $\mathcal{L}(G)$ with
$H,K\in\mathcal{F}$ one has $L\in\mathcal{F}$, it is clear that, for $H$ and
$K$ in $\mathcal{F}$, $\mu(H,K)$ has the same value whether taken in
$\mathcal{W}(G)$ or in $\mathcal{W}_{\mathcal{F}}$. (See also Remark 4.1.) The
same goes for the zeta function, and so we can use the notations $\mu$ and
$\zeta$ unambiguously.

In order to apply Möbius inversion to (4), we introduce two auxiliary
functions $\alpha$ and $\beta$ from the ring $\mathcal{W}_{\mathcal{F}}$

$\displaystyle\alpha(K,L)$ $\displaystyle=\begin{cases}\,\lambda(K)&\text{if
}|K|\text{ divides }t\text{ and }L=G\\\ \,0&\text{otherwise}\end{cases}$
$\displaystyle\beta(K,L)$ $\displaystyle=\begin{cases}\,b_{m}(t/|K|)&\text{if
}|K|\text{ divides }t\text{ and }L=G\\\ \,0&\text{otherwise}\end{cases}$

In terms of these, we have for $H,L\in\mathcal{F}$:

$m\cdot\beta(H,L)=\Sigma_{H\leq K\leq L}\,\alpha(K,L).$

For in case $L=G$ and $|H|\mid t$ this follows by (4), and the formula is
trivial otherwise.

Reformulating it as $m\cdot\beta(H,L)=\Sigma_{H\leq K\leq
L}\,\zeta(H,K)\,\alpha(K,L)$, the equation shows that
$m\cdot\beta=\zeta*\alpha$ in $\mathcal{W}_{\mathcal{F}}$. Inverting $\zeta$
now gives $\alpha=m\cdot(\mu*\beta)$. Hence, for any $H\in\mathcal{F}$ with
$|H|\mid t$:

$\lambda(H)=\alpha(H,G)=m\cdot\Sigma_{H\leq K\leq G}\>\mu(H,K)\>\beta(K,G).$

By the definition of $\beta$ and formula (3) applied to
$\mathcal{E}=\\{H\in\mathcal{F}\mid|H|=t/d\\}$, one obtains, dividing out $m$

$\displaystyle\forall_{d\mid
t}\,\Sigma_{H\in\mathcal{F},\,|H|=t/d}\,\Sigma_{H\leq K\leq G,\,|K|\mid
t}\>\mu(H,K)\>b_{m}(t/|K|)\equiv\,0\>(d).$

Collecting the $K$ that are of equal index over the corresponding $H$ and
eliminating $m=|G|/t$ produces

$\displaystyle\forall_{d\mid t}\,\Sigma_{k\mid
d}\,(\Sigma_{H\in\mathcal{F},\,|H|=t/d}\,\Sigma_{H\leq K\leq
G,\,[K:H]=k}\>\mu(H,K))\cdot b_{|G|/t}(d/k)\equiv\,0\>(d).$

This last formula is valid for any $t\mid|G|$ for which $f:=|F|\mid t$. So,
given any divisor $d$ of $[G:F]$, one can employ the formula with $t=f\cdot
d$. In this situation, the $H\in\mathcal{F}$ for which $|H|=t/d$ are just the
elements of the conjugacy class $\mathcal{C}$ of $F$, and we arrive at:

$\forall_{d\mid[G:F]}\,\Sigma_{k\mid
d}\,(\Sigma_{H\in\mathcal{C}}\,\Sigma_{H\leq K\leq
G,\,[K:H]=k}\>\mu(H,K))\cdot b_{|G|/(fd)}(d/k)\equiv\,0\>(d).$

We are now in a position to apply Corollary 3.4, yielding

$\forall_{d\mid[G:F]}\,\Sigma_{k\mid
d}\,\Sigma_{H\in\mathcal{C}}\,\Sigma_{H\leq K\leq
G,\,[K:H]=k}\>\mu(H,K)\equiv\,0\>(d).$

And this is precisely the content of the theorem of Hawkes, Isaacs and
Özaydin.

######  Theorem 5.1.

([3, Theorem 5.1]) If $G$ is a finite group, $F$ a subgroup, $\mathcal{C}$ the
conjugacy class of $F$ in $G$, and $d$ a divisor of $[G:F]$, the following
congruence applies

$\displaystyle\Sigma_{H\in\mathcal{C}}\,\Sigma_{H\leq K\leq G,\,[K:H]\mid
d}\>\mu_{G}(H,K)\equiv\,0\text{ mod }d$

Taking the sum over all conjugacy classes of subgroups of order $h\mid|G|$,
and letting $d\mid|G|/h$, one has, as a consequence

$\Sigma_{H\leq G,\,|H|=h}\,\Sigma_{H\leq K\leq G,\,[K:H]\mid
d}\>\mu(H,K)\equiv\,0\text{ mod }d$ (5)

Loosely speaking, the sum of the $\mu(H,K)$, taken over all $H$ ”at level $h$”
and all $K$ ”at level at most $h\cdot d$”, is a multiple of the ”height $d$ of
the resulting slice” of $G$.

##  6 Further observations

Write $\boldsymbol{\psi(n)}=\psi_{G}(n)=|\\{H\leq G\mid|H|=n\\}|$ for the
number of subgroups of order $n$ in $G$.

Taking $d=p$, a prime, $h\in\mathbb{N}$ with $hp\mid|G|$, $H\in\mathcal{L}(G)$
with $|H|=h$, and $H\leq K\leq G$ with $[K:H]\mid p$, we either have $K=H$ and
$\mu(H,K)=1$ by properties (2), or $|K|=hp$ and $K$ covers $H$ (in the sense
that no intermediate subgroups $H<L<K$ exist), so that
$\mu(H,K)=\scalebox{0.6}[0.75]{$-$}1$, again by (2). Hence, according to (5):

$\psi(h)-|\\{(H,K)\mid H\leq K\leq
G,\>|H|=h\>\text{and}\>[K:H]=p\\}|\,\equiv\,0\>(p),$

or, putting $t=hp$,

$\forall_{t\mid|G|}\,\forall_{p\mid
t,\,p\,prime}\>\psi_{G}(t/p)\,\equiv\,\Sigma_{K\leq
G,\,|K|=t}\>\psi_{K}(t/p)\;(p)$ (6)

Sylow’s theorem follows by an easy induction: if $1<t\mid|G|$ is a power of a
prime $p$, and one assumes that $\psi_{K}(t/p)\equiv 1\,(p)$ for all $K\leq
G$, the left-hand side of (6) and all terms on the right-hand side are
congruent to 1 mod $p$, so that $\psi_{G}(t)$, being the number of terms on
the right, must be $\equiv 1$ mod $p$ as well.$\hfill\square$

Note that Frobenius’ theorem, by which $\Sigma_{d\mid t}\,\chi_{G}(d)\equiv
0\>(t)$ for a finite group $G$ of order divisible by $t$, follows from
Proposition 2.1, with the aid of a little arithmetic. Indeed,
$\forall_{t\mid|G|}\,\Sigma_{d\mid t}\,\chi(d)\,b_{|G|/t}(t/d)\equiv 0\,(t)$
by Proposition 2.1, and Corollary 3.4 applies.$\hfill\square$

Next, we note that the proof of Proposition 3.3 goes through for any function
$b\in Ar_{n}$ (notation from that proof) which is a unit in $Ar_{n}$ and
satisfies $b*\varphi\in R_{n}$, i.e., for any $b$ in the coset
$\varphi^{\scalebox{0.6}[0.75]{$-$}1}*R_{n}^{*}$ of $R_{n}^{*}$ in
$Ar_{n}^{*}$. This coset equals
$\mu^{\scalebox{0.6}[0.75]{$-$}1}*R_{n}^{*}=E*R_{n}^{*}$, by (b) of Corollary
3.2 applied to $f=\varphi$. Thus, for any function $b$ in the coset and any
function $h\in Ar_{n}$, there is an equivalence similar to the one in
Proposition 3.3:

$\forall_{t\mid n}\,\Sigma_{d\mid
t}\,h(d)\equiv\,0\>(t)\quad\Leftrightarrow\quad\forall_{t\mid
n}\,\Sigma_{d\mid t}\,h(d)\,b(t/d)\equiv\,0\>(t).$

Such $b$ include the inverse of $\varphi$, given by
$\varphi^{\scalebox{0.6}[0.75]{$-$}1}(a)=\prod_{\,p\mid
a,\,p\,\text{prime}}\,(1\scalebox{0.6}[0.75]{$-$}p)$ for $a\in\mathbb{N}$, and
the function $\sigma(a)=\Sigma_{d\mid a}\,d$. For $\sigma=E*I$ and $I\in
R_{n}^{*}$. Generally, putting $I_{k}(a):=a^{k}$ and $\sigma_{k}:=E*I_{k}$, so
that $\sigma_{k}(a)$ is the sum of the $k$-th powers of the divisors of $a$,
the equivalence holds for $b=\sigma_{k}$. Also, for $u\in\mathbb{Z}/n$ it is
easily seen that $\Sigma_{d\mid n}\,u^{d}\cdot\varphi(n/d)\equiv\,0\>(n)$, so
that the function $b:a\mapsto u^{a}$ is in the coset when
$u\in(\mathbb{Z}/n)^{*}$.

We conclude by taking a look at the following elements
$\boldsymbol{i},\boldsymbol{\varphi}$ and $\boldsymbol{\gamma}$ of the
incidence algebra $\mathcal{W}(G)$:

$\displaystyle i(H,K)=\begin{cases}\,[K:H]&\mbox{for }H\leq K\\\
\,0&\mbox{otherwise}\end{cases}$ $\displaystyle\mbox{the {index function} for
}G$ $\displaystyle\varphi=i*\mu$ $\displaystyle\textit{Euler totient
function}\mbox{ for }G$ $\displaystyle\gamma(H,K)=|\\{g\in K\mid K=\langle
H,g\rangle\\}|$ $\displaystyle\mbox{number of }\textit{single
generators}\mbox{ of }K\mbox{ over }H$

Then $i=\varphi\,*\,\zeta$, so for subgroups $H\leq L\leq G$ we have
$[L:H]=\Sigma_{H\leq K\leq L}\,\varphi(H,K)$, and hence

$|L|=|H|\cdot\Sigma_{H\leq K\leq L}\,\varphi(H,K)$ (7)

It follows that for any $H,K\in\mathcal{L}(G)$:

$\gamma(H,K)=|H|\cdot\varphi(H,K)$ (8)

For both sides vanish when $H\nleq K$. We use induction on $[K:H]$ for the
case $H\leq K$. If $[K:H]=1$, both sides are equal to $|H|$. And assuming the
equation holds for all $K$ with $H\leq K<L$, by (7) we find:

$|L|\,=\,|H|\cdot\varphi(H,L)+\Sigma_{H\leq
K<L}\,\gamma(H,K)\,=\,|H|\cdot\varphi(H,L)+|\\{g\in L\mid\langle
H,g\rangle<L\\}|.$

But $|L|\,=\,|\\{g\in L\mid\langle H,g\rangle\leq L\\}|$, and therefore
$|H|\cdot\varphi(H,L)\,=\,|\\{g\in L\mid\langle
H,g\rangle=L\\}|\,=\,\gamma(H,L).$

The theorem of Frobenius mentioned above is the case $F=1$ of:

######  Theorem 6.1.

If $G$ is a finite group, $F\leq G$, $\mathcal{C}$ the conjugacy class of $F$
in $G$, and $n$ divides $|G|$, one has

$\Sigma_{H\in\mathcal{C}}\,\Sigma_{H\leq K\leq G,\,|K|\mid
n}\>\gamma(H,K)\equiv\,0\text{ mod }n.$

That is, $n$ divides $|\mathcal{{C}}|$ times the number of $g\in G$ for which
$|\langle F,g\rangle|\mid n$.

###### Proof.

Using (8) and the definition of $\varphi$,

$\displaystyle\Sigma_{H\in\mathcal{C}}\,\Sigma_{K\geq H,\,|K|\mid
n}\,\gamma(H,K)=$
$\displaystyle|F|\cdot\Sigma_{H\in\mathcal{C}}\,\Sigma_{K\geq H,\,|K|\mid
n}\,\varphi(H,K)=$
$\displaystyle|F|\cdot\Sigma_{H\in\mathcal{C}}\,\Sigma_{K\geq H,\,|K|\mid
n}\,\Sigma_{H\leq L\leq K}\,[L:H]\cdot\mu(L,K)=$
$\displaystyle\Sigma_{H\in\mathcal{C}}\,\Sigma_{L\geq H,\,|L|\mid
n}\,|L|\cdot(\Sigma_{K\geq L,\,|K|\mid n}\,\mu(L,K)).$

For a fixed value of $|L|$, the $L$ appearing in the final expression form a
family closed under conjugation, so by Theorem 5.1 the corresponding terms add
up to a multiple of $|L|\cdot(n/|L|)=n$. ∎

The number of $n$-tupels $(g_{1},\cdots,g_{n})\in G^{n}$ for which $G=\langle
g_{1},\cdots,g_{n}\rangle$ is traditionally denoted $\varphi_{G}(n)$ ([2]). In
our notation it is $\gamma^{n}(1,G)$. We use the symbol $\varphi$ for a
related but different notion. Writing $\boldsymbol{\varphi(K)}$ for
$\varphi(1,K)$, equation (7), applied to $H=1$ and $L=G$, gives
$|G|=\Sigma_{K\leq G}\,\varphi(K)$, generalizing the household formula
$\Sigma_{d\mid n}\,\varphi(d)=n$ (which is the special case $G=\mathbb{Z}/n$).
When $K$ is cyclic, one has $\varphi(K)=\varphi(|K|)$, the ordinary Euler
$\varphi$-function applied to the group order $|K|$, and $\varphi(K)=0$
otherwise.

The smallest number of generators of a group $L$ over a subgroup $H$ is the
least $n$ such that $\varphi^{n}(H,L)>0$, as follows by induction from (8),
using the fact that, again by (8), $\varphi^{n}(H,L)$ is always non-negative.

The inverse of the index function $i$ in $\mathcal{W}(G)$ is given by

$i^{\scalebox{0.6}[0.75]{$-$}1}(H,L)=i(H,L)\,\mu(H,L)$ (9)

For we have $\Sigma_{H\leq K\leq L}\,i(H,K)\cdot
i(K,L)\,\mu(K,L)=[L:H]\cdot\Sigma_{H\leq K\leq
L}\,\mu(K,L)=[L:H]\cdot\delta(H,L)$ by (2), and that simply equals
$\delta(H,L)$.

From (9) and the definition of $\varphi$ one obtains:

$\varphi^{\scalebox{0.6}[0.75]{$-$}1}(H,L)=(\zeta*i^{\scalebox{0.6}[0.75]{$-$}1})(H,L)=\Sigma_{H\leq
K\leq L}\,[L:K]\,\mu(K,L)$ (10)

It is an open problem, raised by Kenneth Brown ([1]), whether
$\varphi^{\scalebox{0.6}[0.75]{$-$}1}(1,G)$ can ever be zero for a finite
group $G$. Gaschütz ([2]) has shown that for solvable $G$ it cannot, and Brown
has derived some interesting divisibility properties of
$\varphi^{\scalebox{0.6}[0.75]{$-$}1}(1,G)$ for general $G$. Whether or not
$\varphi^{\scalebox{0.6}[0.75]{$-$}1}(H,G)$ can be zero for
$H\in\mathcal{L}(G)$ in general is also unknown.

Note that, for $G\neq 1$, one has $0=\delta(1,G)=\Sigma_{1\leq H\leq
G}\,\varphi(1,H)\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(H,G)=\Sigma_{H\leq
G,\,H\,\text{cyclic}}\,\varphi(|H|)\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(H,G)$
$=\Sigma_{g\in G}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(\langle g\rangle,G)$.
So, writing $\boldsymbol{\varphi_{\scalebox{0.6}[0.75]{$-$}1}}$ for the
function
$G\to\mathbb{Z},\,g\mapsto\varphi^{\scalebox{0.6}[0.75]{$-$}1}(\langle
g\rangle,G)$, it follows that:

$|G|>1\,\,\Rightarrow\,\,\Sigma_{g\in
G}\,\varphi_{\scalebox{0.6}[0.75]{$-$}1}(g)\,=\,0$ (11)

######  Proposition 6.2.

The class function $\varphi_{\scalebox{0.6}[0.75]{$-$}1}$ is an integral
linear combination of irreducible characters of G.

###### Proof.

Let $\mathcal{K}=\\{Hx\mid H\leq G,\,x\in G\\}$ be the coset poset of $G$,
ordered by inclusion. (Usually, $G$ itself is not considered to be an element
of the coset poset, but we include it here.) Every right coset
$Hx=x(x^{\scalebox{0.6}[0.75]{$-$}1}Hx)$ is equally a left coset, and hence
$\mathcal{K}$ becomes a $G$-set by putting $g\cdot(Hx):=gHx$ for $g\in G$. The
action of $G$ is compatible with the ordering of $\mathcal{K}$. The fixed
points of $g$ are the $Hx$ with $gHx=Hx$, that is, the right cosets of the
subgroups $H$ of $G$ that contain the element $g$. We claim that:

$\varphi_{\scalebox{0.6}[0.75]{$-$}1}(g)=\Sigma_{H\leq G,\,g\in
H}\,[G:H]\,\mu_{G}(H,G)=\Sigma_{\kappa\in\mathcal{K}^{g}}\,\mu_{g}(\kappa,G),$

where $\mathcal{K}^{g}$ denotes the set of fixed points of $g$ in
$\mathcal{K}$ and $\mu_{g}$ is the Möbius function of the poset
$\mathcal{K}^{g}$. For if $H\backslash G$ is the set of right cosets of $H$ in
$G$, one has $[G:H]\,\mu_{G}(H,G)=\Sigma_{\kappa\in H\backslash
G}\,\mu_{\mathcal{K}}(\kappa,G)$, as noted by S. Bouc (cf. [1, Section 3]),
and $g\in H$ iff all elements of $H\backslash G$ are in $\mathcal{K}^{g}$, and
$\mu_{\mathcal{K}}(\kappa,G)=\mu_{g}(\kappa,G)$ for all
$\kappa\in\mathcal{K}^{g}$ because $\mathcal{K}^{g}$ is a convex subset of
$\mathcal{K}$.
Lemma 2.8 of [3], applied to the dual poset
$\langle\mathcal{K},\supseteq\rangle$ of $\langle\mathcal{K},\subseteq\rangle$
(which has the ”same” Möbius function), now shows that the function
$\varphi_{\scalebox{0.6}[0.75]{$-$}1}$ is a difference of permutation
characters of $G$. ∎

By (11), the coefficient of the trivial character in the decomposition of
$\varphi_{\scalebox{0.6}[0.75]{$-$}1}$ into irreducible characters is zero for
non-trivial $G$.

######  Proposition 6.3.

For $F\leq K\leq G$, the following formula holds:

$\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,G)\,=\,\Sigma_{F\leq H\leq G,\,\langle
H,K\rangle=G}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(F,H)\,[G:H].$

###### Proof.

First, we note that for $F\leq K\leq G$ one has

$1=\zeta(F,K)=(\zeta*i^{\scalebox{0.6}[0.75]{$-$}1}*i)(F,K)=(\varphi^{\scalebox{0.6}[0.75]{$-$}1}*i)(F,K)=\Sigma_{F\leq
H\leq K}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(F,H)\,[K:H]$ (12)

We now prove the formula by induction on $[G:K]$. If $K=G$, its left-hand side
is $\varphi^{\scalebox{0.6}[0.75]{$-$}1}(G,G)=1$, and the right-hand side is
the sum $\Sigma_{F\leq H\leq
K}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(F,H)\,[K:H]$, which in view of (12)
also equals 1. Thus we may assume that $K<G$.
Using (12) plus the fact that for every sandwich $F\leq H\leq G$, the join
$\langle H,K\rangle$ of $H$ and $K$ in the lattice $\mathcal{L}(G)$ is either
$K$ itself or a subgroup $L>K$ of $G$, with either $L<G$ or $L=G$, we obtain

$\displaystyle\Sigma_{F\leq H\leq G,\,\langle
H,K\rangle=G}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(F,H)\,[G:H]=$
$\displaystyle 1-\Sigma_{F\leq H\leq
K}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(F,H)\,[G:H]-\Sigma_{K<L<G}\,\Sigma_{F\leq
H\leq L,\,\langle
H,K\rangle=L}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(F,H)\,[G:H]=$
$\displaystyle
1-[G:K]-\Sigma_{K<L<G}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,L)\,[G:L].$

As to the second equality, the second terms on the last two lines agree by
(12). By the induction hypothesis, the third terms agree as well, seeing as,
for $L\leq G$, the restrictions to $\mathcal{L}(L)\times\mathcal{L}(L)$ of the
index and Möbius functions on $\mathcal{L}(G)\times\mathcal{L}(G)$ are just
the corresponding elements of $\mathcal{W}(L)$, so that the same goes for
$\varphi=i*\mu$ and $\varphi^{\scalebox{0.6}[0.75]{$-$}1}$.
Now
$\Sigma_{K<L<G}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,L)\,[G:L]=(\varphi^{\scalebox{0.6}[0.75]{$-$}1}*i)(K,G)-\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,K)\,[G:K]-\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,G)\,[G:G]$,
which is equal to
$\zeta(K,G)-[G:K]-\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,G)=1-[G:K]-\varphi^{\scalebox{0.6}[0.75]{$-$}1}(K,G)$,
and this establishes the result. ∎

The proposition provides an elegant liaison between the subgroups of $G$ that
contain $K$ and the ones that together with $K$ generate $G$, when one applies
it with $F=1$:

$\Sigma_{K\leq H\leq
G}\,\zeta^{\scalebox{0.6}[0.75]{$-$}1}(H,G)\,[G:H]\,=\,\Sigma_{H\leq
G,\,\langle H,K\rangle=G}\,\varphi^{\scalebox{0.6}[0.75]{$-$}1}(1,H)\,[G:H].$

## References

  * [1] Brown, K. S., The Coset Poset and Probabilistic Zeta Function of a Finite Group, J. Algebra 225 (2) (2000), 989–1012.
  * [2] Gaschütz, W., Die Eulersche Funktion endlicher auflösbarer Gruppen, Illinois J. Math. 3 (1959), 469–476.
  * [3] Hawkes, T., I. M. Isaacs, and M. Özaydin, On the Möbius Function of a Finite Group, Rocky Mountain J. Math. 19 (4) (1989), 1003–1034.
  * [4] Huppert, B., Endliche Gruppen I, (Grundlehren; 134), Springer Verlag, Berlin-Heidelberg-New York, 1967.


Volume rigidity and algebraic shifting
Denys Bulavka
Department of Applied Mathematics, Faculty of Mathematics and Physics
Charles University
Czech Republic.
D.B. is supported by the project "Grant Schemes at CU" (reg. no. CZ.02.2.690.00.0190730016935), by the grant no. 21-32817S of the Czech Science Foundation (GAČR) and by Charles University project PRIMUS21SCI014.
Eran Nevo
Einstein Institute of Mathematics

Hebrew University
Jerusalem 91904
E.N. is partially supported by the Israel Science Foundation grant ISF-2480/20.
Yuval Peled
Einstein Institute of Mathematics

Hebrew University
Jerusalem 91904

We study the generic volume rigidity of $(d-1)$-dimensional simplicial complexes in $\R^{d-1}$, and show that the volume rigidity of a complex can be identified in terms of its exterior shifting. In addition, we establish the volume rigidity of triangulations of several $2$-dimensional surfaces and prove that, in all dimensions

$>1$, volume rigidity is not characterized by a corresponding hypergraph sparsity property.

§ INTRODUCTION

Let $K$ be an $n$-vertex $(d-1)$-dimensional simplicial complex and $\p:V(K)\to\R^{d-1}$ be a generic mapping of its vertices, in the sense that its $(d-1)n$ coordinates are algebraically independent over $\Q$. This paper deals with the infinitesimal version of the following problem: is there a non-trivial continuous motion of the vertices starting at $\p$ that preserves the volumes of all the $(d-1)$-simplices in $K$? By “non-trivial" we mean that, for some $(d-1)$-simplex on $V(K)$ that is not in $K$, its volume would change along the motion.
It is easy to show that the continuous and infinitesimal versions coincide for generic embeddings, as is the case for graph rigidity [2].

Volume Rigidity.
The signed volume of a $(d-1)$-face $\sigma=\{v_1,\dots ,v_d\} \in K$ with respect to $\p$ is given by the determinant of the $d\times d$ matrix

\begin{equation*}
M_{\p, \sigma} =
\begin{pmatrix}
\p(v_1) & \dots & \p(v_d)\\
1 & \dots &1
\end{pmatrix}.
\end{equation*}

Observe that , for every $1\le i\le d-1,~1\le j \le d$, the derivative of the signed volume $\det M_{\p,\sigma}$ with respect to the $i$-th coordinate of $\p(v_j)$ is given by the cofactor $C_{i,j} (M_{\p, \sigma})$ — that is, the determinant of the submatrix obtained by removing the $i$-th row and  $j$-th column multiplied by $(-1)^{i+j}$.

The volume-rigidity matrix $\fV(K,\p)$ of the pair $(K,\p)$ is a $(d-1)n\times f_{d-1}(K)$ matrix, where the columns are indexed by the $(d-1)$-faces of $K$, and every vertex is associated with a block of $(d-1)$ rows. The column vector $\bv_\sigma$ corresponding to a $(d-1)$-face $\sigma=\{v_1,\dots ,v_d\} \in K$ is defined by

\[
(\bv_\sigma)_{v_i,j} = C_{i,j}(M_{\p,\sigma})~,~i\in[d],~j\in [d-1],
\]

and $0$ elsewhere. Here $(\bv_\sigma)_{v_i,j}$ denotes the $j$-th coordinate of $\bv_\sigma$ in the block of $v_i$. In words, $\fV$ is the Jacobian of the function $\p\mapsto (\det M_{\p, \sigma})_{\sigma\in K}$, viewing $\p$ as a $(d-1)n$-dimensional vector.

This matrix was introduced in  <cit.> along with the description of a trivial $(d^2-d-1)$-subspace of the left kernel of $\fV(K,\p)$, arising from the volume-preserving transformations of $\R^{d-1}$. Concretely, the trivial subspace consists of all $(d-1)n$-dimensional vectors $z$ obtained by choosing a $(d-1)\times (d-1)$ matrix $A$ whose trace is zero and a vector $u\in\R^{d-1}$, and letting
z_v = A\cdot\p(v)+u
for every vertex $v$. The following definition suggests itself.

An $n$-vertex $(d-1)$-dimensional simplicial complex $K$ is called volume-rigid if
$$\mathrm{rank}(\fV(K,\p)) = (d-1)n - (d^2-d-1),$$
for a generic $\p:V(K)\to\R^{d-1}$.

Exterior shifting.
Algebraic shifting was introduced by Kalai (see e.g. [8] and the survey <cit.>) and has been studied extensively in algebraic combinatorics. Here we present a variant of exterior shifting. The standard basis $(e_i)_{i\in [n]}$ of $\R^n$ induces the basis  $(e_{\sigma})_{\sigma \subseteq [n]}$ of its exterior algebra $\bigwedge \R^n$.
Consider a generic  basis $(f_1,\dots ,f_n)$ of $\R^n$, where without loss of generality we assume that $f_1 = \unitvec \in \R^n$, namely, the other $n^2-n$ coordinates in this basis are algebraically independent over $\Q$. Consider the exterior face ring $\bigwedge K = \bigwedge \R^n~/~(e_{\sigma} \colon \sigma\notin K)$, and let $q$ denote the natural quotient map.  Given a partial order $<$ on the power set of $[n]$, define

\begin{equation}\label{eqn:Delta}
\Delta^<(K) = \{\sigma \colon q(f_\sigma) \notin \SPAN_{\R} \{q(f_\tau) \colon \tau< \sigma, |\tau|=|\sigma|\}\}.
\end{equation}

Of special importance in our case is the partial order $<_p$  defined by $\sigma=\{\sigma_1<...<\sigma_m\} \le_p \tau=\{\tau_1<...<\tau_{m'}\}$ if

$m=m'$ and $\sigma_i\le \tau_i,~\forall i\in[m]$. Corollary <ref> asserts that $\Delta^p(K):= \Delta^{<_p}(K)$ is a shifted simplicial complex independent of the generic choice of $f$. (Note that  $\Delta^p(K)$ may have more faces than  $K$.)

§.§ Main results.

Our main result is a characterization of volume rigidity in the setting of Kalai's exterior shifting.

Fix $d\ge 3$. An $n$-vertex $(d-1)$-dimensional simplicial complex $K$ is volume-rigid if and only if $\{1,3,4,...,d,n\} \in \Delta^p(K)$.

In the $2$-dimensional case we are able to derive the volume rigidity of triangulations of the following surfaces.

Every triangulation of the $2$-sphere, the torus, the projective plane or the Klein bottle is volume rigid.
In addition, every triangulation of the $2$-sphere and the torus minus a single triangle is also volume-rigid. In particular, every simplicial disc with a $3$-vertex boundary is minimally volume-rigid.

In the case of the $2$-sphere we give a complete mathematical proof. For the
other surfaces

, we reduce  — via edge contractions á la Whiteley [20] — to irreducible triangulations, whose volume-rigidity we verify numerically.

Hypergraph sparsity was introduced by Streinu and Theran [17], generalizing results on graph sparsity, prominently by White and Whiteley [21] who studied it from a matroid perspective. We say that a $(d-1)$-complex is $(d-1,d^2-d-1)$-sparse
(resp. tight)
if every subset $A$ of its vertices of cardinality at least $d$ spans at most $(d-1)|A|-(d^2-d-1)$ simplices of dimensions $d-1$
(resp. and equality holds when $A$ equals the entire vertex set).

Clearly, a vertex subset $A$ spanning more $(d-1)$-simplices induces a non trivial linear dependence between the columns of $\fV(K,\p),$ and it is natural to ask whether this characterizes all the linear dependencies in the volume rigidity matrix. Using Theorem <ref>, we show that the answer is negative,
hence a Laman-type condition for volume-rigidity does not hold true [Corollary <ref> shows that Prop.1 in the preprint [16] from 2007 is a misstatement.].

For every $d\ge 3$, there exists a $(d-1,d^2-d-1)$-tight $(d-1)$-complex
that is not volume-rigid.

§.§ Relation to previous works.

The maximal independent sets of columns of $\fV(\binom{[n]}{d},\p)$, for all generic embeddings $\p$, form the bases of the same matroid. For $d=2$ they correspond to spanning trees, namely the bases in the graphic matroid on $\binom{[n]}{2}$. Kalai <cit.> introduced for every integer $k\ge 1$ the $k$-hyperconnectivity matroid on $\binom{[n]}{2}$ [The $k$-hyperconnectivity matroid is derived from an embedding of the vertex set into $\R^k$. Studying higher hyperconnectivity translates to increasing the dimension of the embedding space.], where $k=1$ corresponds to the graphic matroid, and identified its bases in terms of exterior shifting (w.r.t. the lexicographic order): $G$ is a basis if and only if the edges of $\Delta^{\rm{lex}}(G)$ form the initial segment that ends with $\{k,n\}$, w.r.t. the lex-order.

Here, in Theorem <ref>, rather then increasing the dimension of the embedding space and staying with graphs, we increase also the dimension of the pure complex, by the same number, and characterize the bases of the resulted $d$-volume-rigidity matroid in terms of exterior shifting w.r.t. the partial order $<_p$.

The fact that $(d-1,d^2-d-1)$-sparse complexes form the independent sets of a matroid on $\binom{[n]}{d}$ was asserted in [12, 21]. Additional matroidal and algorithmic properties of sparsity matorids were studied by Streinu and Theran in [17, 18]. By Corollary <ref>, the  $(d-1,d^2-d-1)$-sparsity matroid strictly contains the $(d-1)$-volume-rigidity matroid for all $d\ge 3$. It would be interesting to find further combinatorial conditions that once imposed on the bases of the sparsity-matroid would give the bases of the volume-rigidity matroid.

The remainder of the paper is organized as follows. In Section <ref> we establish the connection between volume rigidity and exterior shifting, and prove Theorem <ref>. Afterwards, in Section <ref> we investigate the effect of local moves on volume rigidity and prove Corollary <ref>. In the following Section <ref> we prove Corollary <ref>, and we conclude in Section <ref> with some related open problems.

Notation. Throughout this notes $K$ will be a pure $(d-1)$-dimensional simplicial complex with vertex set $[n]$. For an $n\times n$  matrix $M$, $C_{i,j} M$ is the determinant of the matrix $M$ with the row $i$ and column $j$ removed. For $S,T \in \binom{[n]}{k}$ Let $T = \{t_1 < \dots < t_k\}$ and $S=\{s_1 < \cdots < s_k\}$, the partial order $T\leq_p S$ if $t_i \leq s_i$ for $i=1,\dots ,k$. For a poset $(P, <)$, $P_{< \sigma}$ denotes the sub-poset of all the elements stricly less than $\sigma$ and $P_{\leq \sigma}$ is defined analgously.

Volume rigidity.  Let $p \colon V(K) \rightarrow \R^{d-1}$ be a placement of the vertices of $K$ in $\R^{d-1}$, i.e. $p\in \R^{(d-1)n}$. The (signed) volume of a $d$-face $\sigma=\{v_1,\dots ,v_d\} \in K$ with respect to $p$ is given by

\begin{equation}
\det M_{p, \sigma} =
\det
\begin{pmatrix}
p(v_1) & \dots & p(v_d)\\
1 & \dots &1
\end{pmatrix}.
\end{equation}

Consider the map $\rho \colon \R^{(d-1)n}\rightarrow \R^{f_{d-1}(K)}$ given by $\rho(p)_{\sigma} = \det M_{p,\sigma}$. The derivative of $\rho$ with respect to $p$ is the $(d-1)n\times f_{d-1}(K)$ matrix

\[
\left (\frac{d\rho}{dp} \right)_{i,v;\sigma} =
\begin{cases}
0 & \text{if } v \notin \sigma \\
\frac{\partial \det M_{p,\sigma}}{\partial v_i} = (-1)^{j+1} C_{i,v} M_{p,\sigma}       & \text{if } v \text{ is $j$-th vertex in } \sigma.
\end{cases}
\]

The following result appears in [13].

$\rank \frac{d\rho}{dp} \leq (d-1)n - d(d-1) + 1$.

Assume $n\ge d$. We say that $K$ is volume rigid w.r.t $p$ if $\rank \frac{d\rho}{dp}  = (d-1)n - d(d-1) + 1$ and $\frac{d\rho}{dp}$ is the volume rigidity matrix of $K$ w.r.t $p$. We say that $K$ is $(d-1)$-volume rigid if $K$ is volume rigid w.r.t $p$ for some  $p \colon V(K) \rightarrow \R^{d-1}$  (equivalently, for generic $p$, namely where all $(d-1)n$ entries of $p$ are algebraically independent over the rationales).

Algebraic shifting. Let $\R^n$ be the vector spaces with coordinates indexed by vertices, its standard basis is given by $e=(e_i)_{i\in [n]}$. Let $\bigwedge \R^n$ be its exterior algebra with basis $(e_{\sigma})_{\sigma \subseteq [n]}$. Let $\bigwedge K = \bigwedge V /(e_{\sigma} \colon \sigma\notin K)$ . Consider $(f_1,\dots ,f_n)$ a generic change of basis of $e$ in $\R^n$. Without loss of generality we can assume that $f_1 = \unitvec \in \R^n$. Let $A$ be the change of basis matrix from $e$ to $f$, i.e. $A = (  \unitvec | f_2 | \cdots | f_n)$. For $f\in \bigwedge V$ let $\bar{f}$ denote the class of $f$ in $\bigwedge K$.

An alternative definition of $\bigwedge K$ is as follows: first we take $\bigwedge^j K =\SPAN \{e_S \colon S\in K, |S| = j\}$ and $\bigwedge K = \SPAN \{e_S \colon S\in K\}$. Then the elements $\bar{f}$ are simply the projection to the subspace spanned by faces of $K$. Let $q\colon \bigwedge V \rightarrow \bigwedge K$ be the projection map.

For a partial order $<$ on $\{S\subset [n]\}$, set
$$\Delta^<(K) = \{S \colon \bar{f}_S \notin \SPAN \{\bar{f}_T \colon T< S, |T|=|S|\}\}.$$

§ VOLUME RIGIDITY AND $\DELTA^P(\CDOT)$

This section is devoted to studying the basic properties of the shifted complex $\Delta^p(K)$, and to establishing the connection between $\Delta^p(K)$ and $K$'s volume rigidity.

§.§ Basic properties of $\Delta^p(\cdot)$

We start by briefly exploring some useful properties of the complex $\Delta^p(K)$ that appears in Theorem <ref>.
Given a partially ordered set (poset) $(P,<)$ and an element $x\in P$ we denote by $P_{<,x}$ the prefix $\{y\in P~:~ y\le x\}$.

Let $(P, <)$ be a poset and $x \in P$, then there exists a linear extension $<_l$ of $<$ such that $P_{<_l,x} = P_{<,x}$.

View the sets $A=P_{<,x}$ and $B=P\setminus P_{<,x}$ as posets with the partial order induced by $<$. Extend each of these posets linearly, and concatenate the extensions such that the elements in $A$ are smaller than those in $B$.

We will mainly work with the partial order $<_p$ on the power set of $[n]$ and denote the set of its linear extensions by $\cL$. We usually denote an element in $\cL$ by $<_l$ and the corresponding shifted complex by $\Delta^l(K) := \Delta^{<_l}(K)$.

$\Delta^p(K) = \bigcup_{<_l\in \cL} \Delta^l(K)$.

On the one hand, if $\sigma\in\Delta^l(K)$
for some $<_l\in\cL$ then $q( f_\sigma)$ is not spanned by $B_{l,\sigma}:=\{q(f_\tau)~:~\tau <_l \sigma\}$, which contains the vector set $B_{p,\sigma}$. Therefore, by the definition of $\Delta^<$ in (<ref>), we find that $\Delta^p(K)\supseteq\Delta^l(K)$. On the other hand, for every $\sigma\in\Delta^p(K)$, there exists by the previous claim a linear extension $<_l\in\cL$ satisfying $B_{p,\sigma}=B_{l,\sigma}$ hence $\sigma \in \Delta^l(K)$.

For every simplicial complex $K$ there holds that $\Delta^p(K)$ is a shifted simplicial complex independent of the choice of the generic basis $f$. In addition, $\Delta^p(K) = K$ if $K$ is shifted. $\square$

That $\Delta^p(K)$ is downwards closed follows exactly as in the proof for $\Delta^{\mathrm{lex}}(K)$. The rest of
Corollary <ref> follows immediately from the above decomposition of $\Delta^p(K)$ and the fact that the basic properties of algebraic shifting in  [8] – being shifted, and independence the the generic $f$ chosen– hold in every linear extensions of $<_p$, as remarked in <cit.>.

§.§ Volume rigidity and $\Delta^p(\cdot)$

We are now ready to prove Theorem <ref>. We denote $\sigma_0=\{1,3,...,d,n\}$ and observe that the prefix $B:=\{\tau\le_p\sigma_0~:~|\tau|=d\}$ consists of the subsets $[d]$ and  $[d]\setminus\{i\}\cup\{v\}$ for $
2\le i \le d$ and $d+1\le v\le n$. We define a linear transformation $\psi: \bigoplus_{i=2}^{d}\bigwedge^1 \R^n \rightarrow \bigwedge^d \R^n$ given by
$$\psi(m_2,\dots ,m_d)  = \sum_{i=2}^d f_{[d]\setminus \{i\}}\wedge m_i.$$

The image of $\psi$ is spanned by $\{f_\tau~:~\tau\in B\},$ and its kernel is $(d^2-d-1)$-dimensional.

The fact that $f_\tau\in\mathrm{im}(\psi)$ for every $\tau \in B$ can be shown directly. Indeed, $\psi(0,...,0,f_d)=f_{[d]}$ and by taking $m_i=f_v,~m_{i'}=0~\forall i'\ne i$ we have that $\psi(0,...,f_v,...,0)=f_{[d]\setminus\{i\}\cup\{v\}}$ for $2\le i \le d$ and $d+1\le v\le n$. To show that these $1+(n-d)(d-1)$ linearly independent vectors span the image of $\psi$, we will construct $d^2-d-1$ linearly independent vectors in $\ker\psi$ which actually completes the proof by the rank-nullity theorem since $(1+(n-d)(d-1)) + (d^2-d-1) = n(d-1).$

First, for every $2\le i\le d$ and $j\in[d]\setminus \{i\}$ consider the vector defined by setting $m_i=f_j$ and $m_{i'}=0$ for every $i'\ne i$. Then,

\[
\psi(m_2,...,m_d) = f_{[d]\setminus\{i\}}\wedge f_j = 0
\]

since $j\in[d]\setminus \{i\}$. This amounts to $(d-1)^2$ vectors in $\ker\psi,$ and the remaining $d-2$ are given by vectors of the form $m_i=a_if_i,~2\le i \le d$,
where the scalars $a_2,...,a_d$ satisfy $\sum_{i=2}^{d} (-1)^ia_i = 0$. Indeed,

\[
\psi(m_2,...,m_d) = \sum_{i=2}^d a_i f_{[d]\setminus\{i\}}\wedge f_i = \sum_{i=2}^d a_i(-1)^{d-i}f_{[d]}=0\,.
\]

The linear independence of these $d^2-d-1$ vectors follows directly from the linear independence of $f_1,...,f_d$.

Identify the vertices of $K$ with the set $[n]$.
W.l.o.g. assume that $f_{d-1}(K)\ge (d-1)n-(d^2-d-1)$, as otherwise $K$ is not volume-rigid and $\{1,3,4,...,d,n\} \notin \Delta^p(K)$.
In addition, suppose that the generic embedding $\p:V(K)\to\R^{d-1}$ is obtained from the vectors $f_2,...,f_d$ in the generic basis of $\R^n$ by taking $(f_i)_v=\p(v)_{i-1}$ for every $2\le i \le d$ and $v\in [n]$.

Consider the $(i,v)$-unit vector $e_{i,v}=(m_2,...,m_d)$  in the domain of $\psi$, for  $2\le i \le d$ and $v\in [n]$, defined by $m_i=e_v$ and $m_{i'}=0,~\forall i'\ne i$. Then,

\begin{align*}
\psi(e_{i,v})&=f_{[d]\setminus\{i\}}\wedge e_v\\&= (-1)^{d-i}f_1\wedge\dots\wedge f_{i-1}\wedge e_v \wedge f_{i+1}\wedge\dots\wedge f_d\\&=
(-1)^{d-i+d-1}f_2\wedge\dots\wedge f_{i-1}\wedge e_v \wedge f_{i+1}\wedge\dots\wedge f_d\wedge f_1.
\end{align*}

Let $\sigma =\{v_1,...,v_d\}\subset [n]$. Clearly, for the inner product on $\bigwedge \R^n$ with orthonormal basis $\{e_\sigma:\ \sigma \subset [n]\}$, we have
$\langle e_\sigma, \psi(e_{i,v})\rangle = 0$  if $v\notin\sigma.$ Otherwise, by the identification of $\p$ with $f_2,...,f_d$ above and $f_1=\unitvec$, if $v=v_j$ then $\langle e_\sigma, \psi(e_{i,v})\rangle$ is equal to $(-1)^{i-1}$ times the determinant of the matrix that is obtained from $M_{\p,\sigma}$ by replacing  its $(i-1)$-th row with the $j$-th $d$-dimensional all-ones row vector. Consequently,

\langle e_\sigma, \psi(e_{i,v})\rangle = (-1)^{i-1}C_{i-1,j}(M_{\p,\sigma}).

Thus, by letting $q: \bigwedge \R^n \longrightarrow \bigwedge K$ be the natural quotient map, and by choosing the basis $\{{e}_\sigma: \sigma \in K\}$ for $\bigwedge K$, we find that the $f_{d-1}(K)\times (d-1)n$ matrix representation of $q\circ\psi$ is equal — up to multiplying some of its columns by $-1$ and reordering them — to the transpose of the volume-rigidity matrix $\fV(K,\p)$. Therefore, $K$ is volume-rigid if and only if $\dim\ker(q\circ \psi)=d^2-d-1.$ In other words, $K$ is not volume-rigid if and only if there exists a non-zero $f\in\mathrm{im}(\psi)$ such that $q(f)=0$. By the characterization of $\psi$'s image in Lemma <ref>, $f$ can be written as a non-trivial linear combination $f=\sum_{\tau\in B}\lambda_\tau f_\tau$.

To conclude the proof we claim that $q(f)=0$ for some $f\in\SPAN\{f_\tau~:~\tau\in B\}$ if and only if $\sigma_0\notin \Delta^{p}(K)$. Indeed, on one direction, $q(\sum_{\tau\in B}\lambda_\tau f_\tau)=0$ implies that for some $\tau\in B$, $q(f_\tau)$ is a linear combination of its predecessors in $<_p$. By (<ref>), $\tau\notin\Delta^p(K)$ and since $\Delta^p(K)$ is shifted then $\sigma_0\notin\Delta^p(K)$. On the other hand, by manipulating the linear combination which asserts that $\sigma_0\notin\Delta^p(K)$, we obtain a non-zero vector $f=\sum_{\tau\in B}\lambda_\tau f_\tau$ satisfying $q(f)=0$.

§ VOLUME RIGIDITY, LOCAL MOVES AND HOMOLOGY

We turn to study the effect of local combinatorial moves on volume rigidity. We start by proving a volume-rigidity analog of Whiteley's vertex splitting [20], by which he showed that every triangulation of the $2$-sphere has a $3$-rigid $1$-skeleton.

Let $K$ be a pure $(d-1)$-dimensional simplicial complex, $e =\{u,w\} \in K$ such that
at least $(d-1)$ facets in $K$ contain $e$. Let $K'$ to be the simplicial complex obtained from $K$ by contracting the edge $e$, i.e. by identifying the vertex $u$ with $w$, and removing duplicates. If $K'$ is
volume rigid then so is $K$.

Without loss of generality assume that $u<w$ are the first among the $n$ vertices of $K$, as the vertex labels do not effect volume-rigidity. We will construct an auxiliary $(d-1)n\times f_{d-1}(K)$ matrix $A$ such that

\[
\rank{\fV(K,\p)}\ge \rank(A) = (d-1)n-(d^2-d-1).
\]

First, we replace the position of the vertex $w$, i.e. $\p(w)$, by the position of the vertex $u$, i.e. $\p(u)$. Formally we define a new (non-generic) placement of vertices $\p'$ that coincides with $\p$ on all vertices except $w$ on which we set it to equal to $\p(u)$. Clearly, since $\p$ is generic, there holds $\rank{\fV(K,\p)}\ge\rank{\fV(K,\p')}.$ To obtain $A$, we add the rows
in $\fV(K,\p')$ corresponding to the vertex $u$ to the rows corresponding to the vertex $w$, an operation that  does not change the rank.

We first claim that the submatrix of $A$ which corresponds to the columns of the facets $L$ containing $e=\{u,w\}$ is supported on the rows corresponding to $u$. Indeed,
if $e\subseteq \sigma=\{v_1,\ldots,v_d\}\in L$ then for $v_j\in \sigma$ such that $v_j\neq \{u,w\}$ we have that each entry $A_{v_j,i ; \sigma} =C_{i,j}(M_{\p',\sigma}) = 0$ because $M_{\p',\sigma}$ has two identical columns as $\p'(u) = \p'(w)$. On the other hand, because we added the rows corresponding to vertex $u$ to the rows corresponding to vertex $w$, we have that
$$A_{w,i;\sigma} = C_{i,1}(M_{\p',\sigma}) + C_{i,2}(M_{\p',\sigma}) = 0.$$
This follows from  our assumption that $u$ and $w$ are the first two vertices hence their cofactors in $M_{\p',\sigma}$ have opposite signs, and they in fact cancel-out since and $\p'(u)=\p'(w)$.

Second, we claim that the submatrix $A_{u,L}$ of $A$ corresponding to the $d-1$ rows of $u$ and the columns of $L$ has a full rank of $d-1$. We derive this claim by the assumption that $|L|\ge d-1$ and the fact that $(\p'(v)~:v\ne u)$ is generic. Indeed, consider a vector $x\in\R^{d-1}$ in the left kernel of $A_{u,L}$. A brief calculation yields that the orthogonality of $x$ and the column in $A_{u,L}$ corresponding to the facet $\sigma =\{u,w,v_2,...,v_d\}$ is equivalent to $x$ being in the span of $\p'(v_i)-\p'(w),~i=2,...,d$. By the assumption that $\p$ is generic, such $|L|\ge d-1$ constraints are only satisfied by $x=0$ hence

\begin{equation}\label{eq:AuL}
\rank(A_{u,L})=d-1.
\end{equation}

Third, consider the complement submatrix $A':=A_{\{u\}^c,L^c}$ whose rows correspond to all the vertices except $u$, and columns to all the facets that are not in $L$. We observe that $A'$ contains as a submatrix the generic volume rigidty matrix $\fV(K',\p)$ — where $\p$ is viewed here as a generic embedding of $V(K')=V(K)\setminus\{u\}$ into $\R^{d-1}$. Indeed, every facet $\sigma$ of $K'$ arises from a facet $\hat\sigma$ of $K$.

* If $u\notin \hat\sigma$ then $\sigma=\hat\sigma$ and the columns in $\fV(K',\p)$ and $A'$ corresponding to $\sigma$ are clearly equal.

* Otherwise, if $u\in \hat\sigma$ then $\sigma = \hat\sigma\cup\{w\}\setminus\{u\}$, and by the construction of $A$ — in which $\p'(u)=\p'(w)$ and the rows of $u$ are added to the rows of $w$ — we have that the column in $A'$ created from $\hat\sigma$ is equal to the column of $\sigma$ in $\fV(K',\p)$.

Note that $A'$ may contain some duplicate columns — in case there are two facets that differ only in the vertices of $e$ — but, regardless, our observation that $A'$ contains $\fV(K',\p)$ as a submatrix implies that

\begin{equation}\label{eq:A'}
\rank(A')= (n-1)(d-1)-(d^2-d-1).
\end{equation}

In conclusion, $A$ takes the form

\[
~ & L & L^c \cr
~~u & A_{u,L} & *\cr
\{u\}^c & 0 & A' \cr
\]

and by combining (<ref>) and (<ref>) we find that

$$\rank(\fV(K,\p)\ge \rank(A)=\rank(A_{u,L})+\rank(A')=n(d-1)-(d^2-d-1)\,,

as claimed.

The next two lemmas are direct analogs of basic results in graph rigidity <cit.> asserting that gluing preserves volume-rigidity. We include their proofs for completeness.

Let $K$ be $(d-1)$-volume-rigid, $v\notin V(K)$ and $S\subseteq V(K)$ such that $|S|\geq d$, then $K \cup (v*\binom{S}{d-1})$ is $(d-1)$-volume-rigid.

The vertex $v$ is in at least $d-1$ facets of $L = K \cup (v*\binom{S}{d-1})$. The volume rigidity matrix of $L$ is of the form

\begin{equation*}
\bordermatrix
~ & K & S*v \cr
V & \fV(K,\p) & *\cr
v & 0 & N \cr
\end{equation*}

where the matrix $N$ has $d-1$ rows and at least $d-1$ columns. Because of general position $N$ has full rank, i.e. $rank(N) = d-1$. Because $K$ is $(d-1)$-volume-rigid we have that $rank(\fV(K,\p)) = n(d-1) - d(d-1) + 1$. Then, $rank(\fV(L,\p)) = rank(\fV(K,\p)) + rank(N) = (n+1)(d-1) - d(d-1) + 1$ and consequently $L$ is $(d-1)$-volume-rigid.

Let $K$ and $L$ be $(d-1)$-volume-rigid complexes such that $|V(K)\cap V(L)|\geq d$. Then $K\cup L$ is  $(d-1)$-volume-rigid.

Because $K$ and $L$ are $(d-1)$-volume-rigid we can assume that each of them has a complete $(d-1)$-skeleton on its respective vertex set. Then $K\cup L$ contains the vertex spanning subcomplex $Q$ obtained from $K$ by adding one vertex $v$ at a time, adding the facets $\binom{S}{d-1} * v$ at step $v$, where $S=V(L)\cap V(K)$. This subcomplex is $(d-1)$-volume-rigid at each step by application of the previous lemma. In particular, $Q$ is $(d-1)$-volume-rigid, hence so is  $K\cup L$.

§.§ Proof of Corollary <ref>

Barnette and Edelson [4, 5] proved that every compact surface without boundary admits only finitely many irreducible triangulations, namely, triangulations where every edge contraction would result in a simplicial complex not homeomorphic to the given surface.
Thus, by Lemma <ref>, in order to conclude that for a given surface $S$ every simplicial complex that triangulates it is volume-rigid, it is enough to verify if for the irreducible triangulations of $S$.
Those are known for the surfaces indicated in Corollary <ref>: one for the $2$-sphere (namely the boundary of a tetrahedron),
two for the projective plane [3],
21 for the torus [10]
and 29 for the Klein bottle [11, 19].
Clearly the boundary of the tetrahedron is volume-rigid, and we verified by computer that the irreducible triangulations $K$ of the
other surfaces mentioned above are volume-rigid – for this it was enough to find some embedding $\p_K: V(K)\longrightarrow \R^2$ such that $\rank(\fV(K,\p_K)=2|V(K)|-5$.

The fact that every triangulation $K$ of the $2$-sphere is volume-rigid follows also from combining the $3$-hyperconnectivity of its graph

with the Cohen-Macaulay property. Indeed, the first property says that $\{3,|V(K)|\}\in \Delta^{\mathrm{lex}}(K)$, and as $K$ is Cohen-Macaluay then $\Delta^{\mathrm{lex}}(K)$ is pure and hence $\{1,3,|V(K)|\}\in \Delta^{\mathrm{lex}}(K)$ as $\Delta^{\mathrm{lex}}(K)$ is shifted, which implies, by Claim <ref>, that $\{1,3,|V(K)|\}\in \Delta^p(K)$, and we are done by Theorem <ref>.

To prove the second part of Corollary <ref> we are left to show that removing one triangle from a triangulated $2$-sphere or torus preserves volume-rigidity, done next.
A pure simplicial complex is a minimal cycle (over some coefficients commutative ring $\F$) if there exists an $\F$-linear combination of its facets whose boundary vanishes, and no proper nonempty subset of its facets has this property. For example, every triangulation of a compact connected surface (resp. and orientable) is a minimal cycle over $\Z_2$ (resp. $\Z$).

If $K$ is a $(d-1)$-dimensional
volume rigid minimal cycle
over $\Z$, then $K\setminus \sigma$ is volume rigid for

$\sigma \in K$.

We first give short proof for the special case $d=3$ and conclude the proof of Corollary <ref>. Afterwards, we give a more technical proof for the general case.

As $K$ is a minimal cycle over $\Z$, its $2$-dimensional homology with $\R$-coefficients is one dimensional, and for each facet $\sigma$ of $K$, for $K\setminus \sigma$ this homology vanishes.
By the translation of homology in terms of algebraic shifting, $\Delta^{\rm{lex}}(K)\ni \{2,3,4\} \notin  \Delta^{\rm{lex}}(K\setminus \sigma)$, and as shifting preserves containment we conclude
\[\Delta^{\rm{lex}}(K\setminus \sigma)= \Delta^{\rm{lex}}(K)\setminus  \{\{2,3,4\}\}.\]

Note that in this dimension[For $d>3$, $\{\tau:\ \tau<_p \{1,3,4,\ldots,d,n\}\}$ is smaller than $\{\tau:\ \tau<_\mathrm{lex} \{1,3,4,\ldots,d,n\}\}$.]
$\tau<_p \{1,3,n\}$ iff $\tau<_\mathrm{lex} \{1,3,n\}$, and thus:
$\{1,3,n\} \in \Delta^p(K)$ (by Theorem <ref>), hence $\{1,3,n\} \in \Delta^{\mathrm{lex}}(K)$, and by the displayed equality above also
$\{1,3,n\} \in \Delta^{\mathrm{lex}}(K\setminus \sigma)$, so finally
$\{1,3,n\} \in \Delta^p(K\setminus \sigma)$, equivalently,
$K\setminus \sigma$ is volume-rigid.

This is immediate from Lemma <ref>, Lemma <ref> for the case $d=3$, and the discussion in the beginning of <ref>.

We conclude this section with a more direct proof of Lemma <ref> for all $d\ge 3$.

For two subsets $\sigma$ and $\tau=\sigma\setminus\{v\}$ of $[n]$ that differ by one element, denote $\mathrm{sign}(\tau,\sigma):=(-1)^j$ if $v$ is the $j$-th element in $\sigma.$ We prove the following stronger statement. Let $z\in \Z^{f_{d-1}(K)}$ be a $(d-1)$-dimensional chain in $K$, and $\partial z \in \Z^{f_{d-2}(K)}$ be its boundary, i.e. $(\partial z)_{\tau} = \sum_{\tau \subset \sigma}{\mathrm{sign}(\tau,\sigma)}\cdot z_\sigma.$ Then, for every vertex $v$ and every $i\in[d-1]$

\begin{equation}\label{eq:bndry}
\left(\fV(K,\p)\cdot z\right)_{v,i} = (-1)^{d+i}\sum_{\rho}  {\mathrm{sign}(\rho,\rho\cup\{v\})}\cdot \det N_{\p,\rho,i}\cdot (\partial z)_{\rho\cup\{v\}}\,,
\end{equation}

where (i) the summation is over the $(d-3)$-faces $\rho$ of $K$ that belong to the link of $v$ and, (ii) the $(d-2)\times(d-2)$ matrix $N_{\p,\rho,i}$ is obtained from the $(d-1)\times (d-2)$ matrix $(\p(v)~:~v\in\rho)$ by removing its $i$-th row. In particular, if $z$ is a generator of the $(d-1)$-homology of a minimal cycle $K$, then $z$ is also a non-trivial linear dependence between the columns of $\fV(K,\p)$. Therefore, removing a $(d-1)$-face from $K$ does not change the rank of the volume rigidity matrix, hence if $K$ is volume rigid then so is $K\setminus\{\sigma\}.$ To derive (<ref>), note that

\begin{align}
\nonumber\left(\fV(K,\p)\cdot z\right)_{v,i}& = \sum_{v\in \sigma \in K} z_\sigma\cdot C_{i,j}M_{\p,\sigma} \\
\label{eq:det_expand}&=\sum_{\sigma} z_\sigma\cdot(-1)^{i+j}\sum_{j'\in[d]\setminus\{j\}} (-1)^{d-1+j'-\mathbf{1}_{j'>j}}\det N_{\p,\sigma\setminus\{v_j,v_j'\},i}
%&=(-1)^{d+i-1}\sum_{\tau} \det N_{\p,\tau,i} \sum_{\sigma }(-1)^{\mathrm{sign}(\{v\}*\tau,\sigma)}z_\sigma.
\end{align}

Indeed, suppose that $\sigma=\{v_1,...,v_d\}$ and $v=v_j$ and expand the $(i,j)$-th minor of $M_{\p,\sigma}$ by the last row (of ones). Denote $\tau := \sigma\setminus\{v_{j'}\}$ and $\rho:=\tau\setminus\{v_j\}$, and we easily observe that $\mathrm{sign}(\rho,\tau) =(-1)^{j-\mathbf{1}_{j'<j}}.$ Therefore, by changing the order of summation in (<ref>) we find that

\[
\left(\fV(K,\p)\cdot z\right)_{v,i} = (-1)^{d+i}\sum_{\rho}\mathrm{sign}(\rho,\tau)\det N_{\p,\rho,i}\sum_{ \tau \subset \sigma} \mathrm{sign}(\tau,\sigma)\cdot z_\sigma,
\]

as claimed.

Two dimensional spheres are $2$-volume rigid.

Let $K$ be a triangulation of the $2$-dimensional sphere. By Fogelsanger <cit.> we have that $\{3,n\} \in \Delta^{e}(K)$ for the exterior shifting w.r.t. the lexicographic order.  Because $K$ is Cohen-Macaulay we have that $\Delta^e(K)$ is pure and consequently $\{1,3,n\} \in \Delta^e(K) \subseteq \Delta^p(K)$. The conclusion follows from the above proposition.

Remark: as $T<_p \{1,3,n\}$ iff $T<_\mathrm{lex} \{1,3,n\}$ we obtain that
$\{1,3,n\} \in \Delta^e(K)$ iff  $\{1,3,n\} \in \Delta^p(K)$. In higher dimensions the analogous statement is false.

Experimental results. We verified by computer that all the irreducible triangulations of the torus, the Klein bottle and the projective plane are area rigid, namely $2$-volume rigid.

A la Fogelsanger.
The next three lemmas, and their proofs, are similar to the corresponding statements for the graph rigidity / hyperconnectivity matroids.

Let $K$ be a pure $(d-1)$-dimensional simplicial complex, $e =\{u,w\} \in K$ such that
there are at least $(d-1)$ facets containing $e$. Set $K'$ to be the complex $K$ with the edge $e$ contracted, i.e. identify the vertex $w$ with $u$. If $K'$ is
$(d-1)$-volume rigid then so is $K$.

Without loss of generality assume that $u<w$ are the first two vertices.
[inline]Eran: Shall we comment somewhere, perhaps in Cor.0.4, that Bjorner-Kalai permutation lemma applies for $\Delta^p$ as it applies for $\Delta^l$ for every linear extension $<_l$ of $<_p$? Thus, the labeling of vertices does not effect $\Delta^p$.

Let $M_{K}=\frac{d\rho}{dp}(K)$ and $M_{K'}$ be the volume rigidity matrices of $K$ and $K'$ respectively. Because $K'$ is volume rigid there are $(d-1)(n-1)-d(d-1)+1$ columns in $M_{K'}$ that are linearly independent, denote this set by $C$. Consider these columns in $M_{K}$[For a column corresponding to a facet $\{u\}\cup\tau \in K'$ that is not present in $K$, associate with it the column in $M_K$ corresponding to $\{w\}\cup\tau$, which is a facet in $K$.]
together with $(d-1)$ columns corresponding to facets in $K$ containing the edge $e$. If these are linearly independent we are done, lets assume that it is not the case.

We translate the linear dependence between columns of $M_{K}$ into a linear dependence between columns of $M_{K'}$. First, we replace the position of the vertex $w$, i.e. $p(w)$, by the position of the vertex $u$, i.e. $p(u)$. Formally we define a new placement of vertices $p'$ that coincides with $p$ on all vertices except on $w$ on which we set it to be equal to $p(u)$. Next, we add the rows corresponding to the vertex $w$ to the rows corresponding to the vertex $u$. Finally, we remove the rows corresponding to the vertex $w$. Notice that at each step we preserve the linear dependency. Denote this last matrix by $\hat{M}_K$.

The matrix $\hat{M}_K$ has zero columns for facets containing the edge $e$ because if $e\subseteq \sigma$ then for $v\in \sigma$ such that $v\neq u$ we have that $(\hat{M}_K)_{i,v ; \sigma} =C_{i,v}M_{p',\sigma} = 0$ because $M_{p',\sigma}$ has two identical columns as $p'(u) = p'(w)$. On the other hand, because we subtracted the rows corresponding to vertex $w$ from the rows corresponding to vertex $u$, we have that $(\hat{M}_{K})_{i,u;\sigma} = C_{i,u}M_{p',\sigma} - C_{i,w}M_{p',\sigma} = 0$ because we assumed $u$ and $w$ are the first two vertices, that is they have opposite sign.

The matrix $\hat{M}_K$ has duplicated columns for pair of facets that differ only in the vertices of $e$. To see this let $\sigma$ and $\sigma'$ be two facets such that $u\in \sigma$, $w\in \sigma'$. Then for $v\in \sigma\cap \sigma'$ we have that $(\hat{M}_K)_{i,v;\sigma} = C_{i,v}M_{p',\sigma} = C_{i,v}M_{p',\sigma'} = (\hat{M}_K)_{i,v;\sigma'}$ and $(\hat{M}_K)_{i,u;\sigma} = (\hat{M}_K)_{i,u; \sigma'}$. By removing the zero columns and for each duplicate remove the one corresponding to the facet containing the vertex $w$, we obtain $M_{K'}$.

As the columns of $M_{K'}$ in $C$ are linearly independent,
for the columns corresponding to facets not containing $e$

coefficient in the above linear combination must be zero. Then the only non-zero coefficients are with the facets containing the edge $e$. By restricting to the rows corresponding to the vertex $w$ we notice a square sub-matrix with generic coefficient of size $(d-1)\times (d-1)$ and consequently of full rank, that is, they are linearly independent as well, which is a contradiction.

Let $K$ be $(d-1)$-volume rigid, $v\notin V(K)$ and $S\subseteq V(K)$ such that $|S|\geq d$, then $K \cup (v*\binom{S}{d-1})$ is $(d-1)$-volume rigid.

The vertex $v$ is in at least $d-1$ facets of $L = K \cup (v*\binom{S}{d-1})$. The volume rigidity matrix of $L$ is of the form

\begin{equation*}
\bordermatrix
~ & K & S*v \cr
V & M_K & *\cr
v & 0 & N \cr
\end{equation*}

where the matrix $N$ has $d-1$ rows and at least $d-1$ columns. Because of general position $N$ has full rank, i.e. $rank(N) = d-1$. Because $K$ is $(d-1)$-volume rigid we have that $rank(M_K) = n(d-1) - d(d-1) + 1$. Then, $rank(M_L) = rank(M_K) + rank(N) = (n+1)(d-1) - d(d-1) + 1$ and consequently $L$ is $(d-1)$-volume rigid.

Let $K$ and $L$ be $(d-1)$-volume rigid complexes such that $|V(K)\cap V(L)|\geq d$. Then $K\cup L$ is  $(d-1)$-volume rigid.

Because $K$ and $L$ are $(d-1)$-volume rigid we can assume that each of them has a complete $(d-1)$-skeleton on its respective vertex set. Then $K\cup L$ contains the vertex spanning subcomplex $Q$ obtained from $K$ by adding one vertex $v$ at a time, adding the facets $\binom{S}{d-1} * v$ at step $v$, where $S=V(L)\cap V(K)$. This subcomplex is $(d-1)$-volume rigid at each step by application of the previous lemma. In particular, $Q$ is $(d-1)$-volume rigid, hence so is  $K\cup L$.

If $K$ is a cycle and $(d-1)$-volume rigid, then $K\setminus \sigma$ is $(d-1)$-volume rigid for some $\sigma \in K$.

Because $K$ is cycle there exists linear combination of its facets $m = \sum_{S\in K}\lambda_S S$  such that $\partial m = f_1 \lip m = 0$, because $f_1 = \unitvec$. Then $f_{[d]\setminus i} \lip m  = \pm f_{[d]\setminus \{1,i\}} \lip (f_1 \lip m) = 0$ for all $i=2,\dots ,d$. Consequently, for $v\in V(K)$ we have that
$$0=\langle e_v, f_{[d]\setminus i}\lip m\rangle = (-1)^{d-1} \langle f_{[d]\setminus i},e_v\lip m\rangle = (-1)^{d-1} \sum_{S\in K\colon v\in S} \lambda_S\langle f_{[d]\setminus i}, e_v\lip e_S\rangle = (-1)^{d-1} \sum_{S\in K} \lambda_S (M_{K})_{i,v;S},$$

that is, the columns of $M_K$ are linearly dependent. Then we can remove one of them that has non-zero $\lambda_S$ without decreasing the rank of the matrix.

Let $K$ be a triangulation of the disc with a triangle boundary. Then $K$ is area-rigid.

Add the missing boundary triangle $T$ to obtain a triangulation of the $2$-sphere $L=K\cup\{T\}$. We saw that $L$ is area-rigid. Now, over $Z_2$ coefficients, the sum of all facets of $L$ is a $2$-cycle. The proof of the lemma above shows that removing any single facet of $L$ results in an area-rigid complex, particularly $K$ is area-rigid.

Let $K$ and $L$ be $(d-1)$-volume rigid and minimal cycles such that $K\cap L = \{S,T\}$, i.e. share two facets. Then $K\cup L\setminus \{S,T\}$ is $(d-1)$-volume rigid.

[inline]Eran: the pf looks wrong. Being a minimal cycle, say over $Z_2$, tells us that the claimed dependence $M_K(S)_{i,v,T}=...$ holds for ONE value of $i$, not for $d-1$ values of $i$. Do you agree?

We show tha the rank of the matrix $M_{K\cup L}$ and the rank of the matrix $M_{K\cup L\setminus \{S,T\}}$ coincide, the conclusion will follows because $|K\cap L|\geq d$. Because $K$ is a cycle we have that $(M_K)_{i,v;S} = \sum_{R\in K\setminus S} \lambda_S (M_K)_{i,v;R}$. Because $L$ is a cycle we have that $(M_K)_{i,v;T} = \sum_{R\in K\setminus T} \lambda_R (M_L)_{i,v;L}$. Then
$$(1-\lambda'_T)(M_K)_{i,v;T} = \sum_{R\in L\setminus \{S,T\}} \lambda_R (M_L)_{i,v;R} + \sum_{R\in K\setminus \{S,T\}} \lambda_R (M_K)_{i,v;R}.$$
Because $\lambda_T$ dependens continuous on $p$, by perturbing $p$ we can ensure that $\lambda_T\neq 1$. Then, the volume of $S$ and $T$ depends on the remaining facets.

§ VOLUME RIGIDITY AND SPARSITY

Let $d\ge 3$ and

$K$ be the $(d-1)$-dimensional simplicial complex obtained from the graph $K_{3,3}$ by iterating the cone operation $d-2$
times. Then $K$ is $(d-1,d^2-d-1)$-sparse. (Indeed, $K_{3,3}$ is $(2,3)$-sparse, and if a pure $(k-1)$-dimensional simplicial complex is $(k-1,k^2-k-1)$-sparse then its cone is $(k,(k+1)^2-(k+1)-1)$-sparse.)
Thus, by completing it to a basis in the $(d-1,d^2-d-1)$-sparsity matroid,
we find a basis $K'$ containing $K$, so $K'$ is $(d-1,d^2-d-1)$-tight.

In order to show that $K'$ is not volume-rigid, by Theorem <ref> it is enough to show that
\[\{1,2,\ldots,d-2,d+1,d+2\}\in \Delta^p(K'),\]
$\{1,2,\ldots,d-2,d+1,d+2\} \nleq_p \{1,3,4,\ldots,d,n\}$ and using tightness.

The displayed equation above follows from basic properties of this shifting operator, proved in the same way as for exterior shifting w.r.t. the lex-order:

* If $K$ is a subcomplex of $K'$ then $\Delta^p(K)\subseteq \Delta^p(K')$.

* Cone and $\Delta^p$ commute, namely, if $K=v*L$ for a simplicial complex $L$ then $\Delta^p(K)=1*(\Delta^p(L)+1)$.

Here for a family $F$ of subsets of $[m]$, $F+1:=\{B+1:\ B\in F\}$, and $B+1:=\{i+1:\ i\in B\}$ (so $\emptyset+1=\emptyset$).
To conclude the proof it is left to note that $\{3,4\}\in \Delta^{\rm{lex}}(K_{3,3})$ and hence, by Claim <ref>, also $\{3,4\}\in \Delta^p(K_{3,3})$.

§ CONCLUDING REMARKS

We end up with some related open problems.
An obvious one is to extend Corollary <ref> to include all surface triangulations.

Every triangulation of a compact connected surface without boundary, minus a single triangle, is volume-rigid.

The problem we face in applying Fogelsanger's decomposition [7] (see also <cit.>) to volume rigidity of surfaces is that the pieces in the decomposition include triangle faces not existing in the original triangulation, and thus the gluing lemmas we could prove, e.g. Lemma <ref>, are not strong enough to settle Conjecture <ref>.

It is known that for every triangulation $K$ of the $2$-sphere on $n$ vertices, minus a single triangle, its exterior shifting $\Delta^{\rm{lex}}(K)=\Delta^p(K)$ consists exactly of the triangle $13n$ and all the triangles that are smaller than it in the lex-order, and their subsets.  This is a sufficient condition for volume rigidity by Theorem <ref>. The following conjecture deals with  a higher-dimensional counterpart of this fact.

For every $d\ge 3$, every triangulation $K$ of the $(d-1)$-sphere minus a single $(d-1)$-simplex is volume rigid.

It is also natural to ask whether the stronger property of $\{1,3,4,\ldots,d,n\} \in \Delta^{\rm{lex}}(K)$ holds true. This is known, and tight, for stacked spheres [14] (also <cit.>).
Let us remark that the conclusion  $\{1,3,4,\ldots,d,n\} \in \Delta^s(K)$ for Kalai's symmetric shifting operator $\Delta^s(\cdot)$ is equivalent to the hard-Lefschetz isomorphism from degree $1$ to degree $d-1$ in a generic Artinian reduction of the Stanley-Reisner ring of $K$ over the field of reals; the later isomorphism was proved recently by Adiprasito [1].

Back to general complexes,

For every dimension, find a combinatorial characterization of the corresponding volume-rigidity matroid.

The combinatorial characterization problem is important for the $d$-rigidity matroid (and is open for $d\geq 3$). The $d$-rigidity of a graph $G$ on $n$ vertices is equivalent to
$\{d,n\}\in \Delta^s(G)$. In view of this fact, we ask:

Define a version of symmetric shifting $\Delta^{sp}(\cdot)$ and find a matroid on $\binom{[n]}{d}$ such that its bases $K$ are exactly those satisfying $\Delta^{sp}(K)=\{\tau: \tau\le_p \{1,3,4,\ldots,d,n\}\}$.

An additional direction to explore is the volume rigidity of a $(d-1)$-dimensional simplicial complex $K$ in $\R^{d'}$  for $d' \ge d-1$. That is, let $\p:V(K)\to\R^{d'}$ be generic, and ask whether there is a non-trivial motion of the vertices that preserves all the volumes of $K$'s $(d-1)$-dimensional simplices in $\R^{d'}$. The case $d=2$ corresponds to  the standard framework rigidity in $\mathbb R^{d'}$, and the case $d'=d-1$ is the volume rigidity notion we study in this paper. Several natural questions on the remaining cases $2<d\le d'$ arise: what are the trivial motions in this setting? Is there a characterization of $(d-1)$-volume rigidity in $\R^{d'}$ in terms of algebraic shifting?

[1]
K. A. Adiprasito.
Combinatorial lefschetz theorems beyond positivity.
arXiv preprint arXiv:1812.10454, 2018.

[2]
L. Asimow and B. Roth.
The rigidity of graphs.
Trans. Amer. Math. Soc., 245:279–289, 1978.

[3]
D. Barnette.
Generating the triangulations of the projective plane.
J. Comb. Theory, Ser. B, 33:222–230, 1982.

[4]
D. Barnette and A. L. Edelson.
All orientable 2-manifolds have finitely many minimal triangulations.
Israel Journal of Mathematics, 62:90–98, 1988.

[5]
D. Barnette and A. L. Edelson.
All 2-manifolds have finitely many minimal triangulations.
Israel Journal of Mathematics, 67:123–128, 1989.

[6]
James Cruickshank, Bill Jackson, and Shin-ichi Tanigawa.
Global rigidity of triangulated manifolds.
arXiv preprint arXiv:2204.02503, 2022.

[7]
Allen Lee Fogelsanger.
The generic rigidity of minimal cycles.
PhD thesis, Cornell University Ithaca, 1988.

[8]
Gil Kalai.
Symmetric matroids.
J. Combin. Theory Ser. B, 50(1):54–64, 1990.

[9]
Gil Kalai.
Algebraic shifting.
In Computational commutative algebra and combinatorics (Osaka,
1999), volume 33 of Adv. Stud. Pure Math., pages 121–163. Math. Soc.
Japan, Tokyo, 2002.

[10]
S. Lavrenchenko.
Irreducible triangulations of the torus.
Journal of Soviet Mathematics, 51:2537–2543, 1990.

[11]
S. Lawrencenko and S. Negami.
Irreducible triangulations of the klein bottle.
J. Comb. Theory, Ser. B, 70:265–291, 1997.

[12]
Michel Lorea.
On matroidal families.
Discrete Mathematics, 28(1):103–106, 1979.

[13]
Eyal Lubetzky and Yuval Peled.
The Threshold for Stacked Triangulations.
International Mathematics Research Notices, 2022.

[14]
Satoshi Murai.
Algebraic shifting of cyclic polytopes and stacked polytopes.
Discrete Math., 307(14):1707–1721, 2007.

[15]
Eran Nevo.
Algebraic shifting and f-vector theory.
PhD thesis, arXiv preprint arXiv:0709.3265, 2007.

[16]
Ileana Streinu and Louis Theran.
Algorithms for area and volume rigidity.
In Proceedings of the 17th Fall Workshop on Computational
Geometry, 2007.

[17]
Ileana Streinu and Louis Theran.
Sparse hypergraphs and pebble game algorithms.
European J. Combin., 30(8):1944–1964, 2009.

[18]
Ileana Streinu and Louis Theran.
Natural realizations of sparsity matroids.
Ars Mathematica Contemporanea, 4(1):141–151, 2011.

[19]
T. Sulanke.
Note on the irreducible triangulations of the klein bottle.
J. Comb. Theory, Ser. B, 96:964–972, 2006.

[20]
Walter Whiteley.
La division de sommet dans les charpentes isostatiques.
Structural Topology, (16):23–30, 1990.
Dual French-English text.

[21]
Walter Whiteley.
Some matroids from discrete applied geometry.
In Matroid theory (Seattle, WA, 1995), volume 197 of Contemp. Math., pages 171–311. Amer. Math. Soc., Providence, RI, 1996.