Lower Bounds on the Graver Complexity of M-Fold Matrices

Elisabeth Finhold; Raymond Hemmecke

doi:10.1007/s00026-015-0297-2

Lower Bounds on the Graver Complexity of M-Fold Matrices

Elisabeth Finhold, Raymond Hemmecke

Computation, Information and Technology

Technical University of Munich

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

6 Scopus citations

Abstract

In this paper, we present a construction that turns certain relations on Graver basis elements of an M-fold matrix (Formula presented.) into relations on Graver basis elements of an (Formula presented.) -fold matrix (Formula presented.). In doing so, we strengthen the bound on the Graver complexity of the M-fold matrix (Formula presented.) from (Formula presented.) (Berstein and Onn) to (Formula presented.) , for (Formula presented.). Moreover, we give a lower bound on the Graver complexity (Formula presented.) of general (Formula presented.) -fold matrices (Formula presented.) and we prove that the bound for (Formula presented.) is not tight.

Original language	English
Pages (from-to)	73-85
Number of pages	13
Journal	Annals of Combinatorics
Volume	20
Issue number	1
DOIs	https://doi.org/10.1007/s00026-015-0297-2
State	Published - 1 Mar 2016

Keywords

Graver basis
Graver complexity
lower bound

Access to Document

10.1007/s00026-015-0297-2

Cite this

@article{191240b9c2f644a0b109ecaa7d1bbbf8,

title = "Lower Bounds on the Graver Complexity of M-Fold Matrices",

abstract = "In this paper, we present a construction that turns certain relations on Graver basis elements of an M-fold matrix (Formula presented.) into relations on Graver basis elements of an (Formula presented.) -fold matrix (Formula presented.). In doing so, we strengthen the bound on the Graver complexity of the M-fold matrix (Formula presented.) from (Formula presented.) (Berstein and Onn) to (Formula presented.) , for (Formula presented.). Moreover, we give a lower bound on the Graver complexity (Formula presented.) of general (Formula presented.) -fold matrices (Formula presented.) and we prove that the bound for (Formula presented.) is not tight.",

keywords = "Graver basis, Graver complexity, lower bound",

author = "Elisabeth Finhold and Raymond Hemmecke",

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

year = "2016",

month = mar,

day = "1",

doi = "10.1007/s00026-015-0297-2",

language = "English",

volume = "20",

pages = "73--85",

journal = "Annals of Combinatorics",

issn = "0218-0006",

publisher = "Birkhauser Verlag Basel",

number = "1",

}

TY - JOUR

T1 - Lower Bounds on the Graver Complexity of M-Fold Matrices

AU - Finhold, Elisabeth

AU - Hemmecke, Raymond

PY - 2016/3/1

Y1 - 2016/3/1

N2 - In this paper, we present a construction that turns certain relations on Graver basis elements of an M-fold matrix (Formula presented.) into relations on Graver basis elements of an (Formula presented.) -fold matrix (Formula presented.). In doing so, we strengthen the bound on the Graver complexity of the M-fold matrix (Formula presented.) from (Formula presented.) (Berstein and Onn) to (Formula presented.) , for (Formula presented.). Moreover, we give a lower bound on the Graver complexity (Formula presented.) of general (Formula presented.) -fold matrices (Formula presented.) and we prove that the bound for (Formula presented.) is not tight.

AB - In this paper, we present a construction that turns certain relations on Graver basis elements of an M-fold matrix (Formula presented.) into relations on Graver basis elements of an (Formula presented.) -fold matrix (Formula presented.). In doing so, we strengthen the bound on the Graver complexity of the M-fold matrix (Formula presented.) from (Formula presented.) (Berstein and Onn) to (Formula presented.) , for (Formula presented.). Moreover, we give a lower bound on the Graver complexity (Formula presented.) of general (Formula presented.) -fold matrices (Formula presented.) and we prove that the bound for (Formula presented.) is not tight.

KW - Graver basis

KW - Graver complexity

KW - lower bound

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

U2 - 10.1007/s00026-015-0297-2

DO - 10.1007/s00026-015-0297-2

M3 - Article

AN - SCOPUS:84958760923

SN - 0218-0006

VL - 20

SP - 73

EP - 85

JO - Annals of Combinatorics

JF - Annals of Combinatorics

IS - 1

ER -

Lower Bounds on the Graver Complexity of M-Fold Matrices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this