Top

Published in:

2013 | OriginalPaper | Chapter

A Beginner’s Guide to Edge and Cover Ideals

Author : Adam Van Tuyl

Published in: Monomial Ideals, Computations and Applications

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Monomial ideals, although intrinsically interesting, play an important role in studying the connections between commutative algebra and combinatorics. Broadly speaking, problems in combinatorics are encoded into monomial ideals, which then allow us to use techniques and methods in commutative algebra to solve the original question. Stanley’s proof of the Upper Bound Conjecture [180] for simplicial spheres is seen as one of the early highlights of exploiting this connection between two fields. To bridge these two areas of mathematics, Stanley used square-free monomial ideals.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Stanley Decompositions Using CoCoA

next chapter Edge Ideals Using Macaulay2

I’m using the British–Canadian spelling of colouring, but if you prefer, you can call it a coloring. To be consistent, I’ll also use neighbour.

Although the book is out-of-print, you can have a free electronic copy if you send the authors a postcard; see http://www.ams.jhu.edu/~ers/fgt/ for details.

For a refresher on Stanley–Reisner rings, see either Stanley [182] or Bruns and Herzog [30].

If you are not familiar with this notion, see Peeva [156].

For more details on this construction, see [156, Chap. 1, Sect. 27].

The result holds for a larger class of graphs called perfect graphs .

A. Alilooee, S. Faridi, Betti numbers of path ideals of cycles and line (2011). Preprint [arXiv:1110.6653v1]

20.

J. Biermann, Cellular structure on the minimal resolution of the edge ideal of the complement of the n-cycle (2011). Preprint

27.

R. Bouchat, H.T. Hà, A. O’Keefe, Path ideals of rooted trees and their graded Betti numbers. J. Comb. Theory Ser. A 118, 2411–2425 (2011)MATHCrossRef

30.

W. Bruns, J. Herzog, Cohen-Macaulay rings, revised edn. (Cambridge University Press, Cambridge, 1998)

33.

J. Chen, S. Morey, A. Sung, The stable set of associated primes of the ideal of a graph. Rocky Mt. J. Math. 32, 71–89 (2002)MathSciNetMATHCrossRef

34.

R.-X. Chen, Minimal free resolutions of linear edge ideals. J. Algebra 324, 3591–3613 (2010)MathSciNetMATHCrossRef

35.

M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem. Ann. Math. (2) 164, 51–229 (2006)

40.

A. Conca, E. De Negri, M-Sequences, graph ideals and ladder ideals of linear type. J. Algebra 211, 599–624 (1999)MathSciNetMATHCrossRef

43.

A. Corso, U. Nagel, Specializations of Ferrers ideals. J. Algebr. Comb. 28, 425–437 (2008)MathSciNetMATHCrossRef

44.

A. Corso, U. Nagel, Monomial and toric ideals associated to Ferrers graphs. Trans. Am. Math. Soc. 361, 1371–1395 (2009)MathSciNetMATHCrossRef

46.

K. Dalili, M. Kummini, Dependence of Betti numbers on characteristic (2010) [arXiv:1009.4243]

48.

A. Dochtermann, A. Engström, Algebraic properties of edge ideals via combinatorial topology. Electron. J. Combin. 16 (2009). Special volume in honor of Anders Bjorner, Research Paper 2, 24 pp.

49.

A. Dochtermann, A. Engström, Cellular resolutions of cointerval ideals. Math. Z. 270, 145–163 (2012)MathSciNetMATHCrossRef

54.

D. Eisenbud, M. Green, K. Hulek, S. Popescu, Restricting linear syzygies: Algebra and geometry. Compos. Math. 141, 1460–1478 (2005)MathSciNetMATHCrossRef

56.

S. Eliahou, M. Kervaire, Minimal resolutions of some monomial ideals. J. Algebra 129, 1–25 (1990)MathSciNetMATHCrossRef

57.

E. Emtander, A class of hypergraphs that generalizes chordal graphs. Math. Scand. 106, 50–66 (2010)MathSciNetMATH

58.

E. Emtander, Betti numbers of hypergraphs. Commun. Algebra 37, 1545–1571 (2009)MathSciNetMATHCrossRef

