Ali Akbar YAZDAN POUR
Assistant Prof. of Mathematics

Welcome to my homepage

Institute for Advanced Studies in Basic Sciences (IASBS), Prof. Yousef Sobouti Blvd., P. O. Box 45195-1159 Zanjan 45137-66731 Iran.
Fax: (+98) 24 3315 5142. Tel: (+98) 24 3315 5047.

Chordal graphs are probably one of the most important objects in combinatorial commutative algebra. The
algebraic importance of chordal graphs is twofolds. First, the independence complex of a chordal graph is shellable
[5, Theorem 2.13] (even more, vertex decomposable [6, Corollary 5.5]) and hence the Stanley-Reisner ring of these
complexes are sequentially Cohen-Macaulay. Second, chordal graphs lead to a beautiful classification of square-
free monomial ideals with 2-linear resolution. Indeed, thanks to Fröberg, we know that a square-free monomial ideal
I has a 2-linear resolution if and only if I is the edge ideal of a non-trivial graph G, such that the complement of G is a
chordal graph. It turns out that, by using Alexander duality, the algebraic mechanism behind chordal graphs is quite
rich. For example the following theorem explains the power of chordal graphs in combinatorial commutative algebra.

Theorem ([2, Theorems 8.1.9 and 9.2.12]). Given a finite incomplete graph G with vertex set [n] = {1, ...,
n}, let Δ := Δ(G) be the clique complex of G. The following conditions are equivalent:
(i) G is chordal;
(ii) IΔ has a 2-linear resolution;
(iii) reg (IΔ) = 2;
(iv) the Stanley-Reisner ring of Δ˅ is Cohen-Macaulay;
(v) Δ is a quasi-forest;
(vi) G is the 1-skeleton of a quasi-forest;
(vii) G has a perfect elimination ordering;
(viii) Δ˅ is vertex decomposable.

One of the aspects of chordal graphs that makes it interesting, is perhaps that they may be described in different
equivalent ways. Several mathematicians have generalized the definition of chordal graphs, to chordal hypergraphs
based on particular definition. Since such generalizations may be made in many different directions, no particular
standard concerning the use of the word "chordal hypergraph" has been established. In [3], it is introduced a class
of hypergraphs Cd, called chordal, that extends graph theoretical definition of chordal graphs in the case d = 2 and
inherits the same algebraic properties of graphs. This class is of great importance, because it has been shown that,
this class contains other famous classes that have been introduced till now [1]. A short note concerning required
definition of chordal clutters can be found here.

The importance of the class of chordal clutter is that the circuit ideal to every member of this class has a d-linear
resolution over any field. However, it is almost impossible for computer algebra systems like CoCoA, Singular,
Macaulay, etc. to check whether a given ideal has a linear resolution over any field. But as mentioned above, a
sufficient condition for an ideal to have a linear resolution over any field, is to show that the ideal comes from a
chordal clutter.

Given a square-free monomial ideal I in the polynomial ring with n indeterminate and generated in degree d. In the
following, we explain a method to check that whether I has a d-linear resolution over any field.
1. Construct a d-uniform clutter C with circuits Fi, where Fi is a subset of {1, ..., n} with |Fi|=d and xFi does not
belong to I.

2. Apply this program to check if C is chordal. (See the manual for using this program)

3. If C is chordal, then the ideal I has a d-linear resolution over any field.

In step 3, if the clutter C is not chordal, we can not deduce that, I does not have d-linear resolution over any field.
However, at the moment, we do not know any example of a square-free monomial ideal, which has a linear
resolution over any field, but its associated clutter is not chordal (see  [1, Question 1]).
C++ Program for detecting chordality

Some Examples
In this part, we apply the program ChordalityCheck.cpp to check the chordality of some strange examples whose associated ideal has a linear resolution over any field. The source code of this program has been written by Iman Kiarazm.

References
1.
M. Bigdeli, A. A. Yazdan Pour and R. Zaare-Nahandi, Stability of Betti Numbers under Reduction Processes: Toward Chordality of Clutters, preprint, (2015).
2.
J. Herzog, and T. Hibi, Monomial Ideals, in: GTM 260, Springer, London, (2011).

3.
M. Morales, A. Nasrollah Nejad, A. A. Yazdan Pour and R. Zaare-Nahandi, Monomial ideals with 3-linear resolutions, Annales de la Faculté des Sciences de Toulouse, Sér. 6, 23: (4), pp 877-891, (2014).
4.
M. Morales, A. A. Yazdan Pour and R. Zaare-Nahandi, The regularity of edge ideals of graphs, J. Pure and Applied Algebra, vol. 216, issue 12, pp. 2714-2719, (2012).

5.
A. Van Tuyl and R. H. Villarreal, Shellable graphs and sequentially Cohen-Macaulay bipartite graphs. J. Combin. Theory Ser. A, 115(5): pp 799-814, (2008).
6.
R.Woodroofe, Chordal and sequentially Cohen-Macaulay clutters, Electron. J. Combin. 18, no. 1, Paper 208, 20 pages, (2011).