Higher connectivity of fiber graphs
of Gröbner bases
arXiv:1209.1533v2 [math.CO] 31 Jan 2013

Samu Potka
Abstract
Fiber graphs of Gröbner bases from contingency tables are important in statistical hypothesis testing, where one studies random walks
on these graphs using the Metropolis-Hastings algorithm. The connectivity of the graphs has implications on how fast the algorithm
converges. In this paper, we study a class of fiber graphs with elementary combinatorial techniques and provide results that support a
recent conjecture of Engström: the connectivity is given by the minimum vertex degree.

1

Introduction

We will study a class of graphs coming from Gröbner bases related to the twoway n×n contingency tables with equal row and column sums. By summing
the entries of the tables both row-wise and column-wise, it is easy to see that
the n×n tables are the only ones that can satisfy this property. Let G(n, r) be
a graph whose vertices are the n×n-matrices of non-negative integers with all
row and column sums r. Two vertices are adjacent if one can move between
the corresponding matrices by adding one to two entries and subtracting
one from two others. As an example, consider the graph G(3, 2), drawn in
Figure 1.1. The vertices are the 3×3-matrices of non-negative integers with
row and column sums two. The graph G(n, r) is the underlying undirected
graph of a fiber graph of a reduced Gröbner basis and the edges correspond
to Markov moves. After stating our main result, we shortly review the basics
of algebraic statistics.
To state our main result, we need to mention some standard definitions
from graph theory. The degree d(v) of a vertex v in G is the number of edges
at v. The minimum degree δ(G) of a graph G is the smallest of the degrees
in the graph. A graph G is k-connected, k ∈ N, if |G| > k and G − X is

1




0 1
0 1 
2 0




1 0
0 2 
1 0

1
 1
0



0
 2
0


0 0
 1 1
1 1


0
 0
2

0
2
0

1
 0
1


1
 0
1


0
 1
1
0 1
 0 1
2 0


2
0 
0


2
0 
0


2
0 
0


0
0
2

1
0
1


1
1 
0


1
1 
0
0
 0
2

2
0
0


0
2 
0

1 0
 1 1
0 1
1
 0
1

0
 1
1

2
 0
0









0 1
1 1 
1 0




1 1
0 0 
1 1




2 0
0 1 
0 1

0
 1
1

2 0
 0 1
0 1
1
 1
0

1 1
 0 1
1 0








0
 2
0


1
0 
1


0 1
2 0 
0 1


1 1
1 0 
0 1


0 0
0 2 
2 0


1 0
0 1 
1 1


0
1 
1



2 0
 0 2
0 0


1 1
 1 1
0 0


0
 2
0


0
1 
1

0
0 
2


0
0 
2


2 0
0 0 
0 2

Figure 1.1: The graph G(3, 2).
connected for every set X ⊆ V (G) with |X| < k. The connectivity κ(G) of a
graph G is the largest k such that G is k-connected.
The Metropolis-Hastings algorithm can be used for statistical tests for
contingency tables. The algorithm performs a random walk on the fiber graph
containing the contingency table we want to study [2]. The connectivity of
the fiber graphs affects the convergence of the algorithm: typically, the lower
the connectivity, the slower the convergence [6]. Our main result is:

Theorem 2.9. The connectivity κ(G(n, r)) = n2 for r > 2.

We also prove several other statements regarding G(n, r). The proof of
the main result is based on Liu’s criterion [8], proved, for example, in [1]:
Lemma 2.8 (Liu’s criterion). Let G be a connected graph and |V (G)| > k.
If for any two vertices u and v of G with distance dG (u, v) = 2 there are k
disjoint u − v paths in G, then G is k-connected.

For the first time, the following conjecture is confirmed for a large class
of fiber graphs of an important and common class of Gröbner bases.
Conjecture (Engström ’12, [5][9]). The connectivity of a large fiber graph
of a reduced Gröbner basis of a lattice ideal is given by the minimum vertex
degree of the fiber graph.
2

The technical version of the conjecture with the condition of a large fiber
graph is spelled out in the appendix.

1.1

The basics of algebraic statistics

