On Face Numbers of Flag Simplicial Complexes

Abstract

Denham and Suciu (Pure Appl Math Q 3(1):25–60, 2007) and Panov and Ray (in: Harada, et al. (eds) Toric topology. Contemporary Mathematics, American Mathematical Society, Providence, 2008) computed the ranks of homotopy groups and the Poincaré series of a moment-angle-complex $\mathcal Z(\mathcal K$)/Davis–Januszkiewicz space $DJ(\mathcal K)$ associated to a flag simplicial complex $\mathcal K.$ In this note we revisit these results and interpret them as polynomial bounds on the face numbers of an arbitrary simplicial flag complex.

1 Introduction

Let $\mathcal K$ be an n-dimensional simplicial complex. Denote by $f_i$ the number of i-dimensional simplices of $\mathcal K.$ Characterization of possible f-vectors $(f_0,\ldots ,f_n)$ of various classes of simplicial complexes is a classical problem of enumerative combinatorics. We mention several results in this direction:

• (1) The Kruskal–Katona theorem [11, II.1], describing all possible f-vectors of general simplicial complexes.

• (2) Analogue of the Kruskal–Katona theorem for Cohen–Macaulay simplicial complexes [11, II.2].

• (3) The upper bound theorem due to McMullen [11, II.3.4], which gives necessary conditions for a tuple of integers to be the f-vector of a triangulation of an n-dimensional sphere.

• (4) g-Theorem, characterizing the f-vectors of simplicial polytopes, see [11, II.6.2].

The proofs of these results led to numerous constructions, associating certain algebraic and topological objects to combinatorial objects (simplicial complexes, triangulations of spheres, polytopes, etc.). These constructions allow to employ methods of homological algebra, algebraic geometry and algebraic topology in purely combinatorial problems.

In a similar spirit, in this note we derive a series of inequalities on the f-vectors of flag simplicial complexes. The characterization of the f-vectors of flag simplicial complexes, or, equivalently clique vectors of simple graphs, is a well-studied problem with many partial results. In [12] Zykov gave a generalization of the classical Turán’s theorem for graphs. Razborov [10] proved asymptotic bounds on the component $f_2$ in terms of $f_1$ and $f_0.$ Herzog et al. [7] gave a complete characterization of all the possible f-vectors of chordal flag simplicial complexes. Goodarzi [6] generalized this result for k-connected chordal simplicial complexes.

Our article is built upon the results of Denham and Suciu [3] and Panov and Ray [9], where the authors relate the Poincaré series of a face ring of a flag simplicial complex to the Poincaré series of a free graded algebra. Let $p_n(x_1,\,x_2,\ldots )$ and $e_n(x_1,\,x_2,\ldots )$ be the degree n Newton (power-sum) and elementary symmetric polynomials, respectively (see [8, I.2]). Slightly abusing notation, we denote the unique representation of $p_n$ as a polynomial in $\underline{e}:=\{e_1,\,e_2,\ldots \}$ by $p_n(\underline{e}):=p_n(e_1,\,e_2,\ldots ).$ The main result can be formulated as follows.

Theorem 1.1

Let $\mathcal K$ be a flag simplicial complex with the f-vector $(f_0,\ldots ,f_n).$ Then for any $N\geqslant 1$ we have

$$\begin{aligned} (-1)^{N}\sum _{d|N}\mu (N/d) (-1)^d p_d(\underline{\alpha })\geqslant 0, \end{aligned}$$

(1)

where

$$\begin{aligned} \alpha _n:=\sum _{i=0}^{n-1} f_i\left( {\begin{array}{c}n-1\\ i\end{array}}\right) , \end{aligned}$$

and $\mu (n)$ is the Möbius function

