Edge ideals of Cameron-Walker graphs

Edge ideals of Cameron-Walker graphs

Augustine O'Keefe (joint w/ T. Hibi, A. Higashitani, and K. Kimura)

Department of Mathematics, University of Kentucky

Abstract

In 2005 Cameron and Walker classified all finite simple graphs G such that the matching number of G , m(G ), is equal to the induced matching number of G , i(G ). We call such graphs Cameron-Walker graphs. This class of graphs is of particular interest as these graph theoretic invariants provide upper and lower bounds for the Castelnuovo-Mumford regularity of the ring R/I (G ), where R is the polynomial ring in |V (G )| variables and I (G ) is the edge ideal of G . Here we explore other algebraic properties of the edge ideals of Cameron-Walker graphs such as (sequentially) Cohen-Macaulayness, (pure) shellability, and (pure) vertex decomposability.

Introduction and Preliminary Definitions

Let G be a finite simple graph on vertex set [n] := {1, . . . , n} with edge set E (G ). Definition. The edge ideal of G is then defined to be the ideal

I (G ) := xi xk : {i, j} E (G ) k[x1, . . . , xn] = S.

Example.

1

2

3

G:

I(G) = x1x2, x2x3, x3x5, x4x5, x2x4

4

5

Since I (G ) is a square-free monomial ideal, we can realize I (G ) as the Stanley-Reisner ideal of the independence complex of G , denoted (G ).

(G ) = {F V (G ) : F is an independent set in G } By an independent set in G we mean a collection of vertices F V (G ) such that for all i, j F we have {i, j} E (G ).

We say a property holds for (G ), I (G ), and G interchangeably.

We say a simplicial complex is pure if all its maximal faces are of the same cardinality. It is well-known that a Stanley-Reisner ideal, I () is unmixed, i.e. ht I () = ht p for all associated primes p, if and only if the associated simplicial complex is pure. Recall that Cohen-Macaulay ideals are unmixed.

Definition. We say that a graph G is vertex-decomposable if either G is an empty graph or satisfies both of the following conditions for some vertex v G .

1. G \ v and G \ N[v ] are vertex-decomposable. 2. No independent set in G \ N[v ] is a maximal independent set in G \ v .

Definition. A simplicial complex is shellable if all of its facets (maximal faces) can be listed

F1, . . . , Fs is such a way that

i-1

i -1

Fj Fi = Fj Fi

j =1

j =1

is a pure simplicial complex of dimension dim Fi - 1 for all 1 < i s.

Definition. A module M is sequentially Cohen-Macaulay if there exists a filtration of M

0 = M0 M1 ? ? ? Mr-1 Mr = M such that Mi /Mi-1 is Cohen-Macaulay for all 1 i r and dim Mi /Mi-1 < dim Mi+1/Mi for all 1 i r - 1.

We then have the following hierarchies of implications:

pure vertex-decomposable pure shellable Cohen-Macaulay vertex-decomposable shellable sequentially Cohen-Macaulay.

What is Known

G bipartite: We say a graph G is bipartite if there is a partition of the vertex set V (G ) = [n] [m] such that for all edges i, j E (G ) we have i [n] and j [m].