Let us review the basics of algebraic statistics. See the foundational paper
[2] or the textbook [4] for an introduction to the field.
Fix an integer matrix A ∈ Zd×n whosePcolumn sums are equal. The
probability simplex is ∆n−1 = {p ∈ [0, 1]n : ni=1 pi = 1}. Let MA = {p ∈
∆n−1 : log p ∈ rowspan(A)} be the log-linear model associated with the
matrix A. The vector Au is the minimal sufficient statistic for MA and
F(u) = {v ∈ Nn : Av = Au} the fiber of a contingency table u, represented
in a vectorized form. Let kerZ (A) be the integer kernel of the matrix A. The
finite set B ⊂ kerZ (A) is a Markov basis
PL exists a sequence
PL for MA if there
0
u1 , ..., uL ∈ B such that v = v + k=1 uk and v + k=1 uk ≥ 0 for all
l = 1, ..., L; all contingency tables u and all pairs v, v 0 ∈ F(u). The elements
of the Markov basis are called Markov moves.
Another way of describing Markov bases is via finite subsets of lattices.
In this case, we are interested in the integer lattice kerZ (A), where A is the
matrix associated with the log-linear model. The fiber F(u) of u ∈ Nn , for
example, a contingency table in vectorized form, is the set {v ∈ Nn : u − v ∈
L}, where L is a lattice. Note that if L = kerZ (A), this definition is exactly
the same as the definition of the fiber of a contingency table mentioned
earlier. Let B be an arbitrary finite subset of L. The subset determines
an undirected graph F(u)B whose vertices are the elements of F(u). Two
vertices v and v 0 are connected by an edge if either v − v 0 or v 0 − v is in B.
The subset B is a Markov basis of L if the graphs F(u)B are connected for
all u ∈ Nn . Fix a weight vector w ∈ Rn such that b · w < 0 for all b ∈ B.
The graph F(u)B is an acyclic directed graph if the edges are now directed:
v → v 0 , and present whenever v 0 − v is in B. We call B a Gröbner basis
of L if F(u)B has a unique sink for all u ∈ Nn . Then, F(u)B is called a
fiber graph of a Gröbner basis. It is important to note that since our focus is
on algebraic statistics and Markov bases, we undirect the edges of the fiber
graphs of Gröbner bases and discuss ordinary connectivity instead of strong
connectivity of directed graphs.
It is fruitful to view the previous notions from the standpoint of commutative algebra as well. A lattice L ⊂ Zn can be represented by the lattice
ideal IL = hpu − pv : u, v ∈ Nn , u − v ∈ Li ⊂ R[p1 , ..., pn ]. IL is a toric ideal.
We can write b = b+ − b− with non-negative b+ and b− for every b ∈ L.
The following result is considered one of the starting points for algebraic
statistics:
3

Theorem 1.1 (The fundamental theorem of Markov bases, [2]). A subset
B of the lattice L is a Markov basis if and only if the corresponding set of
+
−
binomials {pb − pb : b ∈ B} generates the lattice ideal IL .
In the case of two-way contingency tables, the sufficient statistic is the row
and columns sums of the tables and the matrix A is chosen correspondingly.
Since we consider the case of equal, fixed row and column sums, all tables
are in the same fiber. The integer kernel of A has a Markov basis whose
2
cardinality is 2 n2 , namely B = {±(eij + ekl − eil − ekj ) : 1 ≤ i < k ≤ n, 1 ≤
j < l ≤ n}, where eij denotes the matrix which has one in the position
(i, j) and zeroes elsewhere. This is exemplified in [2], and for an explicit
proof of a more general result which implies it, see [4]. By Theorem 1.1,
+
−
{pb − pb : b ∈ B} generates the lattice ideal IL . One can verify that
the Markov basis gives a Gröbner basis by the cost vector with (r + c)2 for
the element on row r and column c. Since we need to have b · w < 0, the
generators need to be of the form −(eij + ekl − eil − ekj ). The reason why the
corresponding fiber graph has a unique sink is that the moves of this form
are not possible from the anti-diagonal contingency table. The fact that this
Gröbner basis is reduced is justified, for example, in Chapter 5 of [10]. As
mentioned earlier, for the purposes of this paper, we undirect the edges of
the fiber graph of the Gröbner basis. This means that the edges in our graph
G(n, r) correspond exactly to the elements of the Markov basis B, Markov
moves.

1.2

Basic notation of graph theory

Next, we define a number of basic notions for graphs following those in [3].
Let G be a graph, V (G) be the vertex set of G and |G| = |V (G)|. The
degree d(v) of a vertex v in G is the number of edges at v. The minimum
degree δ(G) of a graph G is the smallest of the degrees in the graph and the
maximum degree ∆(G) the largest. We call a graph G k-connected, k ∈ N,
if |G| > k and G − X is connected for every set X ⊆ V (G) with |X| < k.
The notation G − X means a graph with the vertex set V (G) − X and edges
of G such that their endpoints are in V (G) − X. A subgraph of this type is
called an induced subgraph of G. By Menger’s Theorem [3, p. 71], a graph is
k-connected if and only if it contains k independent (in other words, vertexdisjoint) paths between any two vertices. We will use disjoint as a synonym
of independent. The connectivity κ(G) of a graph G is the largest k such that
G is k-connected, the distance dG (u, v) between two vertices u and v of G is
the number of edges in a shortest u − v path in G, and the diameter diam(G)
of G is defined as the largest distance in G. The graph G is r-regular if,
4

all its vertices have the same degree r. If V (G) admits a partition into two
classes such that the vertices in the same class are not adjacent, G is called
a bipartite graph. A matching M in G is a set of independent edges and it
is called perfect if every vertex of G is incident to exactly one edge in M .
A multigraph is a pair (V, E) of disjoint sets together with a map E 7→ [V ]2
that assigns two vertices to each edge. Here E denotes the set of edges. A
multigraph differs from an ordinary graph by allowing several edges between
the same two vertices. As opposed to the definition in [3], our definition
does not allow self-loops, edges that start from and end to the same vertex.
The entry aij of the adjacency matrix A of a multigraph is the number of
edges from the vertex i to the vertex j. We define the biadjacency matrix of
a bipartite multigraph as the submatrix of the adjacency matrix, where the
columns correspond to the vertices in a bipartition class of the vertex set and
rows to the vertices in the other class.

