%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{160}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{subfig}
\usepackage[ruled, linesnumbered]{algorithm2e}

\usepackage{svg}


%\hypersetup{hidelinks}

\usepackage{listings}
\lstset{basicstyle=\footnotesize\ttfamily,breaklines=true}
\lstset{frame=none, captionpos=b, framesep=4pt, aboveskip=6pt, belowskip=6pt}

\setcounter{MaxMatrixCols}{30}

\newcommand{\CC}{\mathbb C}
\newcommand{\NN}{\mathbb N}
\newcommand{\PP}{\mathbb P}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\RR}{\mathbb R}
\newcommand{\ZZ}{\mathbb Z}

\newcommand{\MB}{\mathcal B}
\newcommand{\MC}{\mathcal C}
\newcommand{\MI}{\mathcal I}
\newcommand{\ML}{\mathcal L}
\newcommand{\MT}{\mathcal T}
\newcommand{\MR}{\mathcal R}

\newcommand{\init}{\text{in}}
\newcommand{\mac}{\textit{Macaulay2}}


\DeclareMathOperator{\Fl}{Fl}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\Dr}{Dr}
\DeclareMathOperator{\conv}{Conv}
\DeclareMathOperator{\trop}{trop}
\DeclareMathOperator{\Trop}{Trop}
\DeclareMathOperator{\degA}{\operatorname{deg}_A}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}



%% define your title in the usual way
\title{Computing all Markov bases}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author


