Robust Graph Ideals

Adam Boocher; Bryan Christopher Brown; Timothy Duff; Laura Lyman; Takumi Murayama; Amy Nesky; Karl Schaefer

doi:10.1007/s00026-015-0288-3

Robust Graph Ideals

Adam Boocher, Bryan Christopher Brown, Timothy Duff, Laura Lyman, Takumi Murayama, Amy Nesky, Karl Schaefer

Department of Mathematics & Statistics

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

Let I be a toric ideal. We say I is robust if its universal Gröbner basis is a minimal generating set. We show that any robust toric ideal arising from a graph G is also minimally generated by its Graver basis. We then completely characterize all graphs which give rise to robust ideals. Our characterization shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of G.

Original language	English
Pages (from-to)	641-660
Number of pages	20
Journal	Annals of Combinatorics
Volume	19
Issue number	4
DOIs	https://doi.org/10.1007/s00026-015-0288-3
State	Published - Dec 1 2015

Keywords

graph ideals
toric ideals
universal Gröbner bases

Access to Document

10.1007/s00026-015-0288-3

Cite this

@article{eebac5ae7a7f4ed8b6ceeb588f857e2f,

title = "Robust Graph Ideals",

abstract = "Let I be a toric ideal. We say I is robust if its universal Gr{\"o}bner basis is a minimal generating set. We show that any robust toric ideal arising from a graph G is also minimally generated by its Graver basis. We then completely characterize all graphs which give rise to robust ideals. Our characterization shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of G.",

keywords = "graph ideals, toric ideals, universal Gr{\"o}bner bases",

author = "Adam Boocher and Brown, {Bryan Christopher} and Timothy Duff and Laura Lyman and Takumi Murayama and Amy Nesky and Karl Schaefer",

note = "Publisher Copyright: {\textcopyright} 2015, Springer Basel.",

year = "2015",

month = dec,

day = "1",

doi = "10.1007/s00026-015-0288-3",

language = "English",

volume = "19",

pages = "641--660",

journal = "Annals of Combinatorics",

issn = "0218-0006",

number = "4",

}

TY - JOUR

T1 - Robust Graph Ideals

AU - Boocher, Adam

AU - Brown, Bryan Christopher

AU - Duff, Timothy

AU - Lyman, Laura

AU - Murayama, Takumi

AU - Nesky, Amy

AU - Schaefer, Karl

PY - 2015/12/1

Y1 - 2015/12/1

N2 - Let I be a toric ideal. We say I is robust if its universal Gröbner basis is a minimal generating set. We show that any robust toric ideal arising from a graph G is also minimally generated by its Graver basis. We then completely characterize all graphs which give rise to robust ideals. Our characterization shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of G.

AB - Let I be a toric ideal. We say I is robust if its universal Gröbner basis is a minimal generating set. We show that any robust toric ideal arising from a graph G is also minimally generated by its Graver basis. We then completely characterize all graphs which give rise to robust ideals. Our characterization shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of G.

KW - graph ideals

KW - toric ideals

KW - universal Gröbner bases

UR - http://www.scopus.com/inward/record.url?scp=84940888787&partnerID=8YFLogxK

U2 - 10.1007/s00026-015-0288-3

DO - 10.1007/s00026-015-0288-3

M3 - Article

AN - SCOPUS:84940888787

SN - 0218-0006

VL - 19

SP - 641

EP - 660

JO - Annals of Combinatorics

JF - Annals of Combinatorics

IS - 4

ER -

Robust Graph Ideals

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this