2

The fiber graphs

The first results are on the degree of the vertices of G(n, r). The degree
d(v) of v ∈ V (G(n, r)) is exactly the number of Markov moves that can be
performed from v. From here on, a move means a Markov move. Recall that
here the set of Markov moves is the Markov basis
B = {±(eij + ekl − eil − ekj ) : 1 ≤ i < k ≤ n, 1 ≤ j < l ≤ n}.
Thus, we want to calculate the number of unordered pairs
{vi1 j1 , vi2 j2 : vi1 j1 , vi2 j2 > 0, i1 6= i2 , j1 6= j2 }.
If we have such a pair, the entries vi2 j1 and vi1 j2 cannot be r, and the move
ei1 j2 + ei2 j1 − ei1 j1 − ei2 j2 must then be possible from v. We define the support
of a vertex v ∈ V (G(n, r)) as the set
supp(v) = {(i, j) : i, j ∈ N, 1 ≤ i, j ≤ n, vij 6= 0}.
Note that the cardinality of supp(v) is the number of positive entries in v.
Lemma 2.1. Let v ∈ V (G(n, r)),
(a) if v has r as its only positive entries, then d(v) = δ(G(n, r)) =
(b) if v does not have r as its only positive entries, then d(v) ≥
n
+ n − 1.
2
5


.

n
2

(n+2)(n−1)
2

=

Proof. Part a). Since there are exactly n nonzero
entries in v, all of them

in different rows and columns, there are n2 pairs {vi1 j1 , vi2 j2 : vi1 j1 , vi2 j2 >
0, i1 6= i2 , j1 6= j2 }. Thus, d(v) = n2 . To prove that d(v) is in this case the
minimum degree, we need to prove part b) of this lemma.
Part b). Consider starting from a vertex that has r as its only positive
entries, and therefore support of size n, and using a Markov move to get to
v. Now, because we must have r > 1, the size of the support must grow by at
least two in the process. Therefore, the size of supp(v) is at least n + 2. The
pair {vi1 j1 , vi2 j2 : vi1 j1 , vi2 j2 > 0, i1 6= i2 , j1 6= j2 } can be picked in (n+2)(n−1)
2
ways, because the row i1 and column j1 cannot contain any r-entries if vi1 j1
is positive, and there are n − 1 other rows and columns which then need to
contain positive entries. Hence, there are at least (n+2)(n−1)
Markov moves
2

(n+2)(n−1)
n
from v, and d(v) ≥
= 2 + n − 1.
2
Using the definition of connectivity with X = {v}, v being the vertex with
all positive entries equal to r, we get the following result as an immediate
implication of Lemma 2.1.

Proposition 2.2. The connectivity of G(n, r) satisfies κ(G(n, r)) ≤ n2 .

Proposition 2.3. If V (G(n, r)) contains a vertex v that has one as its only
positive entries, then ∆(G(n, r)) = d(v) = nr(nr−2r+1)
.
2
Proof. If r = 1, we are done by Lemma 2.1 and the fact that all the vertices
need to be of this type. Thus, assume r > 1. There has to be nr one-entries.
Say that one of them is in the position (i1 , j1 ). The row i1 and column
pairs
j1 contain 2r − 1 other one-entries. Therefore, there are nr(nr−2r+1)
2
{vi1 j1 , vi2 j2 : vi1 j1 , vi2 j2 > 0, i1 6= i2 , j1 6= j2 }. All of these pairs correspond to
a different Markov move from v, and thus d(v) = nr(nr−2r+1)
. Because the
2
row and column sums are r and we have an n × n-matrix, |supp(u)| ≤ nr for
any u ∈ V (G(n, r)). The equality corresponds to the case where the positive
entries are all ones. Thus, if there is at least one >one-entry in u, the number
of positive entries is less than nr. Then, we can pick ui1 j1 in less than nr
ways. We claim that d(u) < d(v). If n = 2, we are done by Lemma 2.1. Let
n ≥ 3, and start from v. Perform a Markov move ei01 j10 + ei02 j20 − ei01 j20 − ei02 j10
from v to u so that an entry ui01 j10 > 1. If we would pick ui1 j1 = ui01 j10 ,
the entry ui2 j2 in the pair {ui1 j1 , ui2 j2 : ui1 j1 , ui2 j2 > 0, i1 6= i2 , j1 6= j2 }
could be chosen in at most one more way than vi2 j2 for the corresponding
vi1 j1 , because by our assumption, only ui02 j20 can be both positive and such
that its position, (i02 , j20 ), is not in the support of v. For any other ui1 j1 ,
the number of pairs ui2 j2 can only decrease or stay the same, since we can
assume that (i01 , j20 ) and (i02 , j10 ) are in the support of v but not in the support
6