59.

S. Faridi, The facet ideal of a simplicial complex. Manuscripta Math. 109, 159–174 (2002)MathSciNetMATHCrossRef

60.

G. Fatabbi, On the resolution of ideals of fat points. J. Algebra 242, 92–108 (2001)MathSciNetMATHCrossRef

61.

O. Fernández-Ramos, P. Gimenez, First nonlinear syzygies of ideals associated to graphs. Commun. Algebra 37, 1921–1933 (2009)MATHCrossRef

64.

C.A. Francisco, Resolutions of small sets of fat points. J. Pure Appl. Algebra 203, 220–236 (2005)MathSciNetMATHCrossRef

65.

C. Francisco, H.T. Hà, A. Van Tuyl, Splittings of monomial ideals. Proc. Am. Math. Soc. 137, 3271–3282 (2009)MATHCrossRef

66.

C.A. Francisco, H.T. Hà, A. Van Tuyl, A conjecture on critical graphs and connections to the persistence of associated primes. Discrete Math. 310, 2176–2182 (2010)MathSciNetMATHCrossRef

67.

C.A. Francisco, H.T. Hà, A. Van Tuyl, Associated primes of monomial ideals and odd holes in graphs. J. Algebr. Comb. 32, 287–301 (2010)MATHCrossRef

68.

C.A. Francisco, H.T. Hà, A. Van Tuyl, Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals. J. Algebra 331, 224–242 (2011)MathSciNetMATHCrossRef

69.

C.A. Francisco, A. Hoefel, A. Van Tuyl, EdgeIdeals: A package for (hyper)graphs. J. Softw. Algebra Geom. 1, 1–4 (2009)MathSciNet

70.

R. Fröberg, On Stanley-Reisner rings, in Topics in Algebra, Part 2 (Warsaw, 1988). PWN, vol. 26 (Banach Center Publ., Warsaw, 1990), pp. 57–70

80.

D. Grayson, M. Stillman, Macaulay2, A software system for research in algebraic geometry (2011). Available at: http://www.math.uiuc.edu/Macaulay2

83.

H.T. Hà, A. Van Tuyl, Splittable ideals and the resolution of monomial ideals. J. Algebra 309, 405–425 (2007)MathSciNetMATHCrossRef

84.

H.T. Hà, A. Van Tuyl, Resolutions of square-free monomial ideals via facet ideals: A survey. Contemp. Math. 448, 91–117 (2007)CrossRef

85.

H.T. Hà, A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. J. Algebr. Combin. 27, 215–245 (2008)MATHCrossRef

86.

J. He, A. Van Tuyl, Algebraic properties of the path ideal of a tree. Commun. Algebra 38, 1725–1742 (2010)MATHCrossRef

91.

J. Herzog, T. Hibi, in Monomial Ideals. GTM, vol. 260 (Springer, Berlin, 2010)

92.

J. Herzog, T. Hibi, F. Hreinsdóttir, T. Kahle, J. Rauh, Binomial edge ideals and conditional independence statements. Adv. Appl. Math. 45, 317–333 (2010)MATHCrossRef

93.

J. Herzog, T. Hibi, X. Zheng, Monomial ideals whose powers have a linear resolution. Math. Scand. 95, 23–32 (2004)MathSciNetMATH

105.

T. Hibi, K. Kimura, S. Murai, Betti numbers of chordal graphs and f-vectors of simplicial complexes. J. Algebra 323, 1678–1689 (2010)MathSciNetMATHCrossRef

106.

A. Hoefel, G. Whieldon, Linear quotients of the square of the edge ideal of the anticycle (2011). Preprint [arXiv:1106.2348v2]

107.

N. Horwitz, Linear resolutions of quadratic monomial ideals. J. Algebra 318, 981–1001 (2007)MathSciNetMATHCrossRef

117.

T. Kaiser, M. Stehlik, R. Skrekovski, Replication in critical graphs and the persistence of monomial ideals (2013). Preprint [arXiv:1301.6983.v2]

118.

M. Katzman, Characteristic-independence of Betti numbers of graph ideals. J. Comb. Theory Ser. A 113, 435–454 (2006)MathSciNetMATHCrossRef

