# The toric ring of one dimensional simplicial complexes

Antonino Ficarra, Jürgen Herzog, Dumitru I. Stamate  Antonino Ficarra,
Department of mathematics and computer sciences, physics and earth sciences,
University of Messina, Viale Ferdinando Stagno d’Alcontres 31, 98166 Messina,
Italy<EMAIL_ADDRESS>Jürgen Herzog, Fakultät für Mathematik, Universität
Duisburg-Essen, 45117 Essen, Germany<EMAIL_ADDRESS>Dumitru I.
Stamate, Faculty of Mathematics and Computer Science, University of Bucharest,
Str. Academiei 14, Bucharest – 010014, Romania<EMAIL_ADDRESS>
###### Abstract.

Let $\Delta$ be a 1-dimensional simplicial complex. Then $\Delta$ may be
identified with a finite simple graph $G$. In this article, we investigate the
toric ring $R_{G}$ of $G$. All graphs $G$ such that $R_{G}$ is a normal domain
are classified. For such a graph, we determine the set $\mathcal{P}_{G}$ of
height one monomial prime ideals of $R_{G}$. In the bipartite case, and in the
case of whiskered cycles, this set is explicitly described. As a consequence,
we determine the canonical class $[\omega_{R_{G}}]$ and characterize the
Gorenstein property of $R_{G}$. For a bipartite graph $G$, we show that
$R_{G}$ is Gorenstein if and only if $G$ is unmixed. For a subclass of non-
bipartite graphs $G$, which includes whiskered cycles, $R_{G}$ is Gorenstein
if and only if $G$ is unmixed and has an odd number of vertices. Finally, it
is proved that $R_{G}$ is a pseudo-Gorenstein ring if $G$ is an odd cycle.

###### Key words and phrases:

toric rings, simplicial complexes, class group, canonical module

###### 2020 Mathematics Subject Classification:

Primary 13A02; 13P10; Secondary 05E40.

Acknowledgment. This paper was written while the first and the third author
visited the Faculty of Mathematics of Essen. D.I. Stamate was partly supported
by a grant of the Ministry of Research, Innovation and Digitization, CNCS -
UEFISCDI, project number PN-III-P1-1.1-TE-2021-1633, within PNCDI III.

## Introduction

Let $\Delta$ be a simplicial complex on vertex set $[n]=\\{1,2,\dots,n\\}$.
Typically, in Commutative Algebra, one associates to $\Delta$ the
Stanley–Reisner ring $S/I_{\Delta}$, where $S=K[x_{1},\dots,x_{n}]$, $K$ is a
field and $I_{\Delta}$ is the Stanley–Reisner ideal of $\Delta$. The theory of
Stanley–Reisner ideals has been deeply studied by many researchers. In [7],
the authors introduced a different algebraic object attached to $\Delta$,
which they called the toric ring of $\Delta$.

Let $S=K[x_{1},\dots,x_{n}]$ be the polynomial ring with coefficients in a
field $K$. For a face $F\in\Delta$, we set ${\bf x}_{F}=\prod_{i\in F}x_{i}$
if $F$ is non-empty, otherwise we set ${\bf x}_{\emptyset}=1$. Then, the toric
ring of $\Delta$ is defined to be the $K$-subalgebra

$R_{\Delta}=K[{\bf x}_{F}t:F\in\Delta]$

of $S[t]$. This algebra is standard graded if we put $\deg(x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}t^{b})=b$, for all monomials $x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}t^{b}\in R_{\Delta}$. This concept was further extended to
multicomplexes in [8], where discrete polymatroids were mainly considered.
When $R_{\Delta}$ is a normal domain, its divisor class group
$\textup{Cl}(R_{\Delta})$ can be explicitly described in terms of the
combinatorics of the pure 1-dimensional skeleton of $\Delta$. This skeleton
may be viewed as a graph, which we denote by $G_{\Delta}$. With such data, one
may compute the canonical class $[\omega_{R_{\Delta}}]$, that is, the class of
the canonical module $\omega_{R_{\Delta}}$ in $\textup{Cl}(R_{\Delta})$.
Hence, $R_{\Delta}$ is Gorenstein if and only if $[\omega_{R_{\Delta}}]=0$.
For a Noetherian normal domain $R$, this is one of the most efficient ways to
check the Gorenstein property of $R$.

In this article, we consider the toric ring of a 1-dimensional simplicial
complex $\Delta$. In this case, the 1-dimensional facets of $\Delta$ are the
edges of $G_{\Delta}$. On the other hand, given a graph $G$ on $[n]$, we may
consider the simplicial complex $\Delta$ whose facets are the edges of $G$.
Then $G=G_{\Delta}$. Therefore, we write $R_{G}$ instead of $R_{\Delta}$. With
this notation, we have $R_{G}=K[t,x_{1}t,\dots,x_{n}t,\\{{\bf x}_{e}t\\}_{e\in
E(G)}]$. We always assume that $G$ has no isolated vertices. To compute the
canonical class, one has to determine the set $\mathcal{P}_{G}$ of height one
monomial prime ideals of $R_{G}$. This is a very difficult task. On the other
hand, for the class of bipartite graphs and for certain non-bipartite graphs,
including whiskered cycles, we are able to determine such a set. Then, we
succeed in classifying the Gorenstein algebras among these classes.

The outline of the article is as follows. In Section 1, we summarize the main
results proved in [7] about the set $\mathcal{P}_{\Delta}$ of height one
monomial prime ideals of $R_{\Delta}$. When $R_{\Delta}$ is normal, then
$\omega_{R_{\Delta}}=\bigcap_{P\in\mathcal{P}_{\Delta}}P$. Thus, in principle,
one can fairly explicitly compute the canonical module and the canonical
class. By the facts (iii) and (v) recalled in Page (iii),
$\mathcal{P}_{\Delta}$ always contains the following set of prime ideals
$\mathcal{A}_{\Delta}=\\{P_{C}:C\in\mathcal{C}(G_{\Delta})\\}\cup\\{Q_{1},\dots,Q_{n}\\}$.
For the precise definitions of the primes $P_{C}$ and $Q_{i}$ see Section 1.
It is natural to ask when $\mathcal{P}_{\Delta}=\mathcal{A}_{\Delta}$. If
$R_{\Delta}$ is normal, this is equivalent to the fact that $\Delta$ is a flag
complex and $G_{\Delta}$ is a perfect graph (Theorem 1.1).

In Section 2, we consider the rings $R_{G}$. In order to apply the machinery
developed in Section 1, we need to classify the graphs $G$ such that $R_{G}$
is normal. This is accomplished in Theorem 2.2. Such a result follows by
noting that $R_{G}$ is isomorphic to the extended Rees algebra of the edge
ideal $I(G)$ of $G$, as shown in [3]. Then, by using results in [3, 9, 10,
11], we show that $R_{G}$ is a normal domain if and only if $G$ has at most
one non-bipartite connected component and this component satisfies the so-
called odd cycle condition [10]. Next, we investigate the set
$\mathcal{P}_{G}$. It turns out that the monomial ideal
$P_{0}=(t,x_{1}t,\dots,x_{n}t)$ is always a prime ideal of $R_{G}$
(Proposition 2.1). For a connected graph $G$, it is proved in Theorem 2.3 that
$P_{0}$ is a non minimal prime ideal of $(t)$ if and only if $G$ is bipartite.
These two facts are further equivalent to the property that
$\mathcal{P}_{G}=\mathcal{A}_{G}$ (Theorem 2.3(d)). Thus, in the connected
bipartite case we know precisely the set $\mathcal{P}_{G}$. Rephrasing this
theorem, we obtain that $P_{0}$ is a minimal prime if and only if $G$ is non-
bipartite (Corollary 2.4).

Hence, one is led to the problem of characterizing the connected non-bipartite
graphs $G$ such that $\mathcal{P}_{G}=\mathcal{A}_{G}\cup\\{P_{0}\\}$. This
problem is addressed in Theorem 3.1. For a connected graph $G$, we show that
if $\mathcal{P}_{G}=\mathcal{A}_{G}\cup\\{P_{0}\\}$, then $G$ must be non-
bipartite and for any induced odd cycle $G_{0}$ of $G$, we have that any
vertex in $V(G)\setminus V(G_{0})$ is adjacent to some vertex of $G_{0}$. We
expect that the converse of this statement holds as well. However, at present
we have only partial results supporting this expectation. Therefore, we
restrict our attention to unicyclic graphs. In this particular case, we obtain
that $\mathcal{P}_{G}=\mathcal{A}_{G}\cup\\{P_{0}\\}$ if and only if $G$ is a
whiskered odd cycle (Theorem 3.3).

Finally, in the last section we discuss the Gorenstein property of the rings
$R_{G}$. By combining some of the results from [7] a very general criterion
for the Gorensteiness of $R_{\Delta}$ is stated (Theorem 4.3). Then, we apply
this result to our rings $R_{G}$, in the case that $G$ is bipartite or $G$ is
an odd (whiskered) cycle. Finally, we prove that $R_{G}$ is pseudo-Gorenstein
if $G$ is an odd cycle (Proposition 4.7).

##  1\. Generalities about toric rings of simplicial complexes

In the section we summarize some basic facts from [7] about toric rings of
simplicial complexes. Let $K$ be a field. Then, the toric ring of a simplicial
complex $\Delta$ on vertex set $[n]$ is defined as the toric ring

$R_{\Delta}=K[{\bf x}_{F}t:F\in\Delta]\ \subset\ K[x_{1},\dots,x_{n},t],$

where we set ${\bf x}_{F}=\prod_{i\in F}x_{i}$, if $F$ is nonempty, and ${\bf
x}_{\emptyset}=1$, otherwise.

We denote by $G_{\Delta}$ the graph on vertex set $[n]$ and whose edges are
the 1-dimensional faces of $\Delta$. For a graph $G$, we denote by
$\mathcal{C}(G)$ the set of the minimal vertex covers of $G$. For a subset
$C\subseteq[n]$, we set $\Delta_{C}=\\{F\in\Delta:F\subseteq C\\}$.

Let $\mathcal{P}_{\Delta}$ be the set of height one monomial prime ideals of
$R_{\Delta}$. We are interested in this set, because we have
$\omega_{R_{\Delta}}=\bigcap_{P\in\mathcal{P}_{\Delta}}P$, if $R_{\Delta}$ is
a normal ring, see [2, Theorem 6.3.5(b)]. In particular,
$[\omega_{R_{\Delta}}]=\sum_{P\in\mathcal{P}_{\Delta}}[P]$ in the divisor
class group $\textup{Cl}(R_{\Delta})$ of $R_{\Delta}$.

Next, we summarize what is known about the set $\mathcal{P}_{\Delta}$.

  1. (i)

Suppose that $R_{\Delta}$ is a normal domain. Let $P_{1},\dots,P_{r}$ be the
minimal monomial prime ideals of $(t)\subseteq R_{\Delta}$. Then the classes
$[P_{1}],\dots,[P_{r}]$ generate the divisor class group
$\textup{Cl}(R_{\Delta})$ of $R_{\Delta}$. Furthermore
$\textup{Cl}(R_{\Delta})$ is free of rank $r-1$ [7, Theorem 1.1 and Corollary
1.8].

  2. (ii)

Let $P$ be a monomial prime ideal of $R_{\Delta}$, then the set
$C=\\{i:x_{i}t\in P\\}$ is a vertex cover of $G_{\Delta}$ [7, Lemma 1.2].

  3. (iii)

If $C\subseteq[n]$ is a vertex cover of $G_{\Delta}$, then the ideal
$P_{C}=({\bf x}_{F}t:F\in\Delta_{C})$ is a prime ideal containing $t$ and it
is a minimal prime ideal if and only if $C\in\mathcal{C}(G_{\Delta})$ [7,
Theorem 1.3 and Proposition 1.4].

  4. (iv)

Not all minimal monomial prime ideals of $(t)$ are of the form $P_{C}$ for
some $C\in\mathcal{C}(G_{\Delta})$, see [7, Example 1.5].

  5. (v)

The set of height one monomial prime ideals of $R_{\Delta}$ not containing $t$
is $\\{Q_{1},\dots,Q_{n}\\}$, with $Q_{i}=({\bf x}_{F}t:F\in\Delta,i\in F)$
[7, Proposition 1.9].

By (iii) and (v), the set $\mathcal{P}_{\Delta}$ of height one monomial prime
ideals of $R_{\Delta}$ contains the set
$\\{P_{C}:C\in\mathcal{C}(G_{\Delta})\\}\cup\\{Q_{1},\dots,Q_{n}\\}$. In [7,
Theorem 1.10] the authors characterized those simplicial complexes such that
this set coincides with $\mathcal{P}_{\Delta}$ and determined the canonical
class $[\omega_{R_{\Delta}}]$ in such a case [7, Theorem 1.13].

We recall that $\Delta$ is called flag if all its minimal nonfaces are of
dimension one. Equivalently, $\Delta$ is flag if and only if it is the clique
complex of $G_{\Delta}$.

######  Theorem 1.1.

Let $\Delta$ be a simplicial complex on $[n]$. Then, the following conditions
are equivalent.

  1. (a)

$R_{\Delta}$ is a normal ring and the set of height one monomial prime ideals
of $R_{\Delta}$ is the set

$\mathcal{P}_{\Delta}\ =\
\\{P_{C}:C\in\mathcal{C}(G_{\Delta})\\}\cup\\{Q_{1},\dots,Q_{n}\\}.$

  2. (b)

$\Delta$ is a flag complex and $G_{\Delta}$ is a perfect graph.

Furthermore, if any of these equivalent conditions hold, we have

$[\omega_{R_{\Delta}}]\ =\ \sum_{C\in\mathcal{C}(G)}(n+1-|C|)[P_{C}].$ (1)

##  2\. The bipartite case

Let $G$ be a graph with no isolated vertices. In this section, we consider the
algebras $R_{G}$.

For a monomial $u=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}t^{b}\in R_{G}$, we set
$\deg_{x_{i}}(u)=a_{i}$ for $1\leq i\leq n$, and $\deg_{t}(u)=b$. Moreover, if
$e=\\{i,j\\}\in E(G)$, we set ${\bf x}_{e}=x_{i}x_{j}$.

######  Proposition 2.1.

Let $G$ be any graph on $n$ vertices and let $R=R_{G}$. Then, the ideal
$P_{0}=(t,x_{1}t,x_{2}t,\dots,x_{n}t)$ is a monomial prime ideal of $R$.

###### Proof.