of u. Moreover, since n ≥ 3, r > 1 and we assume that vi01 j20 = vi02 j10 = 1, if
vi02 j20 = 0 there is a positive entry of u such that it is in the row i02 but not
in the column j20 . If the pick ui1 j1 is that entry, by our assumption there is
one less possible pair ui2 j2 for ui1 j1 than a pair vi2 j2 for the corresponding
vi1 j1 , because ui01 j20 = 0, but vi01 j20 = 1. On the other hand, if vi02 j20 > 0,
the number of pairs {ui1 j1 , ui2 j2 : ui1 j1 , ui2 j2 > 0, i1 6= i2 , j1 6= j2 } where
ui1 j1 = ui01 j10 does not change while moving from v to u. As we iterate the
process from u, similar arguments hold. Thus, because we could pick ui1 j1
in less than nr ways, d(u) < d(v) and ∆(G(n, r)) = nr(nr−2r+1)
. Therefore,
2
nr(nr−2r+1)
d(v) = ∆(G(n, r)) =
.
2
Note that when n < r, there is no such v with all positive entries equal
to one. Nevertheless, the maximum degree obtained is an upper
 bound for
the vertex degree in that case as well. Thus, we know that n2 ≤ d(G) ≤
nr(nr−2r+1)
. Now, having information on how the degree of the vertices of
2
G(n, r) behaves, we try to find the connectivity κ(G(n, r)). First, we will
introduce a couple of auxiliary results:
Lemma 2.4. The number of same
Markov moves M from u, v ∈ V (G(n, r))

n
with dG (u, v) ≤ 2 is at least 2 for r > 2.

Proof. Because dG (u, v) ≤ 2 and r > 2, |supp(u) ∩ supp(v)| ≥ n. We want
to know whether at least n2 pairs of those positions are usable by a Markov
move M . Those positive entries in u that are not in the support of v must
equal 1 or 2. Then, because r > 2, there has to be entries ei satisfying
1 ≤ ei ≤ r − 1, at least one in the same column and one in the same row
as such an entry. In general, each of the columns not containing an ei has
to contain a positive entry as well. Having a positive entry in a particular
column means that there cannot be an r-entry in the same row. Thus, there
is a positive entry not in this row in each of the other columns. We can
choose
 a pair {(i1 , j1 ), (i2 , j2 ) : i1 6= i2 , j1 6= j2 } ⊂ supp(u) ∩ supp(v) in total
n
in 2 ways by first selecting one of the n columns and then one of the (n − 1)
other columns.

Theorem 2.5 (Kőnig, [7]). Every r-regular bipartite multigraph decomposes
into r perfect matchings.
Let En (i, j) be the n×n-matrix with all entries 0, except for that position
(i, j) is 1.
Lemma 2.6. Let u be a vertex of G(n, r) and (i1 , j1 ), ..., (ik , jk ) positions in
an n×n-matrix such that u ≥ En (i1 , j1 ) + ... + En (ik , jk ), and k ≤ r. Then
there is a decomposition of u into a sum of matrices u1 + ... + ur that are
7

vertices of G(n, 1) such that u1 + ... + ul ≥ En (i1 , j1 ) + ... + En (il , jl ) for all
1 ≤ l ≤ k.
Proof. The proof is by induction on k. For k = 0 we are done. According to
Theorem 2.5, every r-regular bipartite multigraph decomposes into r perfect
matchings. Interpreting u as the biadjacency matrix of an r-regular bipartite
multigraph, we get a decomposition into matrices u1 + ... + ur with row
and column sum 1. Assume that we have indexed the matrices such that
(u1 )i1 ,jP
1 > 0. Let L be a maximal subset of {1, 2, .., k} with 1, such that
u1 ≥ l∈L En (il , jl ). By induction we can find a decomposition of u − u1
admitting the conditions for {(il , jl ) | l ∈ {1, 2, .., k} \ L}, and then we extend
it.
It might be of interest to the reader that the previous result, Lemma 2.6,
implies that the semigroup generated by permutation matrices is a normal
cone.
Proposition 2.7. The graph G(n, r) is connected.
Proof. The graph G(n, r) is the underlying undirected graph of a fiber graph
of a Gröbner basis, and therefore connected.
Lemma 2.8 (Liu’s criterion, [8]). Let G be a connected graph and |V (G)| >
k. If for any two vertices u and v of G with distance dG (u, v) = 2 there are
k disjoint u − v paths in G, then G is k-connected.
A proof of Lemma 2.8 can be found in [1]. With these tools, we can set
out to prove our main result:

Theorem 2.9. The connectivity κ(G(n, r)) = n2 for r > 2.

n
Proof. By Proposition
2.2,
κ(G(n,
r))
≤
. Therefore, our goal is to show
2

that G(n, r) is n2 -connected. We aim to achieve this by applying Proposition 2.7 and Lemma 2.8 as well as a technique of building a large number of
paths. We need to show that using the technique, we will in every case get
at least n2 independent paths. It turns
 out that the technique used will not
n
work in the cases r < 3. If n = 2, 2 = 1. By Proposition 2.7, G(n, r) is
connected and the case n = 2 is done. Thus, we assume from now on that
n ≥ 3.
We will start by setting up the machinery. By Proposition 2.7, we can
apply Lemma 2.8. Let u, v ∈ V (G(n, r)) with dG (u, v) = 2. Then there are
Markov moves ∆1 and ∆2 such that u + ∆1 + ∆2 = v. Because dG (u, v) =
2, ∆1 + ∆2 does not correspond to a single move. Now, let us consider
the sequences M, ∆1 , ∆2 , −M , where M is an additional move, such that
8

