Trung's Construction and the Charney-Davis Conjecture
Ashkan Nikseresht Mohammad Reza Oboudi







Trung's Construction and the Charney-Davis Conjecture
    Ashkan Nikseresht and Mohammad Reza Oboudi

Department of Mathematics, Shiraz University,

71457-13565, Shiraz, Iran

E-mail: ashkan_nikseresht@yahoo.com

E-mail: mr_oboudi@yahoo.com 
    
===========================================================================================================================================================================================





We consider a construction by which we obtain a simple graph (H,v) from a simple graph H and a non-isolated
vertex v of H. We call this construction “Trung's construction”. We prove that (H,v) is well-covered, W_2
or Gorenstein if and only if H is so. Also we present a formula for computing the independence polynomial of
(H,v) and investigate when (H,v) satisfies the Charney-Davis conjecture. As a consequence of our results, we
show that every Gorenstein planar graph with girth at least four, satisfies the Charney-Davis conjecture.


Keywords:  Gorenstein simplicial complex; Edge ideal; Trung's construction; Independence polynomial;

2010 Mathematical Subject Classification: 13F55, 05E40, 13H10, 05C31.


                                        

§ INTRODUCTION



Throughout this paper, K is a field, S=K[x_1,…, x_n] and G denotes a simple undirected graph with vertex set
(G)={v_1,…, v_n} and edge set (G). Recall that the edge ideal I(G) of G is the ideal of S
generated by {x_ix_j|v_iv_j∈(G)}. Many researchers have studied how algebraic properties of S/I(G) relates
to combinatorial properties of G (see <cit.> and references therein). Recall
that G is called a Gorenstein (resp, Cohen-Macaulay or CM for short) graph over K, if S/I(G) is a Gorenstein
(resp. CM) ring. When G is Gorenstein (resp. CM) over every field, we say that G is Gorenstein (resp. CM). Finding
combinatorial conditions on a graph equivalent to being Gorenstein has recently gained attention. For example, in
<cit.> a characterization of planar Gorenstein graphs of girth at least four is presented. Also in
<cit.> a condition on a planar graph equivalent to being Gorenstein is stated.

An importance of characterization of Gorenstein graphs comes from the Charney-Davis conjecture on the Euler
characteristic of certain manifolds (see <cit.> and <cit.>). This conjecture could be restated in
terms of independence polynomials of Gorenstein graphs (see char conj).

In this paper, first we recall some needed concepts and preliminary results. Then in Section 3, we show that planar
Gorenstein graphs with girth at least four satisfy the Charney-Davis conjecture. All Gorenstein graphs with girth four
are constructed using a recursive construction. We call a more general form of this recursive construction “Trung's
construction” and show that this construction preserves several properties related to independent sets such as being
well-covered, W_2 or Gorenstein. We also present a formula for computing the independence polynomial of graphs
constructed using Trung's construction and study when these graphs satisfy the Charney-Davis conjecture.

                                        

§ PRELIMINARIES



Recall that a simplicial complex Δ on the vertex set V={v_1,…, v_n} is a family of subsets of
V (called faces) with the property that {v_i}∈Δ for each i∈ [n]={1,…,n} and if A
B∈Δ, then A∈Δ. In the sequel, Δ always denotes simplicial complex. Thus the family
Δ(G) of all cliques of a graph G is a simplicial complex called the clique complex of G. Also
Δ(G̱) is called the independence complex of G, where G̱ denotes the complement of G. Note that
the elements of Δ(G̱) are independent sets of G. If Δ=Δ(G̱) for some graph G, then Δ
is called a flag complex. The ideal of S generated by {∏_v_i∈ F x_i|F V is a non-face of
Δ} is called the Stanley-Reisner ideal of Δ and is denoted by I_Δ and S/I_Δ is
called the Stanley-Reisner algebra of Δ over K. Therefore we have I_Δ(G̱)= I(G). Many
researchers have studied the relation between combinatorial properties of Δ and algebraic properties of
S/I_Δ, see for example <cit.> and their references.