Since $P_{0}$ is a monomial ideal, it is enough to prove that for any two
monomials $u,v$ not belonging to $P_{0}$, then the product $uv$ is also not in
$P_{0}$. Since $u,v\notin P_{0}$ and $R=K[t,\\{x_{i}t\\}_{i\in V(G)},\\{{\bf
x}_{e}t\\}_{e\in E(G)}]$, it follows that $uv=\prod_{k=1}^{r}({\bf
x}_{e_{k}}t)$ for some edges $e_{1},\dots,e_{r}$, not necessarily distinct.
Suppose by contradiction that $uv\in P_{0}$, then $t$ divides $uv$ or $x_{j}t$
divides $uv$ for some $j$.

In the first case, $uv=tw$ for a suitable monomial $w$. In particular,
$\deg_{t}(w)=r-1$ and
$\sum_{i=1}^{n}\deg_{x_{i}}(w)=\sum_{i=1}^{n}\deg_{x_{i}}(uv)=2r$. Since
$\deg_{t}(w)=r-1$, $w$ is a product of $r-1$ generators of $R$ and we have
$\sum_{i=1}^{n}\deg_{x_{i}}(w)\leq 2(r-1)$, absurd.

Similarly, in the second case we could write $uv=(x_{j}t)w$ and
$\sum_{i=1}^{n}\deg_{x_{i}}(w)=\sum_{i=1}^{n}\deg_{x_{i}}(uv)-\deg_{x_{j}}(x_{j}t)=2r-1$.
This is again impossible because $w$ is a product of $r-1$ generators of $R$
and $\sum_{i=1}^{n}\deg_{x_{i}}(w)$ is at most $2(r-1)$.

Let $S=K[x_{1},\dots,x_{n}]$ be the standard graded polynomial ring. For a
graph $G$, the edge ideal of $G$ is the ideal $I(G)$ generated by all
monomials ${\bf x}_{e}$ with $e\in E(G)$. Set $I=I(G)$. Recall that the Rees
algebra of $I$ is the $K$-algebra

$S[It]=\bigoplus_{j\geq 0}I^{j}t^{j}=K[x_{1},\dots,x_{n},\\{{\bf
x}_{e}t\\}_{e\in E(G)}]\subset S[t],$

and the associated graded ring of $I$ is defined as
$\textup{gr}_{I}(S)=S[It]/IS[It]$.

Whereas, the extended Rees algebra of $I(G)$ is defined as

$S[It,t^{-1}]=S[It][t^{-1}]\subset S[t,t^{-1}].$

We have the isomorphism $\varphi:S[It,t^{-1}]\rightarrow R_{G}$ established by
setting $\varphi(t^{-1})=t$, $\varphi(x_{i})=x_{i}t$ for $1\leq i\leq n$, and
$\varphi({\bf x}_{e}t)={\bf x}_{e}t$ for $e\in E(G)$, see [3, Proposition
3.1].

As a first consequence, we classify all graphs $G$ such that $R_{G}$ is a
normal domain. For this purpose, we recall that a connected graph $G$ is said
to satisfy the odd cycle condition if for any two induced odd cycles $C_{1}$
and $C_{2}$ of $G$, either $C_{1}$ and $C_{2}$ have a common vertex or there
exist $i\in V(C_{1})$ and $j\in V(C_{2})$ such that $\\{i,j\\}\in E(G)$.

######  Theorem 2.2.

Let $G$ be any graph. Then $R_{G}$ is a normal domain if and only if at most
one connected component of $G$ is non-bipartite and this connected component
satisfies the odd cycle condition.

###### Proof.

Let $I=I(G)$. By [9, Proposition 2.1.2], the Rees algebra $S[It]$ is normal if
and only if the extended Rees algebra $S[It,t^{-1}]$ is normal. Since
$R_{G}\cong S[It,t^{-1}]$, it follows that $R_{G}$ is normal if and only if
$S[It]$ is normal. It is well–known that this is the case, if and only if $I$
is a normal ideal. By [11, Theorem 8.21], $I$ is normal if and only if $G$ has
at most one non-bipartite connected component $G_{i}$ and $I(G_{i})$ is a
normal ideal. By [3, Theorem 3.3], $I(G_{i})$ is normal if and only
$S[I(G_{i})t]$ is normal if and only if the toric ring $K[I(G_{i})]$ is
normal. By [10, Corollary 2.3] this is the case if and only if $G_{i}$
satisfies the odd cycle condition. The assertion follows.

Next, we want to algebraically characterize the set of height one monomial
prime ideals of $R_{G}$, for a connected graph $G$. For this aim, note that

$\textup{gr}_{I}(S)=\frac{S[It]}{IS[It]}\cong\frac{S[It,t^{-1}]}{t^{-1}S[It,t^{-1}]}\cong\frac{R_{G}}{(t)R_{G}},$
(2)

because $t^{-1}$ is mapped to $t$ under the isomorphism $\varphi$.

######  Theorem 2.3.

Let $G$ be a connected graph with $n$ vertices. Then, the following conditions
are equivalent.

  1. (a)

The associated graded ring $\textup{gr}_{I(G)}(S)$ is reduced.

  2. (b)

The ideal $(t)\subset R_{G}$ is radical.

  3. (c)

$G$ is a bipartite graph.

  4. (d)

The set

$\\{P_{C}:C\in\mathcal{C}(G)\\}\cup\\{Q_{1},\dots,Q_{n}\\}$

is the set of height one monomial prime ideals of $R_{G}$.

  5. (e)

The ideal $P_{0}=(t,x_{1}t,\dots,x_{n}t)\subset R_{G}$ is not a minimal prime
of $(t)$.

If any of the above equivalent conditions hold, then $R_{G}$ is a normal
domain.

###### Proof.

We prove the implications (a)$\Longleftrightarrow$(b),
(a)$\Longleftrightarrow$(c) and
(c)$\Rightarrow$(d)$\Rightarrow$(e)$\Rightarrow$(c).

By equation (2) the equivalence (a)$\Longleftrightarrow$(b) follows. The
equivalence (a)$\Longleftrightarrow$(c) is shown in [12, Proposition 14.3.39].

Now, assume (c). Since $G$ is bipartite, it follows that $G$ does not have odd
cycles. Thus $R_{G}$ is a normal domain by Theorem 2.2. In particular, $G$ is
triangle-free. Hence $G$ is a flag complex and a perfect graph, because it is
bipartite. Thus, statement (d) follows from Theorem 1.1(b)$\Rightarrow$(a). If
(d) holds, then $P_{0}$ is a monomial prime ideal (Proposition 2.1), but is a
not a minimal prime of $(t)$, because $P_{0}$ is not of the form $P_{C}$ for
any minimal vertex cover $C\in\mathcal{C}(G)$. Statement (e) follows.

Finally, assume (e) and suppose by contradiction that $G$ is non-bipartite.
Then $G$ has at least one induced odd cycle $G_{1}$. By Proposition 2.1,
$P_{0}$ is a monomial prime ideal. By [1, Corollary 4.33], the minimal primes
ideals containing $(t)$ are monomial prime ideals. Thus, by hypothesis (e),
there exists a proper subset $D$ of $V(G)$ such that $Q=(t,\\{x_{i}t\\}_{i\in
D})$ is a minimal prime of $(t)$ and $Q\subsetneq P_{0}$. It follows that $D$
is a vertex cover of $G$. In particular, $D\cap V(G_{1})$ is a vertex cover of
$G_{1}$. Since $G_{1}$ is an odd cycle, $D$ must contain two adjacent vertices
$i,j\in V(G_{1})$. Recall that the distance of two vertices $p,q\in V(G)$ is
defined to be the number $d(p,q)=r$ if there exists a path from $p$ to $q$ of
length $r$, that is, a sequence of $r+1$ distinct vertices
$p=v_{0},v_{1},\dots,v_{r-1},v_{r}=q$ of $G$ such that $\\{v_{i},v_{i+1}\\}\in
E(G)$, and no shorter path from $p$ to $q$ exists. If no path between $p$ and
$q$ exists, we set $d(p,q)=+\infty$.

Since $G$ is connected and $V(G)\setminus D\neq\emptyset$, the number

$m\ =\ \min\\{d(k,i):k\in V(G)\setminus D\\}$

exists and is finite.

Let $k\in V(G)\setminus D$ such that $d(k,i)=m$. Then, there exists a path of
lenght $m$, $i=v_{0},v_{1},\dots,v_{m-1},v_{m}=k$. By definition of $m$, it
follows that $v_{0},v_{1},\dots,v_{m-1}\in D$.

If $m\geq 2$, then $\\{v_{m-2},v_{m-1}\\},\\{v_{m-1},v_{m}\\}\in E(G)$. Now,
$x_{v_{m-2}}x_{v_{m-1}}t,x_{v_{m}}t\notin Q$, but
$(x_{v_{m-2}}x_{v_{m-1}}t)(x_{v_{m}}t)=(x_{v_{m-2}}t)(x_{v_{m-1}}x_{v_{m}}t)\in
Q$ because $x_{v_{m-2}}t\in Q$. This is a contradiction.

If $m=1$, then $v_{1}=k$ and $\\{i,j\\},\\{i,k\\}\in E(G)$. We have that
$x_{i}x_{j}t,x_{k}t\notin Q$. However,
$(x_{i}x_{j}t)(x_{k}t)=(x_{j}t)(x_{i}x_{k}t)\in Q$, because $x_{j}t\in Q$.
Again a contradiction. Therefore, $G$ must be bipartite and (c) follows.

Finally, under the equivalent conditions (a)-(e), $G$ is connected and
bipartite. The normality of $R_{G}$ follows from Theorem 2.2.

An immediate consequence of this result is the following corollary.

######  Corollary 2.4.

Let $G$ be a connected graph with $n$ vertices. Then $G$ is non-bipartite if
and only if

$(t,x_{1}t,\dots,x_{n}t)\in\mathcal{P}_{G}.$

##  3\. The non-bipartite case

By Corollary 2.4, if $G$ is a connected non-bipartite graph on $n$ vertices,
we have the inclusion

$\\{P_{C}:C\in\mathcal{C}(G)\\}\cup\\{(t,x_{1}t,\dots,x_{n}t)\\}\cup\\{Q_{1},\dots,Q_{n}\\}\subseteq\mathcal{P}_{G}.$
(3)

Thus, it would be interesting to characterize those connected graphs such that
equality in (3) holds. As a first step, we have the following result.

######  Theorem 3.1.

Let $G$ be a connected graph on $n$ vertices such that $R_{G}$ is a normal
domain. Consider the following statements.

  1. (a)

The set

$\mathcal{P}_{G}=\\{P_{C}:C\in\mathcal{C}(G)\\}\cup\\{(t,x_{1}t,x_{2}t,\dots,x_{n}t)\\}\cup\\{Q_{1},\dots,Q_{n}\\}$

is the set of height one monomial prime ideals of $R_{G}$.

  2. (b)

$G$ is non-bipartite and for any induced odd cycle $G_{0}$ of $G$, we have
that any vertex in $V(G)\setminus V(G_{0})$ is adjacent to some vertex of
$G_{0}$.

Then, (a) implies (b).

To prove the theorem, we recall some basic facts about semigroups and
semigroup algebras. We denote by $\Delta_{G}$ the simplicial complex on $[n]$
whose facets are the edges of the graph $G$. As customary, we identify a
monomial $x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}t^{b}\in R_{G}$ with its exponent
vector $(a_{1},\dots,a_{n},b)\in{\mathbb{Z}}^{n+1}$. Thus, the monomial
$K$-basis of $R_{G}$ corresponds to the affine semigroup
$S\subset{\mathbb{Z}}^{n+1}$ generated by the lattice points $p_{F}=\sum_{i\in
F}e_{i}+e_{n+1}\in{\mathbb{Z}}^{n+1}$, where $F\in\Delta_{G}$. Here,
$e_{1},\dots,e_{n+1}$ is the standard basis of ${\mathbb{Z}}^{n+1}$.

Following [2], we denote by ${\mathbb{Z}}S$ the smallest subgroup of
${\mathbb{Z}}^{n+1}$ containing $S$ and by
${\mathbb{R}}_{+}S\subset{\mathbb{R}}^{n+1}$ the smallest cone containing $S$.
In our case ${\mathbb{Z}}S={\mathbb{Z}}^{n+1}$. Furthermore,
$S={\mathbb{Z}}^{n+1}\cap{\mathbb{R}}_{+}S$ if $R_{G}$ is normal [2,
Proposition 6.1.2].

A hyperplane $H$, defined as the set of solutions of the linear equation
$f(x)=a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n+1}x_{n+1}=0$, is called a supporting
hyperplane of the cone ${\mathbb{R}}_{+}S$ if
$H\cap{\mathbb{R}}_{+}S\neq\emptyset$ and $f({\bf c})\geq 0$ for all ${\bf
c}\in{\mathbb{R}}_{+}S$. Since any element ${\bf c}\in{\mathbb{R}}_{+}S$ is a
linear combination with non-negative coefficients of the lattice points
$p_{F}$, with $F\in\Delta_{G}$, it follows that $H$ is a supporting hyperplane
of ${\mathbb{R}}_{+}S$, if and only if $f(p_{F})\geq 0$ for all
$F\in\Delta_{G}$.

A subset $\mathcal{F}$ of ${\mathbb{R}}_{+}S$ is called a face of
${\mathbb{R}}_{+}S$, if there exists a supporting hyperplane $H$ of
${\mathbb{R}}_{+}S$ such that $\mathcal{F}=H\cap{\mathbb{R}}_{+}S$. We may
assume that the coefficients $a_{i}$ appearing in $f(x)=0$ are integers and
$\gcd(a_{1},\dots,a_{n+1})=1$. If $H$ is the supporting hyperplane of a facet
$\mathcal{F}$, the normalized form defining $H$ is unique and we called it the
support form of $\mathcal{F}$.

Let $P\subset R_{G}$ be a monomial ideal. By [1, Propositions 2.36 and 4.33]
we have that $P$ is a monomial prime ideal if and only if there exists a face
$\mathcal{F}$ of the cone ${\mathbb{R}}_{+}S$ such that $P=({\bf
x}_{F}t:F\in\Delta_{G}\setminus\mathcal{F})$. Equivalently, $P$ is a monomial
prime ideal, if and only if there exists a supporting hyperplane $H$ of
${\mathbb{R}}_{+}S$ such that

$P\ =\ ({\bf x}_{F}t:F\in\Delta_{G}\ \text{and}\ f(p_{F})>0).$

###### Proof of Theorem 3.1.