u + M + ∆1 + ∆2 − M = v, as depicted in Figure 2.1. Let cM be the number
of ways to select
 M so that we get disjoint paths. We
 want to show that cM
n
n
is at least 2 − 1. Then we would have in total 2 disjoint paths between
u and v when we count the original path of length two as well. Note that
the move M has to be a valid Markov move from u. By valid, we mean that
the move does not take entries of u negative (or correspondingly, larger than
r). In other words, the move M needs to connect u to another vertex in the
graph. The term possible move is used as a synonym for valid move.

Figure 2.1: The types of paths considered in the proof with the directions
corresponding to the signs of the moves.
There are some remarks to be made:
• We must have M 6= ∆1 , because M = ∆1 would lead to an intersection.
For the same reason, we need M 6= −∆2 .
• If we can use M = ∆2 or M = −∆1 , we have u+∆2 +∆1 = v. However,
if both of them are valid Markov moves from u, we have to subtract
one from cM , because then the paths with M = ∆2 and M = −∆1
intersect.
• On the other hand, if the move M = ∆2 is not valid, the path using
M = −∆1 does not connect u and v.
• If r = 1, the entries ∆1 subtracts from are not usable by M. By
Lemma 2.1, in that case each of the vertices have the degree n2 , and
thus this method does not apply, because we will not get enough ways
of choosing M .
• If r = 2, M, ∆1 and ∆2 cannot have even one same entry where they
subtract from, again problematic
in the cases where we start from a

n
vertex with the degree 2 . Then we cannot get the desired result using
solely this procedure. For simplicity, assume r ≥ 3.
9

The basic case. Let us first assume that M can subtract from the same entries
as ∆1 and ∆2 . By this, we mean that the entries are large enough that we
do not have to worry whether using M before ∆1 and ∆2 causes an entry to
be negative after performing M + ∆1 or M + ∆1 + ∆2 . Consider ∆1 = ∆2 .

n
• We have at
least
−1 ways of choosing M such that M 6= ∆1 , because
2

d(u) ≥ n2 by Lemma 2.1.
• If it is even possible to select M = −∆1 , some nonzero-entries of u are
not
 r, and by Lemma 2.1, the degree of the vertex we are at is at least
n
+ n − 1. Therefore, after subtracting
the disallowed
moves M = ∆1
2


and M = −∆1 , we have cM ≥ n2 + n − 3 ≥ n2 in this case, because
n ≥ 3.

However, we also have to take the case ∆1 6= ∆2 into account.

• If M = ∆2 is possible, but d(u) = n2 , M = −∆2 is not possible.
Therefore, the previous results hold in this case as well.
• If also M = −∆1 is possible
as well as M = −∆2 , by the earlier

n
analysis
we
get
c
≥
−
1,
because with our assumption n ≥ 3,
2

M
n
n
+ n − 4 ≥ 2 − 1.
2

• If on the other hand M = ∆2 is not possible, we want to know whether
the possibility M = −∆2 is included in d(u). If the number of entries
of ∆2 that prevent its use is at least two, ∆1 must be −∆2 , because
∆2 will then subtract from entries zero in u ∆1 adds to. However,
there is no point in this. Therefore, consider that ∆2 has only one
entry obstructing its use. Then ∆2 subtracts from an entry zero in u,
which implies that ∆1 has to add to that entry, but then −∆1 would
subtract from the entry. Thus, M = −∆1 is not included in d(u).
If M = −∆2 is to be possible, by Lemma 2.1, we need to be at u
with d(u) ≥ n2 + n − 1, because otherwise we would subtract from
an r-entry
 with ∆2 , nbut
 then we would add to a zero-entry. Then
n
cM ≥ 2 + n − 3 ≥ 2 . Otherwise weonly need to avoid M = ∆1 and
have cM ≥ n2 − 1, because d(u) ≥ n2 by Lemma 2.1.

Problematic entries. Let us now move on to the cases where M cannot subtract from all the entries where ∆1 and ∆2 . Then, the moves ∆1 and ∆2
subtract from entries smaller than two in u. The number of this kind of
problematic entries can range from one to four. By Lemma 2.4, the number
of same Markov moves M from u and v must be at least n2 .
10

• First, say that ∆1 + ∆2 subtracts from either four or three one-entries
or two or one two-entry. Then the choices of moves at v do not include
∆1 or ∆2 . We have to avoid −∆2 , and thus cM ≥ n2 − 1.

• If ∆1 and ∆2 subtract from three one-entries in total, but the sum
∆1 +∆2 does not, there are six different cases: either ∆1 or ∆2 subtracts
from two one-entries, and ∆1 , ∆2 or both add to an entry the other
subtracts from. If ∆1 subtracts from two one-entries, the moves ∆1
and ∆2 are clearly not possible at v. Then we have cM ≥ n2 − 1. The
same thing happens when ∆2 subtracts from two one-entries and ∆2
does not add to an entry ∆1 subtracts from. In the two cases left, we
cannot rely on Lemma 2.4.
• If ∆1 and ∆2 subtract from a total number of two one-entries, we either
have the other one subtracting from two or both subtracting from one.
In the latter case, if neither of them or only ∆1 adds to an entry the
other subtracts from, ∆1 and ∆2 are not possible at v. Hence, in this
case as well, we have cM ≥ n2 − 1.

