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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- role theory and foreign policy university of iowa
- st christopher s school hy tek s meet manager 7 18 pm 2
- for immediate release navajo nation
- cameron walker aicp midland tx 79711 re south central
- cameron h walker aaci p brunsdon lawrek
- lake county sheriff s office warrants as of 3 8 2022
- urban air mobility advisory committee membership
- how the moon s phases affect all life on earth cameron
- uniform traffic leave
- federal bureau of investigation official notification
Related searches
- examples of ideals in society
- examples of ideals and values
- examples of ideals in life
- ideals of america
- founding fathers ideals of america
- founding ideals of america
- walker county advancing education center
- ideals of the founding fathers
- ideals of the american government
- icd 10 code walker device
- the ideals of america
- icd 10 code for walker assist