Unboundedness of Markov complexity of monomial curves in An for n ≥ 4

被引：2

作者：

Kosta, Dimitra ^{[1
]}

Thoma, Apostolos ^{[2
]}

机构：

[1] Univ Glasgow, Sch Math & Stat, Univ Pl, Glasgow G12 8SQ, Lanark, Scotland

[2] Univ Ioannina, Dept Math, GR-45110 Ioannina, Greece

来源：

JOURNAL OF PURE AND APPLIED ALGEBRA | 2020年 / 224卷 / 06期

关键词：

Toric ideals; Markov basis; Monomial curves; Lawrence liftings; GRAVER COMPLEXITY; BASES; TABLES;

D O I：

10.1016/j.jpaa.2019.106249

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Computing the complexity of Markov bases is an extremely challenging problem; no formula is known in general and there are very few classes of toric ideals for which the Markov complexity has been computed. A monomial curve C in A(3) has Markov complexity m(C) two or three. Two if the monomial curve is complete intersection and three otherwise. Our main result shows that there is no d is an element of N such that m(C) <= d for all monomial curves C in A(4). The same result is true even if we restrict to complete intersections. We extend this result to all monomial curves in A(n), where n >= 4. (C) 2019 Elsevier B.V. All rights reserved.

引用

页数：12

共 17 条

[1] Minimal basis for a connected Markov chain over 3 x 3 x K contingency tables with fixed two-dimensional marginals [J].

Aoki, S ;

Takemura, A .

AUSTRALIAN & NEW ZEALAND JOURNAL OF STATISTICS, 2003, 45 (02) :229-249

[2] The Graver Complexity of Integer Programming [J].

Berstein, Yael ;

Onn, Shmuel .

ANNALS OF COMBINATORICS, 2009, 13 (03) :289-296

[3] Minimal systems of binomial generators and the indispensable complex of a toric ideal [J].

Charalambous, Hara ;

Katsabekis, Anargyros ;

Thoma, Apostolos .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2007, 135 (11) :3443-3451

[4] Markov Bases and Generalized Lawrence Liftings [J].

Charalambous, Hara ;

Thoma, Apostolos ;

Vladoiu, Marius .

ANNALS OF COMBINATORICS, 2015, 19 (04) :661-669

[5] Markov complexity of monomial curves [J].

Charalambous, Hara ;

Thoma, Apostolos ;

Vladoiu, Marius .

JOURNAL OF ALGEBRA, 2014, 417 :391-411

[6] Markov bases of three-way tables are arbitrarily complicated [J].

De Loera, JA ;

Onn, S .

JOURNAL OF SYMBOLIC COMPUTATION, 2006, 41 (02) :173-181

[7] N-fold integer programming [J].

De Loera, Jesus A. ;

Hemmecke, Raymond ;

Onn, Shmuel ;

Weismantel, Robert .

DISCRETE OPTIMIZATION, 2008, 5 (02) :231-241

[8]

Diaconis P, 1998, ANN STAT, V26, P363

[9]

DRTON M., 2009, Lectures on Algebraic Statistics, Oberwolfach Semin., DOI 10.1007/978-3-7643-8905-5

[10] Lower Bounds on the Graver Complexity of M-Fold Matrices [J].

Finhold, Elisabeth ;

Hemmecke, Raymond .

ANNALS OF COMBINATORICS, 2016, 20 (01) :73-85

← 1 2 →