The cases left are: only ∆1 or ∆2 subtracts from one-entries; ∆1 subtracts
from one one-entry, while ∆2 subtracts from at least one different one-entry
but adds to the one-entry ∆1 subtracts from.

• If ∆1 subtracts from one one-entry, u ≥ En (i, j) where (i, j) is the
position of that particular one-entry. Following Lemma 2.6, decompose
u: u = u1 +...+ur = u1 +u0 , where u1 ≥ En (i, j) and u0 ∈ V (G(n, r−1)).
The one-entry in the position (i, j) in u is now zero in u0 . Because u
has one one-entry, it must have at least another. The second one-entry
can either be in
u1 or u0 . If it is in u1 , d(u0 ) ≥ n2 , and if it is in

u0 , d(u0 ) ≥ n2 + n − 1 by Lemma 2.1. In the former case we get
cM ≥ n2 + (n − 2) − 2 ≥ n2 − 1, where n2 comes from the moves for
u0 and (n − 2) from the moves using the one entry
 not problematic
 in u
n
n
now in u1 . In the latter case we have cM ≥= 2 +(n−1)−2 ≥ 2 . We
subtract two in both cases to avoid counting M = −∆1 and M = −∆2 .
• If ∆1 subtracts from two one-entries at positions (i1 , j1 ) and (i2 , j2 ),
u ≥ En (i1 , j1 ) + En (i2 , j2 ), and we decompose u = u1 + u2 + u0 , where
u0 ∈ V (G(n, r − 2)) and u1 + u2 ≥ En (i1 , j1 ) + En (i2 , j2 ). Thus, the
problematic entries are zero in u0 , and therefore also the move ∆1 is
not possible from u0 . If d(u0 ) = n2 , −∆1 isnot included in d(u0 ), and
we have cM = n2 − 1. Otherwise d(u0 ) > n2 , and we get cM ≥ n2 − 1.
11

• If ∆2 subtracts from one-entries some of which are also in u, the case is
treated exactly the same way as the two previous ones. If the particular
one-entries are not in u, M cannot subtract from them and thus there
is nothing to avoid.
• The case where ∆1 subtracts from one one-entry and ∆2 subtracts
from one or two different one-entries, but ∆2 adds to the one-entry ∆1
subtracts from and at most one of the one-entries ∆2 subtracts from
is present in u already, is treated exactly same way as the previous
ones, because we have to avoid one or two problematic one-entries.
If there are two problematic entries both already in u, they can be
avoided the same way as before. If there are three of them, all present
in u at positions (i1 , j1 ), (i2 , j2 ) and (i3 , j3 ), we have u ≥ En (i1 , j1 ) +
En (i2 , j2 ) + En (i3 , j3 ). Say that the two first are the ones used by ∆2 .
They can be put in the same u1 in the proof of Lemma 2.6. Then we
have u = u1 + u2 + u0 , where u0 ∈ V (G(n, r − 2)). The problematic
entries are zero in u0and the moves ∆1 and ∆2 are not possible from
u0 . Then d(u0) ≥ n2 only includes the disallowed choice M = −∆2 .
Thus cM ≥ n2 − 1.

Intersections. The last question is what if different paths M + ∆1 + ∆2 −
M and M 0 + ∆1 + ∆2 − M 0 intersect. By symmetry and straightforward
calculations, the number of cases reduces to three: M 0 − M = ∆1 ; M 0 − M =
∆2 ; M 0 − M = ∆1 + ∆2 . The different types are drawn in Figure 2.2:

Figure 2.2: The possible types of intersection.
The last case is the easiest to handle. Assume that we only have intersections of this type. An intersection can happen in two different ways.
• The moves ∆1 and ∆2 share one entry the other adds to and the other
subtracts from. This sum can be written in three ways, one being the
original, because M and M 0 have to be Markov moves, both have to
12

use three of the operations in ∆1 + ∆2 and the cancelling operations
can be done to three different entries. Therefore, this case amounts to
two intersections. Let us a write an example to illustrate this:

 

1 −1 0
0
0
0
1 0  +  0 −1
1 
∆1 + ∆2 =  −1
0
0 0
0
1 −1

 

0 0
0
1 −1 0
1 + 0
0 0 
=  −1 0
1 0 −1
−1
1 0

 
 

1 0 −1
0 −1
1
1 −1
0
1 + 0
0
0  =  −1
0
1 .
=  −1 0
0 0
0
0
1 −1
0
1 −1
• The other possibility, disjoint from the previous one, is that the positions of the non-zero rows or columns of ∆1 and ∆2 are the same.
Then there are two ways, the original and another with swapped rows,
to write the sum ∆1 + ∆2 . This gives one intersection. Again, let us
do a basic example:

 

1 −1 0 0
0
0 0 0
 −1

1 0 0 
0 0 0 
+ 0

∆1 + ∆2 = 
 0
1 0 0 
0 0 0   −1
0
0 0 0
1 −1 0 0

 

0
0 0 0
1 −1 0 0
 −1

1 0 0 
0 0 0 
+ 0
.
=
 0
