Contents

1. Summary

We compute Markov bases of the binary (i.e. d_i = 2) hierarchical model of the complete bipartite graph K_3,N.

The proof of this theorem will take up Sections 2 to 5 of this manuscript. The proof will also give an explicit description of a Markov basis of K_3,N. In Section 6 we compare our theoretical bounds with Markov bases that were obtained with 4ti2 [1]. Both bounds are not sharp for N ≤ 3.

The proof relies heavily on the lifting machinery developped in [6]. All the notation and all the notions are explained in detail in that manuscript.

The idea of the proof is to use the fact that K_3,N is a toric fiber product of N copies of the three-star . The associated codimension zero product is a product of copies of the graph ₄ that arises from K₄ by filling the triangle {1, 2, 3} filled ( ). The calculation is complicated by the fact that the marginal cone of is not normal. However, it turns out that all holes are vertices of the projected fibers. This allows to treat the holes in a systematic way by adding additional inequalities to the inequality description of the projected fibers. We compute the holes in Section 2.

The set of holes is described in Section 2. This allows to describe the projected fibers and to calculate a PF Markov basis (Section 3). The liftings are computed in Section 4, where it is also shown that the degree of the glued moves is at most 12. Section 5 presents a kernel Markov basis of degree six. As it turns out, all moves from the kernel Markov basis are redundant except for the quadratic moves. The appendix contains the kernel Markov basis (Appendix A.1), the PF Markov basis (Appendix A.2) and the lifts (Appendix A.3) in tensor notation.

The results in this manuscript were obtained with the help of Normaliz [2], 4ti2 [1] and Macaulay2 [3]. This page contains links to files with code to reproduce the results.

2. The holes of ₄

In this section we study the set of holes of ℕ₄. The following lemma summarizes the most important properties:

The lemma follows from the observations made in the remainder of this section. A Macaulay2-program that does the calculations in this section can be found here.

A computation with Normaliz (input/output) shows that the Hilbert basis of the saturation of ℕ₄ contains two additional vectors h₁,h₂. Both restrict to the all-ones hole h on the K₄-marginals (that is, on all pair marginals). On the triangle-marginal, h₁ corresponds to XOR and h₂ corresponds to the opposite of XOR. They are the only fundamental holes, in the nomenclature of [4], as the following computations show:

Consider one of the fundamental holes h_i. According to [4], we need to do the following:

1. Find the minimal non-negative solutions (λ,μ) of h_i + λ = μ. This can be done, for example, using 4ti2’s command zsolve.

   Input: h1.mat/h2.mat, h1.rhs/h2.rhs, h1.sign/h2.sign.
   Output: h1.zinhom/h2.zinhom.

2. Drop the μ’s and interprete the λ’s (first half of the matrix) as the exponent vectors of monomials that generate a monomial ideal I.
3. Compute the standard monomials. In Macaulay2, this can be done using the command standardPairs.

The result is the following: Let

1	= (b0000,b1100,b1010,b0110,b0001,b1101,b1011,b0111),
2	= (b1000,b0100,b0010,b1110,b1001,b0101,b0011,b1111)

Consider the two linear forms

Therefore, each hole is either derived from h₁ or from h₂, that is, (h₁ + ℕ₁) ∩ (h₂ + ℕ₂) = ∅.

Each set _i is linearly independent. Hence different choices of the λ (or μ) give different holes. Moreover, also the vectors -marginals of _i are linearly independent for each i. Therefore, no two holes of the same type have the same -marginals. Therefore, no projected fiber contains more than one hole of the same type. A projected fiber can have one hole of each type, though (for example, the holes h₁ + ₁(1,…, 1)^t and h ₂ + ₂(1,…, 1)^t have the same pair marginals and lie in the same fiber).

Let h = h₁ + ₁λ be a hole. If v belongs to the same projected fiber as h, then v = ₁λ′ + ₂μ′ with λ′,μ′∈ ℕ⁸. As mentioned above, the -pair marginals of ₁ are linearly independent. Therefore, if μ′ = 0, then, since h and v have the same -marginals, h = v. Hence, if v≠h is not a hole itself, μ′≠0. It follows that l₂(m) > 0 = l₂(h).

3. The projected fiber Markov basis

By Lemma 2, every hole is a vertex of its projected fiber, supported either by l₁ or l₂. Thus we can do the following: We start with an inequality description of the semigroup ℕ₄. This gives us a set of valid inequalities Du ≥ c for each projected fiber. These inequalities are also valid for the holes. We augment the matrix D by two additional rows corresponding to l₁ and l₂ and denote the augmented matrix by D′. Then each projected fiber equals a solution set of linear inequalities of the form D′u ≥ c′. Therefore, any inequality Markov basis of D′ can be used as a PF Markov basis.

Each projected fiber is a subset of ℤ⁸, with basis e ₀₀₀,e₀₀₁,…,e₁₁₁. Let y₀₀₀,…,y₁₁₁ be the corresponding coordinates. In a projected fiber, there are relations