Assume (a) holds. Then, by Corollary 2.4, $G$ is non-bipartite. Hence, $G$
contains at least one induced odd cycle. Suppose for a contradiction that (b)
is not satisfied. Then $G$ contains an induced odd cycle $G_{0}$ and a vertex
$v_{0}\in V(G)\setminus V(G_{0})$ that is not adjacent to any vertex $v\in
V(G_{0})$. After a suitable relabeling, we may assume that $v_{0}=n$.

We claim that the monomial ideal

$Q\ =\ (t,x_{1}t,\dots,x_{n-1}t,\\{x_{i}x_{j}t\\}_{i\in N_{G}(n),j\in
N_{G}(i)\setminus\\{n\\}})$

is a prime ideal of $R_{G}$. Here for a vertex $k$ of $G$, $N_{G}(k)$ denotes
the set of vertices $i$ such that $\\{i,k\\}$ is an edge of $G$.

Let $H$ be the hyperplane defined by the equation $f(x)=0$ where

$f(x)=-\sum_{i\notin N_{G}(n)}x_{i}-2x_{n}+2x_{n+1}.$

Let $F\in\Delta_{G}$. We claim that $f(p_{F})>0$ if ${\bf x}_{F}t\in Q$, and
$f(p_{F})=0$ if ${\bf x}_{F}t\notin Q$. This shows that $H$ is a supporting
hyperplane of ${\mathbb{R}}_{+}S$ where $S$ is the affine semigroup generated
by the lattice points $p_{F}$, $F\in\Delta_{G}$, and that $Q=({\bf
x}_{F}t:F\in\Delta_{G},f(p_{F})>0)$ is a monomial prime ideal.

If $F=\emptyset$, then $f(p_{\emptyset})=2$. Suppose $F=\\{i\\}$. If $i<n$,
then

$f(p_{\\{i\\}})=\begin{cases}2&\textit{if}\ i\in N_{G}(n),\\\ 1&\textit{if}\
i\notin N_{G}(n).\end{cases}$

If $F=\\{n\\}$, then $f(p_{\\{n\\}})=0$.

Finally, assume $F=\\{i,j\\}\in E(G)$. If $i=n$, then $j\in N_{G}(n)$ and
$f(p_{\\{i,j\\}})=0$ in this case. Suppose both $i$ and $j$ are different from
$n$. Then,

$f(p_{\\{i,j\\}})=\begin{cases}2&\textit{if}\ \ i,j\in N_{G}(n),\\\
1&\textit{if}\ \ i\in N_{G}(n),j\notin N_{G}(n)\ \ \textit{or}\ \ i\notin
N_{G}(n),j\in N_{G}(n),\\\ 0&\textit{if}\ \ i,j\notin N_{G}(n).\end{cases}$

Therefore, $Q$ is a prime ideal of $R_{G}$ containing $t$. Thus, there exists
a minimal monomial prime ideal $P$ such that $(t)\subset P\subseteq Q$. Hence,
$P$ is generated by a subset of the generators of $Q$ and contains $t$. We
claim that $P$ is different from $P_{C}$, for all $C\in\mathcal{C}(G)$, and
different from $(t,x_{1}t,\dots,x_{n}t)$. This contradicts (a) and shows that
(b) holds.

It is clear that $P$ is different from $(t,x_{1}t,\dots,x_{n}t)$ because
$x_{n}t\notin P$. Now, let $C\in\mathcal{C}(G)$, then $D=C\cap V(G_{0})$ is a
vertex cover of $G_{0}$. Since $G_{0}$ is an odd cycle, $D$ must contain two
adjacent vertices $i,j\in V(G_{0})$. Thus, $x_{i}x_{j}t\in P_{C}$. Since $n$
is not adjacent to any vertex $v\in V(G_{0})$, we have that $i,j\notin
N_{G}(n)$. Hence $x_{i}x_{j}t\notin Q$ and $x_{i}x_{j}t\notin P$, also. Thus,
$P$ is different from $P_{C}$, for all $C\in\mathcal{C}(G)$, as wanted.

Due to experimental evidence, we expect that statements (a) and (b) of Theorem
3.1 are indeed equivalent.

Recall that a graph $G$ is called unicyclic if $G$ is connected and contains
exactly one induced cycle. Note that a unicyclic graph $G$ satisfies the odd
cycle condition, and so $R_{G}$ is a normal domain. Next, we characterize
those unicyclic graphs such that equality holds in (3). It turns out that for
this class of graphs, the statements (a) and (b) of Theorem 3.1 are
equivalent.

For this aim, we introduce the concept of whiskered cycles. Hereafter, for
convenience and with abuse of notation, we identify the vertices of $G$ with
the variables of $R_{G}$. Let $k\geq 3$ and $a_{1},a_{2},\dots,a_{k}\geq 0$ be
non-negative integers. The whiskered cycle of type $(a_{1},\dots,a_{k})$ is
the graph $G=C(a_{1},\dots,a_{k})$ on vertex set

$V(G)=\\{x_{1},\dots,x_{k}\\}\cup\bigcup_{i=1}^{k}\bigcup_{j=1}^{a_{i}}\\{x_{i,j}\\},$

and with edge set

$E(G)=\\{\\{x_{1},x_{2}\\},\\{x_{2},x_{3}\\},\dots,\\{x_{k-1},x_{k}\\},\\{x_{k},x_{1}\\}\\}\cup\bigcup_{i=1}^{k}\bigcup_{j=1}^{a_{i}}\\{\\{x_{i},x_{i,j}\\}\\}.$

If $k$ is even (odd), $G$ is called a whiskered even (odd) cycle. The vertices
$x_{i,j}$ are called the whiskers of $x_{i}$.

For example, the whiskered cycle $C(3,2,1,0,1)$ is depicted below

The next elementary lemma is required.

######  Lemma 3.2.

Let $G=C(a_{1},\dots,a_{k})$ be a whiskered cycle and $C\in\mathcal{C}(G)$ a
minimal vertex cover. If $a_{i}>0$ for some $i$, then either $x_{i}\in C$ or
$x_{i,j}\in C$ for all $j=1,\dots,a_{i}$.

###### Proof.

Let $a_{i}>0$. Then $x_{i}$ has at least one whisker. Since $C$ is a minimal
vertex cover of $G$, we must have $C\cap\\{x_{i},x_{i,j}\\}\neq\emptyset$ for
all $j=1,\dots,a_{i}$. Suppose $x_{i}\in C$, then $x_{i,j}\notin C$ for all
$j=1,\dots,a_{i}$, by the minimality of $C$. Otherwise, if $x_{i}\notin C$,
then $x_{i,j}\in C$ for all $j=1,\dots,a_{i}$, because $C$ is a vertex cover
of $G$.

Hereafter, we regard the set $[0]$ as the empty set.

Let $G=C(a_{1},\dots,a_{k})$ be a whiskered cycle. Let $j\geq 3$ be a positive
integer and let $x_{i},x_{i+1},\dots,x_{i+j}$ be $j+1$ adjacent vertices of
the unique induced cycle of $G$. Here, if $i+p$ exceeds $k$, for some $1\leq
p\leq j$, we take the remainder modulo $k$. Then, the whisker interval
$W(i,i+j)$ is defined as

$\displaystyle W(i,i+j)$
$\displaystyle=\\{x_{i},x_{i+1},\dots,x_{i+j}\\}\cup\bigcup_{\ell=i+1}^{i+j-1}\bigcup_{h=1}^{a_{\ell}}\\{x_{\ell,h}\\}$
$\displaystyle=\\{x_{i},x_{i+1},\dots,x_{i+j}\\}\cup\\{\text{whiskers of}\
x_{i+1},\dots,x_{i+j-1}\\}.$

We say that $W(i,i+j)$ is proper if
$\\{x_{1},x_{2},\dots,x_{k}\\}\not\subseteq W(i,i+j)$.

Note that, if $i_{1}\leq i_{2}\leq i_{1}+j_{1}-1$ and $i_{1}+j_{1}\leq
i_{2}+j_{2}$, then

$W(i_{1},i_{1}+j_{1})\cup W(i_{2},i_{2}+j_{2})=W(i_{1},i_{2}+j_{2}).$

We say that $W(i_{1},i_{1}+j_{1})$ and $W(i_{2},i_{2}+j_{2})$ are whisker-
disjoint, if

$|W(i_{1},i_{1}+j_{1})\cap W(i_{2},i_{2}+j_{2})|\leq 1,$

that is $W(i_{1},i_{1}+j_{1})$ and $W(i_{2},i_{2}+j_{2})$ intersect at most in
one vertex.

It is clear that for any collection of proper whisker intervals
$W_{1},\dots,W_{r}$ there exist whisker-disjoint proper whisker intervals
$V_{1},\dots,V_{t}$ such that $W_{1}\cup\dots\cup W_{r}=V_{1}\cup\dots\cup
V_{t}$.

Now, we are in the position to state and prove the announced classification.

######  Theorem 3.3.

Let $G$ be a unicyclic graph on $n$ vertices. Then, the following conditions
are equivalent.

  1. (a)

The set

$\mathcal{P}_{G}=\\{P_{C}:C\in\mathcal{C}(G)\\}\cup\\{(t,x_{1}t,x_{2}t,\dots,x_{n}t)\\}\cup\\{Q_{1},\dots,Q_{n}\\}$

is the set of height one monomial prime ideals of $R_{G}$.

  2. (b)

$G$ is a whiskered odd cycle.

###### Proof.

Since $G$ is unicyclic, it follows from Theorem 2.2 that $R_{G}$ is normal.
The implication (a)$\Rightarrow$(b) follows immediately from Theorem 3.1.
(b)$\Rightarrow$(a). Suppose $G$ is a whiskered odd cycle. Then
$G=C(a_{1},\dots,a_{k})$ for some odd $k\geq 3$ and some non-negative integers
$a_{1},a_{2},\dots,a_{k}$. Let $G_{0}$ be the induced graph of $G$ on vertex
set $x_{1},\dots,x_{k}$. Then $G_{0}$ is an odd cycle

Let $P\subset R_{G}$ be a monomial prime ideal containing $t$ and such that
$P\not\supseteq P_{C}$ for all vertex covers $C$ of $G$. Set
$P_{0}=(t,x_{i}t,x_{i,j}t:i\in[k],j\in[a_{i}])$. We claim that

$P_{0}\subseteq P.$

The set $D=\\{x_{i}:x_{i}t\in P\\}\cup\\{x_{i,j}:x_{i,j}t\in P\\}$ is a vertex
cover of $G$. We are going to prove that $D=V(G)$. From this, it will follow
that $P_{0}\subseteq P$.

Since $D$ is a vertex cover, there exists a minimal vertex cover $C$ contained
in $D$. By Lemma 3.2, the only adjacent vertices of $C$ can be the vertices of
the cycle $G_{0}$. In particular, $C_{0}=C\cap V(G_{0})$ is a (possibly non
minimal) vertex cover of $G_{0}$.

Since $G_{0}$ is an odd cycle, $C_{0}$ must contain at least a pair of
adjacent vertices $x_{i},x_{j}$ of $G_{0}$. Suppose that for all such adjacent
vertices $x_{i},x_{j}\in C_{0}$ we have $x_{i}x_{j}t\in P$. Then, $P_{C}$
would be contained in $P$, because by Lemma 3.2 the only adjacent vertices of
$C$ can be the $x_{i}$. But this is against our assumption. Therefore, there
exist two adjacent vertices $x_{i},x_{j}\in C$ for which $x_{i}x_{j}t\notin
P$. Up to relabeling, we may assume $i=2$ and $j=3$. We claim that $x_{1}$ and
all the whiskers of $x_{2}$ and $x_{3}$ belong to $D$.

Suppose that $x_{1}\notin D$. Then $x_{1}t\notin P$. Since also
$x_{2}x_{3}t\notin P$, the product $(x_{1}t)(x_{2}x_{3}t)$ should not be in
$P$. However, $(x_{1}t)(x_{2}x_{3}t)=(x_{1}x_{2}t)(x_{3}t)\in P$, which is a
contradiction. Therefore, $x_{1}\in D$. Similarly, suppose that $x_{2,j}\notin
D$ for some $j$. Then $x_{2,j}t\notin P$. Since also $x_{2}x_{3}t\notin P$,
the product $(x_{2,j}t)(x_{2}x_{3}t)$ should not be in $P$. However,
$(x_{2,j}t)(x_{2}x_{3}t)=(x_{2}x_{2,j}t)(x_{3}t)\in P$, a contradiction.
Therefore, $x_{2,j}\in D$. Similarly $x_{3,\ell}\in D$ and our claim follows.
We distinguish two cases now.
Case 1. Suppose $k=3$. By the previous discussion,
$x_{1},x_{2},x_{3},x_{2,j},x_{3,\ell}\in D$, for all $j\in[a_{2}]$ and
$\ell\in[a_{3}]$. It remains to prove that the whiskers of $x_{1}$ belong to
$D$. Indeed, the vertex cover $C_{1}=\\{x_{1},x_{2},\text{whiskers of}\
x_{3}\\}$ is contained in $D$. Since $P_{C_{1}}\not\subseteq P$, we must have
$x_{1}x_{2}t\notin P$. By the argument used before, we obtain that all
whiskers of $x_{1}$ belong to $D$. Hence, $D=V(G)$ and so $P$ contains
$P_{0}$, as wanted.
Case 2. Suppose $k>3$. By the argument above, we have also that $x_{4}\in D$.
Hence,

$W(1,4)=\\{x_{1},x_{2},x_{3},x_{4}\\}\cup\bigcup_{i=2,3}\bigcup_{h\in[a_{i}]}\\{x_{i,h}\\}\subseteq
D.$

Now, we recursively determine vertex covers $C_{i}\subset D$ in order to
obtain each time new whisker intervals that belong to $D$, and in the end to
have that $D=V(G)$.

Let

$C_{1}=\big{(}C\setminus\\{x_{2},\text{whiskers of}\ x_{1}\ \text{and}\
x_{4}\\}\big{)}\cup\\{x_{1},x_{4}\\}\cup\\{\text{whiskers of}\ x_{2}\\}.$

It is clear that $C_{1}$ is a cover of $G$. Since, by assumption, $P$ does not
contain $P_{C_{1}}$, it follows that $P$ does not contain $x_{i}x_{j}t$, for
some adjacent vertices $x_{i},x_{j}\in C_{1}$. Since $x_{2}\notin C_{1}$, it
follows that $x_{i}x_{j}t$ is different from $x_{2}x_{3}t$. Thus, $j=i-1$ and
$i\in\\{4,\dots,k\\}$ or $j=1$ and $i=k$. Let $p$ and $q$ be the adjacent
vertices of $i-1$ and $i$, different from $i$ and $i-1$. Then $p=i-2$ and
$q=i+1$. Here we take the remainder modulo $k$, if these numbers exceed $k$.
Arguing as before,