0 0 0   −1
1 0 0 
1 −1 0 0
0
0 0 0
To analyse how these affect the earlier calculations, we have to first note
that the entries ∆1 + ∆2 subtracts from must be at least two, because we
want to subtract from the same entries with M and M 0 . Only one of the two
types is possible at a time.
• In the former case, there are two possibilities: either one or two intersections are possible. Let us first consider the case of one intersection. If −∆2 (or −∆1 if the order of the moves is switched) is to
be included in d(u), we must have d(u) > n2 + n − 1, because there
has to be
entries in one column, and therefore
 at least three positive

n
n
cM > 2 + n − 1 − 4 ≥ 2 − 2. The −4 comes from three disallowed
moves and one intersection. If not, the degree is at least n2 + n − 1 by
13



Lemma 2.1, which means we have cM ≥ n2 + n − 4 ≥ n2 − 1. Now,
assume that there are two intersections. The sum ∆1 + ∆2 shows that
there must be at least three positive entries in the 3 × 3-submatrix.
However, when we write the sum in another way, the other move is
−M . Thus, there has to be three additional positive entries, because
in the different cases, M subtracts in total from at least two of the oneentries in ∆1 +∆2 and one other entry. Hence, the support of u has size
at least n + 3. If we pick a positive entry from the 3 × 3-submatrix to
be subtracted from by a Markov move, and the entry is such that four
of the other five positive entries are on its row or column, the selection
of the second positive entry can be done in n − 1 ways, because there
cannot be r-entries in the row or column of the first entry. Clearly,
if we pick the first entry in a different way, there are cases where the
second selection can be done in even more
ways, but no cases where

n
−
5
≥
−
2,
because n ≥ 3. The −5
in less. Thus, cM > (n+3)(n−1)
2
2
comes from three disallowed moves and two intersections.

• In the latter case, d(u)
must be at least n2 + n − 1 by Lemma 2.1,

and we have cM ≥ n2 + n − 1 − 4 ≥ n2 − 1, because we must have
n ≥ 4. We subtract four, because there are at most three disallowed
moves and one intersection.
In the two other cases we have M 0 and M sharing one non-zero row or
column, which disappears in the sum M 0 + (−M ). An example is presented
below:

 
 

1 −1 0 0
0
0 0 0
1 −1 0 0
 −1


1 0 0 
1 0 0 
0 0 0 
 =  −1
+ 0

∆=
 0




0 0 0
0
0 0 0
0
0 0 0 
0
0 0 0
1 −1 0 0
−1
1 0 0

 

1 0 −1 0
0 −1
1 0
 −1 0


1 0   0
1 −1 0 
 = M 0 + (−M ).
=
+
 0 0
0 0   0
0
0 0 
0 0
0 0
0
0
0 0

We assume that either ∆1 or ∆2 causes intersections, and denote the one
causing them with ∆. Let the other one be ∆0 . Because M 0 and −M share
one row with ∆, ∆ also adds to a positive entry, because M needs to subtract
from that. Let the position of that entry be (i1 , j1 ).
• Assume that at least one of the entries ei ∆0 subtracts from satisfies
1 ≤ ei ≤ r − 1. Then there must be at least one positive entry in the
14

same column and one in the same row. If they are both in the row
i1 and column j1 , ei is in the position (i1 , j1 ). Otherwise, we can find
1-entries that do not use the row i1 and the column j1 for each ei ∆0
subtracts from satisfying 1 ≤ ei ≤ r − 1. Denote them with (i2 , j2 ) and
(i3 , j3 ). It might be that (i3 , j3 ) does not exist or (i2 , j2 ) = (i3 , j3 ). We
have u ≥ En (i1 , j1 ) + En (i2 , j2 ) + En (i3 , j3 ). They can all be put in the
same u1 ∈ V (G(n, 1)) in the construction of the proof of Lemma 2.6.
Thus, by Lemma 2.6, we have u = u1 + u0 , where u1 is such that it
does not contain the
entries at most r − 1 ∆ or ∆0 subtract from.

Because d(u1 ) = n2 , and the choices M = ∆1 and
 M = ∆2 as well as
n
intersections are avoided in u1 , we have cM ≥ 2 − 1.

• Now, assume that both of the entries ∆0 subtracts from are r. As
before, decompose u = u1 + u0 using Lemma 2.6. This time, we cannot
avoid the entries used by ∆0 , but they will surely be large enough to be
usable by M . Again, u1 does not contain the entries subtracted from
by ∆. Hence, we cannot have intersections of the other type occuring
with moves from u1 and have to only avoid M = −∆1 , because ∆2
adds to zero-entries,
and thus M = −∆2 is not included in d(u1 ). We

n
have cM ≥ 2 − 1.

In the latter case, ∆0 cannot cause intersections because of the assumption
that ∆0 subtracts from r-entries, but in the former case it could. Because the
entries ∆0 subtracts from are in u0 , the calculations hold even if intersections
of the type M 0 − M = ∆0 are assumed possible.
The last result in this paper concerns the diameter of G(n, r):
Proposition 2.10. The diameter of G(n, r) is (n − 1)r.
Proof. Every row sum is r, and each of the positive entries can be selected to
be subtracted from. Therefore, r changes are enough to transform a row to
any other. The n:th row must be correct at least after changing the (n−1):th
row, because otherwise we would have to change an already correct row to
incorrect. The maximal number of changes needed is then (n − 1)r, and
diam(G(n, r)) ≤ (n − 1)r.
Now, it suffices to show that diam(G(n, r)) ≥ (n − 1)r. Take the diagonal
matrix