[Ravinda '77, Villarreal '07] Unmixed bipartite graphs are Cohen-Macaulay. [Van Tuyl '09] Sequentially Cohen-Macaulay bipartite graphs are vertex decomposable. decomposable.

G chordal: We say a graph G is chordal if every cycle of length at least 4 has a chord.

[Francisco-Van Tuyl '07] Chordal graphs are sequentially Cohen-Macaulay. [Docthermann-Engstrom '09] Chordal graphs are vertex decomposable. [Woodroofe '09] Graphs with no chordless cycle of length other than 3 or 5 are vertex decomposable.

Cameron-Walker Graphs

Definition. A set M E (G ) is said to be a matching if for all e, e E (G ) with e = e we have e e = . The matching number, denoted m(G ) is defined to be

m(G ) := max{|M| : M is a matching in G }.

Definition. A set M E (G ) is said to be an induced matching if for all e, e E (G ) with e = e there does not exist f E (G ) such that e f = and e f = . The induced matching number, denoted i(G ) is defined to be

i(G ) := max{|M| : M is an induced matching in G }.

Example. For G in the first example, {{2, 3}, {4, 5}} is a matching but not an induced matching and we have m(G ) = 2, i(G ) = 1.

These graph theoretic invariants are of particular interest to algebraists as they provide bounds for the Castelnuovo-Mumford regularity of S/I (G ). Theorem. [Katzmann '05, H`a-Van Tuyl '07] Given a finite simple graph G with edge ideal I (G ) S, we have the following inequality

i(G ) reg S/I (G ) m(G ).

Theorem. [Cameron-Walker '05] Suppose G is a finite simple graph such that i(G ) = m(G ). Then G is one of the following:

1. the empty graph, i.e. E (G ) = ,

4. G is comprised of a bipartite graph on vertex set [n] [m] such that for all i [n] there is at least one leaf edge

2. K1,n,

connected to i and for all j [m] there may be a pendant

3. K3, or

triangle connected to j.

We call a graph satisfying any of (1)-(4) above as a Cameron-Walker graph

Example. The following is an example of a Cameron-Walker graph.

reg S/I(G) = m(G) = i(G) = 6

In particular, Cameron-Walker graphs are neither chordal nor bipartite.

(Pure) Vertex Decomposability

A number of people have given ways to construct Cohen-Macaulay and vertex-decomposable graphs. [Villarreal '90] Given any graph G , adding a whisker, i.e. a K2, to every vertex in G results in a Cohen-Macaulay graph. [Dochtermann-Engstrom '09] Villarreal's construction also yields a pure vertex decomposable graph. [Cook-Nagel '09] Introduced a notion of clique whiskering which is essentially coning over disjoint complete graphs in G . The resulting graph is pure vertex decomposable.

The following is a generalization of these constructions. Theorem. [Hibi-Higashitani-Kimura-O'K. '13] Let G be a finite simple graph on a vertex set V = {x1, . . . , xn}. Let k1, . . . , kn 2 be integers. Then the graph G obtained from G by attaching the complete graph Kki to xi for i = 1, . . . , n is unmixed and vertex decomposable. In particular, G is shellable and Cohen-Macaulay.

We can now classify all Cameron-Walker graphs that are pure vertex-decomposable and therefore pure shellable and Cohen-Macaulay. Theorem. [Hibi-Higashitani-Kimura-O'K. '13] For a Cameron-Walker graph G , the following five conditions are equivalent:

1. G is unmixed. 2. G is Cohen-Macaulay. 3. G is unmixed and shellable. 4. G is unmixed and vertex decomposable. 5. G consists of a connected bipartite graph with vertex partition [n] [m] such that

there is exactly one leaf edge attached to each vertex i [n] and that there is exactly one pendant triangle attached to each vertex j [m]. Note that the implications (4) (3) (2) (1) are well known. The implication (5) (4) follows from the above theorem by starting with the supporting bipartite graph and attaching a copy of K2 to each i [n] and a copy of K3 to each j [m]. The implication (1) (5) follows from a straightforward count of maximal vertex covers.

Example. A Cohen-Macaulay Cameron-Walker graph.

It turns out we need no requirements on the number of leaves, pendant triangles, or even the structure of the supporting bipartite graph of a Cameron-Walker graph to obtain vertex decomposability. Theorem. [Hibi-Higashitani-Kimura-O'K. '13] Every Cameron-Walker graph is vertex decomposable.

References

. Cameron and T. Walker, "The graphs with maximum induced matching and maximum matching the same size", Discrete Math. 299 (2005), 49-55. . Hibi, A. Higashitani, K. Kimura and A. O'Keefe, "Algebraic study on Cameron-Walker graphs", .

augustine.okeefe@uky.edu

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download