×

Lexicographic Gröbner bases for transportation problems of format \(r\times 3\times 3\). (English) Zbl 1125.68140

Summary: By means of suitable sequences of graphs, we describe the reduced lexicographic Gröbner basis of the toric ideal associated with the 3-dimensional transportation problem of format \(r\times 3\times 3\) (\(r\) any integer \(> 1\)). In particular, we prove that the bases for \(r=2,3,4,5\) determine all others.

MSC:

68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68R10 Graph theory (including graph drawing) in computer science
05C38 Paths and cycles

Software:

CoCoA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aoki, S.; Takemura, A., Minimal basis for connected Markov chain over \(3 \times 3 \times K\) contingency tables with fixed two-dimensional marginals, Australian and New Zealand Journal of Statistics, 45, 229-249 (2003) · Zbl 1064.62068
[2] Aoki, S., Takemura, A., 2003b. Invariant minimal Markov basis for sampling contingency tables with fixed marginals. Technical Report METR 03-25, Department of Mathematical Engineering and Information Physics, The University of Tokyo; Aoki, S., Takemura, A., 2003b. Invariant minimal Markov basis for sampling contingency tables with fixed marginals. Technical Report METR 03-25, Department of Mathematical Engineering and Information Physics, The University of Tokyo · Zbl 1064.62068
[3] Boffi, G., Rossi, F., 2000. Gröbner bases related to 3-dimensional transportation problems. In: Quaderni matematici dell’Università di Trieste, vol. 482. DSM-Trieste. http://www.dmi.units.it/ rossif/; Boffi, G., Rossi, F., 2000. Gröbner bases related to 3-dimensional transportation problems. In: Quaderni matematici dell’Università di Trieste, vol. 482. DSM-Trieste. http://www.dmi.units.it/ rossif/
[4] Boffi, G.; Rossi, F., Lexicographic Gröbner bases of 3-dimensional transportation problems, Contemporary Mathematics, 286, 145-168 (2001) · Zbl 1023.13016
[5] CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra (2004), Available at
[6] Diaconis, P.; Sturmfels, B., Algebraic algorithms for sampling from conditional distributions, The Annals of Statistics, 26, 363-397 (1998) · Zbl 0952.62088
[7] Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of Combinatorics, vol. 1 (1995), Elsevier: Elsevier Amsterdam · Zbl 0833.05001
[8] Grossman, J. W.; Häggkvist, R., Alternating cycles in edge-partitioned graphs, Journal of Combinatorial Theory, Series B, 34, 77-81 (1983) · Zbl 0491.05039
[9] Santos, F.; Sturmfels, B., Higher Lawrence configurations, Journal of Combinatorial Theory, Series A, 103, 151-164 (2003) · Zbl 1036.52018
[10] Sturmfels, B., Gröbner Bases and Convex Polytopes (1995), AMS: AMS Providence RI
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.