By the dimension of a face F of Δ, we mean |F|-1 and the dimension of Δ is defined as
max{(F)|F∈Δ}. Let f_i be the number of i-dimensional faces of Δ (if Δ≠,
then f_-1=1), then (f_-1, …, f_d-1) is called the f-vector of Δ, where
d-1=(Δ). Now define h_i's such that h(t)= ∑_i=0^d h_it^i= ∑_i=0^d f_i-1t^i(1-t)^d-i. Then
h(t) is called the h-polynomial of Δ. It can be shown that the Hilbert series of S/I_Δ is
h(t)/(1-t)^ d (see <cit.>). Denote by α(G) the independence number of G, that
is, the maximum size of an independent set of G. Then the polynomial I(G,x)=∑_i=0^α(G) a_ix^i, where
a_i is the number of independent sets of size i in G, is called the independence polynomial of G. Note
that a_i=f_i-1 where (f_-1,…, f_α(G)-1) is the f-vector of Δ(G̱). There are many papers
related to this polynomial in the literature, see for example <cit.> and the references therein. It is easy to
check that the h-polynomial h(t) of Δ(G̱) is (1-t)^α(G) I(G,t/(1-t)).

A simplicial complex Δ is said to be Gorenstein* when S/I_Δ is Gorenstein when K= is the field
of rational numbers (for the definition of Gorenstein rings and other algebraic notions the reader is referred to
<cit.>) and there is no vertex v of Δ such that {v}∪ F∈Δ for every F∈Δ. Note
that if Δ=Δ(G̱), then Δ is Gorenstein* G is Gorenstein over  (that is S/I(G) is
Gorenstein when K=) and has no isolated vertex.

The Charney-Davis conjecture states that if Δ is a Gorenstein* flag complex of dimension 2e-1, then
(-1)^eh(-1) ≥ 0. In <cit.>, Richard P. Stanley mentioned this conjecture as one of the
“outstanding open problems in algebraic combinatorics” at the start of the 21st century. This conjecture was proved
in dimension 3 in <cit.> and Stanley in <cit.> showed that this conjecture holds for barycentric
subdivisions of shellable spheres. To see some other cases under which this conjecture is established, see <cit.>. The following is a “more graph theoretical” restatement of the Charney-Davis conjecture.

 
If G is a graph with no isolated vertices which is Gorenstein over  and α(G) is even, then

    (-1)^α(G)2 I(G,-12) ≥ 0.



Next we recall some properties of Gorenstein graphs. A graph G is called well-covered, if all maximal
independent sets of G have size α(G) and it is said to be a W_2 graph, if |(G)|≥ 2 and every
pair of disjoint independent sets of G are contained in two disjoint maximum independent sets. In some texts, W_2
graphs are called 1-well-covered graphs. The following lemma states the relation of Gorenstein graphs and W_2 graphs.

Every Gorenstein graph without isolated vertices is a W_2 graph.


Recall that if F∈Δ, then _Δ(F)={A F| F A∈Δ}. Suppose that F(G). By
[F] we mean F∪{v∈(G)| uv∈(G) for some u∈ F} and we set G_F=G[F]. We simply write
G_v instead of G_{v}.Thus if F is independent, then _Δ(G̱) F= Δ(G̱_̱F̱). Another
combinatorial property of a Gorenstein* graph G is that it has an Eulerian independence complex, that is, G
is well-covered and I(G_F,-1)=(-1)^α(G_F) for every independent set F of G (one can readily check that
this condition is equivalent to Δ(G̱) being an Euler complex as defined in <cit.>).



  *  A graph without isolated vertices is Gorenstein (over K) it has an Eulerian
    independence
    complex
    and
    is CM (over K).

  *  If G has an Eulerian independence complex and α(G) is odd, then I(G,-1/2)=0.



Part goren=>Euler is an especial case of <cit.>. For part Dehn, note that if
h(t) is the h-polynomial of Δ(G̱), then by the Dehn-Sommerville equation (<cit.>)
we have h(-1)=0. But h(-1)=2^α(G)I(G,-1/2) and the result follows.


Since every link of every CM simplicial complex is CM, one of the consequences of the above result is the following.

Suppose that G is a Gorenstein graph (over K), then for every non-maximal independent set F of G, the graph
G_F is also Gorenstein (over K).



                    

§ TRUNG'S CONSTRUCTION AND THE CHARNEY-DAVIS CONJECTURE



In <cit.> a method for constructing a W_2 graph from another W_2 graph is presented and it is shown that
all planar W_2 graphs with girth 4 are constructed by successively applying this method on a certain graph on 8
vertices. In <cit.>, it is proved that all such graphs are indeed Gorenstein. Recently Trung has
generalized this construction, see <cit.>, and showed that this generalized construction preserves the
Gorenstein property. We recall this generalized construction (see <cit.>).


Suppose that H is a graph and v is a non-isolated vertex of H. Let a, b and c be three new vertices. Join
c to b and to every neighbor of v; join b to a; and join a to v. We denote the obtained graph by
(H,v) and call this construction “Trung's construction”.


This construction is illustrated in <ref>. Here we show that many properties of the independence complex of a
graph, is preserved by Trung's construction.