$W(i-2,i+1)\subseteq D.$

After repeating this argument as many time as possible, if $D=V(G)$ then we
are finished. Otherwise, at a given step of this procedure, we have that there
exist integers $i_{1},j_{1}$, $\dots$, $i_{r},j_{r}$, with
$j_{1},\dots,j_{r}\geq 3$ such that

$W(i_{1},i_{1}+j_{1})\cup W(i_{2},i_{2}+j_{2})\cup\dots\cup
W(i_{r},i_{r}+j_{r})\subseteq D,$ (4)

and these whisker intervals are proper and mutually whisker-disjoint.

Now, starting from the vertex cover $C$, we construct another vertex cover
$C^{\prime}$ of $G$ contained in $D$, having the following properties:

  1. (i)

The only adjacent vertices of $C^{\prime}$ belong to the cycle $G_{0}$.

  2. (ii)

if $x_{i},x_{j}\in C^{\prime}$ are adjacent vertices that belong to a whisker
interval above, say $W(i_{a},i_{a}+j_{a})$, then either
$\\{i,j\\}=\\{i_{a},i_{a}+1\\}$ or
$\\{i,j\\}=\\{i_{a}+j_{a}-1,i_{a}+j_{a}\\}$.

The vertex cover $C^{\prime}$ having the properties (i) and (ii) is
constructed as follows. Let $W(i,i+j)$ be a whisker interval in (4). We
distinguish two cases: $j$ even, say $j=2\ell$, and $j$ odd, say $j=2\ell+1$.

If $j=2\ell$, we add to $C$ the vertices

$x_{i},x_{i+1},x_{i+3},x_{i+5},\dots,x_{i+2\ell-3},x_{i+2\ell-1},x_{i+2\ell}$

and remove all the corresponding whiskers, and moreover, we remove the
vertices

$x_{i+2},x_{i+4},\dots,x_{i+2\ell-2}$

and add all the corresponding whiskers. We call $C^{\prime}$ the resulting
set.

Whereas, if $j=2\ell+1$, we add to $C$ the vertices

$x_{i},x_{i+1},x_{i+3},x_{i+5},\dots,x_{i+2\ell-3},x_{i+2\ell-1},x_{i+2\ell+1}$

and remove all the corresponding whiskers, and moreover, we remove the
vertices

$x_{i+2},x_{i+4},\dots,x_{i+2\ell-2},x_{i+2\ell}$

and add all the corresponding whiskers. We call $C^{\prime}$ the resulting
set.

When we have more than one whisker interval, we repeat the operations above
for all whisker intervals, and call $C^{\prime}$ the set obtained in this way.
Such a set is well defined, because our whisker intervals are proper and
mutually whisker-disjoint. It is clear that $C^{\prime}$ is a vertex cover of
$G$ satisfying the properties (i) and (ii).

Now, we argue as follows. Since $P$ does not contain $P_{C^{\prime}}$ by
assumption, and since $G_{0}$ is an odd cycle, by (i) there exists two
adjacent vertices $x_{i},x_{i+1}\in C^{\prime}$ such that $x_{i}x_{i+1}t\notin
P$. If $\\{i,i+1\\}\subseteq W(i_{a},i_{a}+j_{a})$, by (ii) either
$\\{i,i+1\\}=\\{i_{a},i_{a}+1\\}$ or
$\\{i,i+1\\}=\\{i_{a}+j_{a}-1,i_{a}+j_{a}\\}$. Say,
$\\{i,i+1\\}=\\{i_{a},i_{a}+1\\}$, then arguing as before, we have that

$W(i-1,i+2)\subseteq D.$

Otherwise, if $\\{i,i+1\\}$ is not contained in any of the whisker intervals
constructed up to this point, then $W(i-1,i+2)\subseteq D$. In both cases, we
can enlarge the set of the whisker intervals contained in $D$. Therefore,
after a finite number of steps, we obtain either $D=V(G)$ or a non-proper
whisker interval is contained in $D$. In this latter case, up to relabeling we
may assume that $W(1,k)\subseteq D$. So, we only need to argue that the
whiskers of $x_{1}$ and $x_{k}$ are in $D$.

Since $W(1,k)\subseteq D$, the vertex cover

$C_{2}=\\{x_{1},x_{k}\\}\cup\\{x_{3},x_{5},\dots,x_{k-2}\\}\cup\\{\text{whiskers
of}\ x_{2},x_{4},\dots,x_{k-1}\\}$

is contained in $D$. Since $P$ does not contain $P_{C_{2}}$, we must have that
$x_{1}x_{k}t\notin P$. By the similar argument used before, $W(k-1,2)\subseteq
D$. Therefore $D=V(G)$.

Since $D=V(G)$, it follows that $P_{0}\subseteq P$. Therefore, any minimal
monomial prime ideal $P$ of $(t)$ different from $P_{C}$ for all
$C\in\mathcal{C}(G)$, must contain $P_{0}$. Thus $P=P_{0}$ by Corollary 2.4.
Hence, the set of height one monomial prime ideals containing $t$ is given by
$\\{P_{C}:C\in\mathcal{C}(G)\\}\cup\\{P_{0}\\}$ and (a) follows.

##  4\. The Gorenstein property

In this last section, we discuss the Gorenstein property for the toric ring of
a simplicial complex $\Delta$. Summarizing some of the results of [7], we have
the following

######  Lemma 4.1.

Assume that $R_{\Delta}$ is normal and let $P_{1},\dots,P_{r}$ be the height
one monomial prime ideals containing $t$ and $Q_{1},\dots,Q_{n}$ the height
one monomial prime ideals not containing $t$. Furthermore, let

$f_{j}=\sum_{i=1}^{n+1}c_{i,j}x_{i}$

be the support forms associated to $P_{j}$, $j=1,\dots,r$. Then,

  1. (a)

$\textup{Cl}(R_{\Delta})$ is generated by $[P_{1}],\dots,[P_{r}]$ with unique
relation $\sum_{i=1}^{r}c_{i,n+1}[P_{i}]=0$.

  2. (b)

For all $j=1,\dots,n$, $[Q_{j}]=-\sum_{i=1}^{r}c_{i,j}[P_{i}]$.

  3. (c)

$[\omega_{R_{\Delta}}]=\sum_{i=1}^{r}[P_{i}]+\sum_{j=1}^{n}[Q_{j}]$.

Substituting the expressions for $[Q_{j}]$ given in (b) into the formula for
$[\omega_{R_{\Delta}}]$ given in (c), we obtain

$[\omega_{R_{\Delta}}]\ =\
\sum_{i=1}^{r}[P_{i}]-\sum_{j=1}^{n}\sum_{i=1}^{r}c_{i,j}[P_{i}]\ =\
\sum_{i=1}^{r}\big{(}1-\sum_{j=1}^{n}c_{i,j}\big{)}[P_{i}].$

Hence, we have proved that

######  Corollary 4.2.

$[\omega_{R_{\Delta}}]=\sum_{i=1}^{r}(1-\sum_{j=1}^{n}c_{i,j})[P_{i}].$

######  Theorem 4.3.

The following conditions are equivalent

  1. (a)

$R_{\Delta}$ is Gorenstein.

  2. (b)

There exists an integer $a$ such that $1-\sum_{j=1}^{n}c_{i,j}=ac_{i,n+1}$ for
all $i=1,\dots,r$.

###### Proof.

Observe that $R_{\Delta}$ is Gorenstein if and only if
$[\omega_{R_{\Delta}}]=0$. By Lemma 4.1(a) and Corollary 4.2, this is the case
if and only if there exists an integer $a$ such that
$1-\sum_{j=1}^{n}c_{i,j}=ac_{i,n+1}$ for all $i=1,\dots,r$.

Now, we will apply Theorem 4.3 to the algebras $R_{G}$ which we discussed
before.

In the bipartite case, we recover the next result from [3, Corollary 4.3].

######  Proposition 4.4.

Let $G$ be a connected bipartite graph on $n$ vertices. Then $R_{G}$ is
Gorenstein if and only if $G$ is unmixed.

###### Proof.

By Theorem 2.3(d), $R_{G}$ is normal and the height one monomial prime ideals
containing $t$ are of the form $P_{C}$, $C\in\mathcal{C}(G)$. In the proof of
[7, Theorem 1.3], it is shown that the support form associated to $P_{C}$ is

$f_{C}(x)=-\sum_{i\notin C}x_{i}+x_{n+1}.$ (5)

Let $\mathcal{C}(G)=\\{C_{1},\dots,C_{r}\\}$ and $P_{i}=P_{C_{i}}$. Then, by
Theorem 4.3 and formula (5) it follows that $R_{G}$ is Gorenstein if and only
if there exists an integer $a$ such that $1-(n-|C_{i}|)=a$ for all
$i=1,\dots,r$. This yields the conclusion.

Next, we consider non-bipartite graphs.

######  Proposition 4.5.

Let $G$ be a connected non-bipartite graph with $n$ vertices satisfying the
odd cycle condition. Let $\mathcal{C}(G)=\\{C_{1},\dots,C_{r}\\}$,
$P_{i}=P_{C_{i}}$, for $i=1,\dots,r$, and
$P_{0}=(t,x_{1}t,x_{2}t,\dots,x_{n}t)$. Assume that the set of height one
monomial prime ideals containing $t$ is $\\{P_{0},P_{1},\dots,P_{r}\\}$. Then

  1. (a)

$[\omega_{R_{G}}]=(1-n)[P_{0}]+\sum_{i=1}^{r}(1-n+|C_{i}|)[P_{i}]$.

  2. (b)

$R_{G}$ is Gorenstein if and only if $n$ is odd and $G$ is unmixed.

###### Proof.

One can easily see that the support form of $P_{0}$ is
$f_{0}(x)=-\sum_{i=1}^{n}x_{i}+2x_{n+1}$. Part (a) follows from Corollary 4.2.
By using the support forms $f_{0}$ and $f_{C_{i}}$, it follows from Theorem
4.3(b) that $R_{G}$ is Gorenstein if and only if there exists an integer $a$
such that $1-n=2a$ and $1-n+|C_{i}|=a$ for all $i$. This implies that $R_{G}$
is Gorenstein if and only if $n$ is odd and $G$ is unmixed.

Finally, we consider the case in which $G$ is a $k$-cycle, which we denote by
$C_{k}$.

######  Corollary 4.6.

$R_{C_{k}}$ is Gorenstein if and only if $k\in\\{3,4,5,7\\}$.

###### Proof.

By Theorem 2.2, $R_{C_{k}}$ is normal. We claim that $R_{C_{k}}$ is Gorenstein
if and only $C_{k}$ is unmixed. If $k$ is even, $C_{k}$ is bipartite and the
claim follows from Proposition 4.4. If $k$ is odd, the claim follows from
Theorem 3.3 and Proposition 4.5.

It can be easily seen that $C_{k}$ is unmixed if $k\in\\{3,4,5,7\\}$.
Otherwise, if $k=6$ or $k>7$ then $C_{k}$ is not unmixed, as we show next.

Let $k>7$ odd, say $k=2\ell+1$. Then, $\ell\geq 4$ and

$\\{1,2,4,6,8,10,\dots,2\ell-2,2\ell\\},\ \ \
\\{1,2,4,5,7,8,10,\dots,2\ell-2,2\ell\\}$

are minimal vertex covers of $C_{k}$ of size $\ell+1$ and $\ell+2$.

Let $k\geq 6$ even, say $k=2\ell$. If $k=6$, then $\\{1,3,5\\}$ and
$\\{1,2,4,5\\}$ are minimal vertex covers of $C_{6}$ of different size.
Suppose $\ell\geq 4$, then

$\\{1,3,5,7,9,\dots,2\ell-3,2\ell-1\\},\ \ \
\\{1,2,4,5,7,9,\dots,2\ell-3,2\ell-1\\}$

are minimal vertex covers of $C_{k}$ of size $\ell$ and $\ell+1$.

Let $R$ be a standard graded Cohen–Macaulay $K$-algebra with canonical module
$\omega_{R}$. Following [4], we say that $R$ is pseudo-Gorenstein if
$\dim_{K}(\omega_{R})_{a}=1$, where $a=\min\\{i:(\omega_{R})_{i}\neq 0\\}$.

Let $G$ be a graph such that $R_{G}$ is a normal domain. By a theorem of
Hochster, $R_{G}$ is a Cohen–Macaulay $K$-algebra. Furthermore, $R_{G}$ is
standard graded with the grading given by $\deg(x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}t^{b})=b$, for all monomials $x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}t^{b}\in R_{G}$.

######  Proposition 4.7.

Let $G$ be an odd cycle. Then $R_{G}$ is pseudo-Gorenstein.

###### Proof.

Let $k$ be the number of vertices of $G$. Then $k=2\ell+1$ for some $\ell\geq
1$. Set $P_{0}=(t,x_{1}t,\dots,x_{k}t)$. By Theorem 3.3, the set of height one
monomial prime ideals of $R_{G}$ is given by
$\\{P_{C}:C\in\mathcal{C}(G)\\}\cup\\{P_{0},Q_{1},\dots,Q_{k}\\}$, and
moreover

$\omega_{R_{G}}=(\bigcap_{C\in\mathcal{C}(G)}P_{C})\cap P_{0}\cap
Q_{1}\cap\dots\cap Q_{k}.$

By [1, Corollary 4.33], $\omega_{R_{G}}$ and $\bigcap_{i=1}^{k}Q_{i}$ are
monomial ideals. Let $u\in\bigcap_{i=1}^{k}Q_{i}$ be a monomial. Note that for
each $i$, the monomial generators of $Q_{i}$ have multidegree $\geq
e_{i}+e_{k+1}$. Hence, the multidegree of $u$ is $\geq
e_{1}+\dots+e_{k}+e_{k+1}$. Thus, $u=u_{1}u_{2}\cdots
u_{b}=x_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{k}^{a_{k}}t^{b}$, where
$u_{1},u_{2},\dots,u_{b}$ are $b$, not necessarily distinct, generators of
$R_{G}$, and $a_{1},a_{2},\dots,a_{k}\geq 1$. Note that

$k\leq\sum_{i=1}^{k}\deg_{x_{i}}(u)=\sum_{i=1}^{k}\sum_{j=1}^{b}\deg_{x_{i}}(u_{j})=\sum_{j=1}^{b}\sum_{i=1}^{k}\deg_{x_{i}}(u_{j})\leq
2b.$ (6)

