##  1 Quantum Computing Implementation of Gate Scheduling Optimization
Algorithms

Solving a realistic version of a plane-gate scheduling constrained QAP problem
for a very large and busy airport is impractical with digital computing
technologies. A quantum computer may have the potential to circumvent some of
these difficulties.

Implementing a gate scheduling optimization algorithm for a quantum computing
system requires a re-design of the digital version. This requires
understanding the quantum computing hardware architecture and software
environment so that this algorithm can be successfully re-structured and
migrated between these completely different systems.

###  1.1 Quantum Computing Hardware Architectures

Quantum computers are based on a fundamentally different premise for
computation when compared to a digital computer. The digital computer operates
on the mathematics of a $base_{2}$ system, whereas the fundamental premise of
computation for a quantum computer is based on something called a qubit.
Unlike a classical $"bit"$ that only has two states (sometimes designated as
$"On"$ or $"Off"$ or $"0"$ or $"1"$), a quantum bit (qubit) can be represented
by many different weighted, linear combinations of ”0s” and 1s”. The rules for
quantum computation are based on the physics of quantum mechanics and concepts
of superposition and quantum entanglement rather than the electrical
engineering design of digital logic circuits.

Planning computations on a quantum computer and verifying proper operation of
the algorithms running on the machine is also totally different from digital
computations. Unlike digital computations where it is possible to query a
system’s state at different points midway through the computation, it is
impossible to observe the state of a quantum state midway through the
computation without destroying the quantum state. A system cannot be disturbed
with any type of intermediate point measurement until the completion of the
calculation, otherwise the entire computation on the quantum computer will
automatically be terminated in whatever state it was at when the measurement
was attempted. There is no possibility of re-starting the computation from the
point where an intermediate measurement was taken or of re-running a
computation from the beginning in a deterministic way. Upon completion of the
computation, the idea of an $"answer"$ also has a very different
interpretation. Whereas a digital computer will give a deterministic answer, a
quantum computer will provide a histogram representing a spectrum of
measurements with their relative probabilities.

Today there are several different types of quantum computing hardware
architectures that have been developed. These include an analog-based platform
based on Quantum Annealing, various Superconducting transmon devices based on
non-linear Josephson junction circuits, and trapped ion devices. In this
paper, the IBM superconducting, transmon-based quantum computing hardware
platforms were used for the computations. We selected the IBM_Q Toronto, which
is a 27-qubit quantum computing processor.

Noise is an additional consideration when running on a quantum computing
hardware platform. Today’s quantum computers are best described as Noisy
Intermediate Scale Quantum (NISQ) machines. Such types of noise present in
these machines today adversely impacts the stability of the quantum
computations. Noise essentially destroys the coherence of the quantum state
and limits the size of the application that can be run on these machines. This
is an active area of research to mitigate this noise and develop error
correction methodologies that will extend the quantum computer’s computational
capabilities. Figure 1 shows the general architecture and qubit connectivity
of the machine and a graphical ”heat map” showing the level of 1 qubit and 2
qubit errors for this processor.

Figure 1: IBM published information (IBM Quantum Experience: (https://quantum-
computing.ibm.com/) ) on the qubit layout on the IBMQ_Toronto quantum
computing hardware processor. The figure on the right is the actual
connectivity of the qubits. The figure on the left is a color coded ”heat map”
showing the 1 and 2 qubit error rates for each qubit on Toronto.

###  1.2 Software Environments

####  1.2.1 Variational Quantum Eigensolver (VQE)

Quantum computers have the potential to solve specific mathematically
structured problems exponentially faster than classical computers. However,
achieving this goal for some large-scale problems can take several decades and
may require breakthrough technologies due to the high error rates present in
today’s NISQ computers. Because of these limitations, current implementations
of many quantum algorithms on actual hardware are unable reach correct or
optimal solutions. To mitigate these limitations, researchers have been
investigating hybrid algorithms that can be run efficiently using a
combination of both quantum and classical components. Eigenvalues,
eigenvectors, and optimization problems play an important role in such hybrid
algorithms.

Peruzzo and McClean et al. [ref7] presented the Variational Quantum
Eigensolver (VQE) algorithm to solve the eigenvalues and binary optimization
problems that are unsolvable by solely using classical computers. In this
technique, both classical and quantum computers are being used to converge
intermediate results in the correct solution. Finding the quantum state
corresponding to the minimum energy of a Hamiltonian can be solved by applying
a quantum/classical hybrid variational technique.

In the VQE approach [ref7], the Hamiltonian matrix $H$ can be derived by the
interaction spins or electronic systems in physical systems. $H$ can be
calculated to find the eigenvectors $\ket{\psi_{i}(t)}$ and the corresponding
eigenvalues $\lambda_{i}$ of the Hamiltonian matrix by converting an
optimization problem to an adiabatic quantum computation. The main goal of VQE
is to find the desired eigenvectors and eigenvalues by optimizing a
parameterized quantum circuit. The lowest eigenvalue is of primary interest in
the VQE approach since it is the optimum solution of the problem, same as the
lowest energy is the solution to a Hamiltonian in physical systems. VQE can be
used to find the solution for Eq. (1),

$E(\theta)=\underset{\theta}min\bra{\psi(\theta)}H\ket{\psi(\theta)}.$ (1)

Because $\ket{\psi(\theta)}$ is the normalized solution for Eq. (1), it can be
the minimum eigenvalue of $H$. $H=\sum_{i}\beta_{i}H_{i}$ where $H_{i}$ are
the tensor products of Pauli operators and $\beta_{i}$ are the real
coefficients. By considering this reformulation for $H$ matrix, Eq. (1) can be
represented as,

$E(\theta)=\underset{\theta}min\bra{\psi(\theta)}H\ket{\psi(\theta)}=\underset{\theta}min\sum_{i}\beta_{i}\bra{\psi(\theta)}H_{i}\ket{\psi(\theta)}.$
(2)

Figure 2: The schematic diagram of the variational quantum eigensolver (VQE)
algorithm

Finding the minimum eigenvalue can be an NP-hard problem as the size of the
Hamiltonian matrix increases. To address this problem, different quantum
techniques have been developed [ref22]. Quantum phase estimation (QPE) is one
of the main techniques that can be applied to a unitary quantum circuit
derived from a problem to find its minimum eigenvalue, that is the solution of
the Eq. (1). However, implementing QPE requires a large number of controlled
rotation gates. Hence, it is not trivial or possible to find the correct
answer to a problem using near-term noisy quantum computers.

Alternatively, researchers have been developing some hybrid classical-quantum
algorithms (e.g., VQE and QAOA) to solve a problem by finding the minimum
eigenvalue of the Hamiltonian Matrix in a recursive optimization process using
both NISQ quantum computers and classical computers. The optimization of a
Hamiltonian matrix $H$ can be determined by applying a hybrid classical-
quantum technique. In the hybrid system, a classical computer first finds the
optimum values for variational parameters, $\theta$. Second, a quantum
computer uses the $\theta$ to calculate the expectation value
($\bra{\psi(\theta)}H_{i}\ket{\psi(\theta)}$). Then, the calculated
expectation value will be fed back into a classical algorithm to update the
parameter $\theta$. These steps will repeat recursively until the hybrid
system finds the minimum eigenvalue of the $H$ matrix [ref23].

In this hybrid approach, a parameterized quantum circuit ($U(\theta)$) known
as an Ansatz will be applied to the qubits. As a result, the expectation
values will be calculated and used in the classical optimization process
[ref8]. Choosing an ansatz operator as a variational form plays an important
role in the optimization process. In most cases, an ansatz should be able to
efficiently run in quantum devices. Different classical optimizers can be used
to solve the optimum values for $\theta$. These techniques perform various
forms of gradient descent methods to apply iterative optimization algorithms
to solve the problem [ref16, ref17].

This paper considers three well-known classical optimizers to optimize
variational parameters. First, the constrained optimization by linear
approximation (COBYLA) algorithm is a numerical optimization method that finds
the min/max of the objective function without knowing the gradient value
[ref41]. Second, the limited memory Broyden - Fletcher - Goldfarb - Shanno
(L-BFGS) algorithm is a quasi-Newton optimization method that is mainly used
for the parameter identification in machine learning techniques with limited
amounts of computer memory [ref40]. Last, the sequential least squares
programming (SLSQP) algorithm is an iterative optimization algorithm that is
used for constraint nonlinear problems and uses the Han–Powell quasi–Newton
method to find the min/max of the objective function [ref39].

Fig. 2 describes the general view of the VQE algorithm. As indicated in the
figure, all of the qubits in the quantum computer are initialized to the zero
state (i.e., state preparation). The variational quantum circuit is then
applied to the qubits and then a measurement is performed. Next, the results
are fed back into the classical computer to update the variational parameters.
This process is repeated until the minumun eigenvalue is found or an
optimization limit is reached.

####  1.2.2 Binary Optimization Problem and Quantum Hamiltonian

Combinatorial optimization (CO) is a major class of optimization problems hat
has various applications in ndustry and research. In particular, CO for Graph
Coloring has been extensively used in different application domains such as
transportation management, social media, telecommunication, and resource
scheduling. Most of these applications are NP-hard problems that are
attractive but challenging for researchers to solve.

Three approaches can be considered to tackle CO: the Exact Solution algorithm,
the Approximation algorithm, and the Heuristic algorithm [ref36]. The exact
algorithm uses the enumeration with integer formulation to find the exact
solution but it might not be able to find the exact answer as the size of the
problem increases. On the other hand, the approximation algorithm might find a
solution to the problem in polynomial time. However, there is no guarantee
that the results of the algorithm converge into a minimum or optimal solution.
There are situations where the results may display a local minimum that
requires an an exponential increase in computational overhead as the problem
size increases. The heuristic algorithm can be used for some specific types of
CO problems. These algorithms are simple and fast because they use the trial
and error approach to find a solution but they lack the theoretical guarantee
to find a correct answer. Moreover, in some cases, finding a good solution
using these approaches can be almost infeasible.

Recently, Quadratic Unconstrained Binary Optimization (QUBO) has been
introduced to cover a large variety of CO problems [ref21]. The QUBO technique
can find an optimal solution for many types of NP-hard problems such as graph
partitioning, graph coloring, scheduling management, and register allocation.
A QUBO problem can be formulated by Eq. (1.2.2) as described in [ref31], J =
min {X^T Q X + g^T X + c} = ∑_i, j ∈P ∑_k, l ∈G x_i k x_j l v_i j d_k l+P
∑_i(1-∑_k x_i k)^2+P ∑_(i, j) ∑_k x_i k x_j k

where $Q$ is a $n\times n$ matrix with real numbers, $X$ is the state vector
with element of $\\{0,1\\}^{n}$ and $P$ is a positive and large number. The
goal of Eq. (1.2.2) is to find the minimum of the objective function which is
the minimum eigenvalue of the matrix $H$. Eq. (1.2.2) can also be expressed by
Eq. (3) as described in [ref19],

$\sum_{i,j}W_{ij}x_{i}(1-x_{j})+\sum_{i}W_{i}x_{i},$ (3)

where $W_{i}$ are the linear weights $Q_{ii}$ for $i=1,2,...,n$ and $W_{ij}$
are the quadratic weights $Q_{ij}$ for $i<j$. Here $x_{i}$ is a binary
variable that can take $0$ or $1$ and as a result $x_{i}^{2}=x_{i}$. In order
to transfer Eq. (3) into an Ising model, the following substitution can be
used as

$x_{i}=\frac{Z_{i}+1}{2},$ (4)

where $x_{i}\in\\{0,1\\}$ and $Z_{i}\in\\{-1,1\\}$ for $i=0,...,n$. By
applying the substitution the Hamiltonian matrix would be [ref18, ref20],

$\multlined\sum_{i,j}\frac{W_{ij}}{4}(1-Z_{i})(1+Z_{j})+\sum_{i}\frac{W_{i}}{2}(1-Z_{i})\\\
=-\frac{1}{2}\sum_{i,j}W_{ij}Z_{i}Z_{j}+\sum_{i}W_{i}Z_{i}+c.$ (5)

This Hamiltonian matrix will be a form of tensor products of Pauli $Z$
operators. Note that since the $Z$ is a diagonal matrix, the Hamiltonian
matrix should be diagonal so that it can be used in VQE optimization process.
In order to solve the $k-$coloring problem using the standard QUBO
optimization technique, $nk$ qubits are required. The required number of
qubits is the main constraint of the standard QUBO optimization approach. In
the next section a new algorithm is introduced which solves the $k-$coloring
problem by applying $nlog(k)$ number of qubits.

###  1.3 Space-Efficient Graph Coloring Quantum Computing algorithms

In sectionLABEL:, we showed that the standard QUBO optimization algorithm
requires $nk$ number of qubits which increases exponentially with the problem
size. Therefore, it is infeasable to run a gate scheduling problem with a
reasonable size on existing NISQ devices. In this section, a new space-
efficient technique that maps a $k-$coloring problem to a lower number of
qubits is explained. The number of colors is encoded to $m$ bits (total
$2^{m}$ colors) and the goal is to assign a color labeled by $m$ bitstrings to
each vertex [Space_EfficientPaper]. As mentioned in the standard $k-$coloring
approach, two neighboring nodes should not have the same color, therefore in
the space-efficient technique a cost function should evaluate to nonzero if
the neighboring nodes have the same color code. For a graph with adjacency
matrix $A$, the graph coloring problem can be mapped to the ground state of
the following Hamiltonian[Space_EfficientPaper]:

$\multlined
H=\sum_{i,j}A_{ij}\sum_{a\in\\{0,1\\}^{m}}\prod_{l=1}^{m}(\mathds{1}+(-1)^{a_{l}}Z_{i,l})(\mathds{1}+(-1)^{a_{l}}Z_{j,l})$
(6)

The ground state of the $nlog(k)$-qubit Hamiltonian matrix is the solution to
the graph coloring problem which corresponds to the proper bitstring
assignment of the graph vertices. If the number of colors is not a power of
$2$, i.e. $2^{m-1}<k<2^{m}$, $m$ number of bitstrings is considered to map the
colors, however, the bitstrings in which $\sum_{i=1}^{m}2^{k-i}b_{i}<k$ are
allowed for vertex coloring. This means that new penalty terms should be added
to Eq.(6) to satisfy this limitation. For example in case $k=3$, two
bitstrings $\\{00,01,10,11\\}$ should be considered to label the colors. Since
only three colors are required to be assigned to the vertices, a term
$\sum_{i=1}^{n}(1-Z_{i,1})(1-Z_{i,2})$ should be added to the Hamiltonian
matrix to penalize the non-allowed bitstring which is $(b_{1},b_{2})=(1,1)$.
By applying Eq.6 and considering the new penalty term, the corresponding
Hamiltonian matrix will be,

$\multlined
H=\sum_{i,j=1}^{n}A_{ij}(\mathds{1}-Z_{i,1})(\mathds{1}-Z_{i,2})(\mathds{1}-Z_{j,1})(\mathds{1}-Z_{j,2})\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+(\mathds{1}+Z_{i,1})(\mathds{1}+Z_{i,2})(\mathds{1}+Z_{j,1})(\mathds{1}+Z_{j,2})\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+(\mathds{1}+Z_{i,1})(\mathds{1}-Z_{i,2})(\mathds{1}+Z_{j,1})(\mathds{1}-Z_{j,2})\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+(\mathds{1}-Z_{i,1})(\mathds{1}+Z_{i,2})(\mathds{1}-Z_{j,1})(\mathds{1}+Z_{j,2})\\\
+(\mathds{1}-Z_{i,1})(\mathds{1}-Z_{i,2})\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
(7)

As seen in Eq.7, the last term will be added since four colors has been
considered for a problem that only requires three colors. This penalty term
helps remove one of the binary coded colors from the list.

Figure 3: The corresponding derived graph based on the information provided by
Appendix LABEL:tableee

###  1.4 Discussion

Table 1 shows a comparison between the two implementations described in
sections 1.2.2 and 1.3 in terms of number of qubits, run-time and circuit
depth. A Noise-Aware Compilation method from Qiskit was used for the circuit
compilation and optimization. This method maps the circuit to match the
hardware topology of our as discussed in Section 1.1 and also does light-
weight optimizations by collapsing adjacent gates as appropriate. We notice a
direct benefit from the efficient embedding in all aspects of the comparison.
As both circuits run the same ansatz architecture, we see that the efficient
embedding proves advantageous, as it uses less qubits. As discussed in the
hardware architecture’s section (Section 1.1) we know that mapping the circuit
to hardware calls for the usage of SWAP operations, hence circuits that
include less 2-qubit interactions will require less swaps to satisfy them.
This directly impacts the circuit depth and result in a shorter depth for the
efficient embedding and hence a shorter circuit run-time. Moreover, a smaller
circuit size allows for a more efficient mapping to match the limitations of
the hardware topology.

Also, as discussed in Section 1.3, due to the efficient embedding’s usage of a
lesser number of qubits, we’re able to map larger problem sets to current
machines, which is a critical advancement to the usage of variational quantum
algorithms to solve such optimization problems.

Table 1: Comparison between the standard QUBO and the efficient embedding approaches | Standard Embedding | Efficient Embedding
---|---|---
# Qubits | 25 | 15
Circuit Depth | 29 | 19
Run-time (sec) | 5569.84 | 395.48


#  Freiman $t$-spread principal Borel ideals

Guangjun Zhu${}^{{}^{*}}$, Yakun Zhao and Yijun Cui  Authors address:
School of Mathematical Sciences, Soochow University, Suzhou 215006, P.R. China
zhuguangjun@suda.edu.cn(Corresponding author:Guangjun Zhu),
1768868280@qq.com(Yakun Zhao), 237546805@qq.com(Yijun Cui).

###### Abstract.

An equigenerated monomial ideal $I$ is a Freiman ideal if
$\mu(I^{2})=\ell(I)\mu(I)-{\ell(I)\choose 2}$ where $\ell(I)$ is the analytic
spread of $I$ and $\mu(I)$ is the least number of monomial generators of $I$.
Freiman ideals are special since there exists an exact formula computing the
least number of monomial generators of any of their powers. In this paper we
give a complete classification of Freiman $t$-spread principal Borel ideals.

###### Key words and phrases:

Freiman ideal, sorted ideal, $t$-spread principal Borel ideal, the sorted
graph.

###### 2010 Mathematics Subject Classification:

Primary 13C99; Secondary 13E15, 13A15.

* Corresponding author

## Introduction

Let $K$ be a field and $S=K[x_{1},\ldots,x_{n}]$ the polynomial ring in $n$
variables over $K$, and let $I\subset S$ be a monomial ideal. We denote by
$\mathcal{G}(I)$ the unique minimal set of monomial generators of $I$ and by
$\mu(I)$ the number of elements in $\mathcal{G}(I)$. It is a very difficult
problem to exactly compute $\mu(I^{k})$ for each integer $k\geq 2$. If $I$ is
generated by a regular sequence and $\mu(I)=m$, it is well known that
$\mu(I^{k})={k+m-1\choose m-1}$, which is the maximal that $\mu(I^{k})$ can
reach. At the other extreme, Eliahou et. al. [6] constructed a family of
monomial ideals such that $\mu(I)$ can be arbitrarily large but satisfy
$\mu(I^{2})=9$.

As a consequence of the well-known theorem due to Freiman (see [7]) from
additive number theory, Herzog et. al. showed in [9, Theorem 1.8] that if $I$
is an equigenerated monomial ideal, that is, all its generators are of the
same degree, then $\mu(I^{2})\geq\ell(I)\mu(I)-{\ell(I)\choose 2}$, where
$\ell(I)$ is the analytic spread of $I$. If the equality holds, then Herzog
and Zhu [10] called this ideal $I$ to be a Freiman ideal (or simply Freiman).
What makes a Freiman ideal interesting is the fact that $\mu(I^{k})$, for any
$k$, can be computed by an exact formula in terms of $\mu(I)$ and $\ell(I)$
(see [10, Corollary 2.9]). Several characterizations of Freiman ideals were
provided in [8]. For example, it was shown that $I$ is Freiman if and only if
$F(I)$ has minimal multiplicity if and only if $F(I)$ has a $2$-linear
resolution, where $F(I)$ is the fiber cone of $I$. This implies that the
defining ideal of $F(I)$ is generated by quadrics. It is a very restrictive
condition for ideals arising from combinatorial structures, which often
guarantees strong combinatorial properties.

Freiman ideals in the classes of Hibi ideals, Veronese type ideals, matroid
ideals, sortable ideals, edge ideals of several graphs, cover ideals of simple
connected unmixed bipartite graphs, and cover ideals of some classes of graphs
such as trees, circulant graphs, and whiskered graphs have been studied (see
[3, 8, 10, 11, 13]).

Squarefree monomial ideals play some important roles in Commutative Algebra,
not only for its intrinsic value but for its strong connections to
Combinatorics and Topology. Recently, a generalization of the notion of
squarefree ideal has been given in [5] by the definition of $t$-spread
monomial ideal. Let $t\geq 0$ be an integer and $u=x_{i_{1}}x_{i_{2}}\cdots
x_{i_{d}}$ a monomial in $S$ with $1\leq i_{1}\leq\cdots\leq i_{d}\leq n$. $u$
is called $t$-spread if $i_{j+1}-i_{j}\geq t$ for $1\leq j\leq d-1$. By
convention, a monomial of degree one is $t$-spread for any nonnegative integer
$t$. A monomial ideal $I\subset S$ is $t$-spread if it is generated by
$t$-spread monomials. Obviously, every monomial ideal is $0$-spread and every
$t$-spread monomial ideal with $t\geq 1$ is a squarefree monomial ideal. A
monomial ideal $I$ is called $t$-spread strongly stable if it satisfies the
following condition: for all $u\in\mathcal{G}(I)$ and $j\in supp(u)$, if $i<j$
and $x_{i}(u/x_{j})$ is $t$-spread, then $x_{i}(u/x_{j})\in I$. A monomial
ideal $I\subset S$ is called $t$-spread principal Borel if there exists a
monomial $u\in\mathcal{G}(I)$ such that $I=B_{t}(u)$, where $B_{t}(u)$ denotes
the smallest $t$-spread strongly stable ideal which contains $u$. It is
obvious that any $0$-spread principal Borel ideal is a principal Borel ideal.
Herzog and Zhu in [11, Theorem 4] gave a complete characterization of Freiman
principal Borel ideals by considering their sorted graphs.

The purpose of this paper is to provide a complete characterization of Freiman
$t$-spread principal Borel ideals for any integer $t\geq 1$.

Our paper is organized as follows. In Sect. 2, we recall some basic facts used
in the following sections. In Sect. 3, we give a complete characterization of
Freiman $t$-spread principal Borel ideals for any integer $t\geq 1$. The
results are as follows:

######  Theorem 0.1.

Let $u=\prod\limits_{j=1}^{d}x_{i_{j}}$ be a t-spread monomial of degree $d$
in $S$.

  * (1)

If $d=1$, then $B_{t}(u)$ is Freiman;

  * (2)

If $d=2$, then $B_{t}(u)$ is Freiman if and only if $i_{1}\leq 2$, or
$i_{1}=3$ and $i_{2}=t+3$.

  * (3)

If $d\geq 3$, $i_{1}=1$ and $t=1$, then $B_{t}(u)$ is Freiman if and only if
one of the follows holds:

    * (i)

$i_{j}=(j-1)t+1$ for any $j\in[d-2]$ and $i_{d-1}\in\\{(d-2)t+1,(d-2)t+2\\}$;

    * (ii)

There exsits some $p\in[d-3]$ such that $i_{j}=(j-1)t+1$ for any $j\in[p]$,
$i_{j}=(j-1)t+2$ for any $j\in[d-1]\setminus[p]$ and
$i_{d}\in\\{(d-1)t+2,(d-1)t+3\\}$.

  * (4)

If $d\geq 3$, $i_{1}=1$ and $t\geq 2$, then $B_{t}(u)$ is Freiman if and only
if one of the follows holds:

    * (i)

$i_{j}=(j-1)t+1$ for any $j\in[d-2]$ and $i_{d-1}\in\\{(d-2)t+1,(d-2)t+2\\}$,
or $i_{j}=(j-1)t+1$ for any $j\in[d-2]$, $i_{d-1}=(d-2)t+3$ and
$i_{d}=(d-1)t+3$;

    * (ii)

There exsits some $q\in[d-3]$ such that $i_{j}=(j-1)t+1$ for any $j\in[q]$,
$i_{j}=(j-1)t+2$ for any $j\in[d-1]\setminus[q]$ and
$i_{d}\in\\{(d-1)t+2,(d-1)t+3\\}$.

  * (5)

If $d\geq 3$ and $i_{1}=2$, then $B_{t}(u)$ is Freiman if and only if
$u=\prod\limits_{i=1}^{d}x_{(i-1)t+2}$ or
$u=(\prod\limits_{i=1}^{d-1}x_{(i-1)t+2})x_{(d-1)t+3}$;

  * (6)

If $d\geq 3$ and $i_{1}\geq 3$, then $B_{t}(u)$ is not Freiman.

We greatfully acknowledge the use of the computer algebra system CoCoA ([2])
for our experiments.

##  1\. Preliminaries

We firstly recall some basic facts about the sorted graph of a monomial ideal
from [11]. Sortable sets of monomials have been introduced by Sturmfels [12].
Some basic properties of sortable ideals are discussed in [4].

Let $K$ be a field and $S=K[x_{1},\ldots,x_{n}]$ the polynomial ring in $n$
variables over $K$. Let $d$ be a positive integer, $S_{d}$ the $K$-vector
space generated by the monomials of degree $d$ in $S$, and take two monomials
$u,v\in S_{d}$. We write $uv=x_{i_{1}}x_{i_{2}}\cdots x_{i_{2d}}$ with $1\leq
i_{1}\leq i_{2}\leq\cdots\leq i_{2d}\leq n$, and define

$u^{\prime}=x_{i_{1}}x_{i_{3}}\cdots x_{i_{2d-1}},\quad\text{and}\quad
v^{\prime}=x_{i_{2}}x_{i_{4}}\cdots x_{i_{2d}}.$

The pair $(u^{\prime},v^{\prime})$ is called the sorting of $(u,v)$. The map

$\operatorname{sort}:S_{d}\times S_{d}\rightarrow S_{d}\times S_{d},\
(u,v)\mapsto(u^{\prime},v^{\prime})$

is called the sorting operator. For example, if $u=x_{1}^{2}x_{3}$ and
$v=x_{2}x_{3}^{2}$, then
$\operatorname{sort}(u,v)=(x_{1}x_{2}x_{3},x_{1}x_{3}^{2})$. A pair $(u,v)$ is
called to be sorted if $\operatorname{sort}(u,v)=(u,v)$ or
$\operatorname{sort}(u,v)=(v,u)$, otherwise it is called to be unsorted.
Notice that $\operatorname{sort}(u,v)=\operatorname{sort}(v,u)$, and that if
$(u,v)$ is sorted, then $u\geq_{lex}v$.

A subset $B$ of monomials in $S_{d}$ is called sortable if
$\operatorname{sort}(B\times B)\subset B\times B$. A monomial ideal $I\subset
S$ is called a sortable ideal if $\mathcal{G}(I)$ is a sortable set.

Given a sortable ideal $I$, we associate a finite simple graph $G_{I,s}$, the
sorted graph $G_{I,s}$ of $I$, whose vertex set is $\mathcal{G}(I)$ and edge
set is defined as follows:

$E(G_{I,s})=\\{\\{u,v\\}\colon\text{$u\neq v$, $(u,v)$ is sorted}\\}.$

It was shown in [5, Proposition 3.1] that any $t$-spread principal Borel ideal
is a sortable ideal. Therefore, we may apply the following theorem to check
which of the $t$-spread principal Borel ideals are Freiman.

######  Theorem 1.1.

([11, Theorem 3]) Let $I\subset S$ be a sortable ideal. Then $I$ is Freiman if
and only if the sorted graph $G_{I,s}$ is chordal. In particular, if $G_{I,s}$
contains an induced $t$-cycle of length $t\geq 4$, then $I$ is not Freiman.

##  2\. Freiman $t$-spread principal Borel ideals

In this section, we will characterize all Freiman ideals among the $t$-spread
principal Borel ideals for any integer $t\geq 1$.

If $u=x_{i}$ for some $1\leq i\leq n$, then $B_{t}(u)=(x_{1},\ldots,x_{i})$ by
convention. It follows that $B_{t}(u)$ is Freiman from [10, Proposition 3.2
and Theorem 3.3]. Therefore, from now on, we will always assume that $d\geq 2$
and $t\geq 1$ are two integers.

######  Lemma 2.1.

Let $u=x_{i_{1}}x_{i_{2}}\cdots x_{i_{d}}$ be a $t$-spread monomial of degree
$d$ such that $i_{j}=(j-1)t+1$ for $1\leq j\leq d-1$ and $i_{d}>(d-1)t+1$.
Then $B_{t}(u)$ is Freiman.

###### Proof.

Since
$B_{t}(u)=\prod\limits_{j=1}^{d-1}x_{(j-1)t+1}(x_{(d-1)t+1},x_{(d-1)t+2},\ldots,x_{i_{d}-1},x_{i_{d}})$,
it follows that the sorted graph $G_{B_{t}(u),s}$ is a complete graph. Hence
$B_{t}(u)$ is Freiman by Theorem1.1.

######  Theorem 2.2.

Let $u=x_{i_{1}}x_{i_{2}}$ be a $t$-spread monomial of degree $2$.

  1. (a)

If $t=1$, then $B_{t}(u)$ is Freiman if and only if $i_{1}\leq 2$;

  2. (b)

If $t\geq 2$, then $B_{t}(u)$ is Freiman if and only if $i_{1}\leq 2$, or
$i_{1}=3$ and $i_{2}=t+3$.

###### Proof.

We distinguish into the following four cases:

$(1)$ If $i_{1}=1$, then $B_{t}(u)$ is Freiman by Lemma 2.1.

$(2)$ If $i_{1}=2$. We will prove that the sorted graph $G_{B_{t}(u),s}$ does
not contain an induced cycle of length $\geq 4$, thus $B_{t}(u)$ is Freiman by
Theorem 1.1.

Indeed, if there exists an induced $m$-cycle $C_{m}$ of length $m\geq 4$ in
$G_{B_{t}(u),s}$. Let
$x_{k_{1}}x_{j_{1}},x_{k_{2}}x_{j_{2}},\ldots,x_{k_{m}}x_{j_{m}}$ be the
vertices of $C_{m}$ in clockwise order, then $k_{1}\neq k_{3}$, $k_{2}\neq
k_{4}$ and $k_{i}\in\\{1,2\\}$ for any $1\leq i\leq m$. If $m\geq 5$, then
there exist at least three different elements $p,q,r$ in $\\{1,2,\ldots,m\\}$
such that $k_{p}=k_{q}=k_{r}$. It follows that $C_{m}$ contains an induced
cycle $G$ with vertices $x_{k_{p}}x_{j_{p}},x_{k_{q}}x_{j_{q}}$ and
$x_{k_{r}}x_{j_{r}}$. Note that $G$ is also an induced subgraph of
$G_{B_{t}(u),s}$, contradicting our assumption that $C_{m}$ is an induced
cycle graph in $G_{B_{t}(u),s}$.

If $m=4$. We may assume $k_{1}=1$ without loss of generality, thus $k_{3}=2$,
and $j_{1}>j_{3}$ because of no edge between the vertices $x_{k_{1}}x_{j_{1}}$
and $x_{k_{3}}x_{j_{3}}$. We consider the following two cases:

$(i)$ If $k_{2}=1$, then $k_{4}=2$ and $j_{3}\geq j_{2}>j_{4}$. It follows
that $j_{1}>j_{4}$, thus there is no edge between vertices
$x_{k_{1}}x_{j_{1}}$ and $x_{k_{4}}x_{j_{4}}$ of the sorted graph
$G_{B_{t}(u),s}$, a contradiction.

$(ii)$ If $k_{2}=2$, then $k_{4}=1$ and $j_{3}\geq j_{4}>j_{2}$. Hence
$j_{1}>j_{2}$. It follows that there exists no edge between the vertices
$x_{k_{1}}x_{j_{1}}$ and $x_{k_{2}}x_{j_{2}}$ of the sorted graph
$G_{B_{t}(u),s}$, a contradiction.

By the above arguments, we know that the sorted graph
$\mathcal{G}_{B_{t}(u),s}$ does not contain an induced cycle of length $\geq
4$.

$(3)$ If $i_{1}=3$ and $i_{2}=t+3$, then
$\mathcal{G}(B_{t}(u))=\\{x_{1}x_{t+1},x_{1}x_{t+2},x_{1}x_{t+3},x_{2}x_{t+2},x_{2}x_{t+3},\\\
x_{3}x_{t+3}\\}$. In particular, if $t=1$, then
$\mathcal{G}(B_{1}(u))=\\{x_{1}x_{2},x_{1}x_{3},x_{1}x_{4},x_{2}x_{3},x_{2}x_{4},x_{3}x_{4}\\}$.
In this case, $G_{B_{t}(u),s}$ contains an induced $4$-cycle with vertices
$x_{1}x_{2},x_{2}x_{3},x_{3}x_{4}$ and $x_{1}x_{4}$. This yields that
$B_{t}(u)$ is not Freiman by Theorem 1.1. If $t\geq 2$, then the sorted graph
$G_{B_{t}(u),s}$ is a subgraph of a complete graph with $6$ vertices obtained
by deleting an edge $\\{x_{1}x_{t+3},x_{2}x_{t+2}\\}$. Hence $G_{B_{t}(u),s}$
is a chordal graph, it follows that $B_{t}(u)$ is Freiman by Theorem 1.1.

$(4)$ If $i_{1}=3$ and $i_{2}\geq t+4$, or $i_{1}\geq 4$, then
$G_{B_{t}(u),s}$ contains an induced $4$-cycle with vertices
$x_{1}x_{t+3},x_{3}x_{t+3},x_{2}x_{t+2}$ and $x_{2}x_{t+4}$. Theorem 1.1
implies that $B_{t}(u)$ is not Freiman.

######  Theorem 2.3.

Let $d\geq 3$ be an integer, $u=\prod\limits_{i=1}^{d}x_{(i-1)t+2}$ a
$t$-spread monomial in $S$. Then $B_{t}(u)$ is Freiman.

###### Proof.

Note that $\mathcal{G}(B_{t}(u))=A\cup\\{u\\}$, where
$A=\\{(\prod\limits_{j=1}^{i}x_{(j-1)t+1})(\prod\limits_{j=i+1}^{d}x_{(j-1)t+2})\mid
1\leq i\leq d\\}$ and $\prod\limits_{j=\ell}^{m}x_{j}=1$ if $\ell>m$. By
simple calculations, one has the pair $(u,v)$ is sorted for any
$v\in\mathcal{G}(B_{t}(u))$. Let $v_{1},v_{2}\in A$, we may assume
$v_{1}=(\prod\limits_{j=1}^{a}x_{(j-1)t+1})(\prod\limits_{j=a+1}^{d}x_{(j-1)t+2})$,
$v_{2}=(\prod\limits_{j=1}^{b}x_{(j-1)t+1})(\prod\limits_{j=b+1}^{d}x_{(j-1)t+2})$,
where $1\leq a<b\leq d$. Thus
$v_{1}v_{2}=(\prod\limits_{j=1}^{a}x_{(j-1)t+1}^{2})(\prod\limits_{j=a+1}^{b}x_{(j-1)t+1}x_{(j-1)t+2})(\prod\limits_{j=b+1}^{d}x_{(j-1)t+2}^{2})$.
It follows that the pair $(v_{1},v_{2})$ is sorted. Hence the sorted graph
$G_{B_{t}(u),s}$ is a complete graph, the desired result follows from Theorem
1.1.

######  Theorem 2.4.

Let $d\geq 3$ be an integer,
$u=(\prod\limits_{i=1}^{d-1}x_{(i-1)t+2})x_{(d-1)t+3}$ a $t$-spread monomial
of degree $d$ in $S$. Then $B_{t}(u)$ is Freiman.

###### Proof.

Note that $\mathcal{G}(B_{t}(u))=\\{u_{1}\\}\cup A\cup B\cup\\{u\\}$, where
$u_{1}=\prod\limits_{j=1}^{d}x_{(j-1)t+1}$,
$A=\\{(\prod\limits_{j=1}^{p}x_{(j-1)t+1})(\prod\limits_{j=p+1}^{d}x_{(j-1)t+2})\mid
0\leq p\leq d-1\\}$,
$B=\\{(\prod\limits_{j=1}^{q}x_{(j-1)t+1})(\prod\limits_{j=q+1}^{d-1}x_{(j-1)t+2})\cdot
x_{(d-1)t+3}\mid 1\leq q\leq d-1\\}$ and $\prod\limits_{j=\ell}^{m}x_{j}=1$ if
$\ell>m$.

It is enough to show that the sorted graph $G_{B_{t}(u),s}$ of $B_{t}(u)$ is a
chordal graph by Theorem 1.1.

Let $C_{\ell}$ be an induced cycle of length $\ell\geq 4$ in $G_{B_{t}(u),s}$
and we label its vertices $v_{1},v_{2},\ldots,v_{\ell}$ in clockwise order. By
simple calculations, we obtain the pairs $(u,v)$ and $(u_{1},v)$ are sorted
for any $v\in\mathcal{G}(B_{t}(u))$. It follows that
$u,u_{1}\not\in\\{v_{1},v_{2},\ldots,v_{\ell}\\}$. Let $w_{1},w_{2}$ be two
vertices of $C_{\ell}$. We distinguish into the following three cases:

(i) If $w_{1},w_{2}\in A$, we may assume
$w_{1}=(\prod\limits_{j=1}^{a}x_{(j-1)t+1})(\prod\limits_{j=a+1}^{d}x_{(j-1)t+2})$,
$w_{2}=(\prod\limits_{j=1}^{b}x_{(j-1)t+1})(\prod\limits_{j=b+1}^{d}x_{(j-1)t+2})$
where $0\leq a<b\leq d-1$. Thus

$w_{1}w_{2}=(\prod\limits_{j=1}^{a}x_{(j-1)t+1}^{2})(\prod\limits_{j=a+1}^{b}x_{(j-1)t+1}x_{(j-1)t+2})(\prod\limits_{j=b+1}^{d}x_{(j-1)t+2}^{2}).$

It follows that the pair $(w_{1},w_{2})$ is sorted.

(ii) If $w_{1},w_{2}\in B$, then, by an argument similar to (i), one has the
pair $(w_{1},w_{2})$ is also sorted.

(iii) If $w_{1}\in A$, $w_{2}\in B$, then
$w_{1}=(\prod\limits_{j=1}^{a}x_{(j-1)t+1})(\prod\limits_{j=a+1}^{d}x_{(j-1)t+2})$,
$w_{2}=(\prod\limits_{j=1}^{b}x_{(j-1)t+1})\\\
\cdot(\prod\limits_{j=b+1}^{d-1}x_{(j-1)t+2})x_{(d-1)t+3}$ for some $a,b$.
Note that $x_{(d-1)t+2}$ is a factor of $w_{1}$ and $x_{(d-1)t+3}$ is a factor
of $w_{2}$, it follows that the pair $(w_{1},w_{2})$ is also sorted if and
only if $a\geq b$.

If $\ell\geq 5$, then there exist at least three different elements
$v_{i_{1}},v_{i_{2}},v_{i_{3}}\in A$ or $v_{i_{1}},v_{i_{2}},v_{i_{3}}\in B$.
It follows that $C_{\ell}$ contains an induced cycle $G$ with vertices
$v_{i_{1}},v_{i_{2}}$ and $v_{i_{3}}$ by case (i) or (ii). Moreover $G$ is
also an induced subgraph of $G_{B_{t}(u),s}$, contradicting our assumption
that $C_{\ell}$ is an induced cycle graph in $G_{B_{t}(u),s}$.

If $\ell=4$. Let $v_{1}\in A$, then $v_{3}\in B$ since there exists no edge
between the vertices $v_{1}$ and $v_{3}$. We prove the desired results when
$v_{2}\in A$, and the case $v_{2}\in B$ can be shown by similar arguments. Let
$v_{2}\in A$, then $v_{4}\in B$. We may assume that
$v_{1}=(\prod\limits_{j=1}^{a}x_{(j-1)t+1})(\prod\limits_{j=a+1}^{d}x_{(j-1)t+2})$,
$v_{2}=(\prod\limits_{j=1}^{b}x_{(j-1)t+1})(\prod\limits_{j=b+1}^{d}x_{(j-1)t+2})$,
$v_{3}=(\prod\limits_{j=1}^{c}x_{(j-1)t+1})(\prod\limits_{j=c+1}^{d-1}x_{(j-1)t+2})x_{(d-1)t+3}$
and
$v_{4}=(\prod\limits_{j=1}^{e}x_{(j-1)t+1})(\prod\limits_{j=e+1}^{d-1}x_{(j-1)t+2})x_{(d-1)t+3}$,
where $a\neq b$ and $c\neq e$. Note that $x_{(d-1)t+2}$ is a common factor of
$v_{1}$ and $v_{2}$, and $x_{(d-1)t+3}$ is a common factor of $v_{3}$ and
$v_{4}$. Hence $a\geq e$ and $b\geq c$ since $\\{v_{1},v_{4}\\}$ and
$\\{v_{2},v_{3}\\}$ are the two edges of $C_{\ell}$. If $a>b$, then $a>c$,
this implies that $\\{v_{1},v_{3}\\}$ is an edge of $C_{\ell}$. If $b>a$, then
$b>e$, this implies that $\\{v_{2},v_{4}\\}$ is an edge of $C_{\ell}$. Hence,
in both cases, contradicting our assumption that that $C_{\ell}$ is an induced
cycle of length $\ell$ in $G_{B_{t}(u),s}$. We finished the proof.

######  Theorem 2.5.

Let $d\geq 3$ be an integer, $u=\prod\limits_{j=1}^{d}x_{i_{j}}$ a $t$-spread
monomial of degree $d$ in $S$.

  * (1)

If $i_{1}=2$, then $B_{t}(u)$ is Freiman if and only if
$u=\prod\limits_{i=1}^{d}x_{(i-1)t+2}$ or
$u=(\prod\limits_{i=1}^{d-1}x_{(i-1)t+2})x_{(d-1)t+3}$;

  * (2)

If $i_{1}\geq 3$, then $B_{t}(u)$ is not Freiman.

###### Proof.

(1) First, if $u=\prod\limits_{i=1}^{d}x_{(i-1)t+2}$ or
$u=(\prod\limits_{i=1}^{d-1}x_{(i-1)t+2})x_{(d-1)t+3}$, then $B_{t}(u)$ is
Freiman by Theorems 2.3 and 2.4. In the remaining cases, we distinguish into
the following two cases:

$(i)$ Let $d=3$ and $u=x_{2}x_{i_{2}}x_{i_{3}}$. If $i_{2}=t+2$ and $i_{3}\geq
2t+4$, then $A\subset\mathcal{G}(B_{t}(u))$, where
$A=\\{x_{1}x_{t+2}x_{2t+2},x_{1}x_{t+2}x_{2t+4},x_{1}x_{t+1}x_{2t+3},x_{2}x_{t+2}x_{2t+3}\\}$.
It’s easy to see that the graph with the vertex set $A$ is an induced
$4$-cycle in $G_{B_{t}(u),s}$. If $i_{2}\geq t+3$, then
$B\subset\mathcal{G}(B_{t}(u))$, where
$B=\\{x_{1}x_{t+1}x_{2t+3},x_{1}x_{t+3}x_{2t+3},x_{1}x_{t+2}x_{2t+2},x_{2}x_{t+2}x_{2t+3}\\}$.
Moreover, the graph with the vertex set $B$ is an induced $4$-cycle in
$G_{B_{t}(u),s}$. In both cases, Theorem 1.1 implies that $B_{t}(u)$ is not
Freiman.

$(ii)$ Suppose $d\geq 4$ and $u=x_{2}\prod\limits_{j=2}^{d}x_{i_{j}}$. If
there exists some $i_{j}=(j-1)t+3$ for $2\leq j\leq d-1$, then
$C\subset\mathcal{G}(B_{t}(u))$, where
$v=\prod\limits_{j=1}^{d-3}x_{(j-1)t+1}$ and
$C=\\{x_{(d-3)t+1}x_{(d-2)t+1}x_{(d-1)t+3}v,x_{(d-3)t+1}x_{(d-2)t+3}x_{(d-1)t+3}v,x_{(d-3)t+1}x_{(d-2)t+2}x_{(d-1)t+2}v,\\\
x_{(d-3)t+2}x_{(d-2)t+2}x_{(d-1)t+3}v\\}$. It’s easy to see that the graph
with the vertex set $C$ is an induced $4$-cycle in $G_{B_{t}(u),s}$. If
$i_{j}\geq(j-1)t+4$ for some $2\leq j\leq d$, then
$D\subset\mathcal{G}(B_{t}(u))$, where
$D=\\{x_{(d-3)t+1}x_{(d-2)t+2}x_{(d-1)t+2}v,x_{(d-3)t+1}x_{(d-2)t+2}x_{(d-1)t+4}v,\\\
x_{(d-3)t+1}x_{(d-2)t+1}x_{(d-1)t+3}v,x_{(d-3)t+2}x_{(d-2)t+2}x_{(d-1)t+3}v\\}$
and $v=\prod\limits_{j=1}^{d-3}x_{(j-1)t+1}$. Moreover, the graph with the
vertex set $D$ is an induced $4$-cycle in $G_{B_{t}(u),s}$. In both cases,
Theorem 1.1 implies that $B_{t}(u)$ is not Freiman.

(2) Note that $A\subset\mathcal{G}(B_{t}(u))$, where
$A=\\{x_{1}x_{t+1}x_{2t+3}v,x_{2}x_{t+2}x_{2t+3}v,x_{1}x_{t+2}x_{2t+2}v,\\\
x_{1}x_{t+3}x_{2t+3}v\\}$, $v=\prod\limits_{j=4}^{d}x_{(j-1)t+3}$ and we
stipulate $\prod\limits_{j=\ell}^{d}x_{(j-1)t+3}=1$ if $\ell>d$. It’s obvious
that the graph with the vertex set $A$ is an induced $4$-cycle in
$G_{B_{t}(u),s}$. Theorem 1.1 implies that $B_{t}(u)$ is not Freiman.

######  Lemma 2.6.

Let $S=K[x_{1},\ldots,x_{n}]$ and $S^{\prime}=S[x_{n+1},\ldots,x_{n+t}]$ be
two polynomial rings over field $K$. Let $u=x_{1}x_{i_{2}}\cdots x_{i_{d}}$ is
a $t$-spread monomial of degree $d$ in $S^{\prime}$ and the map

$\varphi_{t}:S^{\prime}\longrightarrow S,\ u\longmapsto
x_{i_{2}-t}x_{i_{3}-t}\cdots x_{i_{d}-t}.$

Then $B_{t}(u)$ is Freiman if and only if $B_{t}(\varphi_{t}(u))$ is Freiman.

###### Proof.

Let $u_{1}=x_{1}x_{i_{2}}\cdots x_{i_{d}}$, $u_{2}=x_{1}x_{j_{2}}\cdots
x_{j_{d}}$ be two $t$-spread monomials of degree $d$ in $S^{\prime}$. From the
definition of $\varphi_{t}$, one has the pair $(u_{1},u_{2})$ is sorted in
$S^{\prime}$ if and only if the pair $(\varphi_{t}(u_{1}),\varphi_{t}(u_{2}))$
is sorted in $S$. It follows that the sorted graphs $G_{B_{t}(u),s}$ and
$G_{B_{t}(\varphi_{t}(u)),s}$ are isomorphic. Hence $B_{t}(u)$ is Freiman if
and only if $B_{t}(\varphi_{t}(u))$ is Freiman from Theorem 1.1.

Let $m$ be a positive integer, we set $[m]=\\{1,\ldots,m\\}$.

######  Theorem 2.7.

Let $d\geq 3$ be an integer, $u=x_{1}\prod\limits_{j=2}^{d}x_{i_{j}}$ a
$t$-spread monomial of degree $d$ in $S$.

  * (1)

If $t=1$, then $B_{t}(u)$ is Freiman if and only if one of the follows holds:

    * (i)

$i_{j}=(j-1)t+1$ for any $j\in[d-2]$ and $i_{d-1}\in\\{(d-2)t+1,(d-2)t+2\\}$;

    * (ii)

There exsits some $p\in[d-3]$ such that $i_{j}=(j-1)t+1$ for any $j\in[p]$,
$i_{j}=(j-1)t+2$ for any $j\in[d-1]\setminus[p]$ and
$i_{d}\in\\{(d-1)t+2,(d-1)t+3\\}$.

  * (2)

If $t\geq 2$, then $B_{t}(u)$ is Freiman if and only if one of the follows
holds:

  * (i)

$i_{j}=(j-1)t+1$ for any $j\in[d-2]$ and $i_{d-1}\in\\{(d-2)t+1,(d-2)t+2\\}$,
or $i_{j}=(j-1)t+1$ for any $j\in[d-2]$, $i_{d-1}=(d-2)t+3$ and
$i_{d}=(d-1)t+3$;

  * (ii)

There exsits some $q\in[d-3]$ such that $i_{j}=(j-1)t+1$ for any $j\in[q]$,
$i_{j}=(j-1)t+2$ for any $j\in[d-1]\setminus[q]$ and
$i_{d}\in\\{(d-1)t+2,(d-1)t+3\\}$.

###### Proof.

The desired results hold by repeatedly appling Lemmas 2.1, 2.6 and Theorems
2.2 $\sim$ 2.5.

Acknowledgments

This research is supported by the National Natural Science Foundation of China
(No.11271275) and by foundation of the Priority Academic Program Development
of Jiangsu Higher Education Institutions.

## References

  * [1] W. Bruns and J. Herzog, Cohen-Macaulay rings, Revised Edition, Cambridge University Press, the United Kingdom (1998).
  * [2] CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra, Avaible at http://cocoa.dima.unige.it.
  * [3] B. Drabkin and L. Guerrieri On quasi-equigenerated and Freiman cover ideals of graphs, Comm. Algebra, 48(10) (2020), 4413-4435.
  * [4] V. Ene and J. Herzog, Gröbner Bases in Commutative Algebra, Grad. Stud. Math. 130, Amer. Math. Soc., Providence, RI 2012.
  * [5] V. Ene, J. Herzog and A. Asloob Qureshi, $t$-spread strongly stable ideals, Comm. Algebra 47(12) (2019), 5303-5316.
  * [6] S. Eliahou, J. Herzog and M. Mohammadi Saem, Monomial ideals with tiny squares, J. Algebra 514 (2018), 99-112.
  * [7] G. A. Freiman, Foundations of a structural theory of set addition, Translations of mathematical monographs 37, Amer. Math. Soc. Providence, Phode Island, 1973.
  * [8] J. Herzog, T. Hibi, G. Zhu, The relevance of Freiman’s theorem for combinatorial commutative algebra, Math. Z., 291(2019), 999-1014.
  * [9] J. Herzog, M. Mohammadi Saem and N. Zamani, On the number of generators of powers of an ideal, Internat. J. Algebra Comput., 29(5) (2019), 827-847.
  * [10] J. Herzog and G. J. Zhu, Freiman ideals, Comm. Algebra, 47(1) (2019), 407-423.
  * [11] J. Herzog and G. J. Zhu, Sortable Freiman ideals, Math. Notes, 107 (2020), 946-952.
  * [12] B. Sturmfels, Gröbner Bases and Convex Polytopes, Amer. Math. Soc., Providence, RI, 1995.
  * [13] G. J. Zhu, Y. K. Zhao and Y. J. Cui, Freiman cover ideals of unmixed bipartite graphs, To appear in Math. Notes.