CHALLENGING COMPUTATIONS OF HILBERT BASES OF CONES ASSOCIATED WITH ALGEBRAIC STATISTICS 0 1 WINFRIED BRUNS, RAYMOND HEMMECKE, BOGDAN ICHIM, MATTHIAS KO¨PPE, 0 AND CHRISTOF SO¨GER 2 n a Abstract. Inthispaperwepresenttwoindependentcomputationalproofsthatthe J monoid derived from 5×5×3 contingency tables is normal, completing the classifi- 3 cationbyHibiandOhsugi.We showthatVlach’svectordisprovingnormalityforthe 2 monoid derived from 6×4×3 contingency tables is the unique minimal such vector up to symmetry. Finally, we compute the full Hilbert basis of the cone associated ] O with the non-normalmonoidofthe semi-graphoidfor |N|=5.The computationsare C based on extensions of the packages LattE-4ti2 and Normaliz. . h t a m [ 1. Introduction 1 v Let S = monoid(G) be an affine monoid generated by a finite set G ⊆ Zn of integer 5 vectors. We call S normal if S = cone(G) ∩ lattice(G), where cone(G) = {x ∈ Rn : 4 x = λ g ,λ ∈ R ,g ∈ G} denotes the rational polyhedral cone generated by G 1 i i i + i 4 and wPhere lattice(G) = {x ∈ Rn : x = λ g ,λ ∈ Z,g ∈ G} denotes the sublattice i i i i 1. of Zn generated by G. In this paper, wPe will stick to the case that lattice(G) = Zn. 0 Then, normality of S is equivalent to saying that G contains the Hilbert basis of 0 cone(G), i.e., every lattice point in cone(G) can be written as a nonnegative integer 1 : linear combination of elements in G. By the Hilbert basis H(C) of a pointed rational v i cone C we mean the unique minimal system of generators of the monoid M of lattice X points in C. The Hilbert basis of C consists of the irreducible elements of M, i.e., those r a elements of M that do not have a nontrivial representation as a sum of two elements of M (see [2, Ch. 2] for a comprehensive discussion). Note that deciding normality of an affine monoid is NP-hard [5]. Normality of monoids derived from r × r × ··· × r contingency tables by taking 1 2 N N−1-marginals (that is, line sums) was settled almost completely by Hibi and Ohsugi [9]. In this paper we close the last open cases by showing computationally, via two different approaches and independent implementations, that 5 × 5 × 3 has a normal monoid. The normality for 5 × 5 × 3 implies normality for the other two open cases 5×4×3 and 4×4×3 by [9, 3.2]. Date: January 23, 2010. Acknowledgement:B.IcimwaspartiallysupportedbyCNCSISgrantRP-1no.7/01.07.2009during the preparation of this work. 1 2 W. BRUNS,R.HEMMECKE, B. ICHIM,M. KO¨PPE, ANDCH. SO¨GER Here is the defining matrix A5×5×3 whose columns generate the monoid associated to 5×5×3 contingency tables. Every · corresponds to an entry 0. 1··············1··············1··············1··············1·············· ·1··············1··············1··············1··············1············· ··1··············1··············1··············1··············1············ ···1··············1··············1··············1··············1··········· ····1··············1··············1··············1··············1·········· ·····1··············1··············1··············1··············1········· ······1··············1··············1··············1··············1········ ·······1··············1··············1··············1··············1······· ········1··············1··············1··············1··············1······ ·········1··············1··············1··············1··············1····· ··········1··············1··············1··············1··············1···· ···········1··············1··············1··············1··············1··· ············1··············1··············1··············1··············1·· ·············1··············1··············1··············1··············1· ··············1··············1··············1··············1··············1 1··1··1··1··1······························································ ·1··1··1··1··1····························································· ··1··1··1··1··1···························································· ···············1··1··1··1··1··············································· ················1··1··1··1··1·············································· ·················1··1··1··1··1············································· ······························1··1··1··1··1································ ·······························1··1··1··1··1······························· ································1··1··1··1··1······························ ·············································1··1··1··1··1················· ··············································1··1··1··1··1················ ···············································1··1··1··1··1··············· ····························································1··1··1··1··1·· ·····························································1··1··1··1··1· ······························································1··1··1··1··1 111········································································ ···111····································································· ······111·································································· ·········111······························································· ············111···························································· ···············111························································· ··················111······················································ ·····················111··················································· ························111················································ ···························111············································· ······························111·········································· ·································111······································· ····································111···································· ·······································111································· ··········································111······························ ·············································111··························· ················································111························ ···················································111····················· ······················································111·················· ·························································111··············· ····························································111············ ·······························································111········· ··································································111······ ·····································································111··· ········································································111 CHALLENGING COMPUTATIONS OF HILBERT BASES 3 Note that this normality problem cannot be settled directly by computing the Hilbert basis of the associated cone using state-of-the-art software such as Normaliz v2.2 [3, 4] or 4ti2 v1.3.2 [1, 6]. Both codes fail to return an answer due to time and to mem- ory requirements of intermediate computations. Using the computational approaches presented below, we can now show the following. Lemma 1. The monoid derived from of 5 × 5 × 3 contingency tables by taking line sums (= two-marginals) is normal. This completesthenormalityclassificationofthemonoidsderived fromr ×r ×···×r 1 2 N contingency tables by taking line sums as given in [9]: Theorem 2. Let r ≥ r ≥ ... ≥ r ≥ 2 be integer numbers. Then the monoid derived 1 2 N from r ×r ×···×r contingency tables by taking line sums is normal if and only if 1 2 N the contingency table is of size • r ×r , r ×r ×2×...×2, or 1 2 1 2 • r ×3×3, or 1 • 4×4×3, 5×4×3, or 5×5×3. For the monoid of 6 × 4 × 3 contingency tables, a vector disproving normality was presentedbyVlach[12].Theright-handsidevectorf forthecountsalongthecoordinate axes is given by the following three matrices: 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0   1 1 1 1 0 1 1 1 0 0 ,  and  . 1 1 1 1 0 1 0 0 1 1       1 1 1 0 1 1 1 0 1 0     0 1 1 0 1 0 1 The unique point in the 6×4×3 transportation polytope {z ∈ R72 : Az = f,z ≥ 0} is 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0   1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 ∗ z = . 2  0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0     1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1  So z∗ is indeed a hole of the 6×4×3 monoid. We are able to show the following. Lemma 3. The right-hand side vector f presented by Vlach [12] is the unique vector (up to the underlying S ×S ×S symmetry) in the Hilbert basis of the cone of 6×4×3 6 4 3 contingency tables that is not an extreme ray. The treatment in [7] now completely describes all holes of the cone, that is, all lattice points in cone(A6×4×3) that cannot be written as a nonnegative linear integer combi- nation of the (integer) generators of the cone: 4 W. BRUNS,R.HEMMECKE, B. ICHIM,M. KO¨PPE, ANDCH. SO¨GER Corollary 4. Let f be the hole in cone(A6×4×3) presented by Vlach [12] and let z∗ ∈ R7+2 be the unique solution to A6×4×3z = f,z ∈ R7+2, as stated above. Moreover, let G denote the set of those 24 columns of A6×4×3 for which z∗i > 0. Then the set of holes in cone(A6×4×3) is the set of all points that can be written uniquely as σ(f +s) with σ ∈ S ×S ×S and with s ∈ monoid(G). 6 4 3 Finally, we have computed theHilbert basis ofthe coneassociated tothesemi-graphoid for |N| = 5 [10]. It was already shown in [8] that the corresponding monoid is not normal by constructing a hole via a different method. The computation of the full Hilbert basis was not possible at that time, neither with Normaliz, nor with 4ti2. Here is the defining matrix whose columns generate the monoid associated to the semi- graphoid for |N| = 5. Every . corresponds to an entry 0. + and − represent entries 1 and −1. ++++++++++...................................................................... ----......++++++................................................................ -...---.........++++++.......................................................... .-..-..--................++++++................................................. ..-..-.-.-............................++++++.................................... ...-..-.--..............................................++++++.................. +.........---...---...+++....................................................... .+........-..--..........---...+++.............................................. ..+........-.-.-......................---...+++................................. ...+........-.--........................................---...+++............... ....+...........-..--....-..--....+++........................................... .....+...........-.-.-................-..--....+++.............................. ......+...........-.--..................................-..--....+++............ .......+..................-.-.-........-.-.-.......+++.......................... ........+..................-.--..........................-.-.-.......+++........ .........+..............................-.--..............-.--............+++... ..........+.....+.....--.+.....--.--.+.......................................... ...........+.....+....-.-.............+.....--.--.+............................. ............+.....+....--...............................+.....--.--.+........... .............+............+....-.-.....+....-.-....--.+......................... ..............+............+....--.......................+....-.-....--.+....... ...............+........................+....--...........+....--.........--.+.. ...................+........+.....-.-....+.....-.-.-.-.+........................ ....................+........+.....--......................+.....-.-.-.-.+...... .....................+....................+.....--..........+.....--......-.-.+. ..............................+............+........--.......+........--...--..+ ......................+........+..+..-......+..+..-+..--........................ .......................+........+..+.-........................+..+..-+..--...... ........................+....................+..+.-............+..+.-.....+..--. .................................+............+.....+.-.........+.....+.-..+.-.- ....................................+............+...+.-...........+...+.-..+.-- .....................................+............+...++............+...++...+++ CHALLENGING COMPUTATIONS OF HILBERT BASES 5 Lemma 5. The Hilbert basisof the cone associated to the semi-graphoidfor|N| = 5 has 1300 elements that come into 21 orbits under the underlying symmetry group S ×S . 5 2 These are represented by the 21 rows of the following matrix: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 −1 −1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 −1 −1 0 0 0 0 1 0 2 0 0 0 0 −2 −1 −1 1 1 0 −1 1 −1 1 1 1 0 0 0 −1 −2 1 −1 −1 0 −1 0 1 1 0 1 2 0 0 0 −2 0 −1 −1 1 0 0 1 −1 1 −1 1 1 −1 1 0 1 −1 −1 1 0 −1 0 −2 0 0 0 2 1 0 0 1 0 0 0 −1 −1 2 −1 2 −1 −1 −1 0 0 −1 −1 2 −1 −1 −1 2 −1 0 0 0 1 0 0 1 1 0 1 1 0 −1 −1 1 −1 1 −2 0 0 −1 0 1 0 1 −1 0 −2 0 1 1 −1 −1 −1 1 0 1 0 1 0 1 1 0 1 1 −1 0 −2 1 0 0 −2 0 0 −1 −1 1 0 1 −2 0 −1 1 1 −1 0 1 −1 1 0 1 0 1 1 0 1 1 −1 0 −2 0 0 0 −2 0 0 −1 −1 1 1 1 −1 1 −1 1 1 −1 0 0 −2 0 0 2 1 0 0 1 0 0 −1 −1 0 2 −1 2 0 −1 −1 −1 1 −1 −1 1 −1 −1 −1 1 −1 1 0 0 1 0 0 1 0 1 1 1 1 1 −2 −1 −1 1 −1 1 −1 −1 −1 −2 1 0 0 1 −1 0 −1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 −1 −1 −1 −1 −1 −1 −1 −1 1 1 −1 −1 1 1 1 1 0 0 0 0 −2 2 1 1 0 1 0 −1 −1 −1 −1 0 −1 1 1 −1 0 1 1 0 −1 1 1 −1 0 −1 −1 −1 −1 0 1 0 1 1 0 1 0 1 1 1 0 −1 1 −2 0 0 0 −2 1 −1 −1 −2 1 0 0 0 1 −2 −1 0 1 1 1 0 1 0 2 −1 0 0 −1 −1 0 0 1 1 −1 1 1 1 1 0 1 −2 −1 −1 −2 0 −1 −1 −1 −1 1 1 1 1 1 0 0 1 1 1 1 1 −2 −1 −1 0 −1 0 −1 −1 −1 −2 1 1 1 1 0 1 0 1 1 1 −1 −1 −2 −1 −1 3 0 1 1 1 1 1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 0 0 2 2 0 0 1 1 1 1 −1 −1 −1 −1 −2 3 1 0 0 1 2 −1 −1 −1 −1 1 −1 −1 1 −2 0 0 2 1 0 1 −1 −1 1 −1 −1 1 −2 0 0 0 0 2 2 0 0 0 0 −2 −1 −1 1 2 1 −1 1 −1 1 1 0 0 −1 0 −1 −2 0 −2 −1 −1 0 1 1 1 2 0 3 −1 −1 1 −1 −2 0 −1 0 1 −1 0 1 −1 1 1 1 1 −1 1 0 −1 1 0 −1 0 −2 −1 1 −1 −1 3 3 1 −1 −1 −1 −2 −1 −1 −1 2 0 0 1 0 1 1 1 1 −1 1 −1 −1 1 −1 −1 −1 −2 0 0 0 1 2 2 1 0 0 0 −2 −1 −1 −1 2 −1 −1 1 −1 1 1 1 1 −1 1 −1 −1 2 −1 −1 −1 −2 0 0 0 1 2 2. Computational Approaches In this section we present the two computational approaches that allowed us to solve the three challenging Hilbert basis computations of the cones associated to 5×5×3- tables, to 6×4×3-tables, and to semi-graphoids for |N| = 5. In the first approach, we iteratively decompose the cone into smaller cones and exploit the underlying symmetry and set inclusion to avoid a lot of unnecessary computations. An implementation of this approach is freely available in the new release latte-for-tea-too-1.4 of “LattE for tea, too” (http://www.latte-4ti2.de), a joint source code distribution of the two software packages LattE macchiato and 4ti2. In the second approach, we exploit the fact that the cones are nearly compressed; hence many cones in any pulling triangula- tion are unimodular, and the same holds in placing triangulations. Using our second approach, none of these unimodular cones is constructed, saving a lot of computation time. An implementation of this approach will be freely available in the next release of Normaliz (http://www.math.uos.de/normaliz), together with the input files of the examples of this paper. 2.1. First approach: exploiting symmetry. Letusassumethatwewishtocompute the Hilbert basis of a rational polyhedral cone C = cone(r ,...,r ) ⊆ Rn. Moreover, 1 s assume that C has a coordinate-permuting symmetry group S, that is, if v ∈ V and σ ∈ S then also σ(v) ∈ C. Herein, the vector σ(v) is obtained by permuting the components of v according to the permutation σ. 6 W. BRUNS,R.HEMMECKE, B. ICHIM,M. KO¨PPE, ANDCH. SO¨GER One approach to find the Hilbert basis of C is to find a regular triangulation of C into simplicial cones C ,...,C and to compute the Hilbert bases of the simplicial cones 1 k C ,...,C .Clearly, theunionoftheseHilbert basesisa(typically non-minimal)system 1 k of generators of the monoid of lattice points in C. The drawback of this approach is that a complete triangulation of C is often too hard to accomplish. Instead of computing a full triangulation, we compute only a (regular) subdivision of C intofewcones.Tothisendweremoveoneofthegeneratorsofthecones,sayr ,compute s the convex hull of the cone C′ = cone(r1,...,rs−1), and find all facets F of C′ that are visible from r . By F′ we denote the set of all cones that we get as the convex hull of s a facet in F with the ray generated by r . Then F′ ∪{C′} gives a regular subdivision s of C, called the subdivision with distinguished generator r . Before we now subdivide s ′ those cones in F further into smaller cones, we use the following simple observation to remove cones that can be avoided due to the underlying symmetry given by S. Lemma 6. Let C,C ,...,C ⊆ Rn be rational polyhedral cones such that C = ∪k C 1 k i=1 i (not necessarily a disjoint union). Suppose that there is a permutation σ and indices i and j such that C ⊆ σ(C ) ⊆ C. Then the Hilbert basis of C is contained in the union i j of the Hilbert bases of the cones C1,...,Ci−1,σ(Cj),Ci+1,...,Ck. Proof. The result follows by observing that all lattice points in C also belong to σ(C ) i j andthuscanbewritten asanonnegative integer linear combination oftheHilbert basis of σ(C ). (cid:3) j If successful, this test whether C can be dropped is a very efficient way of removing i unnecessary cones. However, the fewer generators are present in the cones C ,...,C , 1 k the higher the chance that this test fails. So one has to make a trade-off between a simple test (that may fail more and more often) and a direct treatment of each cone C . As we compute only regular subdivisions whose cones are spanned by some of the i vectors r ,...,r , each of the cones C ,...,C can be represented by a characteristic 1 s 1 k 0-1-vector χ(C ),...,χ(C ) of length s that encodes which of the generators of C are 1 k present in this cone. This makes the test C ⊆ σ(C ) comparably cheap, as we only i j need to check whether χ(C ) ≤ σ(χ(C )). i j Summarizing these ideas, the symmetry exploiting approach can be stated as follows: (1) Let C = cone(r ,...,r ) ⊆ Rn and C = {C}. 1 s (2) i := 0 (3) While C =6 ∅ do (a) i := i+1 (b) For all K ∈ C compute a subdivision with distinguished ith generator (if existent in K). (c) Let T be the set of all cones in these subdivisions. (d) Let M be the set of those cones with a maximum number of rays. (e) Let C =6 ∅ be the set M together with all cones T ∈ T that are not covered by a cone σ(M) with M ∈ M and σ ∈ S, see Lemma 6. CHALLENGING COMPUTATIONS OF HILBERT BASES 7 (f) Remove from C all simplicial cones and compute their Hilbert bases. (4) ForeachcomputedHilbert basiselement hcomputeitsfullorbit{σ(h) : σ ∈ S} and collect them in a set H. (5) Remove the reducible elements from H. (6) Return the set of irreducible elements as the minimal Hilbert basis of C. This quite simple approach via triangulations and elimination of cones by symmetric covering already solves all three presented examples. In particular, it gives a compu- tational proof to Lemma 1. The candidates for the representatives of Hilbert basis elements can be computed using “LattE for tea, too” by calling dest/bin/hilbert-from-rays-symm --hilbert-from-rays="dest/bin/hilbert-from-rays" --dimension=26 S5.rays dest/bin/hilbert-from-rays-symm --hilbert-from-rays="dest/bin/hilbert-from-rays" --dimension=43 355.short.rays dest/bin/hilbert-from-rays-symm --hilbert-from-rays="dest/bin/hilbert-from-rays" --dimension=42 346.short.rays Thedatafilescanbefoundonhttp://www.latte-4ti2.de.(Fortypographicalreasons each command has been printed in two lines.) 2.2. Second approach: partial triangulation. In the second approach, we build up a triangulation of the given cone C = cone(r ,...,r ) ⊆ Rn. However, by using the 1 s following Lemma 7 and its Corollary 8, we can avoid triangulating many regions of the cone, since the triangulation would consist only of unimodular cones (for which the extreme ray generators already constitute a Hilbert basis), or, more precisely, avoid to construct simplicial cones whose non-extreme Hilbert basis elements are contained in previously computed simplicial cones. In the following we describe the facets of a full-dimensional rational cone by (uniquely determined) primitive integral exterior normal vectors. In other words, F = {x ∈ C : c⊺x = 0} where c has coprime integer entries and c⊺y ≤ 0 for all y ∈ C. Lemma 7. Let C = cone(r ,...,r ) ⊆ Rn be a rational polyhedral cone such that 1 k • r ,...,r ∈ Zn, 1 k • r1,...,rk−1 lie in a facet of C defined by the hyperplane c⊺x = 0, • c⊺r = 1. k Then the Hilbert basis of C is the union of {r } and the Hilbert basis of cone(r ,..., k 1 rk−1). Proof. Let z ∈ C ∩ Zn. Then z = k λ r for some nonnegative real numbers i=1 i i P λ ,...,λ . Multiplying by c⊺, we obtain 1 k k c⊺z = λ c⊺r = λ c⊺r = λ . X i i k k k i=1 8 W. BRUNS,R.HEMMECKE, B. ICHIM,M. KO¨PPE, ANDCH. SO¨GER As c,z ∈ Zn, we obtain λ ∈ Z. Hence, z is the sum of an nonnegative integer multiple k of rk and a lattice point z − λkrk ∈ cone(r1,...,rk−1), which can be written as a nonnegative integer linear combination of elements from the Hilbert basis of this cone. The result now follows. (cid:3) This lemma implies the following fact, which excludes many regions when searching for missing Hilbert basis elements. Corollary 8. Let r1,...,rk ∈ Zn such that C′ = cone(r1,...,rk−1) has dimension n, and C = C′ + cone(r ). Suppose that r ∈/ C′. Moreover, let F ,...,F be the facets k k 1 q of C′ visible from r and let c ,...,c the normal vectors of these facets as introduced k 1 q above. Then H(C′)∪{r }∪ {H(F +cone(r )) : |c⊺r | ≥ 2, i = 1,...,q} k [ i k i k generates C ∩Zn. Proof. Evidently we obtain a system of generators of C ∩Zn if we extend the union in the proposition over all facets F , i = 1,...,q. It remains to observe that i ′ H(F +cone(r )) = {r }∪H(C ∩F ) i k k i if |c⊺r | = 1. But this is the statement of Lemma 7. (cid:3) i k Corollary 8 yields an extremely efficient computation of Hilbert bases—provided the case |c⊺r | ≥ 2 occurs only rarely, or, inother words, thesystem r ,...,r of generators i k 1 k is not too far from a Hilbert basis. A thoroughly consequent application of Corollary 8 could be realized as follows, col- lecting the list A(C) of critical simplicial cones in a recursive algorithm. (C1) Initially A(C) is empty. (C2) One searches the lexicographically first linearly independent subset {r ,..., i1 r }. If the cone generated by these elements is not unimodular, it is added to id A(C). (C3) Now the remaining elements among r ,...,r (if any) are inserted into the 1 s ′ algorithm in ascending order. Suppose that C is the cone generated by the elements processed already, and let r be the next element to be inserted. Then j for all facets F of C′ such that c⊺r ≥ 2 the list A(C) is augmented by A(F + i i k i cone(r )). j After all the critical simplicial cones have been collected, it remains to compute their Hilbert bases and to reduce their union globally, together with {r ,...,r }. 1 s Let us add some remarks on this approach. (a) It is not hard to see that the list A(C) constitutes a subcomplex of the lexi- cographical triangulation obtained by inserting r ,...,r . However, this fact is 1 s irrelevant for the computation of Hilbert bases. CHALLENGING COMPUTATIONS OF HILBERT BASES 9 semi-graph- 4×4×3 5×4×3 5×5×3 6×4×3 oid N = 5 emb-dim 40 47 55 54 32 dim 30 36 43 42 26 # rays 48 60 75 72 80 # HB 48 60 75 4,392 1,300 # supp hyp 4,948 29,387 306,955 153,858 117,978 # full tri 2,654,000 102,538,980 ? ? ? # partial tri 48 4,320 775,800 206,064 3,109,495 # cand 96 1,260 41,593 10,872 168,014 Table 1. Data of challenging Hilbert basis computations (b) In an optimal list of simplicial cones each candidate for the Hilbert basis of C would appear exactly once. (The candidates are the elements of the Hilbert bases of the simplicial cones.) The algorithm above cannot achieve this goal since the cones F +cone(r ) are treated independently of each other. Neverthe- j less it yields a reasonable approximation. (c) The drawback of the algorithm above is that it uses the Fourier-Motzkin elimi- nationrecursively forsubcones. Therefore Normalizapplies thealgorithmabove only on the top level and produces a full triangulation of the cones F +cone(r ) i k for which c⊺r ≥ 2 (instead of the list A(F +cone(r ))). i k i j (d) It is a crucial feature of the height 1 strategy that it reduces memory usage drastically. We illustrate the size of the computation and the gain of the improved algorithm by the data in Table 1. In the table we use the following abbreviations: emb-dim is the dimension of the space in which the cone (or monoid) is embedded, dim denotes its dimension, # rays is the number of extreme rays, # HB is the number of elements in the Hilbert basis, # full tri is the number of simplicial cones in a full triangulation computedbyNormaliz, #partialtriisthenumber ofconesinthepartialtriangulation, #candisthenumber of candidatesfor theHilbert basis, and#supphyp isthenumber of support hyperplanes. In addition to the improved algorithm just presented, parallelization has contributed substantially to the rather short computation times that (the experimental version of) Normaliz needs for the cones considered. The computations were done on a SUN Fire X4450 with 24 Xeon cores, but even on a single processor machine computation times would be moderate. Remark 9. Sturmfels and Sullivant [11, 3.7] stated a very interesting conjecture on the normality of cut monoids of graphs without K -minors. For graphs with 7 and 8 5 vertices we have used the approach via partial triangulations (and parallelization) in order to verify the conjecture. For these graphs no counterexample could be found. 10 W. BRUNS,R.HEMMECKE, B. ICHIM,M. KO¨PPE, ANDCH. SO¨GER References [1] 4ti2team.4ti2–Asoftwarepackageforalgebraic,geometricandcombinatorialproblemsonlinear spaces. Available at www.4ti2.de. [2] W.BrunsandJ.Gubeladze.Polytopes,rings,andK-theory.SpringerMonographsinMathematics (2009). [3] W. Bruns and B. Ichim. NORMALIZ. Computing normalizations of affine semigroups. With contributions by C. So¨ger. Available at http://www.math.uos.de/normaliz. [4] W. Bruns and B. Ichim. Normaliz: algorithms for affine monoids and rational cones. Preprint (2009), to appear in J. Algebra. [5] A. Durand, M. Hermann and L. Juban. On the Complexity of Recognizing the Hilbert Basis of a Linear Diophantine System. In: Proceedings of the 24th International Symposium on Mathe- matical Foundations of Computer Science, LNCS 1672 (1999), 92–102. [6] R. Hemmecke. On the computation of Hilbert bases of cones. In: Mathematical Software, ICMS 2002, A. M. Cohen, X.-S. Gao, N. Takayama (eds.), World Scientific, 2002, 307–317. [7] R.Hemmecke,A.Takemura,andR.Yoshida.Computingholesinsemi-groupsanditsapplication to transportation problems. Contributions to Discrete Mathematics 4 (2009), 81–91. [8] R. Hemmecke, J. Morton, A. Shiu, B. Sturmfels, and O. Wienand. Three counterexamples on semigraphoids. Combinatorics, Probability and Computing 17 (2008), 239–257. [9] T. Hibi and H. Ohsugi. Toric ideals arising from contingency tables. In: Commutative Algebra and Combinatorics.In: Ramanujan Mathematical Society Lecture Note Series 4 (2006), 87–111. [10] M. Studeny´. Probabilistic Conditional Independence Structures. Springer Series in Information Science and Statistics, Springer, London, 2005. [11] B. Sturmfels and S. Sullivant. Toric geometry of cuts and splits. Mich. Math. J. 57 (2008), 689–709 . [12] M.Vlach.Conditionsfortheexistenceofsolutionsofthethree-dimensionalplanartransportation problem. Disc. App. Math. 13 (1986), 61–78. WinfriedBruns,Universita¨tOsnabru¨ck,FBMathematik/Informatik,49069Osnabru¨ck, Germany E-mail address: [email protected] RaymondHemmecke,ZentrumMathematik,M9,TechnischeUniversita¨tMu¨nchen,Boltz- mannstr. 3, 85747 Garching, Germany E-mail address: [email protected] Bogdan Ichim, Institute of Mathematics, C.P. 1-764, 70700 Bucharest, Romania E-mail address: bogdan [email protected] Matthias Ko¨ppe, University of California, Davis, Department of Mathematics, One Shields Avenue, Davis, CA 95616, USA E-mail address: [email protected] ChristofSo¨ger,Universita¨tOsnabru¨ck,FBMathematik/Informatik,49069Osnabru¨ck, Germany E-mail address: [email protected]