Thus $2b\geq k$. Hence $b\geq\ell+1$ and the initial degree of
$\bigcap_{i=1}^{k}Q_{i}$ is $\ell+1$.

We claim that the only monomials of degree $\ell+1$ belonging to
$\bigcap_{i=1}^{k}Q_{i}$ are

$w_{0}=(x_{1}x_{2}\cdots x_{k})t^{\ell+1},\ \ w_{i}=(x_{1}\cdots
x_{i-1}x_{i}^{2}x_{i+1}\cdots x_{k})t^{\ell+1},\ \ i=1,\dots,k.$ (7)

Indeed, for all $j=1,\dots,k$, we can write

$w_{0}=(x_{j}t)(x_{j+1}x_{j+2}t)\cdots(x_{j+k-2}x_{j+k-1}t)\in Q_{j},$ (8)

where $j+p$ is understood to be $q$, where $j+p\equiv q$ modulo $k$ and $1\leq
q\leq k$. Thus $w_{0}\in\bigcap_{i=1}^{k}Q_{i}$. Similarly, we can write

$w_{i}=(x_{i-1}x_{i}t)(x_{i}x_{i+1}t)(x_{i+2}x_{i+3}t)\cdots(x_{i+2(\ell-1)}x_{i+2(\ell-1)+1}t)$

with the same convention as before for the indices. Hence, we see that
$w_{i}\in Q_{j}$ for all $j$, because $j=i+p$, for some $-1\leq p\leq
2\ell-1$, and $x_{j-1}x_{j}t,x_{j}x_{j+1}t\in Q_{j}$.

Conversely, let $u=u_{1}u_{2}\cdots u_{\ell+1}\in\bigcap_{i=1}^{k}Q_{i}$ where
$u_{1},u_{2},\dots,u_{\ell+1}$ are $\ell+1$ generators of $R_{G}$. Note that
at most one of the $u_{i}$ can be of the form $x_{j}t$ and the remaining
monomials $u_{p}$ are of the form $x_{i}x_{j}t$, otherwise
$\sum_{i=1}^{k}\deg_{x_{i}}(u)<k$, contradicting (6). Therefore, we have
$\sum_{i=1}^{k}\deg_{x_{i}}(u)\in\\{2\ell+1,2\ell+2\\}=\\{k,k+1\\}$. Since we
must have $\deg_{x_{i}}(u)\geq 1$ for all $i=1,\dots,k$, we see that the only
monomials of degree $\ell+1$ belonging to $\bigcap_{i=1}^{k}Q_{i}$ are those
listed in (7).

Next, we show that $w_{0}\in P_{0}\cap(\bigcap_{C\in\mathcal{C}(G)}P_{C})$ and
$w_{i}\notin P_{0}$ for all $i=1,\dots,k$. Indeed, let $C\in\mathcal{C}(G)$,
then $x_{j}\in C$ for some $j$. Thus $x_{j}t\in P_{C}$ and by (8) it follows
that $w_{0}\in P_{C}$, as well. This same argument shows that $w_{0}\in
P_{0}$, and so $w_{0}\in P_{0}\cap(\bigcap_{C\in\mathcal{C}(G)}P_{C})$.

Now let $i\in\\{1,\dots,k\\}$. For any factorization $w_{i}=v_{1}v_{2}\cdots
v_{\ell+1}$ of $w_{i}$ into a product of generators $v_{p}\in R_{G}$, we have
$\sum_{j=1}^{k}\deg_{x_{j}}(v_{p})=2$ for all $p$. This shows that
$w_{i}\notin P_{0}$.

Therefore, the only monomial of degree $\ell+1$ belonging to $\omega_{R_{G}}$
is $w_{0}$. Since $\omega_{R_{G}}$ is a monomial ideal, its initial degree is
larger or equal to the initial degree of $\bigcap_{i=1}^{k}Q_{i}$. Hence,
$\min\\{i:(\omega_{R_{G}})_{i}\neq 0\\}=\ell+1$ and
$\dim_{K}(\omega_{R_{G}})_{\ell+1}=1$, that is, $R_{G}$ is pseudo-Gorenstein.

######  Example 4.8.

Let $G=C(1,1,1)$ be the whiskered triangle depicted below.

$x_{1}$$x_{2}$$x_{3}$$x_{1,1}$$x_{2,1}$$x_{3,1}$

Note that $G$ is unmixed, but it has an even number of vertices. Thus, by
Proposition 4.5 it follows that $R_{G}$ is not Gorenstein. Indeed, by using
Macaulay2 [5], we checked that the canonical module of $R_{G}$ is

$\omega_{R_{G}}=(x_{1}x_{2}x_{3}x_{1,1}x_{2,1}x_{3,1}t^{4},x_{1}^{2}x_{2}^{2}x_{3}^{2}x_{1,1}x_{2,1}x_{3,1}t^{5}).$

On the other hand, $R_{G}$ is pseudo-Gorenstein. In general however the
algebra $R_{G}$ of a whisker cycle $G$ need not to be pseudo-Gorenstein. The
algebra $R_{C(1,1,2)}$ gives such an example.

## References

  * [1] W. Bruns and J. Gubeladze, Polytopes, rings, and K-theory, Springer Monographs in Mathematics, Springer, Dordrecht, 2009.
  * [2] W. Bruns, J. Herzog, Cohen–Macaulay rings, Cambridge University Press, 1998.
  * [3] L.A. Dupont, C. Rentería, R. H. Villarreal, Systems with the integer rounding property in normal monomial subrings, An. Acad. Brasil. Ci$\hat{\text{e}}$nc. 82 (2010), no. 4, 801–811.
  * [4] V. Ene, J. Herzog, T. Hibi, S. Saeedi Madani. Pseudo-Gorenstein and level Hibi rings. J. Algebra, 431:138–161, 2015.
  * [5] D. R. Grayson, M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2.
  * [6] J. Herzog, T. Hibi. _Monomial ideals_ , Graduate texts in Mathematics 260, Springer–Verlag, 2011.
  * [7] J. Herzog, T. Hibi, S. Moradi, A. Asloob Qureshi, The toric face ring of a simplicial complex, 2023, preprint arXiv:2302.03653.
  * [8] J. Herzog, T. Hibi, S. Moradi, A. Asloob Qureshi, The toric face ring of a discrete polymatroid, 2023, preprint arXiv:2302.12475.
  * [9] J. Herzog, A. Simis, W.V. Vasconcelos, Arithmetic of normal Rees algebras, 1991, J. Algebra 143: 269–294.
  * [10] H. Ohsugi and T. Hibi, Normal polytopes arising from finite graphs, J. Algebra 207 (1998), 409-426.
  * [11] M. Vaz Pinto, R.H. Villarreal, Graph rings and ideals: Wolmer Vasconcelos contributions, 2023, preprint arXiv:2305.06270
  * [12] R. H. Villarreal, _Monomial Algebras_ , Second Edition, Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2015.


# On the Independent Set and Common Subgraph Problems in Random Graphs

Yinglei Song
School of Computer Science and Engineering, Jiangsu University of Science and
Technology
Zhenjiang, Jiangsu 212003, China
<EMAIL_ADDRESS>

###### Abstract

In this paper, we develop efficient exact and approximate algorithms for
computing a maximum independent set in random graphs. In a random graph $G$,
each pair of vertices are joined by an edge with a probability $p$, where $p$
is a constant between $0$ and $1$. We show that, a maximum independent set in
a random graph that contains $n$ vertices can be computed in expected
computation time $2^{O(\log_{2}^{2}{n})}$. Using techniques based on
enumeration, we develop an algorithm that can find a largest common subgraph
in two random graphs in $n$ and $m$ vertices ($m\leq n$) in expected
computation time $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$. In
addition, we show that, with high probability, the parameterized independent
set problem is fixed parameter tractable in random graphs and the maximum
independent set in a random graph in $n$ vertices can be approximated within a
ratio of $\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in expected polynomial time.

##  1 Introduction

In computer science, many optimization problems can be reduced to the
optimization of objectives that are formulated and described in a graph. The
development of efficient exact or approximate algorithms for graph
optimization problems thus constitute an important part of the research in
combinatorial optimization. However, a large number of graph optimization
problems have been shown to be NP-hard [18], which suggests that it is
unlikely to develop algorithms that can solve these problems in polynomial
time. A well known example is the Maximum Independent Set problem. Given a
graph $G=(V,E)$, a vertex set $I\subseteq V$ is an independent set if there is
no edge between any pair of two vertices in $I$. The goal of the Maximum
Independent Set problem is to find an independent set of the largest size in a
given graph $G$. The problem can be trivially solved in time $2^{O(n)}$ by
enumerating and checking all possible vertex subsets in the graph. Although
intensive research has been performed to improve the computation time needed
to find an optimal solution [2, 6, 14, 17, 36, 23, 27, 30, 31, 32, 33, 34, 37,
38], an algorithm that needs subexponential time is not yet available for this
problem. Recently, it is proposed that this problem is unlikely to be solved
in subexponential time [7, 8].

Due to the difficulty of developing efficient algorithms that can find optimal
solutions for these problems, a large number of algorithms have been developed
to generate approximate solutions that are close to optimal ones in polynomial
time [24]. Solutions provided by these algorithms are often guaranteed to be
within a ratio of the optimal solution and thus can be useful in practice. For
example, the Minimum Vertex Cover problem can be approximated by a simple
polynomial time algorithm within a ratio of $2.0$. However, it has been shown
that it is NP-hard to approximate this problem within a ratio of $1.362$ [9].
A well known inapproximability result regarding the Maximum Independent Set
problem is that it is NP-hard to approximate the maximum independent set in a
graph within a ratio of $n^{1-\epsilon}$, where $0<\epsilon<1$ is a constant
and $n$ is the number of vertices in the graph [21]. This result suggests that
an approximate solution with a guaranteed constant approximate ratio cannot be
obtained in polynomial time for the Maximum Independent Set problem unless
NP=P. So far, the best known approximation ratio that has been achieved for
this problem in general graphs is
$O(\frac{n\log_{2}^{2}{\log_{2}{n}}}{\log_{2}^{3}{n}})$ [15].

For those problems that cannot be even approximated within a good
approximation ratio in polynomial time, such as the Maximum Independent Set
problem, heuristics that can efficiently generate approximate solutions are
often employed in practice to solve them [3, 26, 20]. However, solutions
generated by heuristics are not guaranteed to be close to the optimal ones and
their applications are thus restricted to scenarios where the accuracy of
solutions is not a crucial issue.

Parameterized computation provides another potentially practical solution for
some problems that are computationally intractable. In particular, one or a
few parameters in some intractable problems can be identified and
parameterized computation studies whether efficient algorithms exist for these
problems while all parameters are small. A parameterized problem may contain a
few parameters $k_{1},k_{2},\cdots,k_{l}$ and the problem is fixed parameter
tractable if it can be solved in time $O(f(k_{1},k_{2},\cdots,k_{l})n^{c})$,
where $f$ is a function of $k_{1},k_{2},\cdots,k_{l}$, $n$ is the size of the
problem and $c$ is a constant independent of all parameters. For example, the
Vertex Cover problem is to determine whether a graph $G=(V,E)$ contains a
vertex cover of size at most $k$ or not. The problem is NP-complete. However,
a simple parameterized algorithm can solve the problem in time $O(2^{k}|V|)$
[11]. In practice, this algorithm can be used to efficiently solve the Vertex
Cover problem when the parameter $k$ is fixed and small. On the other hand,
some problems do not have known efficient parameterized solutions and are
therefore parameterized intractable. Similar to the conventional complexity
theory, a hierarchy of complexity classes has been constructed to describe the
parameterized complexity of these problems [11]. For example, the Independent
Set problem is to decide whether a graph contains an independent set of size
$k$ or not and has been shown to be W[1]-complete [12]. It cannot be solved
with an efficient parameterized algorithm unless all problems in W[1] are
fixed parameter tractable. A thorough investigation on these parameterized
complexity classes are provided in [10].

In this paper, we develop exact and approximate algorithms for the Maximum
Independent Set problem where the underlying graph is a random graph generated
based on the Erdős Rényi model [13]. Such a random graph is generated by
treating each pair of vertices independently and adding an edge to join them
with a probability of $p$ ($0<p<1$), where $p$ is a constant. Recent research
in molecular biology has shown that the protein side chain interaction network
conforms remarkably well to random graphs generated by the Erdős Rényi model
[5]. Therefore, efficient algorithms for some NP-hard problems in random
graphs, if exist, may significantly improve the computational efficiency for
some important optimization problems related to protein structure prediction.

In [19, 25], it has been shown that with high probability, the maximum
independent set in a random graph is of size $O(\log_{2}{n})$. However, this
result does not directly lead to an algorithm that can compute the maximum
independent set in a random graph in expected subexponential time. In [16], a
polynomial time algorithm that can compute a maximum independent set in a
sparse random graph with high probability is developed. However, the algorithm
is based on a large independent set that is embedded in the graph and thus
cannot be used for all graphs. We show that the maximum independent set in a
random graph can be computed in expected computation time
$2^{O(\log_{2}^{2}{n})}$, where $n$ is the number of vertices in the graph.
This result significantly improves the best known time complexity
$O(2^{\frac{n}{4}})$ for finding a maximum independent set in general graphs
[34].

Using techniques based on enumeration, we develop an algorithm that can
compute a largest common subgraph of two random graphs of $n$ and $m$ vertices
($n\geq m$) in expected computation time
$2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$. This result significantly
improves on the best known time complexity $2^{O(m\log_{2}{n})}$ for this
problem when $m=O(n)$. In addition, we show that, with high probability, the
parameterized independent set problem is fixed parameter tractable in random
graphs. For approximate algorithms, we develop an algorithm that can achieve
an approximation ratio of $\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in expected
polynomial time, which is a significant improvement compared with the best
known approximate ratio that can be achieved in general graphs [1, 35].

##  2 Maximum Independent Set in Random Graphs

A random graph $G(V,p)$, where $0<p<1$, is a graph obtained by independently
adding edges between each pair of vertices in $V$ with a probability $p$.
Given a vertex $v\in V$, the degree of $v$ in $G$ is the number of vertices
that are connected to $v$ by an edge in G. We use $deg_{G}(v)$ to denote the
degree of vertex $v$ in graph $G$ and $N_{G}(v)$ to denote the set of vertices
that are connected to $v$ by an edge in $G$. A vertex subset $I\subseteq V$ is
an independent set in $G$ if there is no edge between any pair of vertices in
$I$. The goal of the Maximum Independent Set problem is to find an independent
set of the largest size in a given graph.