Let H be a graph and v a non-isolated vertex of H. If G=(H,v), then


  *  α(G)=α(H)+1;

  *  G is Gorenstein (over K) H is Gorenstein (over K).



Tr Goren1 is clear. Tr Goren2: () <cit.>; ()  Noting that
H=G_b, this follows from G_F goren.



Let H be a graph and v a non-isolated vertex of H. Then G= (H,v) is well-covered H is so.


Let F be a maximal independent set of G. We show that there is a maximal independent set of H with |F|-1
vertices. Note that |F∩{a,b,c}| equals 1 or 2. In the latter case, F∩{a,b,c}={a,c} and (F∩(H))
∪{v} is a maximal independent set of H. Now suppose that F∩{a,b,c}={a}.  If F{a} is not a
maximal independent set of H, then {x}∪ F{a} is an independent set of H for some x∈(H). Since
F∪{x} is not independent in G, x is adjacent to a, that is, x=v. This means that N_H(v)∩ F=.
Thus F∪{c} is an independent set of G larger than F, a contradiction. Thus F{a} is a maximal
independent set of H. Similarly, in other cases that |F∩{a,b,c}|=1, one can conclude that F∩(H) is a
maximal independent set of H. Consequently, cardinality of each maximal independent sets of G is exactly one more
than the cardinality of some maximal independent set of H. Conversely each maximal independent set of H can be
extended to a maximal independent set of G with exactly one more vertex. From this the result follows.



The argument in the proof of Tr well shows that maximal independent sets of (H,v) are exactly the sets of
the form A∪{a}, A∪{b}, B∪{c}, B∪{b} or B∪{a,c}{v}, where A, B are maximal
independent sets of H with v∈ B A.



Let H be a graph and v a non-isolated vertex of H. Then G= (H,v) is W_2 H is so.


(): Suppose that A, B∈Δ(H̱) are disjoint. We have to find disjoint A', B'∈Δ(H̱) such that
|A'|=|B'|=α(H), A A' and B B'. As G is W_2, there are disjoint independent sets A”, B” of G
with size α(H)+1 such that A A” and B B”. If |A”∩(H)|= |B”∩(H)|= α(H), then we
are done. Thus according to the above remark, we can assume that b∈ B” and a,c∈ A”. So N_H(v)∩
A”=. If v∉ B”, then A'=A”∪{v}{a,c} and B'=B”{b} have the required properties.
Hence we assume that v∈ B”.

Set A”'=A”{c} and B”'= B”∪{c}{b}. Since G is W_2, we can extend A”' and B”' to
disjoint maximum size independent sets of G. Equivalently, there is a u∈(G) (B”'∪ A”') such that
A”'∪{u} is independent. Note that u≠ a,b,c and hence u∈(H) B”. Therefore, A'=A”∪{u}{a,c} and B'=B”{b} are disjoint maximum size independent sets of H containing A and B
respectively, as required.

(): Let A, B be disjoint independent sets of G. We must find disjoint maximum size independent sets A', B'
of G such that A A', B B'. We consider several cases:



    Case 1:
 c∉ A and v∈ B. Then A_0=A∩ H and B_0=B∩ H are disjoint independents
sets of H and we can extend them to disjoint maximal independent sets A'_0 and B'_0 of H, respectively. If
A∩{a,b} is nonempty, then let E=A∩{a,b} and if A∩{a,b}=, let E={a}. Now set
A'=A'_0∪ E. If b∈ B, let B'=B'_0∪{b}, else let B'=B'_0∪{c}. One can readily check that A'
and B' satisfy the required conditions.



    Case 2:
 c∈ A and v∈ B. Let A_0=A ∩ H_v and B_0=B∩ H_v. Note that by
<cit.>, H_v is W_2 with α(H_v)=α(H)-1. Suppose that A'_0 and B'_0 are disjoint
maximal independent extensions of A_0 and B_0 in H_v. Now A'=A'_0∪{c,a} and B'=B'_0∪{v,b} are
disjoint maximum size independent sets of G. Since c∈ A and v∈ B, we have A∩ N_H(v)= and B∩
N_H(v)=. Therefore, A∩ H=A_0 and B∩ H= B_0∪{v} and it follows that A A' and B B', as
required.