$$\begin{aligned} \mu (n)= \left\{ \begin{array}{ll} (-1)^k, &{} \text{ if } n \, \text{ is } \text{ a } \text{ product } \text{ of } k \text{ distinct } \text{ prime } \text{ factors };\\ 0, &{} \text{ otherwise }, \end{array}\right. \end{aligned}$$

and the summation is taken over all positive integers d dividing N.

The rest of the paper is organized as follows. In Sect. 2 we recall standard lower bounds on the dimensions of the graded components of a graded free algebra. In Sect. 3 we discuss basic notions of the toric topology and recall the results of Denham–Suciu and Panov–Ray. Finally, in Sect. 4 we prove our main result, Theorem 4.1.

2 Free Graded Algebras

Throughout this paper we work with algebras over a field k of characteristic zero, which are

• (1) (graded) $A=\sum ^\infty _{i=0} A^i$ with $A^i\cdot A^j\subset A^{i+j};$

• (2) (locally finite dimensional) $\dim _k A^i<\infty ;$

• (3) (commutative) $a \cdot b=(-1)^{ij}\,b \cdot a$ for $a\in A^i,$ $b\in A^j;$

• (4) (connected) $A^0=\langle \mathbf 1\rangle _k.$

The aim of this section is to derive certain identities involving the dimensions of the graded components of a free graded algebra $A^\bullet .$ In different contexts similar identities appeared, e.g., in [1, Chap. 3], see also references therein. As a corollary of these identities we get lower bounds on $\dim A^N,\, N\in \mathbb N.$

Definition 2.1

Let $V^\bullet =\sum _{i\geqslant 1} V^i$ be a graded vector space over a ground field k. Assume that $\dim _k V^i<\infty$ for $i\geqslant 1.$ A free graded commutative algebra generated by V is the algebra

$$\begin{aligned} S^\bullet (V):=\bigotimes _{i=2k} \mathrm{Sym}^\bullet (V^i)\otimes \bigotimes _{i=2k+1}\Lambda ^\bullet (V^i), \end{aligned}$$

where $\hbox {Sym}^\bullet (V^{2k})$ and $\Lambda ^\bullet (V^{2k+1})$ are the symmetric and the exterior graded algebras generated by $V^{2k}$ and $V^{2k+1},$ respectively.

Definition 2.2

For a graded vector space $V^\bullet =\sum _{i\geqslant 0} V^i,$ the Poincaré series of $V^\bullet$ is a formal power series

$$\begin{aligned} h\left( V^\bullet ;\,t\right) :=\sum _{i} \dim _k V^i t^i. \end{aligned}$$

For a graded algebra $A^\bullet ,$ its Poincaré series $h(A^\bullet ;\,t)$ is the Poincaré series of the underlying graded vector space.

Proposition 2.3

Let $V^{\bullet }=\sum _{i\geqslant 1} V^i$ be a graded vector space. Let $h(V^\bullet ;\,t)=v_1t+v_2t^2+\cdots$ be the Poincaré series of $V^\bullet .$ Then, for the free graded algebra generated by V,  one has:

$$\begin{aligned} h\left( S^\bullet (V);\,t\right)&=\prod _{i=2k}\big (1-t^{2k}\big )^{-v_{2k}}\prod _{i=2k+1}\big (1+t^{2k+1}\big )^{v_{2k+1}} \nonumber \\&= \prod _{i}\big (1-(-t)^i\big )^{(-1)^{i+1}v_i}. \end{aligned}$$

(2)

Proof

For a one-dimensional $V^\bullet =V^{2k}$ the corresponding free algebra $S^\bullet (V^{2k})$ is a polynomial algebra with one generator in degree 2k,  hence

$$\begin{aligned} h\big (S\big (V^{2k}\big );\,t\big )=1+t^{2k}+t^{4k}+\cdots =\frac{1}{1-t^{2k}}. \end{aligned}$$

Similarly for a one-dimensional $V^{2k+1}$

$$\begin{aligned} h\big (S\big (V^{2k+1}\big );\,t\big )=1+t^{2k+1}. \end{aligned}$$

These identities together with the multiplicativity of $h(\cdot ;\,t)$ with respect to the tensor product imply formula (2). $\square$

Let $\underline{s}=\{s_1,\,s_2,\ldots \}$ be an arbitrary sequence of indeterminates. Fix some integer $N>1$ and introduce new variables $\gamma _1,\ldots ,\gamma _N$ such that $s_i=e_i(\gamma _1,\ldots ,\gamma _N),\, i\leqslant N$, is the elementary symmetric polynomial in $\{\gamma _k\}_{k=1}^N.$ We denote the unique presentation of the ith Newton polynomial $\gamma _1^i+\cdots +\gamma _N^i$ as a polynomial in $\{s_1,\ldots ,s_N\}$ by $p_i(\underline{s}).$ It is easy to check that for a fixed i this presentation does not depend on the choice of $N>i.$ The first few polynomials $p_i(\underline{s})$ are:

$$\begin{aligned} \begin{aligned} p_1(\underline{s})&= s_1,\\ p_2(\underline{s})&= s_1^2 - 2s_2,\\ p_3(\underline{s})&= s_1^3 - 3s_2s_1 + 3s_3,\\ p_4(\underline{s})&= s_1^4 - 4s_2s_1^2+4s_3s_1+2s_2^2-4s_4.\\ \end{aligned} \end{aligned}$$

If we assign gradings $\deg s_i=i,$ then $p_i(\underline{s})$ is a homogeneous polynomial of degree i. We also point out that in $p_i(\underline{s})$ the coefficient at $s_i$ equals $(-1)^{i+1}i.$

The following proposition gives a converse of Proposition 2.3.

Proposition 2.4

Let $V^{\bullet }=\sum _{i\geqslant 1} V^i$ be a graded vector space. Let $h(S^\bullet (V);\, t)=1+s_1 t+ s_2 t^2+\cdots$ be the Poincaré series of the corresponding free algebra. Then the dimensions of graded components of $V^\bullet$ are given by the formulas:

$$\begin{aligned} \dim _k V^N=\frac{(-1)^{N+1}}{N}\sum _{d|N}\mu (N/d) p_d(\underline{s}), \end{aligned}$$

(3)

where the summation is taken over all positive integers d dividing N.

Proof

Taking the logarithm of the identity (2) we get

$$\begin{aligned} \log \big (1+s_1t+s_2t^2+\cdots \big )=\sum _i (-1)^{i+1}v_i\log \big (1-(-t)^i\big ). \end{aligned}$$

(4)

Now let us fix any integer N and formally expand

$$\begin{aligned} 1+s_1t+\cdots +s_Nt^N=\prod _{i=1}^N\left( 1+\gamma _i t\right) , \end{aligned}$$

where $\{\gamma _i\}$ are new variables. Then in $k[s_1,\ldots ,s_N][[t]]/t^{N+1}\subset k[\gamma _1,\ldots ,\gamma _N][[t]]/t^{N+1}$ we have

$$\begin{aligned} \log \big (1+s_1t+s_2t^2+\cdots \big )=\sum ^N_{i=1}\log \left( 1+\gamma _it\right) =\sum _{i=1}^N (-1)^{i+1}\,\frac{p_i(\underline{s})}{i}\,t^i. \end{aligned}$$

Taking the limit $N\rightarrow \infty ,$ we obtain in $k[s_1,\,s_2,\ldots ][[t]]$ the following identity:

$$\begin{aligned} \log \big (1+s_1t+s_2t^2+\cdots \big )=\sum _N (-1)^{N+1}\,\frac{p_N(\underline{s})}{N}\,t^N. \end{aligned}$$

After expanding the power series $\log (1-(-t)^i)$ in the RHS of (4), and comparing the coefficients of $t^N,$ we conclude that

$$\begin{aligned} \sum _{i|N} (-1)^i iv_i=-\,p_N(\underline{s}). \end{aligned}$$

Finally, with the use of the Möbius inversion formula we get

$$\begin{aligned} v_N=\frac{(-1)^{N+1}}{N}\sum _{d|N}\mu (N/d) p_d(\underline{s}), \end{aligned}$$

as stated. $\square$

Proposition 2.4 gives a necessary condition for a sequence of integers $\{1,\,s_1,\,s_2,\ldots \}$ to be the dimensions of the graded components of a free graded algebra $S^\bullet (V).$

Corollary 2.5

If $1+s_1t+s_2t^2+\cdots$ is the Poincaré series of a free graded algebra $S^\bullet (V),$ then for any integer $N\geqslant 1$ the sequence $\underline{s}=\{s_1,\,s_2,\ldots \}$ satisfies

$$\begin{aligned} (-1)^{N+1}\sum _{d|N}\mu (N/d) p_d(\underline{s})\geqslant 0. \end{aligned}$$

(5)

Example 2.6

For small values of N Corollary 2.5 gives

$$\begin{aligned} (N=1) \, s_1\,\geqslant & {} 0;\\ (N=1)\, s_2\,\geqslant & {} \frac{1}{2}s_1\left( s_1-1\right) ;\\ (N=1)\, s_3\,\geqslant & {} \frac{1}{3}s_1\big (3s_2-s_1^2+1\big ). \end{aligned}$$

More generally, for any N inequality (5) is equivalent to a lower bound on $s_N$ of the form

$$\begin{aligned} s_N\geqslant q_N\left( s_1,\ldots ,s_{N-1}\right) , \end{aligned}$$

where $q_N$ is some polynomial of degree N,  with $\deg s_i=i.$

3 Toric Topology

We begin this section by recalling the basic combinatorial notions of simplicial complexes, f-vectors and flag simplicial complexes.

Definition 3.1

An abstract simplicial complex $\mathcal K$ on the set of vertices $[m]=\{1,\ldots ,m\}$ is a collection $\mathcal K=\{\sigma \}$ of subsets of [m] such that for any $\sigma \in \mathcal K$ all subsets of $\sigma$ also belong to $\mathcal K.$ Elements $\sigma \in \mathcal K$ are called simplices of $\mathcal K.$ The dimension of a simplex $\sigma \in \mathcal K$ is $|\sigma |-1.$ We also assume that all one-element sets belong to $\mathcal K,$ i.e., there are no ‘ghost vertices’.

For an n-dimensional simplicial complex $\mathcal K,$ let $f_i$ be the number of its i-dimensional simplices. Then the f-vector of $\mathcal K$ is $(f_0,\ldots ,f_n).$

Definition 3.2

Let $\mathcal K$ be a simplicial complex on the set of vertices [m]. A subset $\sigma \subset [m]$ is a minimal non-face of $\mathcal K$ if $\sigma \not \in \mathcal K,$ but all proper subsets $\sigma '\subsetneq \sigma$ are simplices of $\mathcal K: \sigma '\in \mathcal K.$

Simplicial complex $\mathcal K$ is flag if all its minimal non-faces are two-element subsets of [m]. Clearly, any flag simplicial complex is determined by its 1-skeleton.

Now we describe a construction originating from toric topology [2]. This construction associates a topological space $(X,\,A)^\mathcal K$ to a simplicial complex $\mathcal K$ and a pair of topological spaces $(X,\,A).$ The main idea is that the ‘topology’ of $(X,\,A)^\mathcal K$ somehow captures the ‘combinatorics’ of $\mathcal K.$

Definition 3.3

(Polyhedral product) Let $\mathcal K$ be an abstract simplicial complex on the set of vertices [m]. Let $(X,\, A)$ be a pair of topological spaces. The polyhedral product associated to $\mathcal K$ is a topological space $(X,\,A)^\mathcal K\subset X^m$ defined as follows. For any subset $\sigma \subset [m]$ let us denote a ‘building block’ inside $X^m$:

$$\begin{aligned} (X,\,A)^\sigma :=\prod _{i\in \sigma } X\times \prod _{i\not \in \sigma } A\subset X^m. \end{aligned}$$

Then by definition $(X,\,A)^\mathcal K$ is the union of the building blocks $(X,\,A)^\sigma ,$ where $\sigma$ runs over simplices of $\mathcal K$:

$$\begin{aligned} (X,\,A)^\mathcal K:=\bigcup _{\sigma \in \mathcal K}(X,\,A)^\sigma . \end{aligned}$$

Example 3.4

Let us consider a pair $(D^2,\,S^1),$ where $D^2$ is the unit disc and $S^1$ is its boundary. The corresponding polyhedral product is called the moment-angle-complex and is denoted by

$$\begin{aligned} Z(\mathcal K):=\big (D^2,\,S^1\big )^\mathcal K. \end{aligned}$$

Starting with the pair $(\mathbb {C}P^\infty ,\, pt),$ we get the Davis–Januszkiewicz space

$$\begin{aligned} DJ(\mathcal K)=\left( \mathbb {C}P^\infty ,\, pt\right) ^\mathcal K. \end{aligned}$$

It is known (see [2, Theorem 4.3.2]) that the moment-angle-complex $Z(\mathcal K)$ is a homotopy fibre of the inclusion $DJ(\mathcal K)\rightarrow (\mathbb {C}P^\infty )^m.$ In particular, the higher homotopy groups of $Z(\mathcal K)$ and $DJ(\mathcal K)$ coincide:

$$\begin{aligned} \pi _i(Z(\mathcal K))\simeq \pi _i(DJ(\mathcal K)),\quad i\geqslant 3. \end{aligned}$$

Remark 3.5

The crucial property of Davis–Januszkiewicz spaces is that for any simplicial complex $\mathcal K,$ the cohomology ring of $DJ(\mathcal K)$ is the face ring:

$$\begin{aligned} H^*(DJ(\mathcal K);\, k)\simeq k[\mathcal K]:=k\left[ v_1,\ldots ,v_m\right] /\mathcal I_{SR}(\mathcal K),\quad \deg v_i=2, \end{aligned}$$

where $\mathcal I_{SR}$ is the ideal generated by the monomials corresponding to all non-simplices of $\mathcal K$:

$$\begin{aligned} \mathcal I_{SR}=\left\{ v_{i_1},\ldots , v_{i_k}\mid \sigma =\left\{ i_1,\ldots ,i_k\right\} \not \in \mathcal K\right\} . \end{aligned}$$

The following result is due to Panov and Ray.

Proposition 3.6

[9, Proposition 9.5] For any flag simplicial complex $\mathcal K,$ we have

$$\begin{aligned} h(H^\bullet (\Omega DJ(\mathcal K);\, \mathbb Q);\, t)= & {} h\big (\mathbb Q[\mathcal K],\, (-t)^{1/2}\big )^{-1}\nonumber \\ {}= & {} \Biggl (1+ \sum _{i=0}^{\dim \mathcal K} (-1)^{i+1}\,f_i\,\frac{t^{i+1}}{(1+t)^{i+1}} \Biggr )^{-1}. \end{aligned}$$

Let X be an arbitrary simply connected pointed CW-complex. Its loop space $\Omega X$ is an H-space, hence its rational cohomology is a Hopf algebra. At the same time, any Hopf algebra over a field of characteristic zero is a free graded algebra, see [4]:

$$\begin{aligned} H^\bullet (\Omega X,\,\mathbb Q)\simeq S^\bullet (V), \end{aligned}$$

where $V=V^\bullet$ is a graded vector space spanned by primitive elements in the Hopf algebra $H^\bullet (\Omega X,\,\mathbb Q).$ Alternatively, $V^\bullet$ could by described as the dual to $\pi _\bullet (\Omega X)\simeq \pi _{\bullet }(X)[-1],$ where $[-1]$ stands for the grading shift, see, e.g., [5]. This observation together with the remark in Example 3.4 explains that the following slightly reformulated result due to Denham and Suciu contains essentially the same information as Proposition 3.6:

Theorem 3.7

[3, Theorem 4.2.1] Let $\mathcal K$ be a flag complex with the face ring $k[\mathcal K].$ Then the ranks $\pi _i=\pi _i(Z(\mathcal K))$ of the homotopy groups of the moment-angle complex $Z(\mathcal K)$ are given by

$$\begin{aligned} \prod _{r=1}^\infty \frac{ (1+t^{2r-1})^{\pi _{2r}} }{ (1-t^{2r})^{\pi _{2r+1}} } = h\big (\mathrm{Tor}(\mathbb Q[\mathcal K],\, \mathbb Q),\, (-t)^{1/2},\, -(-t)^{1/2}\big )^{-1}, \end{aligned}$$

where $h(A^\bullet ,\, t_1,\, t_2)$ is the bigraded Poincaré series of $\mathrm Tor$-algebra.

4 Proof of the Main Result

Now we are ready to prove our main result:

Theorem 4.1

Let $\mathcal K$ be a flag complex with the f-vector $(f_0,\ldots ,f_n).$ Then the coefficients of the power series $\big (1+ \sum _{i=0}^{\dim \mathcal K} (-1)^{i+1}f_i\,\frac{t^{i+1}}{(1+t)^{i+1}}\big )^{-1}$ satisfy inequalities (5). Specifically, for any $N\geqslant 1$ we have

$$\begin{aligned} (-1)^{N}\sum _{d|N}\mu (N/d) (-1)^d p_d(\underline{\alpha })\geqslant 0, \end{aligned}$$

(6)

where $p_d$ is the dth Newton polynomial expressed in the elementary symmetric polynomials $\underline{\alpha }=(\alpha _1,\,\alpha _2,\ldots )$ with

$$\begin{aligned} \alpha _n:=\sum _{i=0}^{n-1} f_i\left( {\begin{array}{c}n-1\\ i\end{array}}\right) . \end{aligned}$$

Proof

The fact that the coefficients of a power series $Q(t):=\big (1+ \sum _{i=0}^{\dim \mathcal K} (-1)^{i+1}f_i\,\frac{t^{i+1}}{(1+t)^{i+1}} \big )^{-1}$ satisfy inequalities (5) immediately follows from the fact that this power series is the Poincaré series of a free graded algebra $H^*(\Omega DJ(\mathcal K),\,\mathbb Q)$ and from Corollary 2.5.

To find the explicit form of these inequalities we follow the proof of Proposition 2.4 with slight modifications. Namely, we first rewrite Q(t) as follows

$$\begin{aligned} Q(t)=\left( \sum _{n=0}^\infty \sum _{j=0}^{n-1} f_j\left( {\begin{array}{c}n-1\\ j\end{array}}\right) (-t)^n\right) ^{-1}. \end{aligned}$$

Now we take logarithm of the identity

$$\begin{aligned} Q(t)=\prod _{r=1}^\infty \frac{ (1+t^{2r-1})^{v_{2r}} }{ (1-t^{2r})^{v_{2r+1}} }, \end{aligned}$$

and comparing coefficients at $t^N$ as in the proof of Proposition 2.4 we find that

$$\begin{aligned} \sum _{i|N}(-1)^iiv_i=-p_N\left( \underline{\left\{ (-1)^k\alpha _k\right\} }^\infty _{k=1}\right) =(-1)^{N+1} p_N(\underline{\alpha }). \end{aligned}$$

Applying again the Möbius inversion formula we get the identity

$$\begin{aligned} v_N=\frac{(-1)^N}{N}\sum _{d|N}\mu (N/d) (-1)^d p_d(\underline{\alpha }), \end{aligned}$$

which implies the stated inequality. $\square$

Example 4.2

For small values of N Theorem 4.1 gives:

($N=1$) Inequality (6) reads $p_1\geqslant 0.$ Plugging in $p_1=f_0,$ we get

$$\begin{aligned} f_0\geqslant 0. \end{aligned}$$

($N=2$) Inequality (6) reads $p_2+p_1\geqslant 0.$ Plugging in $p_2=\alpha _1^2-2\alpha _2$ with $\alpha _1=f_0,\, \alpha _2=f_0+f_1,$ we get

$$\begin{aligned} f_1\leqslant \left( {\begin{array}{c}f_0\\ 2\end{array}}\right) . \end{aligned}$$

($N=3$) Inequality (6) reads $p_3-p_1\geqslant 0.$ With $p_3=\alpha _1^3-3\alpha _1\alpha _2+3\alpha _3,\, \alpha _1=f_0,\, \alpha _2=f_0+f_1,\, \alpha _3=f_0+2f_1+f_2$ we arrive at

$$\begin{aligned} f_0^3-3f_0\left( f_0+f_1\right) +3f_2-f_0\geqslant 0, \end{aligned}$$

or, equivalently,

$$\begin{aligned} f_2\geqslant \left( {\begin{array}{c}f_0\\ 3\end{array}}\right) -\bigg (f_0-2\bigg )\bigg (\left( {\begin{array}{c}f_0\\ 2\end{array}}\right) -f_1\bigg ). \end{aligned}$$

The first two inequalities are trivially satisfied for any simplicial complex and simply indicate that the number of vertices is non-negative and the number of edges is bounded above by $\left( {\begin{array}{c}f_0\\ 2\end{array}}\right) .$

The third inequality is not satisfied for a general simplicial complex. It says that for a flag simplicial complex the number of non-triangles is less or equal than the number of non-edges times $(f_0-2).$ Indeed, each non-triangle contains at least one non-edge, while every non-edge is a side of $f_0-2$ non-triangles.

Remark 4.3

For a general N inequality (6) has the form

$$\begin{aligned} (-1)^Nf_N\geqslant q_N\left( f_1,\ldots , f_{N-1}\right) , \end{aligned}$$

where $q_N$ is a polynomial of degree N with $\deg f_i=i+1.$

It is interesting if inequalities (6) have a simple combinatorial interpretation:

Question

Does there exist a direct combinatorial proof of inequalities (6) for all N?