In [19, 25], it is shown that, with high probability, the size of a maximum
independent set in a random graph $G(V,p)$ is
$\frac{2\log_{2}{n}}{\log_{2}{\frac{1}{1-p}}}$, where $n$ is the number of
vertices in $G$. A straightforward algorithm by exhaustively enumerating all
vertex subsets of size $\frac{2\log_{2}{n}}{\log_{2}{\frac{1}{1-p}}}$ can thus
compute a maximum independent set in most random graphs in time
$n^{O(\log_{2}{n})}$. However, to compute a maximum independent set in all
random graphs, the algorithm must be able to cope with the cases where the
graph contains an independent set of size larger than $O(\log_{2}{n})$. The
algorithm needs time $2^{O(n)}$ to compute a maximum independent set in these
cases. The best known upper bound of the probability for a random graph to
have a maximum independent set larger than $O(\log_{2}{n})$ is
$\frac{1}{n^{O(1)}}$ [19, 25], the expected time complexity of this
enumeration based algorithm is thus $2^{O(n)}$.

We show that the maximum independent set in a random graph $G=(V,p)$ can be
computed in expected subexponential time.

###### Lemma 2.1

Given a random graph $G=(V,p)$ where $n=|V|$ and a sufficiently small constant
$\epsilon$ such that $\epsilon<p$, there exists a vertex $v\in V$ such that
$deg_{G}(v)\geq(p-\epsilon)n$ with probability at least $1-2^{-\mu n^{2}}$,
where $\mu$ is a positive constant that only depends on $\epsilon$ and $p$.

Proof.  If such a vertex does not exist, the number of edges $n(E)$ in $G$ is
at most $\frac{(p-\epsilon)n^{2}}{2}$ since the degree of each vertex is at
most $(p-\epsilon)n$. However, from the construction of graph $G$, the
expected number of edges in $G$ can be obtained as follows

$E(n(E))=\frac{pn(n-1)}{2}$ (1)

From Chernoff bound, we can bound the probability for
$n(E)<\frac{(p-\epsilon)n^{2}}{2}$ by

$Pr(n(E)<\frac{(p-\epsilon)n^{2}}{2})<\exp{(-\frac{pn(n-1)\delta^{2}}{4})}$
(2)

where $\delta=\frac{n\epsilon-p}{p(n-1)}$. For sufficiently large $n$, we have

$\displaystyle\delta$ $\displaystyle>$ $\displaystyle\frac{\epsilon}{2p}$ (3)
$\displaystyle n-1$ $\displaystyle>$ $\displaystyle\frac{n}{2}.$ (4)

We can thus immediately obtain

$\displaystyle Pr(n(E)$ $\displaystyle<$
$\displaystyle\frac{(p-\epsilon)n^{2}}{2})$ (5) $\displaystyle<$
$\displaystyle\exp{(-\frac{\epsilon^{2}n^{2}}{32p})}$ (6) $\displaystyle=$
$\displaystyle 2^{-\frac{\epsilon^{2}n^{2}}{32p\ln{2}}}.$ (7)

We then let $\mu=\frac{\epsilon^{2}}{32p\ln{2}}$ and we conclude that with
probability at least $1-2^{-\mu n^{2}}$, there exists vertex $v\in V$ such
that $deg_{G}(v)\geq(p-\epsilon)n$.

The proof of Lemma 2.1 relies on the fact that $p$ is a constant independent
of $n$, the Lemma does not hold if the value of $p$ depends on $n$. A random
graph $G=(V,p)$ in $n$ vertices is good if it contains at least one vertex
whose degree is at least $(p-\epsilon)n$. Given a random graph, the algorithm
starts by finding a vertex $v$ such that $deg_{G}(v)$ is at least
$(p-\epsilon)n$. If such a vertex does not exist, the algorithm enumerates all
subsets of $V$ and returns an independent set of the largest size. If $v$
exists, the algorithm branches on two possible cases on whether $v$ is
contained in $I$ or not. In particular, if $v\in I$, $v$ and vertices in
$N(v)$ are deleted from $G$ and the resulting graph is $G_{1}$; if $v\notin
I$, $v$ is deleted from $G$ and the resulting graph is $G_{2}$. The algorithm
is then recursively applied on both $G_{1}$ and $G_{2}$ to compute a maximum
independent set in each of them. We use $I_{1}$ and $I_{2}$ to denote the
maximum independent sets in $G_{1}$ and $G_{2}$ found by the algorithm
respectively. $I_{2}$ is returned as a maximum independent set in $G$ if
$|I_{2}|\geq|I_{1}|+1$ and $I_{1}\cup\\{v\\}$ is returned otherwise. We show
that this algorithm terminates in expected time $2^{O(\log_{2}^{2}{n})}$.

###### Theorem 2.1

A maximum independent set in a random graph $G=(V,p)$ with $n$ vertices can be
computed in expected computation time $2^{O(\log_{2}^{2}{n})}$.

Proof.  We show that the algorithm described above terminates in expected time
$2^{O(\log_{2}^{2}{n})}$. In particular, the algorithm is recursive and for
each step of recursion, we have the following recursion relation for the
computation time if the underlying graph is good and contains $m$ vertices

$T(m)\leq T((1-p+\epsilon)m)+T(m-1)+O(m^{2})$ (8)

where $T(m)$ is the computation time needed by the algorithm in a graph on $m$
vertices. The term $O(m^{2})$ is the computation time needed to find a vertex
whose degree is at least $(p-\epsilon)m$, since the time needed to compute the
degree of a vertex is $O(m)$ and the algorithm may need to check $m$ vertices
to find such a vertex. If the underlying graph is not good, the algorithm
exhaustively enumerates all subsets in the graph and finds an independent set
of the largest size. The computation time is $2^{O(m)}$.

We are now ready to establish the expected computation time for the algorithm.
In particular, we use $ET(m)$ to denote the expected computation time of the
algorithm on a graph that contains $m$ vertices. From Lemma 2.1, an underlying
graph $G^{\prime}$ in $m$ vertices is good with a probability of at least
$1-2^{-\mu m^{2}}$. We thus can immediately obtain the following recursion for
$ET(m)$.

$\displaystyle ET(m)$ $\displaystyle\leq$ $\displaystyle
ET((1-p+\epsilon)m)+ET(m-1)+O(m^{2})+2^{O(m)-\mu m^{2}}$ (9)
$\displaystyle\leq$ $\displaystyle ET((1-p+\epsilon)m)+ET(m-1)+O(m^{2})$ (10)

where the second inequality is due to the fact that $2^{O(m)-\mu m^{2}}$ is
bounded by a constant for all positive integers $m$.

We then show that $ET(m)\leq 2^{c\log_{2}^{2}{m}}$, where $c$ is a positive
constant. We show this by induction. First, for a sufficiently large positive
integer $m_{0}$ whose value will be specified later, we let $c_{0}=\max_{1\leq
t\leq m_{0}}{\\{\frac{\log_{2}{ET(t)}}{\log_{2}^{2}{t}}\\}}$ and choose
$c=\max{\\{c_{0},\frac{2}{\log_{2}{\frac{1}{1-p+\epsilon}}},1\\}}$. It is not
difficult to see that $ET(l)\leq 2^{c\log_{2}^{2}{l}}$ if $1\leq l\leq m_{0}$.
We then assume this holds for all positive integers less than $m$. From the
above recursion relation on $ET(m)$, we can obtain

$\displaystyle ET(m)$ $\displaystyle\leq$ $\displaystyle
2^{c\log_{2}^{2}{((1-p+\epsilon)m)}}+2^{c\log_{2}^{2}{(m-1)}}+Bm^{2}$ (11)
$\displaystyle\leq$ $\displaystyle
sm^{-l}2^{c\log_{2}^{2}{m}}+2^{c\log_{2}^{2}{m}}+(2^{c\log_{2}^{2}{(m-1)}}-2^{c\log_{2}^{2}{m}})+Bm^{2}$
(12) $\displaystyle\leq$ $\displaystyle
sm^{-l}2^{c\log_{2}^{2}{m}}+2^{c\log_{2}^{2}{m}}-\frac{\log_{2}{m}}{24m}2^{c\log_{2}^{2}{m}}+Bm^{2}$
(13) $\displaystyle\leq$ $\displaystyle 2^{c\log_{2}^{2}{m}}$ (14)

where $B$ is a positive constant independent of $c,p,\epsilon$ and $s$, $q$,
$l$ are some positive constants that depend on $c,p,\epsilon$ only. The first
inequality is obtained from the assumption for induction. The second one is
due to the fact that
$\log_{2}^{2}{((1-p+\epsilon)m)}=\log_{2}^{2}{(1-p+\epsilon)}+2\log_{2}{(1-p+\epsilon)}\log_{2}{m}+\log_{2}^{2}{m}$
and we can let $l=2c\log_{2}{\frac{1}{1-p+\epsilon}}$ ,
$s=2^{c\log_{2}^{2}{(1-p+\epsilon)}}$.

To establish the third inequality, we have

$\displaystyle\log_{2}^{2}{(m-1)}-\log_{2}^{2}{m}$ $\displaystyle=$
$\displaystyle(\log_{2}{m}+\log_{2}{(1-\frac{1}{m})})^{2}-\log_{2}^{2}{m}$
(15) $\displaystyle\leq$
$\displaystyle(\log_{2}{m}-\frac{1}{6m})^{2}-\log_{2}^{2}{m}$ (16)
$\displaystyle\leq$ $\displaystyle-\frac{\log_{2}{m}}{6m}$ (17)
$\displaystyle\leq$ $\displaystyle-\frac{\log_{2}{m}}{6cm}$ (18)

when $m\geq 16$, we can obtain

$\displaystyle 2^{c\log_{2}^{2}{(m-1)}}-2^{c\log_{2}^{2}{m}}$ $\displaystyle=$
$\displaystyle
2^{c\log_{2}^{2}{m}}(2^{c(\log_{2}^{2}{(m-1)}-\log_{2}^{2}{m})}-1)$ (19)
$\displaystyle\leq$ $\displaystyle
2^{c\log_{2}^{2}{m}}(2^{-\frac{\log_{2}{m}}{6m}}-1)$ (20) $\displaystyle\leq$
$\displaystyle-\frac{\log_{2}{m}}{24m}2^{c\log_{2}^{2}{m}}$ (21)

the third inequality thus follows.

From the fact that $c\geq\frac{2}{\log_{2}{\frac{1}{1-p+\epsilon}}}$, we have
$l\geq 4$. We let

$\displaystyle c^{\prime}$ $\displaystyle=$
$\displaystyle\frac{2}{\log_{2}{\frac{1}{1-p+\epsilon}}}$ (22) $\displaystyle
s^{\prime}$ $\displaystyle=$ $\displaystyle
2^{c^{\prime}\log_{2}^{2}{((1-p+\epsilon)m)}}$ (23) $\displaystyle l^{\prime}$
$\displaystyle=$ $\displaystyle 2c^{\prime}\log_{2}{\frac{1}{1-p+\epsilon}}$
(24)

we now consider the function
$F(m)=(s^{\prime}{m}^{-l^{\prime}}-\frac{\log_{2}{m}}{24m})2^{c^{\prime}\log_{2}^{2}{m}}+B{m}^{2}$.
Since $s^{\prime}$, $l^{\prime}$, $c^{\prime}$, and $B$ are independent of $m$
and $l^{\prime}\geq 4$, there exists a positive integer $m_{1}(p,\epsilon)$
such that $F(m)\leq 0$ when $m\geq m_{1}(p,\epsilon)$. $m_{0}$ can be
determined as follows

$m_{0}=\max\\{m_{1}(p,\epsilon),\frac{1}{\sqrt{1-p+\epsilon}},16\\}$ (25)

It is not difficult to see that when $c\geq c^{\prime}$ and $m\geq m_{0}$, we
have $s^{\prime}m^{-l^{\prime}}-\frac{\log_{2}{m}}{24m}\leq 0$. In addition,
we can further verify that

$sm^{-l}=2^{c\log_{2}{(1-p+\epsilon)}\log_{2}{(m^{2}(1-p+\epsilon))}}$ (26)

since $c\geq c^{\prime}$, $m\geq\frac{1}{\sqrt{1-p+\epsilon}}$, and
$\log_{2}{(1-p+\epsilon)}\leq 0$, we can immediately obtain

$\displaystyle sm^{-l}$ $\displaystyle=$ $\displaystyle
2^{c\log_{2}{(1-p+\epsilon)}\log_{2}{(m^{2}(1-p+\epsilon))}}$ (27)
$\displaystyle\leq$ $\displaystyle
2^{c^{\prime}\log_{2}{(1-p+\epsilon)}\log_{2}{(m^{2}(1-p+\epsilon))}}$ (28)
$\displaystyle=$ $\displaystyle s^{\prime}m^{-l^{\prime}}$ (29)

the following thus holds

$\displaystyle(sm^{-l}-\frac{\log_{2}{m}}{24m})2^{c\log_{2}^{2}{m}}+B{m}^{2}$
$\displaystyle\leq$
$\displaystyle(s^{\prime}m^{-l^{\prime}}-\frac{\log_{2}{m}}{24m})2^{c\log_{2}^{2}{m}}+B{m}^{2}$
(30) $\displaystyle\leq$
$\displaystyle(s^{\prime}m^{-l^{\prime}}-\frac{\log_{2}{m}}{24m})2^{c^{\prime}\log_{2}^{2}{m}}+Bm^{2}$
(31) $\displaystyle=$ $\displaystyle F(m)$ (32) $\displaystyle\leq$
$\displaystyle 0$ (33)

the fourth inequality thus follows. From the principle of induction, the
theorem has been proved.

##  3 Parameterized Algorithm for Independent Set Problem

The parameterized independent set problem is to decide whether a given graph
$G=(V,E)$ contains an independent set of size $k$ or not. The problem is known
to be W[1]-hard [10, 11, 12] and cannot be solved in time $n^{o(k)}$ in
general graphs unless W[2]=FPT [7, 8]. We show that if the underlying graph
$G$ is a random graph, the problem can be solved in expected time
$2^{O(k^{2})}+O(n^{3})$, where $n$ is the number of vertices in the graph. We
need the following lemma to analyze the time complexity of the algorithm.

###### Lemma 3.1