121.

K. Kimura, Non-vanishingness of Betti numbers of edge ideals (2011). Preprint [arXiv:1110.2333v3]

125.

M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals. J. Algebr. Comb. 30, 429–445 (2009)MathSciNetMATHCrossRef

138.

J. Martinez-Bernal, S. Morey, R. Villarreal, Associated primes of powers of edge ideals (2011). Preprint [arXiv:1103.0992v3]

141.

E. Miller, B. Sturmfels, in Combinatorial Commutative Algebra. Graduate Texts in Mathematics, vol. 227 (Springer, New York, 2005)

143.

S. Moradi, D. Kiani, Bounds for the regularity of edge ideal of vertex decomposable and shellable graphs. Bull. Iran. Math. Soc. 36, 267–277 (2010)MathSciNetMATH

144.

S. Morey, E. Reyes, R. Villarreal, Cohen-Macaulay, shellable and unmixed clutters with a perfect matching of König type. J. Pure Appl. Algebra 212, 1770–1786 (2008)MathSciNetMATHCrossRef

145.

S. Morey, R. Villarreal, Edge ideals: Algebraic and combinatorial properties, in Progress in Commutative Algebra, vol. 1 (de Gruyter, Berlin, 2012), pp. 85–126

150.

E. Nevo, Regularity of edge ideals of C ₄-free graphs via the topology of the lcm-lattice. J. Comb. Theory Ser. A 118, 491–501 (2011)MathSciNetMATHCrossRef

151.

E. Nevo, I. Peeva, Linear resolutions of powers of edge ideals (2010). Preprint

156.

I. Peeva, Graded Syzygies (Springer, New York, 2010)

169.

E. Scheinerman, D. Ullman, Fractional Graph Theory. A Rational Approach to the Theory of Graphs (Wiley, New York, 1997)

173.

R.Y. Sharp, Steps in Commutative Algebra, 2nd edn. (Cambridge University Press, Cambridge, 2000)MATH

175.

A. Simis, W. Vasconcelos, R.H. Villarreal, On the ideal theory of graphs. J. Algebra 167, 389–416 (1994)MathSciNetMATHCrossRef

180.

R. Stanley, The Upper Bound Conjecture and Cohen-Macaulay rings. Stud. Appl. Math. 54, 135–142 (1975)MathSciNetMATH

182.

R.P. Stanley, Combinatorics and Commutative Algebra (Birkhäuser, Basel, 1983)MATH

185.

B. Sturmfels, S. Sullivant, Combinatorial secant varieties. Pure Appl. Math. Q. 2(3), Part 1, 867–891 (2006)

189.

G. Valla, Betti numbers of some monomial ideals. Proc. Am. Math. Soc. 133, 57–63 (2005)MathSciNetMATHCrossRef

190.

A. Van Tuyl, Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity. Arch. Math. (Basel) 93, 451–459 (2009)MathSciNetMATHCrossRef

192.

R.H. Villarreal, Cohen-Macaulay graphs. Manuscripta Math. 66, 277–293 (1990)MathSciNetMATHCrossRef

193.

R.H. Villarreal, in Monomial Algebras. Monographs and Textbooks in Pure and Applied Mathematics, vol. 238 (Marcel Dekker, New York, 2001)

196.

G. Whieldon, Jump sequences of edge ideals (2010). Preprint [arXiv:1012.0108v1]

197.

R. Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity (2010). Preprint [arXiv:1009.2756]

198.

R. Woodroofe, Chordal and sequentially Cohen-Macaulay clutters. Electron. J. Comb. 18, Paper 208 (2011)

203.

X. Zheng, Resolutions of facet ideals. Commun. Algebra 32, 2301–2324 (2004)MATHCrossRef

Title: A Beginner’s Guide to Edge and Cover Ideals
Author: Adam Van Tuyl
Publisher: Springer Berlin Heidelberg
Book: Monomial Ideals, Computations and Applications
Print ISBN: 978-3-642-38741-8

Electronic ISBN: 978-3-642-38742-5

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-3-642-38742-5_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner