Matchings, coverings, and Castelnuovo-Mumford regularity

By Russ Woodroofe. 2010

127 citations recorded by the source corpus.

We show that the co-chordal cover number of a graph G gives an upper bound for the Castelnuovo-Mumford regularity of the associated edge ideal. Several known combinatorial upper bounds of regularity for edge ideals are then easy consequences of covering results from graph theory, and we derive new upper bounds by looking at additional covering results.

Subfields: Algebra and Number Theory, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/c374cfdd7a37325f4d0ec9e9bb12710f28b273d5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Geometry and Topology

Citations in the corpus

Regularity of Edge Ideals and Their Powers (2017, background): “then regI(G) n: Another special class of graphs are planar graphs. This class of graphs emerges frequently in applications since they can be drawn in the plane without edges crossing. It is given in [64] that even though regularity of a planar graph may be arbitrarily large, regularity of its comple”
Combinatorial Topology and the Global Dimension of Algebras Arising in Combinatorics (2012, background): “The k-Leray number of a simplicial complexK turns out to be the Castelnuovo–Mumford regularity of the Stanley–Reisner ring of K over k [38, 51, 93].”
Regularity of Squarefree Monomial Ideals (2013, background): “ be the complement of a chordal graph (in which case, reg(I(G)) = 2), one can make (G) + 1 arbitrarily larger than reg(I(G)). A number of generalizations for Theorem 4.4 has been developed. Woodroofe [51] was the rst to observe that giving a matching in a graph Gis a simple way to \cover" the e”
Regularity of powers of bipartite graphs (2016, unknown): “The lower bound was proved by Katzman [18] and the upper bound was proved byWoodroofe [32].”
Algebraic study on Cameron-Walker graphs (2013, background): “[5, Theorem 6.7]) that im(G) reg(S=I(G)) m(G): One has reg(S=I(G)) = im(G) for, e.g., chordal graphs, unmixed bipartite graphs and sequentially Cohen{Macaulay bipartite graphs ([5, 8, 11]; see also [3, 9, 16, 17]). Cameron and Walker [1] succeeded in classifying the nite connected simple graphs Gwit”