Given a random graph $G=(V,p)$ where $n=|V|$ and a sufficiently small constant
$\epsilon$ such that $p+\epsilon<1$, there exists vertex $u\in V$ such that
$deg_{G}(u)\leq(p+\epsilon)n$ with a probability of at least $1-2^{-\mu
n^{2}}$, where $\mu$ is a positive constant that only depends on $\epsilon$
and $p$,

Proof.  The proof is similar to the proof of Lemma 2.1. If such a vertex does
not exist, the degree of every vertex in $G$ is at least $(p+\epsilon)n$. The
graph thus contains at least $\frac{(p+\epsilon)n^{2}}{2}$ edges. The expected
number of edges in $G$ is $\frac{pn(n-1)}{2}$. We use $n(E)$ to denote the
number of the edges in $G$. From Chernoff bound, we can bound the probability
for $G$ to contain at least $\frac{(p+\epsilon)n^{2}}{2}$ edges.

$\displaystyle Pr(n(E)$ $\displaystyle\geq$
$\displaystyle\frac{(p+\epsilon)n^{2}}{2})$ (35) $\displaystyle<$
$\displaystyle\exp{(-\frac{\epsilon^{2}n^{2}}{64p})}$ (36) $\displaystyle=$
$\displaystyle 2^{-\frac{\epsilon^{2}n^{2}}{64p\ln{2}}}$ (37)

the lemma immediately follows by letting $\mu=\frac{\epsilon^{2}}{64p\ln{2}}$.

The proof of Lemma 3.1 relies on the fact that $p$ is a constant independent
of $n$, the Lemma does not hold if the value of $p$ depends on $n$.

###### Theorem 3.1

Given a random graph $G=(V,p)$, there exists an algorithm that can decide
whether $G$ contains an independent set of size $k$ in expected time
$2^{O(k^{2})}+O(n^{3})$.

Proof.  We start the proof by comparing the values of $k$ and
$L(n)=\frac{1}{3}\log_{\frac{1}{1-p-\epsilon}}{n}$, if $k>L(n)$, we can
enumerate all possible vertex subsets of size $k$ in $G$ and check whether one
of them is an independent set of size $k$ or not. The enumeration and checking
needs at most $O(k^{2}n^{k})$ time. However, since $k>L(n)$, we can obtain
$n<(\frac{1}{1-p-\epsilon})^{3k}$, the computation time needed to determine
whether $G$ contains an independent set of size $k$ or not is thus at most
$O(k^{2}(\frac{1}{1-p-\epsilon})^{3k^{2}})=2^{O(k^{2})}$ in this case.

We then consider the case where $k\leq L(n)$. We use the following procedure
to generate an independent set $I$. We start with the vertex $u$ with the
minimum degree in $G$, we include $u$ in $I$ and remove $u$ and all its
neighbors in $G$ from $G$. We denote the resulting graph by $G_{1}$. The
procedure can be repeatedly executed until there are at most $n^{\frac{2}{3}}$
vertices left in the graph. We use $G_{0}=G,G_{1},G_{2},G_{3},\cdots,G_{l}$ to
denote the intermediate graphs generated during this iterative procedure. It
is not difficult to see that vertices in $I$ form an independent set in $G$.

We show that the above procedure can generate an independent set $I$ of size
at least $L(n)$ with high probability. We use $G_{1},G_{2},G_{3},\cdots,G_{l}$
to denote the resulting graph in each iterative step and $n(G_{i})$ to denote
the number of vertices in graph $G_{i}$. From Lemma 3.1, the following holds
with a probability of at least 1-$2^{-\mu n^{2}(G_{i})}$ for each $i$ between
$0$ and $l$.

$n(G_{i+1})\geq(1-p-\epsilon)n(G_{i})$ (38)

Since $n(G_{i})>n^{\frac{2}{3}}$, the probability for this inequality to hold
for all $i$’s between $0$ and $l$ is at least $1-n2^{-\mu n^{\frac{4}{3}}}$.
If this inequality holds for all $i$’s between $0$ and $l$. We can immediately
obtain

$\displaystyle l$ $\displaystyle\geq$
$\displaystyle\log_{\frac{1}{1-p-\epsilon}}{(\frac{n}{n^{\frac{2}{3}}})}$ (39)
$\displaystyle=$ $\displaystyle\frac{1}{3}\log_{\frac{1}{1-p-\epsilon}}{n}$
(40) $\displaystyle=$ $\displaystyle L(n)$ (41)

$I$ thus contains at least $L(n)$ vertices. With a probability of at least
$1-n2^{-\mu n^{\frac{4}{3}}}$, the above iterative procedure generates an
independent set of size $L(n)$. Since $k<L(n)$, the algorithm returns “yes” if
$I$ indeed contains $L(n)$ independent vertices, otherwise, the algorithm
simply enumerates all vertex subsets in $G$ and checks whether one of them is
an independent set of size at least $k$. Since the procedure for generating
$I$ needs $O(n^{3})$ time, the expected computation time needed for this is at
most

$O(n^{3})(1-n2^{-\mu n^{\frac{4}{3}}})+2^{O(n)}n2^{-\mu
n^{\frac{4}{3}}}=O(n^{3})$ (42)

where the equality is due to the fact that the second term is bounded by a
constant when $n$ is sufficiently large. The algorithm thus needs an expected
time $2^{O(k^{2})}+O(n^{3})$, the theorem has been proved.

##  4 The Largest Common Subgraph Problem

Given two graphs $G$, $H$, a common subgraph of $G$ and $H$ is a third graph
$K$ such that both $G$ and $H$ contain an induced subgraph that is isomorphic
to $K$. The largest common subgraph problem is to compute a common subgraph
that contains the largest number of vertices. The problem has important
applications in computational biology. For example, it is often desirable to
identify common subgraphs in the protein interaction networks of two
homologous organisms since proteins in these common subgraphs often together
play important roles for certain biological functions [28].

Unfortunately, the problem is NP hard when both of the underlying graphs are
general graphs [18]. The asymptotically best known algorithm for this problem
needs time $O^{*}((m+1)^{n})$ [1, 35] and little progress has been made to
improve the asymptotical time complexity of this problem. We show that, given
two random graphs $G$ and $H$ in $n$ and $m$ vertices, where $n\geq m$, the
largest common subgraph problem in $G$ and $H$ can be computed in expected
time $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$.

###### Lemma 4.1

The largest common subgraph problem can be solved in computation time
$O(m^{2}2^{m}n^{m})\leq 2^{hm\log_{2}{n}}$, where $h$ is some positive
constant that does not depend on $n$ or $m$.

Proof.  We can solve the largest common subgraph problem with the following
simple algorithm. For each positive integer $l$ not greater than $m$, we
enumerate all vertex subsets that contain $l$ vertices in $G$. For each such
vertex subset $S_{1}$, we enumerate all vertex subsets of size $l$ in graph
$H$ and for each such vertex subset $S_{2}$, we enumerate all possible one to
one mappings between vertices in $S_{1}$ and those in $S_{2}$. We then check
whether there exists a one to one mapping that can establish the isomorphism
between the subgraph induced by $S_{1}$ in $G$ and the subgraph induced by
$S_{2}$ in $H$. The algorithm can find all common subgraphs and return one
that is of the largest size.

The number of vertex subsets of size $l$ in $G$ is ${n\choose l}$ and the
number of vertex subsets of size $l$ in $H$ is ${m\choose l}$. The number of
one to one mappings between $S_{1}$ and $S_{2}$ is $l!$ and the computation
time needed to check whether the two subgraphs induced by $S_{1}$ and $S_{2}$
are isomorphic under a particular mapping is at most $O(l^{2})$. The total
computation time needed to find and return the largest common subgraph is thus
at most

$\displaystyle\sum_{l=1}^{m}{C{n\choose l}{m\choose l}l!l^{2}}$
$\displaystyle\leq$ $\displaystyle\sum_{l=1}^{m}{Cn^{m}{m\choose l}m^{2}}$
(43) $\displaystyle\leq$ $\displaystyle C2^{m}n^{m}m^{2}$ (44)
$\displaystyle\leq$ $\displaystyle 2^{hm\log_{2}{n}}$ (45)

where $C$ and $h$ are some positive constants independent of $n$ and $m$. The
first inequality is due to the fact that ${n\choose l}l!\leq n^{l}$ and $l\leq
m$; the second inequality is due to the fact that $\sum_{l=1}^{m}{m\choose
l}=2^{m}-1$. The lemma thus has been proved.

###### Lemma 4.2

Given two random graphs $G=(V,p)$ and $H=(U,q)$, where $p$ and $q$ are
positive constants between 0 and 1, $G$ contains $n$ vertices and $H$ contains
$m$ vertices ($n\geq m$), the probability that $G$ and $H$ contain a common
subgraph of size $n^{\frac{1}{2}}\log_{2}^{\frac{2}{3}}{n}$ is at most
$2^{-\mu n\log_{2}^{\frac{4}{3}}{n}}$, where $\mu$ is a positive constant that
only depends on $p$ and $q$.

Proof.  We let $k=n^{\frac{1}{2}}\log_{2}^{\frac{2}{3}}{n}$ and consider two
given subsets of size $k$ in graph $G$ and $H$ respectively. We use
$S_{1}=\\{g_{1},g_{2},\cdots,g_{k}\\}$ and
$S_{2}=\\{h_{1},h_{2},\cdots,h_{k}\\}$ to denote them and $G_{1}$, $H_{1}$ to
denote the subgraphs induced by them in $G$ and $H$ respectively. We assume
that $G_{1}$ is isomorphic to $H_{1}$ under a given one to one mapping $M$,
where vertex $g_{i}$ in $S_{1}$ is mapped to $h_{i}$ in $S_{2}$ for $1\leq
i\leq k$.

We then estimate the probability for $M$ to be such a mapping. If $G_{1}$ is
isomorphic to $H_{1}$ under $M$, for any integer pair $(i,j)$, where $1\leq
i<j\leq k$, either both $(g_{i},g_{j})$ and $(h_{i},h_{j})$ are edges or
neither of them are edges. The probability for the former case is $pq$ and the
probability for the latter case is $(1-p)(1-q)$. Since there are in total
$\frac{k(k-1)}{2}$ such pairs, the probability for $G_{1}$ and $H_{1}$ to be
isomorphic under $M$ is thus $(pq+(1-p)(1-q))^{\frac{k(k-1)}{2}}$.

We use $P(k)$ to denote the probability for $G$ and $H$ to contain a common
subgraph of size $k$. Since the number of vertex subsets of size $k$ in $G$ is
${n\choose k}$ and the number of vertex subsets of size $k$ in $H$ is
${m\choose k}$, we can obtain an upper bound for $P(k)$ using the union bound.

$\displaystyle P(k)$ $\displaystyle\leq$ $\displaystyle{n\choose k}{m\choose
k}\sum_{M}{s^{\frac{k(k-1)}{2}}}$ (46) $\displaystyle\leq$
$\displaystyle{n\choose k}{m\choose k}k!s^{\frac{k(k-1)}{2}}$ (47)
$\displaystyle\leq$ $\displaystyle n^{k}m^{k}s^{\frac{k(k-1)}{2}}$ (48)
$\displaystyle\leq$ $\displaystyle n^{2k}s^{\frac{k(k-1)}{2}}$ (49)
$\displaystyle\leq$ $\displaystyle
2^{2n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n}}s^{\frac{k^{2}}{4}}$ (50)
$\displaystyle=$ $\displaystyle
2^{2n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n}-\frac{n\log_{2}^{\frac{4}{3}}{n}\log_{2}{\frac{1}{s}}}{4}}$
(51) $\displaystyle\leq$ $\displaystyle 2^{-\mu n\log_{2}^{\frac{4}{3}}{n}}$
(52)

where $s=pq+(1-p)(1-q)$ and $\mu$ is some positive constant that depends on
$p$ and $q$ only. The first inequality is due to the union bound. The second
inequality follows from the fact that there are in total $k!$ one to one
mappings between vertices in $S_{1}$ and $S_{2}$. The third inequality is due
to the fact that ${n\choose k}\leq n^{k}$ and ${m\choose k}k!\leq m^{k}$. The
fifth inequality follows from the fact that
$k=n^{\frac{1}{2}}\log_{2}^{\frac{2}{3}}{n}$ and
$\frac{k(k-1)}{2}>\frac{k^{2}}{4}$ when $n$ is sufficiently large. The last
inequality is due to the fact that $s<1$ and
$2n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n}\leq\frac{n\log_{2}^{\frac{4}{3}}{n}\log_{2}{\frac{1}{s}}}{8}$
for sufficiently large $n$.

The proof of the Lemma 4.2 relies on the fact that $p$ and $q$ are both
constants independent of $n$ and $m$, the Lemma does not hold if the values of
$p$ and $q$ depend on $n$ or $m$.

###### Theorem 4.1

Given two random graphs $G=(V,p)$ and $H=(U,q)$, where $p$ and $q$ are
positive numbers between 0 and 1, $G$ contains $n$ vertices and $H$ contains
$m$ vertices ($m\leq n$), a largest common graph of $G$ and $H$ can be
computed in expected time $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$.

Proof.  We only need to show that such an algorithm exists when
$m>n^{\frac{1}{2}}\log_{2}^{\frac{2}{3}}{n}$. Since if $m\leq
n^{\frac{1}{2}}\log_{2}^{\frac{2}{3}}{n}$, the algorithm in the proof of Lemma
4.1 can be directly used to find a largest common subgraph of $G$ and $H$ in
time $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$.

Let $k=n^{\frac{1}{2}}\log_{2}^{\frac{2}{3}}{n}$, since $m>k$, we can use the
following algorithm to compute a largest common subgraph in $G$ and $H$.

  1. 1.

Enumerate all vertex subsets of size $k$ in $G$. For each such vertex subset
$S_{1}$, enumerate all vertex subsets of size $k$ in $H$;

  2. 2.

for each such subset $S_{2}$ in $H$, we enumerate all possible one to one
mappings between $S_{1}$ and $S_{2}$;

  3. 3.

for each such mapping $M$, determine whether the subgraph induced by $S_{1}$
in $G$ is isomorphic to the subgraph induced by $S_{2}$ in $H$ under $M$ or
not;

  4. 4.

if there exists a mapping that can make the subgraph induced by $S_{1}$ in $G$
isomorphic to the subgraph induced by $S_{2}$ in $H$, call the algorithm in
Lemma 4.1 to compute a largest common subgraph of $G$ and $H$ and return it;

  5. 5.

otherwise, for each integer $i$ between $1$ and $k$, use the same approach as
described in steps 1, 2, 3 to determine whether $G$ and $H$ contains a common
subgraph of size $i$ or not;

  6. 6.