\author{\texorpdfstring{Oliver Clarke\thanks{\href{mailto:oliver.clarke@durham.ac.uk}{oliver.clarke@durham.ac.uk}}\addressmark{1} and Alexander Milner\thanks{\href{mailto:a.j.c.milner@sms.ed.ac.uk}{a.j.c.milner@sms.ed.ac.uk}}\addressmark{2}}{Oliver Clarke and Alexander Milner}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematical Sciences \& Department of Computer Science, Durham University, Stockton Rd, Durham DH1 3LE, United Kingdom \\
\addressmark{2}The University of Edinburgh, James Clerk Maxwell Building, Peter Guthrie Tait Rd, Edinburgh EH9 3FD, United Kingdom}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
We introduce the package \textit{AllMarkovBases} for \textit{Macaulay2}, which computes all minimal Markov bases of a given toric ideal. The package builds on functionality of \textit{4ti2} by producing the \textit{fiber graph} of the toric ideal. The package uses this graph to compute properties of the toric ideal such as its indispensable set of binomials as well as its universal Markov basis.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Markov bases, Toric ideals,  Macaulay2}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{bib.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

A central theme of Algebraic Statistics is the study of Markov bases \cite{sullivant2023algebraic, Kos_2020, ALP_2024}. From an algebraic perspective, a Markov basis is simply a generating set of a toric ideal \cite{sturmfels1996grobner}. The celebrated result of Diaconis and Sturmfels \cite{DS_1998}, often called \textit{the fundamental theorem of Markov bases}, provides an interpretation for these generating sets as moves in a Markov chain, which allows for sampling from conditional distributions. There are many distinct algorithms for producing one Markov basis of a toric ideal \cite{hocsten1995grin, bigatti1999computing, Hemmecke2009Computing}. We refer the reader to the thesis of Malkin \cite{malkin2007computing} for a comprehensive overview of these methods, including the state of the art \textit{project-and-lift} algorithm. An implementation of this algorithm is included in \textit{4ti2} \cite{4ti2}, which is available in many computer-algebra systems including \textit{Macaulay2} \cite{M2} via the package \texttt{FourTiTwo}.


There are a number of important properties of Markov bases, such as the \textit{strongly robust property} \cite{sullivant2019strongly, Kosta2023Strongly} and \textit{distance reduction property} \cite{takemura2005distance, clarke2024distance}, which can be read from the configuration matrix of the toric ideal. Thus, for testing ideas about Markov bases, it may be useful enumerate all minimal Markov bases or (uniformly) sample from them. So, in this extended abstract, we present the package \texttt{AllMarkovBases} \cite{clarke2025computing} for \textit{Macaulay2}, which is available at \url{https://github.com/ollieclarke8787/WorkshopDurham2024/tree/main/ToricIdeals}. Our package builds on \texttt{FourTiTwo} with functionality that allows the user to compute: all minimal Markov bases, the number of minimal Markov bases, the universal Markov basis, and indispensable elements of a toric ideal. These families of elements have alternative combinatorial descriptions and prominently feature in the study of Markov bases. See, for example, \cite{
Charalambous2014Markov,
Kosta2023Strongly,
clarke2024distance,
CTV_2017}. Our package also allows the user to sample uniformly from the set of minimal Markov bases, which may be particularly useful if the number of minimal Markov bases is very large.


\medskip
\noindent \textbf{Setup.} Throughout the abstract, we fix the following setup.
Let $k$ be a field and $A \in \ZZ^{d \times n}$ a matrix. We assume that $\ker(A) \cap \NN^n = \{0\}$. The toric ideal $I_A \subseteq k[x_1, \dots, x_n]$ is the ideal generated by the binomials $x^u - x^v$ where $u,v \in \NN^n$ such that $u - v \in \ker(A)$.
A \textit{(minimal) Markov basis} of $A$ is a (inclusion-minimal) set of generators $M$ of $I_A$ and we identify $M$ with its set of binomial exponents $\{u-v : x^u - x^v \in M\}$. We often write the elements of $M$ as the row-vectors of a matrix.
The \textit{indispensable set $S(A)$} is the intersection of all minimal Markov bases of $A$. And the \textit{universal Markov basis $U(A)$} is the union of all minimal Markov bases of $A$.


\begin{example}
    The matrix $A = \begin{pmatrix}
    7 & 8 & 9 & 10
\end{pmatrix}$ defines a $1$-dimensional toric ideal (monomial curve). The ideal has four minimal Markov bases, which are computed as follows.

\begin{lstlisting}
i1 : needsPackage "AllMarkovBases";
i2 : A = matrix "7,8,9,10";

i3 : countMarkov A
o3 = 4

i4 : markovBases A
o4 = {| -1 2  -1 0  |, | -1 2  -1 0  |, | -1 2  -1 0  |, | -1 2  -1 0  |}
      | -1 1  1  -1 |  | -1 1  1  -1 |  | -1 1  1  -1 |  | -1 1  1  -1 |
      | 0  -1 2  -1 |  | 0  -1 2  -1 |  | 0  -1 2  -1 |  | 0  -1 2  -1 |
      | 4  0  -2 -1 |  | 4  0  -2 -1 |  | 4  -1 0  -2 |  | 4  -1 0  -2 |
      | 3  1  -1 -2 |  | 3  1  -1 -2 |  | 3  1  -1 -2 |  | 3  1  -1 -2 |
      | 3  0  1  -3 |  | 2  2  0  -3 |  | 3  0  1  -3 |  | 2  2  0  -3 |
\end{lstlisting}

So, for instance, the toric ideal $I_A \subseteq k[a,b,c,d]$ is minimally generated by the six polynomials
\[
ac - b^2,\, ad - bc,\, bd-c^2,\,
a^4-c^2d,\, a^3b - cd^2,\, a^3c-d^3.
\]
\end{example}


\begin{example}
The monomial curve given by the matrix $A' = \begin{pmatrix}
    51 & 52 & 53 & 54 & 55 & 56
\end{pmatrix}$ has $24300$ minimal Markov bases. It may not be feasible to work with all of them so we can produce random samples as follows.
\begin{lstlisting}
i5 : A' = matrix "51,52,53,54,55,56";

i6 : countMarkov A'
o6 = 24300

i7 : randomMarkov A'
o7 = | 8  4  0  0  0  -11 |
     | -1 2  -1 0  0  0   |
     | -1 1  1  -1 0  0   |
     | -1 0  2  0  -1 0   |
     | -1 1  0  1  -1 0   |
     | 0  -1 1  1  -1 0   |
     | -1 1  0  0  1  -1  |
     | 0  0  -1 2  -1 0   |
     | 0  -1 0  2  0  -1  |
     | 0  0  -1 1  1  -1  |
     | 0  0  0  -1 2  -1  |
     | 12 0  -1 0  -1 -9  |
     | 11 1  0  -1 -1 -9  |
     | 11 0  1  -1 0  -10 |
     | 9  3  0  0  -1 -10 |
\end{lstlisting}

The \textit{indispensable set} $S(A')$ and the \textit{universal Markov basis} $U(A')$ are computed as follows. We have abridged the output of \texttt{toricUniversalMarkov A'} to save space. We note that the indispensable set and universal Markov bases are read from the fiber graph, so the methods do not require the computation of all 24300 minimal Markov bases.

\begin{lstlisting}
i8 : toricIndispensableSet A'
o8 = | -1 2 -1 0  0 0  |
     | -1 1 1  -1 0 0  |
     | 0  0 -1 1  1 -1 |
     | 0  0 0  -1 2 -1 |

i9 : toricUniversalMarkov A'
o9 = | 10 0  2  0  0  -11 |
     | 8  4  0  0  0  -11 |
      ...
     | 9  3  0  0  -1 -10 |
     | 11 0  0  1  -1 -10 |
              33       6
o9 : Matrix ZZ   <-- ZZ
\end{lstlisting}
\end{example}

\begin{example}\label{example: segre 2x2x2}
In Algebraic Statistics, Segre embeddings play an important role as they correspond to independence models. Consider the Segre embedding
$
\PP^2 \times \PP^2 \times \PP^2
\rightarrow
\PP^{26}
$ defined by
$
([x_1 \!:\! x_2 \!:\! x_3],\, [y_1 \!:\! y_2 \!:\! y_3],\, [z_1 \!:\! z_2 \!:\! z_3]) \mapsto [x_i y_j z_k]_{ijk}$.
The image of this embedding is the toric variety whose toric ideal is given by the matrix
\[
A'' \!= \! \begin{bmatrix}
    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&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&0&0&1&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&0\\
    1&1&1&0&0&0&0&0&0&1&1&1&0&0&0&0&0&0&1&1&1&0&0&0&0&0&0\\
    0&0&0&1&1&1&0&0&0&0&0&0&1&1&1&0&0&0&0&0&0&1&1&1&0&0&0\\
    1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0\\
    0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0&0&1&0
\end{bmatrix}.
\]
We compute the number of Markov bases, the indispensable set, and universal Markov basis as follows. The semicolon suppresses the output, so the following shows that there are $81$ indispensable binomials and the universal Markov bases has size $243$.
\begin{lstlisting}
i10 : A'' = matrix {
    {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,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,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0},
    {1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0},
    {0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0},
    {1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0},
    {0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0}};

i11 : countMarkov A''
o11 = 324518553658426726783156020576256

i12 : toricIndispensableSet A'';
               81       27
o12 : Matrix ZZ   <-- ZZ

i13 : toricUniversalMarkov A'';
               243       27
o13 : Matrix ZZ    <-- ZZ
\end{lstlisting}
We note that this example is particularly amenable to our method as the fiber graphs are all very small.
\end{example}

\section{Implementation details}

We translate the main results of Charalambous, Katsabekis, and Thoma \cite[Section
2]{CKT_2007} into a procedure (Algorithm~\ref{alg:allMarkov}) that produces all minimal Markov bases. In this section, we explain the the procedure through a simple running example $A = \begin{pmatrix}
    1 & 2 & 3
\end{pmatrix} \in \ZZ^{1 \times 3}$. Let us also fix a distinguished Markov basis
\[
M = \begin{bmatrix}
    2 & -1 & 0 \\
    3 & 0 & -1
\end{bmatrix}.
\]
So the toric ideal $I_A \subseteq k[x,y,z]$ is minimally generated by the binomials $x^2 - y$ and $x^3 - z$. The \textit{affine semigroup} of $A$ is $\NN A := \{Ax \in \ZZ^d : x \in \NN^n\}$.
For each $t \in \NN A$, the  \textit{$t$-fiber} of $A$ is the subset $\mathcal F_t := \{u \in \NN^n : Au = t\}$. For each binomial $x^u - x^v \in I_A$, we have that $u, v \in \mathcal F_t$ belong to the same fiber of $A$, and we define its \textit{$A$-degree} $\deg_A(x^u - x^v) = t$.
In our running example we have
\[
\deg_A(x^2 - y) = 2
\quad \text{and} \quad
\deg_A(x^3 - z) = 3.
\]
The following result follows directly from \cite[Theorems~2.6 and 2.7]{CKT_2007}.
\begin{theorem}\label{thm: generating fibers}
    If $M$ and $M'$ are minimal Markov bases of $A$, then $\deg_A(M)$ and $\deg_A(M')$ are equal as multisets.
\end{theorem}


We say that $t \in \NN A$ is a \textit{generating fiber} for $A$ if there exists an element $x^u - x^v$ of a minimal Markov basis with $A$-degree $\deg_A(x^u - x^v) = t$. So, by \Cref{thm: generating fibers}, the set of all generating fibers is determined by a single Markov basis.

\begin{definition}\label{def: fiber graph}
    Let $t \in \NN^d$. The \textit{fiber graph} $G_t$ has vertex set $\mathcal F_t$ and edge set
    \[
    E(G_t) = \{uv : \text{there exists } i \in \{1, \dots, d\} \text{ such that } u_i > 0 \text{ and } v_i > 0\}.
    \]
\end{definition}

To determine the minimal Markov bases, it suffices to consider only the fiber graphs of the generating fibers. With our package, these fiber graphs can be listed with the function \texttt{fiberGraph}. For our running example $A = \begin{pmatrix}
    1 & 2 & 3
\end{pmatrix}$ they are computed as follows.

\begin{lstlisting}
i1 : needsPackage "AllMarkovBases";
i2 : A = matrix "1,2,3"
i3 : fiberGraph A
o3 = {Graph{{0, 1, 0} => {}}, Graph{{0, 0, 1} => {}         }}
            {2, 0, 0} => {}         {1, 1, 0} => {{3, 0, 0}}
                                    {3, 0, 0} => {{1, 1, 0}}
\end{lstlisting}

\begin{figure}%
    \centering
    \subfloat[\label{fig:2fiber} \centering $A$-degree 2]{{\includegraphics[scale = 0.8]{fiber2.pdf} }}%
    \qquad
    \subfloat[\label{fig:3fiber} \centering $A$-degree 3]{{\includegraphics[scale = 0.8]{fiber3.pdf} }}%
    \caption{Fiber graphs of $A$ for the generating fibers}%
    \label{fig:fibers}%
\end{figure}

A visualisation of these fibers, produced by the package \texttt{Graphs}, is shown in \Cref{fig:fibers}.
Each element $z \in \ker(A)$ is thought of as a \textit{move} that connects pairs of points $u, v \in \NN^n$ whenever $u = v + z$. In our example, the move $(2, -1, 0)$ connects $(2,0,0)$ and $(0,1,0)$ and connects $(1,1,0)$ and $(3,0,0)$. A subset $M \subseteq \ker(A)$ is said to \textit{connect} the $t$-fiber, for some $t \in \NN A$, if the graph $G_{M, t}$ on $\mathcal F_t$ with edges $\{uv : u-v \in M \}$ is connected.
The \textit{fundamental theorem of Markov bases} \cite[Theorem~3.1]{DS_1998} tells us that Markov bases are in one-to-one correspondence with subsets of $\ker(A)$ that connect each fiber of $A$. Similarly, by \cite[Theorems~2.6 and 2.7]{CKT_2007}, the minimal Markov bases are in one-to-one correspondence with sets of moves that \textit{minimally connect $G_t$} for each generating fiber $t$ of $A$.

\begin{remark}
    In the literature, the graphs $G_{M,t}$ are often called fiber graphs \cite{Hemmecke2009Computing}. To avoid confusion, for us the term fiber graph will always refer to the graph $G_t$ for some $t$.
\end{remark}

In our running example, observe that the $2$-fiber in \Cref{fig:2fiber} is connected only by the element $(2,-1,0)$, up to sign. It follows that the corresponding binomial $x^2-y$ is \textit{indispensable}, i.e.~it appears in every Markov basis, as there is no other way to connect the $2$-fiber. On the other hand, the $3$-fiber in \Cref{fig:3fiber} is minimally connected with either the move $(1,1,-1)$ or $(3,0,-1)$. These form the two minimal Markov bases of $A$. In our package, this process is carried out by the function \texttt{markovBases}:

\begin{lstlisting}
i4 : markovBases A
o4 = {| 2 -1 0  |, | 2 -1 0  |}
      | 3 0  -1 |  | 1 1  -1 |
\end{lstlisting}

We now state the algorithm implemented by \texttt{markovBases}.

\medskip

\begin{algorithm}[H]\label{alg:allMarkov}
\SetAlgoLined
\SetNlSty{textit}{}{:}
\SetKwInOut{input}{Input}\SetKwInOut{output}{Output}

\input{$A \in \ZZ^{d \times n}$ a configuration matrix}
\output{$\mathcal M$ the set of minimal Markov bases of $A$}
\BlankLine

Initialise $\mathcal M = \emptyset$ \;

\For{$t \in \NN A$ a generating fiber of $A$}{

Compute $C_t := $ the set of connected components of the fiber graph $G_t$ \;

}

\BlankLine

$\mathcal T := \prod_{t} \{T : \text{spanning tree on vertex set } C_t\}$, where the product is taken over all generating fibers $t \in \NN A$ of $A$

\BlankLine

\For{$\{T_t : \text{spanning tree on } C_t\} \in \mathcal T$}{

\For{each collection $\{f_{T, e} : T \in \mathcal T,\, e \in E(T)\}$ where $f_{T, e}$ is a choice function on $e$}{

$M := \{f_{T,e}(u) - f_{T,e}(v) : T \in \mathcal T,\, uv \in E(T)\}$ Markov basis of $A$\;

$\mathcal M \leftarrow \mathcal M \cup \{M\}$\;
}
}

\caption{All minimal Markov bases of a matrix}
\end{algorithm}


\medskip

Let us give some notes on how the algorithm works. Recall that each minimal Markov basis corresponds to a collection of moves that minimally connects the fiber graph $G_t$ for each generating fiber $t$ of $A$. We enumerate these collections of moves in two steps. First, we find the connected components of each fiber graph and connect them with spanning trees. This corresponds to lines 2 to 5 and the loop spanning lines 6 to 11. Next, for each edge of such a spanning tree we choose a pair of points in the fiber that lie in the connected components in the edge. This gives rise to a move, which lies the minimal Markov basis. Let us expand on this explanation with the following example.


\begin{example}\label{example: counting fiber size}
Suppose $\mathcal F_t = \{v_1, \dots, v_6\}$ is a generating fiber and $G_t$ has three connected components $C_t = \{v_1v_2,\, v_3v_4,\, v_5v_6\}$. If we fix a spanning tree with edges $e_1 = \{v_1v_2, v_3v_4\}$ and $e_2 = \{v_1v_2, v_5v_6\}$, then there are four choices for turning the edge $e_1$ into a move:
\[
v_1 - v_3,\, v_1 - v_4,\, v_2 - v_3,\, v_2 - v_4.
\]
Similarly, there are four ways to turn $e_2$ into a move. Thus, this generating fiber contributes two elements of a minimal Markov basis in $16$ ways.
\end{example}

% For each fiber graph $G_t$, with $t \in \NN A$ a generating fiber of $A$, we define $C_t$ to be its set of connected components and pick a spanning tree $T$ with vertices $C_t$. Then the union over all generating fibers of the binomials $x^u-x^v$ where $u,\,v$: are in distinct connected components of $G_t$; and connected by an edge of $T$, forms a minimal Markov basis. Concretely, on line~7, the edge $e \in E(T)$ is a pair of connected components of $C_t$, hence $e$ is set of sets of elements of $\NN^n$. Suppose that $uv \in E(T)$ is an edge of some $T \in \mathcal T$, then the choice function $f_{T,e}$ produces the binomial $x^u - x^v$, which appears in the Markov basis.

The spanning trees are enumerated using the well-known bijection of Prüfer \cite{Pru_1918}. This bijection between labelled spanning trees on $n$ vertices and \textit{Prüfer sequences} (sequences in $\{0, \dots ,n-1\}$ of length $n-2$) is completely constructive. Our package implements the helpful function \texttt{pruferSequence} that takes a Prüfer sequence and returns the edge set of the corresponding spanning tree. For example, the spanning tree associated to the sequence $\{0,0,2,4\}$ is given computed as follows, see \Cref{fig:examplePrufer}.
\begin{lstlisting}
i5 : pruferSequence {0,0,2,4}
o5 = {set {0, 1}, set {0, 3}, set {0, 2}, set {4, 2}, set {4, 5}}
\end{lstlisting}

\begin{figure}
    \centering
    \includegraphics[scale=0.7]{pruferExample.pdf}
    \caption{Spanning tree on $\{0,1,\dots,5\}$ associated to the Pr\"ufer sequence $\{0,0,2,4\}$}
    \label{fig:examplePrufer}
\end{figure}

It is straightforward to see from Algorithm~\ref{alg:allMarkov} and \Cref{example: counting fiber size} that the number of minimal Markov bases can be computed from the sizes of connected components of each fiber graph.

\begin{theorem}[{\cite[Theorem~2.9]{CKT_2007}}]
For each generating fiber $t \in \NN A$, assume $G_t$ has $n_t$ connected components of size $m_{t,1},m_{t,2}, \dots, m_{t,n_t}$ for some positive integers $m_{t,i}$ with $i \in \{1,2, \dots, n_t\}$.
The number of minimal Markov bases of $A$ is given by \[
\prod_{t} m_{t,1} \cdot m_{t,2} \cdots m_{t,n_t} \cdot (m_{t,1} + m_{t,2} + \dots + m_{t,n_t})^{n_t - 2}.
\]
\end{theorem}


Our package implements this as the function \texttt{countMarkov}, which computes the number of minimal Markov bases without enumerating all of them.

\subsection{Applications of fiber graphs}

Once we have computed the fiber graphs of the generating fibers of a toric ideal, other properties become immediately available. Our package extracts these properties with variation on Algorithm~\ref{alg:allMarkov}, which allows us to sample from the set of Markov bases and compute the indispensable set and univeral Markov basis.

\medskip
\noindent \textbf{Random sampling.} The function \texttt{randomMarkov} produces a random Markov basis. In lines~6 and 7 of Algorithm~\ref{alg:allMarkov}, we sample uniformly an element of $\mathcal T$ and a random collection of choice functions. This produces a single uniformly distributed minimal Markov basis of $A$.

\medskip
\noindent \textbf{Indispensable set and universal Markov basis.}
The universal Markov basis $U(A)$ of the matrix $A$ is the union of its minimal Markov bases. Since every minimal Markov basis arises from Algorithm~\ref{alg:allMarkov}, we compute $U(A)$ by replacing the collection of spanning trees $\mathcal T$ with a single complete graph.


By \cite[Corollary
2.10]{CKT_2007}, the indispensable elements are detected directly from the fiber graphs. The function \texttt{toricIndispensableSet} determines the indispensable elements by finding each fiber graph $G_t$ with exactly two vertices $u, v$ such that $|u| = |v| = 1$, i.e.~the two vertices of $G_t$ are subsets of $\NN^n$ of size one. This method is completely analogous to \cite[Algorithm~1, Theorem~3.3]{Charalambous2016Binomial}.


% \acknowledgements{
% }

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