r 0 ··· 0
 0 r ··· 0 


A =  .. .. . . ..  .
 . .
. . 
0 0 ··· r
15

The coordinates of the nonzero-entries are of the form (i, i), i ∈ N ∩ [1, n].
Consider permuting the rows so that (i, i) 7→ (i, i − 1), i 6= 1, and (1, 1) 7→
(1, n). The result is


0 0 ··· r
 r 0 ··· 0 


0
A =  .. .. . . ..  ,
 . .
. . 
0 0 ··· 0

and the permutation matrix





P =



0 ··· 1
0 ··· 0 

.. . . ..  .
. . 
.
0 0 ··· 0

0
1
..
.

On the other hand, A = rI. If p is the number of operations needed to
change 1r A0 = P to I, the number of operations needed to change A0 to A is
clearly pr.
Consider this procedure: start from the row i = 1. Find the row which
has its one-entry in the column i, in this case the second row, and swap the
rows. Repeat this for each of the rows except for the n:th one. Before the
(n − 1):th row is swapped for the second time, it will have its one-entry in
the n:th column, so by interchanging it with the n:th row we will get to I.
In our procedure, each of the swaps corrects the place of one one-entry
except for the last one which corrects two. However, we might be able to use
more swaps that correct two positions. These kind of interchanges require
pairs of one-entries to be in positions of the form (i, j) and (j, i). Say that
we swap (i, j) with (i0 , j 0 ) to get (i0 , j) and (i, j 0 ). Assume i > i0 . If i0 < j
and i < j 0 , j 0 > i0 . Thus, the number of entries in a position of the form
(j, i), i > j increases by at most one with each swap. There are n − 1 positive
entries in positions of the form (i, j), i > j in P . To interchange the positions
of two of n − 2 entries (the entries not in the positions (1, n) and some other)
correcting both, we would then need at least one extra swap. Thus, the best
possible result we could get this way is still n − 1 swaps.
Each swap consists of one operation. Thus, p = n − 1, and therefore we
need (n−1)r operations to make A0 from A. Hence, diam(G(n, r)) ≥ (n−1)r,
but because also diam(G(n, r)) ≤ (n − 1)r, diam(G(n, r)) = (n − 1)r.

16

Appendix
In this appendix, we state the technical version of the conjecture mentioned
in the introduction. The vertices of a fiber graph are the monomials in the
preimage of some monomial m in k[y1 , . . . , yn ]. For some fixed lattice ideal and
Gröbner basis, a fiber graph is N -large if it is the preimage of a monomial
m that is divisible by (y1 · · · yn )N . For ideals from contingency tables this
corresponds to that each row and column sum is at least N.
Conjecture (Engström ’12, [5][9]). For any lattice ideal with a Gröbner
basis, there is an N such that the connectivity of any N -large fiber graph is
given by its minimum vertex degree.
This is an example by Raymond Hemmecke why the technical condition
is needed. Construct a lattice ideal from the (2k + 1) × (4k + 2) matrix


1












...

...
1



−1
..
.

1

−1

1
1

−1
..
.

1
..

..

.
1

.
1
1

−1
1












defining a map k[x1 , . . . , x4k+2 ] → k[y1 , . . . , y2k+1 ] and use the Gröbner basis
from lexicographic ordering. Then the fiber graph of the preimage of y2k+1
is the one dimensional skeleton of two k-dimensional cubes connected by one
edge. This fiber graph has minimum degree k but is not 2-connected.

References
[1] Anders Björner and Kathrin Vorwerk. Connectivity of chamber graphs of
buildings and related complexes. European J. Combin. 31 (2010), no. 8,
2149–2160.
[2] Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling
from conditional distributions. Ann. Statist. 26 (1998), no. 1, 363–397.
[3] Reinhard Diestel. Graph Theory. Fourth edition. Graduate Texts in Mathematics, 173. Springer, Heidelberg, 2010. 437 pp.

17

[4] Mathias Drton, Bernd Sturmfels and Seth Sullivant. Lectures on Algebraic
Statistics. Oberwolfach Seminars, Vol. 39. Birkhäuser, Basel, 2009. 172
pp.
[5] Alexander Engström. Private communication, June 2012.
[6] Shlomo Hoory, Nathan Linial and Avi Wigderson. Expander graphs and
their applications. Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–
561
[7] Dénes Kőnig. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465.
[8] Gui Zhen Liu. Proof of a conjecture on matroid base graphs. Sci. China
Ser. A 33 (1990), no. 11, 1329–1337.
[9] Samu Potka. Connectivity, in "Problem book for Sannäs workshop, August 9-10, 2012", edited by Alexander Engström, 2012.
[10] Bernd Sturmfels. Gröbner Bases and Convex Polytopes. University Lecture Series, Vol. 8. American Mathematical Society, Providence, R.I,
1996. 162 pp.
Samu Potka
Aalto University
Department of Mathematics and Systems Analysis
PO Box 11100
FI-00076 Aalto
Finland
e-mail: samu.potka@aalto.fi

18