Based on the result of the exhaustive search performed in step $5$, return a
common subgraph of the largest size.

We then show that the algorithm can compute the largest common subgraph of $G$
and $H$ in expected $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$ time. In
particular, the computation time needed by the exhaustive search performed in
steps 1, 2, and 3 is at most

$\displaystyle C{n\choose k}{m\choose k}k!k^{2}$ $\displaystyle\leq$
$\displaystyle Cn^{k}m^{k}$ (53) $\displaystyle\leq$ $\displaystyle Cn^{2k}$
(54) $\displaystyle\leq$ $\displaystyle C2^{2k\log_{2}{n}}$ (55)
$\displaystyle=$ $\displaystyle
2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$ (56)

where $C$ is some positive constant. The first inequality is due to the fact
that ${m\choose k}k!\leq m^{k}$ and ${n\choose k}k^{2}\leq n^{k}$ for
sufficiently large $n$. From Lemma 4.1, step 4 of the algorithm, if executed,
needs $2^{hm\log_{2}{n}}$ computation time, where $h$ is some positive
constant independent of $n$ and $m$. The computation time needed by step 5 is
at most

$\displaystyle D\sum_{i=1}^{k-1}{{n\choose i}{m\choose i}i!i^{2}}$
$\displaystyle\leq$ $\displaystyle D\sum_{i=1}^{k-1}{n^{i}m^{i}i^{2}}$ (57)
$\displaystyle\leq$ $\displaystyle Dkn^{2k}k^{2}$ (58) $\displaystyle=$
$\displaystyle D2^{3\log_{2}{k}+2k\log_{2}{n}}$ (59) $\displaystyle=$
$\displaystyle 2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$ (60)

where $D$ is some positive constant. The first inequality is due to the fact
that ${m\choose i}i!\leq m^{i}$ and ${n\choose i}\leq n^{i}$. The second
inequality follows from the fact that $1\leq i<k$.

Only one of steps 4 and 5 is executed by the algorithm. From Lemma 4.2, the
probability for step 4 to be executed is at most $2^{-\mu
n\log_{2}^{\frac{4}{3}}{n}}$, where $\mu$ is some constant that depends on $p$
and $q$ only. The expected computation time to execute steps 4 and 5 is thus
at most

$2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}+2^{hm\log_{2}{n}}2^{-\mu
n\log_{2}^{\frac{4}{3}}{n}}.$ (61)

Since $m\leq n$, the second term is bounded by a constant for sufficiently
large $n$. We thus can conclude that the expected computation time for steps 4
and 5 is $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$. Since steps 1, 2,
3 also need $2^{O(n^{\frac{1}{2}}\log_{2}^{\frac{5}{3}}{n})}$ computation
time, the theorem has been proved.

##  5 Approximate Algorithm

As discussed in the introduction, the maximum independent set problem cannot
be approximated within a ratio of $n^{1-\epsilon}$ in polynomial time unless
P=NP, where $\epsilon$ is any positive constant. In [4], it is shown that the
maximum independent set in a graph can be approximated within a ratio of
$O(\frac{n}{\log_{2}^{2}{n}})$. In [15], the approximation ratio is improved
to $O(\frac{n\log_{2}^{2}{\log_{2}{n}}}{\log_{2}^{3}{n}})$. The result so far
remains the best known approximation ratio achieved for this problem in
general graphs. In [19, 22, 29], a polynomial time algorithm that can
approximate the maximum independent set in a random graph within a constant
ratio with high probability is developed and analyzed. However, the
approximation ratio of the algorithm is not guaranteed to be constant for all
graphs. We show that, the maximum independent set in a random graph can be
approximated within a ratio of $\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in expected
polynomial time, which is a significant improvement compared with the best
known approximate ratio for this problem in general graphs.

###### Theorem 5.1

Given a random graph $G=(V,p)$ in $n$ vertices where $p$ is a positive
constant between $0$ and $1$, the maximum independent set in $G$ can be
approximated within a ratio of $\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in expected
polynomial time.

Proof.  We use the following simple algorithm to compute an independent set in
$G$. We let $k=\lfloor 2^{\sqrt{\log_{2}{n}}}\rfloor$ and partition the
vertices in $G$ into $l$ disjoint vertex subsets such that $l-1$ of them
contains $k$ vertices and the remaining one contains at most $k$ vertices. We
use $G_{1},G_{2},\cdots,G_{l}$ to denote the subgraph induced by vertices in
these vertex subsets. It is not difficult to see that
$l\leq\lfloor\frac{n}{k}\rfloor+1$.

We then use the algorithm we have developed in Theorem 2.1 to compute a
maximum independent set in each of $G_{1},G_{2},\cdots,G_{l}$ and return the
one that contains the largest number of vertices.

We first show that the algorithm returns an independent set in expected
polynomial time. $G_{1},G_{2},\cdots,G_{l}$ are disjoint and the expected time
needed to compute a maximum independent set in each of them is at most
$2^{c\log_{2}^{2}{k}}$, where $c$ is some positive constant that only depends
on $p$. Since $k\leq 2^{\sqrt{\log_{2}{n}}}$, the expected computation time
needed to compute the maximum independent set in one subgraph is at most
$2^{c\log_{2}{n}}=n^{c}$. The algorithm thus returns an independent set in
expected time $n^{c+1}$.

We then show that the algorithm can achieve an approximate ratio of
$\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$. We use $APX(G)$ to denote the size of the
independent set returned by the algorithm and $OPT(G)$ to denote the size of a
maximum independent set in $G$. we assume that $I$ is a maximum independent
set in $G$. Since we have partitioned the graph $G$ into $l$ disjoint
subgraphs $G_{0},G_{1},\cdots,G_{l}$, at least one of the $l$ subgraphs
contains at least $\frac{OPT(G)}{l}$ vertices from $I$. These vertices form an
independent set in the subgraph. Since the algorithm computes a maximum
independent set in each subgraph and returns the one with the largest size, we
immediately obtain

$APX(G)\geq\frac{OPT(G)}{l}$ (62)

this suggests that

$\displaystyle\frac{OPT(G)}{APX(G)}$ $\displaystyle\leq$ $\displaystyle l$
(63) $\displaystyle\leq$ $\displaystyle\lfloor\frac{n}{k}\rfloor+1$ (64)
$\displaystyle\leq$ $\displaystyle\frac{n}{k}+1$ (65) $\displaystyle\leq$
$\displaystyle\frac{n}{2^{\sqrt{\log_{2}{n}}}-1}+1$ (66) $\displaystyle\leq$
$\displaystyle\frac{2n}{2^{\sqrt{\log_{2}{n}}}}.$ (67)

The second inequality is due to the fact that
$l\leq\lfloor\frac{n}{k}\rfloor+1$. The fourth inequality is due to the fact
that $k\geq 2^{\sqrt{\log_{2}{n}}}-1$. The last inequality holds for
sufficiently large $n$. The theorem thus has been proved.

##  6 Conclusions

In this paper, we study the independent set problem in random graphs. We show
that a maximum independent set in a random graph can be computed in expected
subexponential time. We also show that the parameterized independent set
problem is fixed parameter tractable with high probability for random graphs.
Using techniques based on enumeration, we show that the largest common
subgraph in two random graphs can be computed in expected subexponential time.
Our work also suggests that the maximum independent set in a random graph can
be approximated within a ratio of $\frac{2n}{2^{\sqrt{\log_{2}{n}}}}$ in
expected polynomial time, which significantly improves on the best known
approximate ratio for this problem in general graphs.

It remains unknown whether the maximum independent set in a random graph can
be computed in expected polynomial time or not. One possible direction of
future work is to study whether there exists such an algorithm. Another
related open question is that if such an algorithm does not exist, whether it
can be approximated within an improved ratio in expected polynomial time.
Further investigations are needed to solve these problems.

## References

  * [1] F. N. Abu-Khzam, N. F. Samatova, M. A. Rizk, and M. A. Langston, “The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover”, Proceedings of 2007 IEEE/ACS International Conference on Computer Systems and Applications (AICCSA 2007), pp. 367-373, 2007.
  * [2] E. Balas and C. S. Yu,“Finding a Maximum Clique in An Arbitrary Graph”, SIAM Journal on Computing, 15(4):1054-1068, 1986.
  * [3] R. Battiti and M. Protasi, ”Reactive Local Search for the Maximum Clique Problem”, Algorithmica 29(4): 610-637, 2001.
  * [4] R. Boppana and M. Halldórson,“Approximating Maximum Independent Sets by Excluding Subgraphs”, BIT Computer Science and Numerical Mathematics,32(2):180-196, 1994.
  * [5] K. V. Brinda, S. Vishveshwara and S. Vishveshwara, “Random Network Behaviour of Protein Structures”, Molecular, BioSystems, 6:391-398, 2010.
  * [6] R. Carraghan and P. M. Pardalos, “An Exact Algorithm for the Maximum Clique Problem”, Operations Research Letters, 9(6): 375-382, 1990.
  * [7] J. Chen, X. Huang, I. A. Kanj, and G. Xia, “Linear FPT Reductions and Computational Lower Bounds”, Proceedings of the Thirty-Sixth ACM Symposium on Theory of Computing (STOC 2004), pp.212-221, 2004.
  * [8] J. Chen, X. Huang, I. A. Kanj, and G. Xia, “Strong Computational Lower Bounds via Parameterized Complexity”, Journal of Computer and System Sciences, 72(8):1346-1367, 2006.
  * [9] I. Dinur and S. Safra, “The Importance of Being Biased”, Proceeding of the Thirty-Fourth ACM Symposium on Theory of Computing (STOC 2002), pp. 33-42, 2002.
  * [10] R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1998.
  * [11] R. G. Downey and M. R. Fellows, “Fixed Parameter Tractability and Completeness i: Basic Theory”, SIAM Journal of Computing, 24:873-921, 1995.
  * [12] R. G. Downey and M. R. Fellows, “Fixed Parameter Tractability and Completeness ii: Completeness for W[1]”, Theoretical Computer Science A, 141:109-131, 1995.
  * [13] P. Erdős and A. Rényi, “On Random Graphs”, Publicationes Mathematicae, 6: 290-297, 1959.
  * [14] T. Fahle, “Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique”, Proceedings of the Tenth European Symposium on Algorithms pp. 47-86, 2002.
  * [15] U. Fiege, “Approximating Maximum Clique by Removing Subgraphs”, SIAM Journal on Discrete Mathematics, 18(2):219-225, 2004.
  * [16] U. Fiege and E. Ofek,“Finding A Maximum Independent Set in A Sparse Random Graph”, SIAM Journal on Discrete Mathematics, 22(2):693-718, 2008.
  * [17] F. V. Fomin, F. Grandoni, and D. Kratsch, “Measure and Conquer: A simple $O(2^{0.288n})$ Independent Set Problem”, Proceedings of the Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 18-25, 2006.
  * [18] M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman and Co., San Francisco, California, 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.
  * [19] G. R. Grimmett and C. J. H. Mcdiarmid, “On Colouring Random Graphs”, Mathematical Proceedings of the Cambridge Philosophical Society, 77(2):313-324, 1975.
  * [20] A. Grosso, M. Locatelli, F. D. Croce, “Combining Swaps and Node Weights in An Adaptive Greedy Approach for the Maximum Clique Problem”, Journal of Heuristics 10(2):135-152, 2004.
  * [21] J. Håstad, “Clique Is Hard to Approximate Within $n^{1-\epsilon}$”, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (STOC 1996), 627-636, 1996.
  * [22] S. Homer and M. Peinado, “On the performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs”, In Cliques, Coloring, and Satisfiability: second DIMACS Implementation Challenge, pp. 103-124, 1993\.
  * [23] T. Jian, “An $O(2^{0.308n})$ Algorithm for Solving Maximum Independent Set Problem”, IEEE Transactions on Computers, 35(9):847-851, 1986.
  * [24] D. S. Johnson, “Approximate Algorithms for Combinatorial Problems”, Journal of Computer and System Sciences, 9, 256-278, 1974.
  * [25] R. M. Karp, “The Probability Analysis of Some Combinatorial Search Problems”, Algorithms and Complexity: New Directions and Recent Results, 1-19, Academic Press, New York, 1976.
  * [26] K. Katayama, A. Hamamoto, and H. Narihisa, “An Effective Local Search for the Maximum Clique Problem”, Information Processing Letters 95(5):503-511, 2005.
  * [27] J. Konc and D. Janežič, “An Improved Branch and Bound Algorithm for the Maximum Clique Problem”, MATCH Communications in Mathematical and in Computer Chemistry 58(3): 569-590, 2007.
  * [28] O. Kuchaiev, T. Milenković, V. Memišević, W. Hayes, and N. Pržulj, “Topological Network Alignment Uncovers Biological Function and Phylogeny”, Journal of Royal Society Interface, 7(50):1341-1354, 2010.
  * [29] A. Coja-Oghlan and C. Efthymiou, “On Independent Sets in Random Graphs”, Proceedings of the Twenty Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 136-144, 2011.
  * [30] P. R. J. Östergård, “A Fast Algorithm for the Maximum Clique Problem”, Discrete Applied Mathematics 120 (1 3):197-207,2002.
  * [31] P. M. Pardalos and G. P. Rogers, “A Branch and Bound Algorithm for the Maximum Clique Problem”, Computers and Operations Research 19 (5): 363-375, 1992.
  * [32] J. C. Régin, “Using Constraint Programming to Solve the Maximum Clique Problem”, Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming, pp. 634-648, 2003.
  * [33] J. M. Robson, “Algorithms for Maximum Independent Sets”, Journal of Algorithms, 7(3):425-440, 1986.
  * [34] J. M. Robson, “Finding A Maximum Independent Set in Time $O(2^{\frac{n}{4}})$”, Technical Report 1251-01, LaBRI Université de Bordeaux I, 2001.
  * [35] W. H. Suters, F. N. Abu-Khzam, Y. Zhang, C. T. Symons, N. F. Samatova, and M. A. Langston, “A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem”,Proceedings of the Eleventh International Computing and Combinatorics Conference, pp. 717-727, 2005.
  * [36] R. E. Tarjan and A. E. Trojanowski, “Finding A Maximum Independent Set”, Technical Report CS-TR-76-550, Stanford University, 1976.
  * [37] E. Tomita and T. Seki, “An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique”, Discrete Mathematics and Theoretical Computer Science, pp. 278-289, 2003.
  * [38] E. Tomita and T. Kameda, “An Efficient Branch-and-bound Algorithm for Finding A Maximum Clique with Computational Experiments”, Journal of Global Optimization 37(1): 95-111, 2007.