The columns of the corresponding matrix D spans a lattice, and 4ti2 computes its Markov basis (input/output). Since the first four rows of D form a unit matrix, D is easy to invert: The first four coordinates of the Markov basis of D give the PF Markov basis in the coordinates y₀₀₀,y₀₀₁,y₀₁₀,y₁₀₀. In tableau notation, PF Markov basis consists of the 16 moves, that are (up to symmetry; that is, up to a permutation of the columns) of the form

−,

−,

−.

4. Lifting the PF Markov basis

In this section we compute the lifts. We use the algorithm described in [6] to compute the lifting as an inequality Markov basis. Analyzing the results we find that the maximal degree of a glue of lifts is bounded by 12. The file lift.m2 contains Macaulay2 code that does the calculations in this section. It makes use of further routines from M2routines.m2.

First consider

If b = a, then g lifts to

−,

− and −.

Therefore, deg() ≤ 6.

If b = a, then g lifts to

−,

−, and −.

Therefore, deg() ≤ 6.

For

the lifts are (up to symmetry, exchanging the first two columns and state switching)

−, −

, −.

Therefore, deg() ≤ 12.

For

the lifts are (up to symmetry, exchanging the first two columns and state switching)

	−,		−,
	−,		−

Therefore, deg() ≤ 12.

5. The kernel Markov basis in tableau notation

The Markov basis of computed by 4ti2 has 20 elements of degrees four and six (input/output). In tableau notation, it consists of the following moves (up to symmetry, involving permuting the first three columns):

Recall that the kernel Markov basis consists of quadratic moves of the form

and lifts that can be constructed from the moves in the Markov basis of by adding constant columns in the tableau notation. The lifted moves have degree 4 and 6, and so the kernel Markov basis has degree 6.

Let us show that all lifted moves from the kernel Markov basis are redundant; that is: We only need the quadratic moves from the kernel Markov basis. In fact, consider, for example, a lift m of degree six. The glues of lifts of the PF Markov basis contain the quadratic moves of the form

and so on. Applying such quadratic moves reduces m to zero:

The quartic moves of the kernel Markov basis can be reduced similarly.

6. Comparison with computational results

For N ≤ 3, the Markov basis of K_3,N can be computed (within reasonable time) using 4ti2. The Markov degrees are:

These three computed degrees are much smaller than the theoretical bound of min{4 + 2N, 12}.

K_3,1 is a tree; hence the Markov degree is two. The additional moves obtained by lifting the PF Markov basis are not necessary. For a zero-fold toric fiber product it is no wonder that our bound is far from being tight.

A Markov basis of K_3,2 was computed in [5] by interpreting K_3,2 as a TFP of three two-stars. Here, we interprete these moves from the viewpoint of our above computations. The Markov basis of [5] consists of two kinds of quadrics and quartics. First, there are the codimension-zero quadrics. Second, the quadrics of the two three-stars glue together and yield further quadrics. Observe that the two interpretations of K_3,2 interchange the roles of the codimension-zero quadrics and the glued quadrics: The codimension-zero quadrics of K_1,2 ×′ K_1,2 ×′ K_1,2 correspond to the glued quadrics of K_3,1 × K_3,1, and vice versa.

The quartics are of the form

for some l_ij,m_ij ∈{0, 1}, modulo a permutation of the first three rows. All of these quadrics are glues of, say, m and m′. If either (a₀₀,b₀₀) = (a₀₁,b₀₁) or (a₁₀,b₁₀) = (a₁₁,b₁₁), then m is a quadric; that is

Otherwise, m is the quartic

That is, m is a lift of

A g of this form may be quadratic or quartic, depending on the (a_ij,b_ij). One can see that projecting the Markov basis of K_3,2 gives the full PF Markov basis. Therefore, the reason that the bound is not sharp is not that the PF Markov basis is too large, but that not all glues are necessary.

A. Intermediate results in tensor notation

In this appendix we present some of the above results in tensor notation. These results are straightforward translations of the output of 4ti2, without factoring out any symmetry or other structures, and so they should be considered as intermediate steps on the way from the raw 4ti2-output towards the form summarized above.

The tensor notation is as follows: Any state x ∈{0, 1}⁴ corresponds to a binary string x₀x₁x₂x₃, which can be considered as the binary representation of a natural number. The three least-significant bits correspond to the first group of nodes in K_3,N. Identifying the first 16 bitstrings with the letters from a to p, the states appear at the following positions:

A.1. The kernel Markov basis in tensor notation

The Markov basis of computed by 4ti2 has 20 elements of degrees four and six:

A.2. The projected fiber Markov basis in tensor notation

The PF Markov basis consists of the 16 2 × 2 × 2-tableaus

A.3. Lifting in tensor notation

This Section contains the lifts in the raw form, as found by 4ti2.

For

there are ten lifts:

For

there are six lifts:

For

there are 21 lifts: