# Freiman cover ideals of unmixed bipartite graphs

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$ in the polynomial ring
$R=k[z_{1},\ldots,z_{n}]$ 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 number of minimal generators of $I$. In this
paper we classify all simple connected unmixed bipartite graphs whose cover
ideals are Freiman ideals.

###### Key words and phrases:

Hibi ideals, Cover ideals of graphs, Unmixed bipartite graphs, Cohen-Macaulay
bipartite graphs

###### 2010 Mathematics Subject Classification:

Primary 13F20; Secondary 13H10, 13C99, 13E15

* Corresponding author

## Introduction

Let $I$ be a monomial ideal in the polynomial ring $R=k[z_{1},\ldots,z_{n}]$
over a field $k$. Let $\mu(I)$ denote the least number of generators of $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. [5]
constructed ideals of height $2$ in $k[x,y]$ such that $\mu(I^{2})=9$ and
$\mu(I)=m$, where $m\geq 6$ can be any integer.

As a consequence of a well known theorem from additive number theory, due to
Freiman [6], Herzog et. al. showed in [11, 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 [12]
called this ideal $I$ to be a Freiman ideal (or simply Freiman). Herzog et.
al. provided in [10, Theorem 2.3] several equivalent conditions for an
equigenerated monomial ideal $I$ to be a Freiman ideal. For example, they show
that $I$ is Freiman if and only if $\mu(I^{k})={\ell(I)+k-2\choose
k-1}\mu(I)-(k-1){\ell(I)+k-2\choose k}$ for some $k\geq 2$ if and only if the
fiber cone $F(I)$ of $I$ has minimal multiplicity if and only if $F(I)$ is
Cohen-Macaulay and its defining ideal has a $2$-linear resolution. It is a
very restrictive condition for ideals arising from combinatorial structures,
which often guarantees strong combinatorial properties.

Freiman ideals in the classes of principal Borel ideals, Hibi ideals, Veronese
type ideals, matroid ideals, sortable ideals, edge ideals of graphs, and cover
ideals of some classes of graphs such as trees, circulant graphs, and
whiskered graphs have been studied (see [4, 10, 12, 13]).

The purpose of this paper is to give a full classification of Freiman ideals
for cover ideals of all connected unmixed bipartite graphs.

Let $[n]$ denote the set $\\{1,\ldots,n\\}$. Thanks to this fact, let $G$ be
an unmixed bipartite graph on the vertex set
$V(G)=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$, then each of its
minimal vertex covers has the form
$\\{x_{i_{1}},\ldots,x_{i_{s}},y_{i_{s+1}},\ldots,y_{i_{n}}\\}$, where
$\\{i_{1},\ldots,i_{n}\\}=[n]$. Therefore, the set

$\mathcal{L}_{G}=\\{C\cap\\{x_{1},\ldots,x_{n}\\}\mid C\text{\ is a minimal
vertex cover of \ }G\\}$

is a sublattice of the Boolean lattice $\mathcal{L}_{n}$ on
$P_{n}=\\{p_{1},\ldots,p_{n}\\}$ such that $\emptyset\in\mathcal{L}_{G}$ and
$P_{n}\in\mathcal{L}_{G}$. In section 2, we associated the lattice
$\mathcal{L}_{G}$ with its Hibi ideal $H_{\mathcal{L}_{G}}$, which is exactly
the cover ideal of $G$, and show that the result as follows

######  Theorem 0.1.

Let $G$ be a connected unmixed bipartite graph on the vertex set
$V_{n}=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$, then
$H_{\mathcal{L}_{G}}$ is Freiman if and only if $G$ is an almost complete C-M
bipartite graph, or there exist some complete bipartite subgraphs
$K_{m_{1},m_{1}},\ldots,K_{m_{s},m_{s}}$ of $G$ such that the induced graph of
$G$ on $V_{n}\setminus(\bigcup\limits_{i=1}^{s}V_{m_{i}-1})$ is an almost
complete C-M bipartite graph, where
$V_{m_{i}}=\\{x_{i1},\ldots,x_{im_{i}}\\}\cup\\{y_{i1},\ldots,y_{im_{i}}\\}$
is the vertex set of $K_{m_{i},m_{i}}$ for any $i\in[s]$.

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

##  1\. Preliminaries

In this section, we gather together the needed definitions and basic facts,
which will be used throughout this paper. However, for more details, we refer
the reader to [2, 7, 12, 10, 14].

Let $G$ be a simple (i.e., finite, undirected, loopless and without multiple
edges) graph with the vertex set $V(G)$ and the edge set $E(G)$. Throughout
this paper, we assume that $G$ is connected without isolated vertices. A
vertex cover of $G$ is a subset $C\subset V(G)$ such that each edge has at
least one vertex in $C$. Such a vertex cover $C$ is called minimal if no
subset $C^{\prime}\subsetneq C$ is a vertex cover of $G$. The graph $G$ is
unmixed (also called well-covered) if all minimal vertex covers of $G$ have
the same cardinality. The graph $G$ is called bipartite if there are two
disjoint subsets $W,W^{\prime}\subset V(G)$ such that $V(G)=W\cup W^{\prime}$,
and $E(G)\subseteq W\times W^{\prime}$.

As stated before, if $G$ is an unmixed bipartite graph on the vertex set
$V(G)=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$, then each of its
minimal vertex covers has the form
$\\{x_{i_{1}},\ldots,x_{i_{s}},y_{i_{s+1}},\ldots,y_{i_{n}}\\}$, where
$\\{i_{1},\ldots,i_{n}\\}=[n]$. It is shown in [9] that the set

$\mathcal{L}_{G}=\\{C\cap\\{x_{1},\ldots,x_{n}\\}\mid C\text{\ is a minimal
vertex cover of \ }G\\}$

is a sublattice of the Boolean lattice $\mathcal{L}_{n}$ on
$P_{n}=\\{p_{1},\ldots,p_{n}\\}$ such that $\emptyset\in\mathcal{L}_{G}$ and
$P_{n}\in\mathcal{L}_{G}$, and for any sublattice $\mathcal{L}$ of
$\mathcal{L}_{n}$ such that $\emptyset\in\mathcal{L}$ and
$P_{n}\in\mathcal{L}$, there exists an unmixed bipartite graph $G$ such that
$\mathcal{L}=\mathcal{L}_{G}$. Attached to this lattice $\mathcal{L}_{G}$ is a
monomial ideal $H_{\mathcal{L}_{G}}$ in the polynomial ring
$S=k[x_{1},\dots,x_{n},y_{1},\dots,y_{n}]$, this ideal is called the Hibi
ideal of $\mathcal{L}_{G}$. To define $H_{\mathcal{L}_{G}}$, let
$\mathcal{J}(P_{n})$ be the set of poset ideals of $P_{n}$. Recall that a
subset $J\subset P_{n}$ is called a poset ideal of $P_{n}$, if for all $p\in
J$ with $q\in P_{n}$ and $q\leq p$, it follows that $q\in J$. Now
$H_{\mathcal{L}_{G}}$ is defined as follows:

$H_{\mathcal{L}_{G}}=(\\{u_{J}\\}_{J\in\mathcal{J}(P_{n})}),\text{\ \ where\ \
}u_{J}=(\prod\limits_{p\in J}x_{p})(\prod\limits_{p\in P_{n}\setminus
J}y_{p}).$

The ideal

$I(G)=({x_{i}y_{j}|\\{x_{i},y_{j}\\}\in E(G)})$

is called the edge ideal of $G$. Note that $H_{\mathcal{L}_{G}}$ is the
Alexander dual of $I(G)$ and actually the cover ideal of $G$. Since each
$u_{J}$ is a squarefree monomial of degree $n$, and $H_{\mathcal{L}_{G}}$ is
an equigenerated monomial ideal.

We say that a simple graph $G$ is Cohen-Macaulay (C-M for short) if the
quotient ring $R/I(G)$ is Cohen-Macaulay. Observe that if $G$ is C-M then $G$
is unmixed by [1]. A graph theoretical characterization of C-M bipartite
graphs was given in [8] and that of unmixed bipartite graphs was given in
[15].

######  Lemma 1.1.

([8, Theorem 3.4]) Let $G$ be a bipartite graph with the bipartition of its
vertices $V(G)=\\{x_{1},\dots,x_{m}\\}\cup\\{y_{1},\dots,y_{n}\\}$. Then $G$
is C-M if and only if $n=m$, and there is a labeling such that

  * (i)

$\\{x_{i},y_{i}\\}\in E(G)$ for all $i\in[n]$;

  * (ii)

If $\\{x_{i},y_{j}\\}\in E(G)$, then $i\leq j$;

  * (iii)

If $\\{x_{i},y_{j}\\},\\{x_{j},y_{k}\\}\in E(G)$ with $i<j<k$, then
$\\{x_{i},y_{k}\\}\in E(G)$.

######  Lemma 1.2.

([15, Theorem 1.1]) Let $G$ be a bipartite graph. Then $G$ is unmixed if and
only if there is a bipartition
$V(G)=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$ such that

  * (i)

$\\{x_{i},y_{i}\\}\in E(G)$ for all $i\in[n]$;

  * (ii)

If $\\{x_{i},y_{j}\\},\\{x_{j},y_{k}\\}\in E(G)$ for distinct $i,j,k\in[n]$,
then $\\{x_{i},y_{k}\\}\in E(G)$.

######  Definition 1.3.

A bipartite graph $G$ is called complete C-M if there exists a bipartition of
$V(G)=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$ such that, for any
$i,j\in[n]$, $\\{x_{i},y_{j}\\}\in E(G)$ if and only if $i\leq j$.

Let $(P_{n},\leq)$ be a finite poset with $P_{n}=\\{p_{1},\ldots,p_{n}\\}$. We
write $G(P_{n})$ for the bipartite graph on the set $V_{n}=W\cup W^{\prime}$,
where $W=\\{x_{1},\dots,x_{n}\\}$ and $W^{\prime}=\\{y_{1},\dots,y_{n}\\}$,
whose edges are those $\\{x_{i},y_{j}\\}$ such that $p_{i}\leq p_{j}$. A
bipartite graph $G$ on $V_{n}=W\cup W^{\prime}$ is said to come from a poset,
if there exists a finite poset $P_{n}$ on $\\{p_{1},\ldots,p_{n}\\}$ such that
$p_{i}\leq p_{j}$ implies $\\{x_{i},y_{j}\\}\in E(G)$, and after relabeling of
the vertices of $G$ one has $G=G(P_{n})$. Herzog and Hibi in [8] proved that a
bipartite graph $G$ is C-M if and only if $G$ comes from a poset.

######  Remark 1.4.

A complete C-M bipartite graph $G$ is connected and a C-M bipartite graph,
hence it is also an unmixed bipartite graph. It follows that $G$ comes from a
poset.

A poset $P$ is called a chain if it is totally ordered, that is if any two
elements of $P$ are comparable.

######  Theorem 1.5.

Let $G$ be an unmixed bipartite graph, which comes from a poset $P_{n}$. Then
$G$ is a complete C-M bipartite graph if and only if $P_{n}$ is a chain.

###### Proof.

Let $(P_{n},\leq)$ be a poset on $P_{n}=\\{p_{1},\ldots,p_{n}\\}$ such that
$p_{i}\leq p_{j}$ implies $i\leq j$, and $G=G(P_{n})$. For any $i,j\in[n]$
with $i\leq j$, we obtain by Definition 1.3 that $G$ is a complete C-M
bipartite graph if and only if $\\{x_{i},y_{j}\\}\in E(G)$ if and only if
$p_{i}\leq p_{j}$, as desired.

######  Theorem 1.6.

Let $G$ be a C-M bipartite graph on the vertex set
$V(G)=\\{x_{1},\dots,x_{n}\\}\\\ \cup\\{y_{1},\dots,y_{n}\\}$, and
$H_{\mathcal{L}_{G}}$ the Hibi ideal of $G$. Then $H_{\mathcal{L}_{G}}$ is
Freiman if and only if the induced subgraph of $G$ on
$V(G)\setminus\\{x_{i},y_{i}\\}$ is a complete C-M bipartite graph for some
$i\in[n]$.

###### Proof.

Let $(P_{n},\leq)$ be a poset on $P_{n}=\\{p_{1},\ldots,p_{n}\\}$ and
$G=G(P_{n})$ comes from the poset $P_{n}$. It follows from [12, Theorem 4.4]
that $H_{\mathcal{L}_{G}}$ is Freiman if and only if there exist some
$i\in[n]$ such that the subposet $P_{n}\setminus\\{p_{i}\\}$ is a chain. Let
$H$ be the induced subgraph of $G$ on $V(G)\setminus\\{x_{i},y_{i}\\}$. Then
$H$ comes from the subposet $P_{n}\setminus\\{p_{i}\\}$. Indeed, let
$p_{k},p_{\ell}\in P_{n}\setminus\\{p_{i}\\}$ such that $p_{k}\leq p_{\ell}$,
it is obvious that $k,\ell\notin\\{i\\}$ and $p_{k}\leq p_{\ell}$ in $P_{n}$.
It implies that $\\{x_{k},y_{\ell}\\}\in E(G)$ and $k,\ell\notin\\{i\\}$.
Hence $\\{x_{k},y_{\ell}\\}\in E(H)$. The desired results from Theorem 1.5.

A typical example of a Freiman cover ideal of an unmixed bipartite graph is
shown in Figure $1$.

$x_{1}$$x_{2}$$x_{4}$$x_{3}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$$Figure\
1$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$G_{1}$$G_{2}$$Figure\
4$

##  2\. unmixed bipartite graphs

A bipartite graph is called complete if its two vertices are adjacent if and
only if they are in different partite sets. The complete bipartite graph with
partite sets of size $m$ and $n$ is denoted $K_{m,n}$.

######  Theorem 2.1.

Let $G$ be an unmixed bipartite graph on the vertex set
$V_{n}=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$. Then the following
conditions are equivalent:

  * (i)

$G$ is C-M;

  * (ii)

Any complete bipartite graph $K_{m,m}$ with the vertex set
$\\{x_{i_{1}},\ldots,x_{i_{m}}\\}\cup\\{y_{i_{1}},\ldots,\\\ y_{i_{m}}\\}$
cannot be an induced subgraph of $G$, where $m\geq 2$ and
$\\{i_{1},\ldots,i_{m}\\}\subset[n]$;

  * (3)

Any complete bipartite graph $K_{2,2}$ with the vertex set
$\\{x_{i},x_{j}\\}\cup\\{y_{i},y_{j}\\}$ cannot be an induced subgraph of $G$,
where $\\{i,j\\}\subset[n]$.

###### Proof.

$(1)\Rightarrow(2)$ follows from (ii) of Lemma 1.1, and $(2)\Rightarrow(3)$ is
trivial.

$(3)\Rightarrow(1)$. We only need to find a finite poset $P_{n}$ such that
$G=G(P_{n})$ comes from this poset. Let $P_{n}=\\{p_{1},\ldots,p_{n}\\}$ and
$\leq$ denote the binary relation on $P_{n}$ defined by setting $p_{i}\leq
p_{j}$ if and only if $\\{x_{i},y_{j}\\}\in E(G)$. Lemma 1.2 implies that
$p_{i}\leq p_{i}$ for any $i\in[n]$, and if $p_{i}\leq p_{j}$ and $p_{j}\leq
p_{k}$ for any $i,j,k\in[n]$, then $p_{i}\leq p_{k}$. Let $p_{i}\leq p_{j}$
and $p_{j}\leq p_{i}$ for any $i,j\in[n]$, then $i=j$. Otherwise, the complete
bipartite graph $K_{2,2}$ on the vertex set
$\\{x_{i},x_{j}\\}\cup\\{y_{i},y_{j}\\}$ is an induced subgraph of $G$, a
contradiction. Thus $\leq$ is a partial order on $P_{n}$ and $G=G(P_{n})$
comes from the poset $P_{n}$ by [8, Lemma 3.1]. Hence $G$ is C-M, as desired.

######  Theorem 2.2.

Let $G$ be an unmixed bipartite graph on the vertex set
$V_{n}=\\{x_{1},\dots,x_{n}\\}\\\ \cup\\{y_{1},\dots,y_{n}\\}$. Suppose that
$G$ has an induced subgraph $K_{m,m}$ ($m\geq 2$), with the vertex set
$V_{m}=\\{x_{i_{1}},\ldots,x_{i_{m}}\\}\cup\\{y_{i_{1}},\ldots,y_{i_{m}}\\}$.
Let $H$ be the subgraph of $G$ induced by the subset $V_{n}\setminus V_{m-1}$,
where
$V_{m-1}=\\{x_{i_{1}},\ldots,x_{i_{m-1}}\\}\cup\\{y_{i_{1}},\ldots,y_{i_{m-1}}\\}$.
Then there exists a one-to-one correspondence between the sets
$\mathcal{M}(G)$, respectively $\mathcal{M}(H)$, of minimal vertex covers of
$G$, respectively $H$. More precisely, for all subsets $C\in V_{n}\setminus
V_{m-1}$, we have

  * (i)

If $x_{i_{m}}\in C$, then $C\in\mathcal{M}(H)\Leftrightarrow
C\cup\\{x_{i_{1}},\ldots,x_{i_{m}}\\}\in\mathcal{M}(G)$;

  * (ii)

If $x_{i_{m}}\notin C$, then $C\in\mathcal{M}(H)\Leftrightarrow
C\cup\\{y_{i_{1}},\ldots,y_{i_{m}}\\}\in\mathcal{M}(G)$.

###### Proof.

$(\Rightarrow)$ Let $x_{i_{m}}\in C$, put
$B=C\cup\\{x_{i_{1}},\ldots,x_{i_{m}}\\}$. We show that $B\in\mathcal{M}(G)$.
We distinguish into the following three cases:

(1) For any $\\{x_{k},y_{\ell}\\}\in E(H)$, we have
$C\cap\\{x_{k},y_{\ell}\\}\neq\emptyset$ since $C\in\mathcal{M}(H)$. In
particular, $B\cap\\{x_{k},y_{\ell}\\}\neq\emptyset$.

(2) For any $\\{x_{i_{k}},y_{\ell}\\}\in E(G)$ with $k\in[m]$, we have
$x_{i_{k}}\in B\cap\\{x_{i_{k}},y_{\ell}\\}$.

(3) For any $\\{x_{i_{k}},y_{i_{\ell}}\\}\in E(G)$ with $\ell\in[m-1]$ and
$k\notin[m]$. By Lemma 1.2 (ii), we obtain that $\\{x_{i_{k}},y_{i_{m}}\\}\in
E(G)$ since $\\{x_{i_{\ell}},y_{i_{m}}\\}\in E(G)$. Hence
$\\{x_{i_{k}},y_{i_{m}}\\}\in E(H)$, it implies
$C\cap\\{x_{i_{k}},y_{i_{m}}\\}\neq\emptyset$.

Note that $|C\cap\\{x_{i_{m}},y_{i_{m}}\\}|=1$, we have $y_{i_{m}}\notin C$
because of $x_{i_{m}}\in C$. It follows that $x_{i_{k}}\in C$. Thus
$B\cap\\{x_{i_{k}},y_{i_{m}}\\}=\\{x_{i_{k}}\\}$ and $B\in\mathcal{M}(G)$.

If $x_{i_{m}}\notin C$, then $y_{i_{m}}\in C$. Put
$B=C\cup\\{y_{i_{1}},\ldots,y_{i_{m}}\\}$. By similar arguments as above, we
can show that $B\in\mathcal{M}(G)$.

$(\Leftarrow)$ Let $B=C\cup\\{x_{i_{1}},\ldots,x_{i_{m}}\\}$ and
$B\in\mathcal{M}(G)$. Then $|B\cap\\{x_{i_{\ell}},y_{i_{\ell}}\\}|=1$ for any
$\ell\in[m-1]$. This implies that either
$B\cap\\{x_{i_{\ell}},y_{i_{\ell}}\\}=\\{x_{i_{\ell}}\\}$ or
$B\cap\\{x_{i_{\ell}},y_{i_{\ell}}\\}=\\{y_{i_{\ell}}\\}$. If
$B\cap\\{x_{i_{\ell}},y_{i_{\ell}}\\}=\\{x_{i_{\ell}}\\}$, then
$y_{i_{\ell}}\notin B$, it means that
$B\cap\\{x_{i_{m}},y_{i_{\ell}}\\}=\\{x_{i_{m}}\\}$ because of
$\\{x_{i_{m}},y_{i_{\ell}}\\}\in E(G)$. Set
$C=B\setminus\\{x_{i_{1}},\ldots,x_{i_{m-1}}\\}$. Then
$B\cap\\{x_{k},y_{l}\\}\neq\emptyset$ for any $\\{x_{k},y_{l}\\}\in E(H)$, and
$B\cap\\{x_{k},y_{l}\\}\subset C$. Hence $C$ is a vertex cover of $H$. Since
$|C|=|B|-(m-1)=n-m+1$, we get $C\in\mathcal{M}(H)$. If
$B\cap\\{x_{i_{\ell}},y_{i_{\ell}}\\}=\\{y_{i_{\ell}}\\}$, then
$x_{i_{\ell}}\notin B$ and
$C=B\setminus\\{y_{i_{1}},\ldots,y_{i_{m-1}}\\}\in\mathcal{M}(H)$.

For every monomial $z^{a_{1}}\cdots z^{a_{n}}\in R$, we write $Z^{\mathbf{a}}$
for $z^{a_{1}}\cdots z^{a_{n}}$, where $\mathbf{a}=(a_{1},\ldots,a_{n})$ with
$a_{i}\geq 0$ for any $i\in[n]$. We call $\mathbf{a}$ to be the exponential
vector of $z^{\mathbf{a}}$. Let $\mathcal{G}(I)$ denote the unique minimal set
of monomial generators of a monomial ideal.

######  Lemma 2.3.

([1, Lemma 10.3.19]) Let $I\subset R$ be a monomial ideal generated in a
single degree with
$\mathcal{G}(I)=\\{z^{\mathbf{a_{1}}},\ldots,z^{\mathbf{a_{m}}}\\}$, and let
$A$ be the $m\times n$ matrix whose rows are the vectors
$\\{\mathbf{a_{1}},\ldots,\mathbf{a_{m}}\\}$. Then $\ell(I)=\text{rank}\,(A)$.

Now, we are ready to prove major result of this section.

######  Theorem 2.4.

Let $G$ be a connected unmixed bipartite graph on the vertex set
$V_{n}=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$. Suppose that $G$
has an induced subgraph $K_{m,m}$ ($m\geq 2$) with the vertex set
$V_{m}=\\{x_{i_{1}},\ldots,x_{i_{m}}\\}\cup\\{y_{i_{1}},\ldots,y_{i_{m}}\\}$.
Let $H$ be the induced subgraph of $G$ on the subset $V_{n}\setminus V_{m-1}$,
where
$V_{m-1}=\\{x_{i_{1}},\ldots,x_{i_{m-1}}\\}\cup\\{y_{i_{1}},\ldots,y_{i_{m-1}}\\}$.
Let $H_{\mathcal{L}_{G}}$ (resp. $H_{\mathcal{L}_{H}}$) be the Hibi ideal of
the lattice $\mathcal{L}_{G}$ (resp. $\mathcal{L}_{H}$). Then
$H_{\mathcal{L}_{G}}$ is Freiman if and only if $H_{\mathcal{L}_{H}}$ is
Freiman.

###### Proof.

Without loss of generality, we can assume that $i_{j}=j$ for all $j\in[m]$. By
Theorem 2.2, we obtain that generators of $H_{\mathcal{L}_{G}}$ can be
obtained from generators of $H_{\mathcal{L}_{H}}$. Therefore, all generators
of $H_{\mathcal{L}_{G}}$ are of the form

$u_{1}\prod\limits_{i=1}^{m}x_{i},\ldots,u_{s}\prod\limits_{i=1}^{m}x_{i},v_{1}\prod\limits_{i=1}^{m}y_{i},\ldots,v_{t}\prod\limits_{i=1}^{m}y_{i}$

where $x_{m}u_{1},\ldots,x_{m}u_{s},y_{m}v_{1},\ldots,y_{m}v_{t}$ are all
generators of $H_{\mathcal{L}_{H}}$ and monomials $u_{i},v_{j}\in
K[x_{m+1},\ldots,x_{n},y_{m+1},\ldots,y_{n}]$ for all $i\in[s]$, $j\in[t]$. It
follows that

$None$ $\mu(H_{\mathcal{L}_{G}})=\mu(H_{\mathcal{L}_{H}})$

Now we prove that $\mu(H^{2}_{\mathcal{L}_{G}})=\mu(H^{2}_{\mathcal{L}_{H}})$.
Note that

$\displaystyle H_{\mathcal{L}_{G}}$ $\displaystyle=$
$\displaystyle(u_{1}\prod\limits_{i=1}^{m}x_{i},\ldots,u_{s}\prod\limits_{i=1}^{m}x_{i},v_{1}\prod\limits_{i=1}^{m}y_{i},\ldots,v_{t}\prod\limits_{i=1}^{m}y_{i})$
$\displaystyle=$
$\displaystyle(u_{1},\ldots,u_{s})\prod\limits_{i=1}^{m}x_{i}+(v_{1},\ldots,v_{t})\prod\limits_{i=1}^{m}y_{i}$

and

$\displaystyle H_{\mathcal{L}_{H}}$ $\displaystyle=$
$\displaystyle(x_{m}u_{1},\ldots,x_{m}u_{s},y_{m}v_{1},\ldots,y_{m}v_{t})$
$\displaystyle=$
$\displaystyle(u_{1},\ldots,u_{s})x_{m}+(v_{1},\ldots,v_{t})y_{m}.$

It follows that

$\displaystyle H^{2}_{\mathcal{L}_{G}}$ $\displaystyle=$
$\displaystyle[(u_{1},\ldots,u_{s})\prod\limits_{i=1}^{m}x_{i}+(v_{1},\ldots,v_{t})\prod\limits_{i=1}^{m}y_{i}]^{2}$
$\displaystyle=$
$\displaystyle(u_{1},\ldots,u_{s})^{2}\prod\limits_{i=1}^{m}x_{i}^{2}+(v_{1},\ldots,v_{t})^{2}\prod\limits_{i=1}^{m}y_{i}^{2}+(u_{1},\ldots,u_{s})(v_{1},\ldots,v_{t})\prod\limits_{i=1}^{m}x_{i}y_{i}$

and

$\displaystyle H^{2}_{\mathcal{L}_{H}}$ $\displaystyle=$
$\displaystyle[(u_{1},\ldots,u_{s})x_{m}+(v_{1},\ldots,v_{t})y_{m}]^{2}$
$\displaystyle=$
$\displaystyle(u_{1},\ldots,u_{s})^{2}x_{m}^{2}+(v_{1},\ldots,v_{t})^{2}y_{m}^{2}+(u_{1},\ldots,u_{s})(v_{1},\ldots,v_{t})x_{m}y_{m}.$

Note that generators of ideals
$(u_{1},\ldots,u_{s})^{2}\prod\limits_{i=1}^{m}x_{i}^{2}$,
$(v_{1},\ldots,v_{t})^{2}\prod\limits_{i=1}^{m}y_{i}^{2}$ and
$(u_{1},\ldots,u_{s})\\\
\cdot(v_{1},\ldots,v_{t})\prod\limits_{i=1}^{m}x_{i}y_{i}$ are different from
each other, and so are generators of ideals
$(u_{1},\ldots,u_{s})^{2}x_{m}^{2}$, $(v_{1},\ldots,v_{t})^{2}y_{m}^{2}$ and
$(u_{1},\ldots,u_{s})(v_{1},\ldots,v_{t})x_{m}y_{m}$. Thus we get

$\displaystyle\hskip 28.45274pt\mu(H^{2}_{\mathcal{L}_{G}})$ $\displaystyle=$
$\displaystyle\mu((u_{1},\ldots,u_{s})^{2})+\mu((v_{1},\ldots,v_{t})^{2})+\mu((u_{1},\ldots,u_{s})(v_{1},\ldots,v_{t}))$
$\displaystyle=$ $\displaystyle\mu(H^{2}_{\mathcal{L}_{H}}).\hskip
264.6107pt(2)$

By (1) and (2), it is enough to show that
$\ell(H_{\mathcal{L}_{G}})=\ell(H_{\mathcal{L}_{H}})=n-m+2$.

Since $G$ is a connected unmixed bipartite graph and $K_{m,m}$ is its unique
induced subgraph, we obtain that $H$ is a C-M bipartite graph on the vertex
set $\\{x_{m},\dots,x_{n}\\}\cup\\{y_{m},\dots,y_{n}\\}$ by Theorem 2.1 and
$H$ is connected. Indeed, there is some edge in $G$ connects a vertex of
$V_{m}$ and a vertex of $V_{n}\setminus V_{m}$. Say $x_{k}y_{\ell}\in E(G)$
with $k\in[n]\setminus[m]$ and $\ell\in[m]$. One has $x_{k}y_{m}\in E(H)$.
Actually, if $\ell\in[m-1]$, then the desired result from Lemma 1.2 because of
$x_{k}y_{\ell}\in E(H)$ and $x_{\ell}y_{m}\in E(H)$. Note that
$\\{y_{m},\ldots,y_{n}\\}$ and $\\{x_{m},\ldots,x_{j},y_{j+1},\ldots,y_{n}\\}$
are the minimal vertex covers of $H$ for all $m\leq j\leq n$. It follows that

$\\{x_{m}\cdots x_{n},\,x_{m}\cdots x_{n-1}y_{n},\,\ldots,\,x_{m}y_{m+1}\cdots
y_{n},\,y_{m}\cdots y_{n}\\}\subset\mathcal{G}(H_{\mathcal{L}_{H}}).$

Let
$\mathcal{G}(H_{\mathcal{L}_{H}})=\\{X^{\mathbf{b}_{1}},\ldots,X^{\mathbf{b}_{q}}\\}$,
where $\mathbf{b}_{j}=(b_{mj},\ldots,b_{nj},1-b_{mj},\ldots,1-b_{nj})$,
$b_{ij}\in\\{0,1\\}$, $m\leq i\leq n$ and $j\in[q]$, is the exponential vector
of monomial $X^{\mathbf{b}_{j}}=x_{m}^{b_{mj}}\cdots
x_{n}^{b_{nj}}y_{m}^{1-b_{mj}}\cdots y_{n}^{1-b_{nj}}$, and let $A$ be the
$q\times 2(n-m+1)$ matrix whose rows are the vectors
$\\{\mathbf{b_{1}},\ldots,\mathbf{b_{q}}\\}$. Let
$\mathbf{\alpha}_{0}=(\underbrace{1,\ldots,1}_{n-m+1},0,\ldots,0)$,
$\mathbf{\alpha}_{n-m+1}=(0,\ldots,0,\underbrace{1,\ldots,1}_{n-m+1})$,
$\mathbf{\alpha}_{i}=(\underbrace{1,\ldots,1}_{n-m+1-i},0,\ldots,0,\underbrace{1,\ldots,1}_{i})\in\mathbb{Z}^{2(n-m+1)}$
for any $i\in[n-m]$, then
$\\{\mathbf{\alpha}_{0},\mathbf{\alpha}_{1},\ldots,\mathbf{\alpha}_{n-m+1}\\}\subset\\{\mathbf{b_{1}},\ldots,\mathbf{b_{q}}\\}$.
Let $B$ be a matrix whose rows are the vectors
$\\{\alpha_{0},\alpha_{1},\ldots,\alpha_{n-m+1}\\}$. Then
$\text{rank}\,(B)=n-m+2$. This implies that $\text{rank}\,(A)\geq n-m+2$.

On the other hand, for any
$\mathbf{b}_{j}\in\\{\mathbf{b_{1}},\ldots,\mathbf{b_{q}}\\}$, we have

$\mathbf{b}_{j}=b_{nj}\alpha_{0}+(b_{n-1,j}-b_{nj})\alpha_{1}+\cdots+(b_{mj}-b_{m+1,j})\alpha_{n-m}+(1-b_{mj})\alpha_{n-m+1}.$

Therefore, $\text{rank}\,(A)=n-m+2$.

Let
$\mathcal{G}(H_{\mathcal{L}_{G}})=\\{X^{\mathbf{a}_{1}},\ldots,X^{\mathbf{a}_{q}}\\}$,
where $\mathbf{a}_{j}=(a_{1j},\ldots,a_{nj},1-a_{1j},\ldots,1-a_{nj})$,
$a_{ij}\in\\{0,1\\}$, $i\in[n]$ and $j\in[q]$, is the exponential vector of
$X^{\mathbf{a}_{j}}=x_{1}^{a_{1j}}\cdots x_{n}^{a_{nj}}y_{1}^{1-a_{1j}}\\\
\cdot\cdots y_{n}^{1-a_{nj}}$, and let $D$ be the $q\times 2n$ matrix whose
rows are the vectors $\\{\mathbf{a_{1}},\ldots,\mathbf{a_{q}}\\}$. For
convenience, we may assume that $x_{m}$ is a factor of $X^{\mathbf{b}_{i}}$
for any $1\leq i\leq t$ and $y_{m}$ is a factor of $X^{\mathbf{b}_{i}}$ for
any $t+1\leq i\leq n$. By the relationship between generators of ideal
$H_{\mathcal{L}_{G}}$ and $H_{\mathcal{L}_{H}}$, we obtain that
$\prod\limits_{i=1}^{m}x_{i}$ is a factor of $X^{\mathbf{a}_{i}}$ for any
$1\leq i\leq t$ and $\prod\limits_{i=1}^{m}y_{i}$ is a factor of
$X^{\mathbf{a}_{i}}$ for any $t+1\leq i\leq n$. Thus the $i$-th column of
matrix $D$ is a copy of its $m$-th column for $1\leq i\leq m-1$ and the $j$-th
column of matrix $D$ is a copy of its $(n+m)$-th column for $n+1\leq j\leq
n+m-1$. Therefore, $\text{rank}\,(D)=\text{rank}\,(A)$. The desired result
from Lemma 2.3.

######  Theorem 2.5.

Let $G$ be a connected unmixed bipartite graph on the vertex set
$V_{n}=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$. Let
$K_{m_{1},m_{1}},\ldots,K_{m_{s},m_{s}}$ be all induced complete bipartite
subgraphs of $G$ on the subsets $V_{m_{1}},\ldots,V_{m_{s}}$ of $V(G)$
respectively, where $m_{i}\geq 2$ for any $i\in[s]$ and $s\geq 1$. Let
$V_{m_{i}}=\\{x_{i1},\ldots,x_{im_{i}}\\}\cup\\{y_{i1},\ldots,y_{im_{i}}\\}$
and $H$ the induced subgraph of $G$ on the subset
$V_{n}\setminus(\bigcup\limits_{i=1}^{s}V_{m_{i}-1})$. Let
$H_{\mathcal{L}_{G}}$ (resp. $H_{\mathcal{L}_{H}}$) be the Hibi ideal of the
lattice $\mathcal{L}_{G}$ (resp. $\mathcal{L}_{H}$). Then
$H_{\mathcal{L}_{G}}$ is Freiman if and only if $H_{\mathcal{L}_{H}}$ is
Freiman.

###### Proof.

We apply induction on $s$. The case $s=1$ follows from Theorem 2.4. Now we
assume that $s\geq 2$. Let $H^{\prime}$ be the induced subgraph of $G$ on the
subset $V_{n}\setminus V_{m_{s}-1}$. Then $H_{\mathcal{L}_{G}}$ is Freiman if
and only if $H_{\mathcal{L}_{H^{\prime}}}$ is Freiman by Theorem 2.4. Note
that $H^{\prime}$ is a connected unmixed bipartite graph by Theorem 2.2 and
similar arguments in the proof of Theorem 2.4. Thus, by induction hypothesis,
$H_{\mathcal{L}_{H^{\prime}}}$ is Freiman if and only if $H_{\mathcal{L}_{H}}$
is Freiman. The proof is completed.

Two typical examples of Freiman cover ideals of unmixed bipartite graphs as in
Theorem 2.5 are shown in Figure $2$ and Figure $3$.

$x_{5}$$x_{1}$$x_{2}$$x_{4}$$x_{3}$$y_{5}$$y_{1}$$y_{2}$$y_{4}$$y_{3}$$Figure\
\
2$$x_{1}$$x_{4}$$x_{2}$$x_{5}$$x_{3}$$y_{1}$$y_{4}$$y_{2}$$y_{5}$$y_{3}$$Figure\
\ 3$

For the convenience of the following description, we call the graph $G$ in
theorem 1.6 almost complete C-M bipartite graph. An immediate consequence of
the above theorem and Theorem is the following corollary.

######  Corollary 2.6.

Let $G$ be a connected unmixed bipartite graph on the vertex set
$V_{n}=\\{x_{1},\dots,x_{n}\\}\cup\\{y_{1},\dots,y_{n}\\}$. Then
$H_{\mathcal{L}_{G}}$ is Freiman if and only if $G$ is an almost complete C-M
bipartite graph, or there exist some complete bipartite subgraphs
$K_{m_{1},m_{1}},\ldots,K_{m_{s},m_{s}}$ of $G$ such that the induced graph of
$G$ on $V_{n}\setminus(\bigcup\limits_{i=1}^{s}V_{m_{i}-1})$ is an almost
complete C-M bipartite graph, where
$V_{m_{i}}=\\{x_{i1},\ldots,x_{im_{i}}\\}\cup\\{y_{i1},\ldots,y_{im_{i}}\\}$
is the vertex set of $K_{m_{i},m_{i}}$ for any $i\in[s]$.

The following example shows that the cover ideal of the union of two disjoint
graphs, whose cover ideals are of Freiman, is not always Freiman ideal.

######  Example 2.7.

Let $H_{\mathcal{L}_{G_{1}}}=(x_{1}x_{2},x_{1}y_{2},y_{1}y_{2})$,
$H_{\mathcal{L}_{G_{2}}}=(x_{3}x_{4},x_{3}y_{4},y_{3}y_{4})$ and
$H_{\mathcal{L}_{G_{1}\sqcup G_{2}}}\\\
=H_{\mathcal{L}_{G_{1}}}H_{\mathcal{L}_{G_{2}}}$ be cover ideals of graphs
$G_{1}$, $G_{2}$ and $G_{1}\sqcup G_{2}$ in Figure $4$, respectively. By using
CoCoA, we obtain that
$H^{2}_{\mathcal{L}_{G_{1}}}=(x_{1}^{2}x_{2}^{2},x_{1}^{2}x_{2}y_{2},x_{1}^{2}y_{2}^{2},x_{1}x_{2}y_{1}y_{2},x_{1}y_{1}y_{2}^{2},y_{1}^{2}y_{2}^{2})$,
$H^{2}_{\mathcal{L}_{G_{2}}}=(x_{3}^{2}x_{4}^{2},x_{3}^{2}x_{4}y_{4},x_{3}^{2}y_{4}^{2},x_{3}x_{4}y_{3}y_{4},x_{3}y_{3}y_{4}^{2},y_{3}^{2}y_{4}^{2})$,
$H^{2}_{\mathcal{L}_{G_{1}\sqcup
G_{2}}}=H^{2}_{\mathcal{L}_{G_{1}}}H^{2}_{\mathcal{L}_{G_{2}}}$,
$\ell(H_{\mathcal{L}_{G_{1}}})=\ell(H_{\mathcal{L}_{G_{2}}})=3$ and
$\ell(H_{\mathcal{L}_{G_{1}\sqcup G_{2}}})=5$. Thus
$\mu(H^{2}_{\mathcal{L}_{G_{i}}})-\ell(H_{\mathcal{L}_{G_{i}}})\mu(H_{\mathcal{L}_{G_{i}}})+{\ell(H_{\mathcal{L}_{G_{i}}})\choose
2}=6-3\times 3+3=0$ for $i=1,2$ and $\mu(H^{2}_{\mathcal{L}_{G_{1}\sqcup
G_{2}}})-\ell(H_{\mathcal{L}_{G_{1}\cup
G_{2}}})\mu(H_{\mathcal{L}_{G_{1}\sqcup
G_{2}}})+{\ell(H_{\mathcal{L}_{G_{1}\sqcup G_{2}}})\choose 2}=36-5\times
9+10=1$. Therefore, the cover ideals of graphs $G_{1}$ and $G_{2}$ are
Freiman, but the cover ideal of their disjoint union $G_{1}\sqcup G_{2}$ is
not Freiman.

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] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York (2008).
  * [3] CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra, Avaible at http://cocoa.dima.unige.it.
  * [4] B. Drabkin and L. Guerrieri On quasi-equigenerated and Freiman cover ideals of graphs, Comm. Algebra, 48(10) (2020), 4413-4435.
  * [5] S. Eliahou, J. Herzog and M. Mohammadi Saem, Monomial ideals with tiny squares, J. Algebra 514 (2018), 99-112.
  * [6] G. A. Freiman, Foundations of a structural theory of set addition, Translations of mathematical monographs 37, Amer. Math. Soc. Providence, Phode Island, 1973.
  * [7] J. Herzog and T. Hibi, Monomial ideals, Springer-Verlag, New York (2011).
  * [8] J. Herzog and T. Hibi, Distributive lattices, Bipartite Graphs and Alexander Duality, J. Algebraic Combin., 22 (2005), 289-302.
  * [9] J. Herzog, T. Hibi and H. Ohsugi, Unmixed bipartite graphs and sublattices of the boolean lattices, J. Algebraic Combin., 30(2009), 415-420.
  * [10] J. Herzog, T. Hibi, G. Zhu, The relevance of Freiman’s theorem for combinatorial commutative algebra, Math. Z., 291(2019), 999-1014.
  * [11] 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.
  * [12] J. Herzog and G. Zhu, Freiman ideals, Comm. Algebra, 47(1) (2019), 407-423.
  * [13] J. Herzog and G. Zhu, Sortable Freiman ideals, Math. Notes, 107(5-6) (2019), 946-952.
  * [14] A. Van Tuyl, A beginner’s guide to edge and cover ideals. Monomial ideals, computations and applications, Lecture Notes in Math., 2083, Springer, 2013, 63-94.
  * [15] R. H. Villarreal, Unimxed bipartite graphs, Rev. Colombiana Mat., 41(2) (2007), 393-395.


$\displaystyle\alpha_{i,t}\alpha_{i^{\prime},t}\Pr[F_{i,t}]\Pr[F_{i^{\prime},t}]\left(\sum_{j}\frac{x_{i,t,j}x_{i^{\prime},t,j}}{p_{t,j}}-\left(\sum_{j}x_{i,t,j}\right)\left(\sum_{j}x_{i^{\prime},t,j}\right)\right)$
(27) $\displaystyle\hskip
14.22636pt\leq\Pr[F_{i,t}]\Pr[F_{i^{\prime},t}](0.5+\kappa)\left(1-\alpha_{i^{\prime},t}\sum_{j}x_{i^{\prime},t,j}\right)\alpha_{i,t}\left(\sum_{j}x_{i,t,j}\right).$

In order to argue that this inequality is indeed true, we depart from the
proof of the Bernoulli case by controlling the term
$\sum_{j}\frac{x_{i,t,j}x_{i^{\prime},t,j}}{p_{t,j}}$ via the online
constraint for the user $i^{\prime}$. By Constraint (26), we know that

$\frac{x_{i^{\prime},t,j}}{p_{t,j}}\leq 1-y_{i^{\prime},t}.$

Using this, we can bound

$\sum_{j}\frac{x_{i,t,j}x_{i^{\prime},t,j}}{p_{t,j}}\leq\left(1-y_{i^{\prime},t}\right)\sum_{j}x_{i,t,j}.$

Plugging this into the left-hand side of Equation 27 and rearranging terms, we
can conclude in a similar way as we did using Fact 4.13 in the Bernoulli case.
Afterwards, Step (S4) of the correlation bound can again proceed via syntactic
generalization which concludes the proof for general distributions.

##  Appendix D Stochastic Rewards

In Section 4 we assumed for convenience that every pair $(i,t)$ had a success
probability $q_{i,t}=1$. This was mainly for convenience of notation, as the
guarantees for our algorithm carry over to the case of arbitrary success
probabilities $q_{i,t}\in[0,1]$. The changes can furthermore be adapted to our
sample-based algorithm (as in Section 5) and algorithm for non-Bernoulli
arrivals (as in Appendix C), although for simplicity we start by extending the
algorithm for Bernoulli arrivals without samples.

We recall that we say $i$ is _allocated_ to $t$ if it is one of the at most
$c_{t}$ items which we attempt to assign to $t$, and we say it is
_successfully allocated_ to $t$ if and only if it is allocated and the
independent success indicator $\text{Ber}(q_{i,t})$ comes up heads. Note that
if for every $(i,t)$ we have that $i$ is allocated to $t$ with probability
$(0.5+\kappa)\cdot x_{i,t}$, then because of the independence of the success
indicators we have that the expected welfare contribution of $(i,t)$ is
$(0.5+\kappa)\cdot x_{i,t}\cdot q_{i,t}$ and hence we achieve a
$(0.5+\kappa)$-approximation to (LPon).

If we naturally update our definition of
$y_{i,t}:=\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot q_{i,t^{\prime}}$ (instead
of $\sum_{t^{\prime}<t}x_{i,t^{\prime}}$), many of the changes required to the
analysis are syntactic. We inductively show that the probability $(i,t)$ is
allocated is $(0.5+\kappa)\cdot x_{i,t}$, and hence have as part of the
inductive hypothesis that $\Pr[F_{i,t}]=1-(0.5+\kappa)\cdot y_{i,t}$. Thus,
the probability an early $(i,t)$ is allocated is precisely

$p_{t}\cdot\Pr[F_{i,t}]\cdot\frac{0.5+\kappa}{1-(0.5+\kappa)y_{i,t}}=(0.5+\kappa)\cdot
x_{i,t}.$

The analysis for late pairs also generalizes syntactically, with the caveat
that we must take care to consider how the independent $\text{Ber}(q_{i,t})$
affect the correlation bound of Lemma 4.9. Intuitively, as these Bernoullis
are independent of our proposals and history, they should not contribute to
worse positive correlation. This is formalized below.

We first consider the proof of 4.12. Our original proof (the grey line below)
used the bound

$\Pr[F_{i,t+1}\wedge F_{j,t+1}]\leq\Pr[F_{i,t}\wedge
F_{j,t}]\cdot\left(1-x_{i,t}\cdot\alpha_{i,t}-x_{j,t}\cdot\alpha_{j,t}+\frac{x_{i,t}\cdot
x_{j,t}}{p_{t}}\cdot\alpha_{i,t}\cdot\alpha_{j,t}\right).$

In the new setting, with the independence of successful matches, we have
instead

$\Pr[F_{i,t+1}\wedge F_{j,t+1}]\leq\Pr[F_{i,t}\wedge
F_{j,t}]\cdot\left(1-x_{i,t}\alpha_{i,t}q_{i,t}-x_{j,t}\alpha_{j,t}q_{j,t}+\frac{x_{i,t}q_{i,t}\cdot
x_{j,t}q_{j,t}}{p_{t}}\cdot\alpha_{i,t}\cdot\alpha_{j,t}\right).$

Hence, we will define $\tilde{x}_{i,t}:=x_{i,t}\cdot q_{i,t}$ and
$\tilde{x}_{j,t}:=x_{j,t}\cdot q_{j,t}$. As
$\Pr[F_{i,t+1}]/\Pr[F_{i,t}]=1-x_{i,t}\alpha_{i,t}q_{i,t}=1-\tilde{x}_{i,t}\cdot\alpha_{i,t}$
the proof proceeds identically with this syntactic change, and implies

$\Pr[F_{i,t+1}\wedge F_{j,t+1}]\leq\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}]\cdot
f(y_{i,t}+\tilde{x}_{i,t})=\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}]\cdot
f(y_{i,t+1}).$

With this change in place the proof of Lemma 4.9 can be modified syntatically
with the new definition of $y_{i,t}$. Indeed, the only property we need is
that is that $A_{i}$ should now denote the event that $i$ is _successfully_
allocated to an arrival in $[t^{i},t-1]$ (and similarly for $j$). Then,we
compute

$\Pr[A_{i}]=\sum_{t^{\prime}\in[t^{i},t-1]}(0.5+\kappa)\cdot
x_{i,t^{\prime}}\cdot q_{i,t^{\prime}}\leq 2\kappa$

where we use the updated definition of $y_{i,t}$.

We also can readily integrate these changes in our (sampling-based) algorithm
for arrivals from general distributions. In particular, we have the following
LP relaxation and algorithm.

$\displaystyle\max\ $ $\displaystyle\sum_{i,t,j}x_{i,t,j}\cdot q_{i,t,j}\cdot
v_{i,t,j}$ (General-LPon-Stochastic) s.t.
$\displaystyle\sum_{t}\sum_{j}x_{i,t,j}\cdot q_{i,t,j}\leq 1$
$\displaystyle\text{for all }i\in I$ (28) $\displaystyle\sum_{i}x_{i,t,j}\leq
p_{t,j}\cdot c_{t,j}$ $\displaystyle\text{for all }t\in[T],j\in[m]$ (29)
$\displaystyle 0\leq x_{i,t,j}\leq
p_{t,j}\cdot\left(1-\sum_{t^{\prime}<t}\sum_{j^{\prime}}x_{i,t^{\prime},j^{\prime}}\cdot
q_{i,t^{\prime},j^{\prime}}\right)$ $\displaystyle\text{for all }i\in
I,t\in[T],j\in[m]$ (30)

Algorithm 4

1:$\kappa\leftarrow 0.0115$

2:Solve (General-LPon-Stochastic) for $\\{x_{i,t,j}\\}$

3:for each time $t$ do

4: Observe index $j$ sampled from $(p_{t,j})_{j}$

5: Define users $\mathsf{FP}_{t,j}:=\textsf{PS}((x_{i,t,j}/p_{t,j})_{i\in I})$

6: for each user $i\in\mathsf{FP}_{t,j}$ do

7: if $i$ is available then

8: Allocate $i$ to $t$ with probability
$\alpha_{i,t}:=\min\left(1,\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot\sum_{t^{\prime}<t}\sum_{j^{\prime}}x_{i,t^{\prime},j^{\prime}}\cdot
q_{i,t^{\prime},j^{\prime}}}\right)$

9: Let $A_{t,j}\leftarrow\text{number of users allocated to }t\text{ with
sampled index }j\text{ thus far}$

10: Define users
$\mathsf{SP}_{t,j}:=\textsf{PS}\left(\left(\left(1-\frac{A_{t,j}}{c_{t,j}}\right)\cdot
x_{i,t,j}/p_{t,j}\right)_{i\in I}\right)$

11: for each user $i\in\mathsf{SP}_{t,j}$ with $\alpha_{i,t}=1$ do

12: if $i$ is available then

13: Compute $\rho_{i,t,j}:=\mathbb{E}\left[\mathbbm{1}[i\text{ available after
\lx@cref{creftypecap~refnum}{line:sample_defAtj_stochastic}}]\cdot\left(1-\frac{A_{t,j}}{c_{t,j}}\right)\mid
t\text{ sampled index }j\right]$

14:
$\beta_{i,t,j}\leftarrow\min\Big{(}1,\left((0.5+\kappa)\cdot\sum_{t^{\prime}<t}\sum_{j}x_{i,t^{\prime},j}\cdot
q_{i,t^{\prime},j}-(0.5-\kappa)\right)\cdot\frac{1}{\rho_{i,t,j}}\Big{)}.$

15: Allocate $i$ to $t$ with prob. ${\beta_{i,t,j}}$

To analyze the algorithm, we can now generalize
$y_{i,t}:=\sum_{t^{\prime}<t}\sum_{j^{\prime}}x_{i,t^{\prime},j^{\prime}}\cdot
q_{i,t^{\prime},j^{\prime}}$, so that
$\alpha_{i,t}=\min\left(1,\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot
y_{i,t}}\right)$ and $\beta_{i,t,j}=\min\Big{(}1,\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right)\cdot\frac{1}{\rho_{i,t,j}}\Big{)}$. Similarly, we
can define $\tilde{x}_{i,t,j}:=x_{i,t,j}\cdot q_{i,t,j}$. Using $y_{i,t}$ and
$\tilde{x}_{i,t,j}$, the arguments of Appendix C now generalize syntatically,
as described above for the Bernoulli case. The stochastic rewards do not
change the argument from Appendix C that $\rho_{i,t,j}$ is bounded away from
$0$ by a constant, and hence can be computed efficiently within a
multiplicative error factor when running the polynomial-time sample-based
algorithm.