Note that if v∈ A, then by changing the names of A and B, case 1 or 2 occurs. So we can assume that
v∉ A∪ B.



    Case 3:
 v∉ A∪ B and a,c∈ A. Let A_0=(A ∩ H)∪{v} (A_0 is independent
because c∈ A and hence _H(v)∩ A=)  and B_0=B∩ H and extend them to disjoint maximum independent
sets A'_0 and B'_0 of H. Now A'=(A'_0{v}) ∪{a,c} and B'=B'_0 ∪{b} have the required
properties.



    Case 4:
 v∉ A∪ B, c∈ A and a∉ A. Let A_0=(A ∩ H)∪{v} and
B_0=B∩ H and extend them to disjoint maximum independent sets A'_0 and B'_0 of H. Set A'=A'_0∪{c}. If
b∈ B, set B'=B'_0 ∪{b} and if b∉ B set B'=B'_0∪{a}.



    Case 5:
 v,c∉ A∪ B and a∈ A. Let A_0=A ∩ H and B_0=B∩ H and extend them to
disjoint maximum independent sets A'_0 and B'_0 of H. Set B'=B'_0∪{b} and if v∈ A'_0, set A'=(A'_0{v})∪{a,c}, else set A'=A'_0∪{a}.



    Case 6:
 v,a,c∉ A∪ B and b∈ B.  Let A_0=A and B_0=B∩ H and extend them to
disjoint maximum independent sets A'_0 and B'_0 of H. Set B'=B'_0 ∪{b} and if v∈ A'_0, let
A'=A'_0∪{c} and if v∉ A'_0, set A'= A'_0∪{a}.



    Case 7:
 v,a,b,c∉ A∪ B. Let A'_0 and B'_0 be disjoint maximum size independent sets
of H containing A and B, respectively. Then v is not in at least one of A'_0 or B'_0, say v∉ A'_0.
Then A'=A'_0∪{a} and B'= B'_0∪{b} have the required properties.





In the next theorem we present a formula for computing the independence polynomial of (H,v) in terms of
independence polynomials of H and H_v.


Let H be a graph and v be a non-isolated vertex of H. Then

    I((H,v),x)=(2x+1)I(H,x)+(x+x^2)I(H_v,x).



Throughout the proof, F always denotes an independent set of G=(H,v) with |F|=i. We denote F∩{a,b,c} by
F_0. Also for any graph Γ by a_i(Γ) we mean the number of independent sets of Γ with cardinality
i. If i<0, we set a_i(Γ)=0. Note that F_0= F is an independent set of H with size i. Thus
there are a_i(H) such F's. Also F_0={a} F=F_1∪{a} for an independent set F_1 of H-v with
|F_1|=i-1. Thus there are a_i-1(H-v) choices of F with F_0={a}. Similarly, there are a_i-1(H)
 choices of F with F_0={b}.

Now assume that F_0={c}. If v∈ F, then F{v} is an independent set of H_v  with cardinality i-2
and  conversely by adding v and c to any such independent set of H_v, we get an F with F_0={c} and
v∈ F. Similarly, those F with F_0={c} and v∉ F correspond to the independent sets of H_v with
size i-1 (note that as c∈ F, we have N_H(v)∩ F=). Therefore, there are totally
a_i-1(H_v)+a_i-2(H_v) choices for F with F_0={c}.

Finally, if F_0={a,c}, then F∩_H[v]= and hence F∩ H H_v. Consequently, there is a
one-to-one correspondence between those F with F_0={a,c} and independent sets of H_v with size i-2. So
there are a_i-2(H_v) choices for F with F_0={a,c}.

Totally, we get that a_i(G)=a_i(H)+a_i-1(H-v)+a_i-1(H)+a_i-1(H_v)+2a_i-2(H_v). Note that
a_i-1(H-v)+a_i-2(H_v)= a_i-1(H), because a_i-1(H-v) is number of independent sets of H with
cardinality i-1 which do not contain v and a_i-2(H_v) is the number of independent sets of H with size
i-1 which contain v. We conclude that

    a_i(G)=a_i(H)+ 2a_i-1(H) +a_i-1(H_v)+a_i-2(H_v).

Multiplying by x^i and taking summation over i=0, …, α(G) we get the desired equation.



Let H be a graph without isolated vertices which is Gorenstein over  such that α(H) is odd and assume that
v ∈(H). Then G=(H,v) satisfies the Charney-Davis conjecture H_v does so.


According to Tr-ind poly, I(G,-1/2)= (-1/4)I(H_v,-1/2). Noting that α(H_v)=α(G)-2, we conclude
that (-1)^α(G)/2I(G,-1/2)≥ 0 (-1)^α(H_v)/2I(H_v,-1/2)≥ 0, as claimed.


Recall that the Stanley-Reisner algebra of the disjoint union of two graphs is isomorphic to the tensor product of the
Stanley-Reisner algebras of the two graphs. Hence a graph is Gorenstein over K all of its connected components
are Gorenstein over K.

Suppose that G is a planar Gorenstein graph without isolated vertices, girth(G)≥ 4 and α(G) is even.
Then the Charney-Davis conjecture holds for G.


We prove the statement by induction on |(G)|. If G is not connected, say G is a disjoint union of G_1 and
G_2, then both G_1 and G_2 are Gorenstein graphs without isolated vertices. If α(G_1) and α(G_2)
are odd, then according to Euler, I(G_i,-1/2)=0 for both i's and if α(G_1) and α(G_2) are
even, then by the induction hypothesis, (-1)^α(G_i)/2 I(G_i,-1/2)≥ 0 for both i=1,2. Therefore the result
follows from the fact that I(G,x)=I(G_1,x)I(G_2,x) (see for example <cit.>).

Thus we assume that G is connected. If G has girth ≥ 5, then as G is W_2 and by <cit.>,
G ≅ K_2 or G ≅ C_5, both of which satisfy the Charney-Davis conjecture. So we can suppose that
girth(G)=4. Then according to <cit.>, G is constructed by several application of Trung's
construction on C_5, where in each application the chosen vertex should be a vertex of degree 2. Thus we can assume
that G=(H,v), for a planar graph H of girth at least 4 which does not have any isolated vertex and _H(v)=2.
Clearly H_v is planar and has girth at least 4. Also it is Gorenstein by G_F goren. If H_v has an isolated
vertex, say y, then in H, y is adjacent to both neighbors of v (else _H(y)=1, which contradicts
W2). Consequently, {y,v}∪ N_H(v) is a 4-cycle in H. But this is against <cit.>,
which says that every vertex on a 4-cycle in a W_2 graph has degree at least 3. Hence H_v has no isolated vertex
and the Charney-Davis conjecture holds for H_v by the induction hypothesis. Now the result follows from Tr
charney.





                                             99





welker F. Brenti and V. Welker, f-vectors of barycentric subdivisions, Math. Z. 259,
    849–865, 2008.




CM ring W. Bruns and Jürgen Herzog, Cohen-Macaulay Rings, Cambridge University Press,
    Cambridge, 1993.

charney R. Charney and M. Davis, Euler characteristic of a nonpositively curved, piecewise Euclidean
    manifold, Pac. J. Math. 171, 117–137, 1995.






davis M. Davis and B. Okun, Vanishing theorems and conjectures for the l^2-homology of
    right-angled Coxeter groups, Geom. Topol. 5, 7–74, 2001.

froh A. Frohmader, The Charney-Davis conjecture for certain subdivisions of spheres, preprint,
    arXiv:0806.4213,
    2008.




hibi J. Herzog  and T. Hibi, Monomial Ideals, Springer-Verlag, London , 2011.

large girth D. T. Hoang, N. C. Minh and T. N. Trung, Cohen-Macaulay graphs with large girth, J.
    Algebra
    Appl.
    14:7,
    paper No. 1550112, 2015.




survey V.E. Levit and E. Mandrescu, The independence polynomial of a graph — a survey,
    Proceedings  of the 1st International Conference on Algebraic Informatics, 233–254,
    Aristotle Univ. Thessaloniki, Thessaloniki, 2005.

my vdec A. Nikseresht, Chordality of clutters with vertex decomposable dual and ascent of clutters,
    J. Combin. Theory —Ser. A, accepted for publication,  arXiv: 1708.07372.

our chordal A. Nikseresht and R. Zaare-Nahandi, On generalization of cycles and chordality to clutters from
    an algebraic viewpoint, Algebra Colloq. 24:4, 611–624,  2017.

pinter1 M. R. Pinter, A class of planar well-covered graphs with girth four, J. Graph Theory
    19:1, 69–81, 1995.

pinter2 —, A class of well-covered graphs with girth four, Ars Combin. 45, 241–255,
    1997.




stanley R. P. Stanley, Combinatorics and Commutative Algebra, Birkhäuser, Boston, 1996.

stanley CD —, Flag f-vectors and the cd-index, Math. Z. 216, 483–499, 1994.

frontier —, Positivity problems and conjectures in algebraic combinatorics, in: V. Arnold,
    et al (Eds.), Mathematics: Frontiers and Prospectives, American Mathematical Society, pp. 295–320, 2000.




planar goren T. N. Trung, A characterization of Gorenstein planar graphs, in T. Hibi, ed., Adv. Stud.
    Pure Math., Vol. 77: The 50th Anniversary of Gröbner Bases, 399–409, 2018, arXiv:1603.00326v2.









