# Non-normal edge rings satisfying $(S_{2})$-condition

Nayana Shibu Deepthi  Department of Pure and Applied Mathematics, Graduate
School of Information Science and Technology, Osaka University, Suita, Osaka
565-0871, Japan<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finite simple connected graph on the vertex set
$V(G)=[d]=\\{1,\dots,d\\}$, with edge set $E(G)=\\{e_{1},\dots,e_{n}\\}$. Let
$K[\mathbf{t}]=K[t_{1},\dots,t_{d}]$ be the polynomial ring in $d$ variables
over a field $K$. The edge ring of $G$ is the semigroup ring $K[G]$ generated
by monomials $\mathbf{t}^{e}:=t_{i}t_{j}$, for $e=\\{i,j\\}\in E(G)$. In this
paper, we will prove that, given integers $d$ and $n$, where $d\geq 7$ and
$d+1\leq n\leq\frac{d^{2}-7d+24}{2}$, there exists a finite simple connected
graph $G$ with $|V(G)|=d$ and $|E(G)|=n$, such that $K[G]$ is non-normal and
satisfies $(S_{2})$-condition.

###### Key words and phrases:

Edge rings - Normality - Odd cycle condition - $(S_{2})$-condition.

###### 2020 Mathematics Subject Classification:

13H10

##  1\. Introduction

Let $G$ be a finite simple connected graph on the vertex set $V(G)=[d]$ and
let $E(G)=\\{e_{1},\dots,e_{n}\\}$ be the edge set of $G$. Let us consider,
$K[\mathbf{t}]=K[t_{1},\dots,t_{d}]$ to be the polynomial ring in $d$
variables over a field $K$. For an edge $e=\\{i,j\\}$ in $E(G)$, we define
$\mathbf{t}^{e}:=t_{i}t_{j}$. The subring of $K[\mathbf{t}]$ generated by
$\mathbf{t}^{e_{1}},\dots,\mathbf{t}^{e_{n}}$ is called the edge ring of $G$,
denoted by $K[G]$. Let $\mathbf{e}_{1},\dots,\mathbf{e}_{d}$ be the canonical
unit coordinate vectors of $\mathbb{R}^{d}$ and for each $e=\\{i,j\\}\in
E(G)$, we define $\rho(e):=\mathbf{e}_{i}+\mathbf{e}_{j}$. Let $S_{G}$ be the
affine semigroup generated by $\rho(e_{1}),\dots,\rho(e_{n})$. Then, the edge
ring $K[G]$ is the affine semigroup ring of $S_{G}$.

For an affine semigroup $S\subset\mathbb{N}^{d}$, let $K[S]$ be the affine
semigroup ring of $S$. While studying for a characterization of Cohen-Macaulay
affine semigroup ring, Goto and Watanabe [2] have defined an extension
$S^{\prime}$ of $S$ and claimed that the condition, $S^{\prime}=S$ is the
necessary and sufficient condition for $K[S]$ to be Cohen-Macaulay. Trung and
Hoa [9] presented a counterexample and also demonstrated that $S^{\prime}=S$
is insufficient to establish the Cohen-Macaulayness of $K[S]$. They have also
provided an additional topological condition on $C_{S}$, the convex rational
polyhedral cone spanned by $S$ in $\mathbb{Q}^{d}$, and characterized the
Cohen-Macaulayness of $K[S]$. Schäfer and Schenzel [7, Theorem 6.3] claimed
that the condition $S^{\prime}=S$ corresponds to the Serre’s condition
($S_{2}$). For the introduction of Serre’s condition ($S_{2}$), readers may
refer to [1, Section 2].

The Cohen-Macaulayness of the edge ring $K[G]$ in terms of the corresponding
graph $G$ has been a subject of extensive research. Given that the edge ring
$K[G]$ is an affine semigroup ring, it is known from [5, Theorem 1] that, if
$K[G]$ is normal then $K[G]$ is Cohen-Macaulay. Ohsugi and Hibi [6] have
characterized the normality of an edge ring in terms of its graph. At about
the same time, Simis-Vasconcelos-Villarreal independently came to the same
conclusion and reported it in [8]. Recall from [1, Theorem 2.2.22] that, the
edge ring $K[G]$ is normal if and if $K[G]$ satisfies Serre’s conditions
$(R_{1})$ and $(S_{2})$. In [3, Theorem 2.1], Hibi and Katthän have
characterized the edge rings satisfying $(R_{1})$-condition. Note that Serre’s
condition $(S_{2})$ is a necessary condition for $K[G]$ to be Cohen-Macaulay.
Based on these insights, Higashitani and Kimura [4] have provided the
necessary condition for an edge ring to satisfy the $(S_{2})$-condition.

The main theorem that we will prove in this paper is as follows:

######  Theorem 1.1.

Given integers $d$ and $n$ such that, $d\geq 7$ and $d+1\leq
n\leq\frac{d^{2}-7d+24}{2}$, there exists a finite simple connected graph $G$
with $|V(G)|=d$ and $|E(G)|=n$ such that, the edge ring $K[G]$ is non-normal
and satisfies $(S_{2})$-condition.

A detailed explanation of why the quadratic expression $\frac{d^{2}-7d+24}{2}$
appears in the main theorem is provided in Section 6.

This paper is organized as follows. In Section 2, we revisit some basic
prerequisite definitions and results that will be encountered throughout this
article. Section 3 deals with introduction of the graph $G_{a,b}$, whose edge
ring $K[G_{a,b}]$ is non-normal. In this section, we further prove that the
edge ring $K[G_{a,b}]$ satisfies $(S_{2})$-condition. Section 4 focuses on the
step-wise removal of edges from $G_{a,b}$, such that each new graph obtained
per step also satisfies both non-normality and $(S_{2})$-condition. In Section
5, we prove that any addition of new edges to the graph $G_{a,b}$, either
affects the non-normality of the edge ring or leads to the violation of
$(S_{2})$-condition. We conclude the article with Section 6, which deals with
supporting evidence for Theorem 1.1 and the conclusions.

######  Acknowledgement.

I would like to thank Professor Akihiro Higashitani, my research supervisor,
for introducing the problem and for his valuable comments that greatly
improved the manuscript.

##  2\. Preliminaries

Let $G$ be a finite simple connected graph on the vertex set $V(G)=[d]$, with
edge set $E(G)=\\{e_{1},\dots,e_{n}\\}$. Let us consider
$K[\mathbf{t}]=K[t_{1},\dots,t_{d}]$ to be the polynomial ring in $d$
variables over a field $K$. For an edge $e=\\{i,j\\}\in E(G)$, we define
$\mathbf{t}^{e}:=t_{i}t_{j}.$ The subring of $K[\mathbf{t}]$ generated by
$\mathbf{t}^{e_{1}},\dots,\mathbf{t}^{e_{n}}$ is called the edge ring of $G$
and let it be denoted as $K[G]$.

We consider $\mathbf{e}_{1},\dots,\mathbf{e}_{d}$ to be the canonical unit
coordinate vectors of $\mathbb{R}^{d}$. For some edge $e=\\{i,j\\}\in E(G)$,
define $\rho(e):=\mathbf{e}_{i}+\mathbf{e}_{j}$. Let
$\mathcal{A}_{G}:=\\{\rho(e)\colon e\in E(G)\\}$ and let $S_{G}$ be the affine
semigroup generated by $\rho(e_{1}),\dots,\rho(e_{n})$. We can express,
$S_{G}:=\mathbb{Z}_{\geq 0}\mathcal{A}_{G}.$ Thus, the edge ring $K[G]$ is the
affine semigroup ring of $S_{G}$.

Consider $C_{G}$ to be the convex rational polyhedral cone spanned by $S_{G}$
in $\mathbb{Q}^{d}$. We may assume that $C_{G}$ is of dimension $d$ and let
$\mathcal{F}(G)$ be the set of all facets of $C_{G}$. We define,
$\overline{S}_{G}:=\mathbb{Q}_{\geq
0}\mathcal{A}_{G}\cap\mathbb{Z}\mathcal{A}_{G}.$ For any facet
$F\in\mathcal{F}(G)$, we define

$S_{F}:=S_{G}-S_{G}\cap
F=\\{\mathbf{x}\in\mathbb{Z}\mathcal{A}_{G}\colon\exists\ \mathbf{y}\in
S_{G}\cap F\textrm{ such that }\mathbf{x}+\mathbf{y}\in S_{G}\\},$

and $S^{\prime}_{G}:=\bigcap\limits_{F\in\mathcal{F}(G)}S_{F}.$ By definition,
$\mathcal{A}_{G}$ is said to be normal when we have

$\mathbb{Z}_{\geq
0}\mathcal{A}_{G}=\mathbb{Z}\mathcal{A}_{G}\cap\mathbb{Q}_{\geq
0}\mathcal{A}_{G},$

that is, when $\overline{S}_{G}=S_{G}.$

A cycle is said to be minimal in $G$ if there exists no chord in it. Let $C$
and $C^{\prime}$ be two minimal cycles of $G$ with $V(C)\cap
V(C^{\prime})=\emptyset$, if we have $i\in V(C)$ and $j\in V(C^{\prime})$,
then $e=\\{i,j\\}\in E(G)$ is called a bridge between $C$ and $C^{\prime}$.

A pair of odd cycles $(C,C^{\prime})$ is called exceptional if $C$ and
$C^{\prime}$ are minimal odd cycles in $G$ such that $V(C)\cap
V(C^{\prime})=\emptyset$ and there exists no bridge connecting them. We say
that a graph $G$ satisfies odd cycle condition, if for any two odd cycles $C$
and $C^{\prime}$ of $G$, either $V(C)\cap V(C^{\prime})\neq\emptyset$ or there
exists a bridge between $C$ and $C^{\prime}$. In other words, the graph $G$
has no exceptional pairs.

######  Theorem 2.1 (From [6, Theorem 2.2] and [8, Theorem 1.1]).

Let G be a finite simple graph. Then, the edge ring $K[G]$ is normal if and
only if $G$ satisfies the odd cycle condition.

From all of the above observations, we have:

$S_{G}=\overline{S}_{G}\iff K[G]\textrm{ is normal }\iff G\textrm{ satisfies
odd cycle condition}.$

Let us consider $U\subset V(G)$, and we define $G_{U}$ as the induced subgraph
of $G$ with $V(G_{U})=U$ and $E(G_{U})=\\{e\in E(G)\colon e\subset U\\}.$ Let
$i\in V(G)$ and we denote $G\backslash i$ as the induced subgraph of $G$ on
the vertex set $V(G\backslash i)=V(G)\backslash\\{i\\}$. Consider a subset
$T\subset V(G)$ and we define:

$N(G;T):=\big{\\{}v\in V(G)\colon\\{v,w\\}\in E(G)\textrm{ for some }w\in
T\big{\\}}.$

A subset $T\subset V(G)$ is called independent if $\\{t_{i},t_{j}\\}\notin
E(G)$ for any $t_{i},t_{j}\in T$. For an independent set $T\subset V(G)$, we
define a bipartite graph induced by $T$ as the graph on vertex set $T\cup
N(G;T)$ with edge set $\big{\\{}\\{v,w\\}\in E(G)\colon v\in T,\ w\in
N(G;T)\big{\\}}$.

Now, we will be looking at the facets of $C_{G}$. For that, let us look at
some important definitions and theorems that have been discussed in [6].

######  Definition 2.2.

Let $G$ be a finite connected simple graph with vertex set $V(G)$. A vertex
$v\in V(G)$ is said to be regular in $G$ if every connected component of
$G\backslash v$ contains at least one odd cycle. A non-empty set $T\subset
V(G)$ is said to be fundamental in $G$ if all the conditions below are
satisfied by $T$:

  1. (1)

$T$ is an independent set;

  2. (2)

the bipartite graph induced by $T$ is connected;

  3. (3)

either $T\cup N(G;T)=V(G)$ or every connected component of the graph
$G_{V(G)\backslash T\cup N(G;T)}$ contains at least one odd cycle.

Facets of $C_{G}$ are given by the intersection of the half-spaces defined by
the supporting hyperplanes of $C_{G}$, and was investigated by Ohsugi and Hibi
[6].

######  Theorem 2.3 (From [6, Theorem 1.7]).

Let $G$ be a finite connected simple graph on the vertex set $[d]$, containing
at least one odd cycle. Then, all the supporting hyperplanes of $C_{G}$ are as
follows:

  1. (1)

$\mathcal{H}_{v}=\big{\\{}(x_{1},\dots,x_{d})\in\mathbb{R}^{d}\colon
x_{v}=0\big{\\}}$, where $v$ is a regular vertex in $G$.

  2. (2)

$\mathcal{H}_{T}=\big{\\{}(x_{1},\dots,x_{d})\in\mathbb{R}^{d}\colon\sum\limits_{i\in
T}x_{i}=\sum\limits_{j\in N(G;T)}x_{j}\big{\\}}$, where $T$ is a fundamental
set in $G$.

In this paper, we denote $F_{v}$ and $F_{T}$ as the facets of $C_{G}$
corresponding to the hyperplanes $\mathcal{H}_{v}$ and $\mathcal{H}_{T}$
respectively.

With reference to the work of Ohsugi and Hibi [6, Theorem 2.2], normalization
of the edge ring $K[G]$ can be expressed as

$\overline{S}_{G}=S_{G}\ +\ \mathbb{Z}_{\geq
0}\big{\\{}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\colon(C,C^{\prime})\textrm{
is exceptional in }G\big{\\}},$

where for any odd cycle $C$, we define $\mathbb{E}_{C}:=\sum\limits_{i\in
V(C)}\mathbf{e}_{i}.$ We observe that,

$2\big{(}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\big{)}=\Bigg{(}\displaystyle{\sum\limits_{e\in
E(C)}}\rho(e)+\displaystyle{\sum\limits_{e^{\prime}\in
E(C^{\prime})}}\rho(e^{\prime})\Bigg{)}\in S_{G}.$

Through the work of Goto and Watanabe [2] and the investigation by Trung and
Hoa [9], the necessary and sufficient conditions for $K[G]$ to be Cohen-
Macaulay were established. Followed by this, Schäfer and Schenzel [7, Theorem
6.3] stated that, the condition $S^{\prime}_{G}=S_{G}$ corresponds to the
Serre’s condition $(S_{2})$.

In general, $S_{G}\subset S^{\prime}_{G}\subset\overline{S}_{G}.$ Therefore,
in order to prove that the edge ring $K[G]$ satisfies $(S_{2})$-condition, it
is enough to show that for any $\alpha\in\overline{S}_{G}\backslash S_{G}$,
the element $\alpha\notin S^{\prime}_{G}$. This implies that
$S^{\prime}_{G}\subset S_{G}$ and therefore $S^{\prime}_{G}=S_{G}$.

In [4], Higashitani and Kimura have provided the necessary condition that a
graph $G$ has to hold in order to satisfy $(S_{2})$-condition.

######  Theorem 2.4 (From [4, Theorem 4.1]).

Let $G$ be a finite simple connected graph. Suppose that, there exists an
exceptional pair $(C,C^{\prime})$ satisfying the following two conditions:

  1. (1)

for each regular vertex $v\in V(G)\backslash[V(C)\cup V(C^{\prime})]$ in $G$,
both $C$ and $C^{\prime}$ belong to the same connected component of the graph
$G\backslash v;$

  2. (2)

for each fundamental set $T\in G$ with $[V(C)\cup V(C^{\prime})]\cap[T\cup
N(G;T)]=\emptyset$, both $C$ and $C^{\prime}$ belong to the same connected
component of $G_{V(G)\backslash(T\cup N(G;T))}$.

Then, $\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\in S_{G}^{\prime}$. In
particular, $S_{G}\neq S_{G}^{\prime}$.

##  3\. The Graph $G_{a,b}$

This section explicitly deals with the construction and study of a special
graph $G_{a,b}$, whose edge ring $K[G_{a,b}]$ is non-normal. We conclude the
section by stating and proving a proposition that, the edge ring $K[G_{a,b}]$
satisfies $(S_{2})$-condition.

Let $G_{a,b}$ be a simple finite connected graph with $|V(G_{a,b})|=d=a+b+1$,
where $3\leq a\leq b$. We construct the graph $G_{a,b}$ (Figure 1) such that,
it is formed by the union of two complete graphs $K_{a+1}$ and $K_{b+1}$ with
exactly one common vertex. Let us consider the vertex set
$V(G_{a,b})=V(K_{a+1})\cup V(K_{b+1})$, such that
$V(K_{a+1})=\\{u_{1},\dots,u_{a},w\\}$ and
$V(K_{b+1})=\\{v_{1},\dots,v_{b},w\\}$.

$v_{b}$$v_{1}$$u_{1}$$w$$K_{b+1}$$u_{2}$$K_{a+1}$$u_{a}$ Figure 1. The graph
$G_{a,b}$

Any vertex $v\in V(G_{a,b})$ is regular in $G_{a,b}$. We observe that the
fundamental sets in $G_{a,b}$ are :

$\\{i\\},\ \forall\ i\in V(G_{a,b})\textrm{ and }\\{i,j\\},\ \forall\
\\{i,j\\}\notin E(G_{a,b}).$

For any fundamental set $T\subset V(G_{a,b})$, let $H_{T}$ be the bipartite
graph induced by $T$. We consider $K_{a}$ to be the induced subgraph of
$G_{a,b}$ on vertex set $V(K_{a+1})\backslash\\{w\\}$, that is, the complete
graph on $V(K_{a})=\\{u_{1},\dots,u_{a}\\}$. Similarly, $K_{b}$ is the induced
subgraph of $G_{a,b}$ on the vertex set $V(K_{b+1})\backslash\\{w\\}$, which
is the complete graph on $V(K_{b})=\\{v_{1},\dots,v_{b}\\}$.

Let us denote $\mathcal{A}_{G_{a,b}}:=\\{\rho(e)\colon e\in E(G_{a,b})\\}$,
$S:=S_{G_{a,b}}$ and $\overline{S}:=\overline{S_{G_{a,b}}}.$ We consider
$C_{S}$ to be the convex rational polyhedral cone spanned by
$\mathcal{A}_{G_{a,b}}$ in $\mathbb{Q}^{d}$, i.e., $C_{S}:=C_{G_{a,b}}$. Let
$\mathcal{F}(G_{a,b})$ be the set of all facets of $C_{S}$ and for any
$F_{i}\in\mathcal{F}(G_{a,b}),$

$S_{i}:=S-S\cap
F_{i}=\\{\mathbf{x}\in\mathbb{Z}\mathcal{A}_{G_{a,b}}\colon\exists\
\mathbf{y}\in S\cap F_{i}\textrm{ such that }\mathbf{x}+\mathbf{y}\in S\\},$
$S^{\prime}:=\bigcap\limits_{F_{i}\in\mathcal{F}(G_{a,b})}S_{i}.$

Now, let us look at the facets of $C_{S}$ in detail. We observe that, for any
regular vertex $v\in V(G_{a,b})$,

$S\cap F_{v}=\mathbb{Z}_{\geq 0}\mathcal{A}_{G_{a,b}\backslash v}.$

Corresponding to each fundamental set in $G_{a,b},$ we have

$S\cap F_{\\{w\\}}=\mathbb{Z}_{\geq 0}\mathcal{A}_{H_{\\{w\\}}},$ $S\cap
F_{\\{u_{i}\\}}=\mathbb{Z}_{\geq 0}\mathcal{A}_{H_{\\{u_{i}\\}}\bigsqcup
K_{b}},$ $S\cap F_{\\{v_{j}\\}}=\mathbb{Z}_{\geq 0}\mathcal{A}_{K_{a}\bigsqcup
H_{\\{v_{j}\\}}},$ $S\cap F_{\\{u_{i},v_{j}\\}}=\mathbb{Z}_{\geq
0}\mathcal{A}_{H_{\\{u_{i},v_{j}\\}}},$

where $1\leq i\leq a$ and $1\leq j\leq b.$ Note that, throughout this
investigation, we are only concerned about the description of $S\cap F_{w}$,
for a regular vertex $w$.

######  Lemma 3.1.

Let the pair of odd cycles $(C,C^{\prime})$ be exceptional in $G_{a,b}$.
Consider vertices $v,w\in V(G_{a,b})$, where $w$ is the common vertex of
$K_{a+1}$ and $K_{b+1}$. Let $\mathbf{e}_{v}$ and $\mathbf{e}_{w}$ be the
canonical unit coordinate vectors of $\mathbb{R}^{d}$ corresponding to
vertices $v$ and $w$ respectively. Then,

$\mathbb{E}_{C}\ +\ \mathbb{E}_{C^{\prime}}\ +\ \mathbf{e}_{v}\ +\
\mathbf{e}_{w}\in S.$

###### Proof.

We consider an exceptional pair $(C,C^{\prime})$ in $G_{a,b}$. Without loss of
generality, let $C=\\{u_{i_{1}},u_{i_{2}},u_{i_{3}}\\}$ be a minimal odd cycle
in $K_{a+1}$ and $C^{\prime}=\\{v_{j_{1}},v_{j_{2}},v_{j_{3}}\\}$ be a minimal
odd cycle in $K_{b+1}$.

Since $K_{a+1}$ and $K_{b+1}$ are complete graphs with common vertex $w$ and
$(C,C^{\prime})$ is exceptional in $G_{a,b}$, we have $V(C)\cap
V(C^{\prime})=\emptyset$ and $w\notin V(C)\cup V(C^{\prime})$.

Without loss of generality, we may assume $v\in V(K_{a+1})$. Given that
$K_{a+1}$ and $K_{b+1}$ are complete graphs, for any $u_{i_{k}}\in V(C)$ that
is distinct from $v$, we have $\\{v,u_{i_{k}}\\}\in E(G_{a,b})$ and for any
$v_{j_{k}}\in V(C^{\prime})$, we have $\\{w,v_{j_{k}}\\}\in E(G_{a,b})$.
Suppose, we choose $u_{i_{1}}\neq v$. Then we can express

$\begin{array}[]{lcl}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}&=&\sum\limits_{k=1}^{3}\mathbf{e}_{u_{i_{k}}}+\sum\limits_{k=1}^{3}\mathbf{e}_{v_{j_{k}}}+\mathbf{e}_{v}+\mathbf{e}_{w}\\\
\\\
&=&(\mathbf{e}_{v}+\mathbf{e}_{u_{i_{1}}})+\sum\limits_{k=2}^{3}\mathbf{e}_{u_{i_{k}}}+\sum\limits_{k=1}^{2}\mathbf{e}_{v_{j_{k}}}+(\mathbf{e}_{v_{j_{3}}}+\mathbf{e}_{w}).\end{array}$

This can be written as,

$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}=\rho\big{(}\\{v,u_{i_{1}}\\}\big{)}+\rho\big{(}\\{u_{i_{2}},u_{i_{3}}\\}\big{)}+\rho\big{(}\\{v_{j_{1}},v_{j_{2}}\\}\big{)}+\rho\big{(}\\{v_{j_{3}},w\\}\big{)}.$

As we can see, the expression
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}$ can be
written as a linear combination of some $\rho(e),$ where $e\in E(G_{a,b})$.
Therefore, for any $v,w\in V(G_{a,b})$, we have
$\big{(}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}\big{)}\in
S.$ ∎

Let us consider
$\mathbf{x}=(x_{u_{1}},\dots,x_{u_{a}},x_{w},x_{v_{1}},\dots,x_{v_{b}})\in\mathbb{Z}^{d}_{\geq
0}$. We define a set,

$A:=\bigg{\\{}\mathbf{x}\ \colon\ x_{w}=0,\
\displaystyle{\sum\limits_{u\in\\{u_{1},\dots,u_{a}\\}}}x_{u}\textrm{ is odd
},\ \displaystyle{\sum\limits_{v\in\\{v_{1},\dots,v_{b}\\}}}x_{v}\textrm{ is
odd }\bigg{\\}}.$

For the simple finite connected graph $G_{a,b}$ (Figure 1) and the set $A$ as
defined above, we can state the following lemma.

######  Lemma 3.2.

$\overline{S}\subset S\cup A$.

###### Proof.

Let $\alpha$ be an arbitrary element in $\overline{S}$. As we have seen in
Section 2, the normalization of the edge ring $K[G_{a,b}]$ can be expressed as

$\overline{S}=S\ +\ \mathbb{Z}_{\geq
0}\big{\\{}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\colon(C,C^{\prime})\textrm{
is exceptional in }G_{a,b}\big{\\}}.$

Therefore, any $\alpha\in\overline{S}$ can be expressed as
$\alpha=\beta+\gamma$, where we have $\beta\in S$ and
$\gamma\in\mathbb{Z}_{\geq
0}\big{\\{}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\colon(C,C^{\prime})\textrm{
is exceptional in }G_{a,b}\big{\\}}.$ If $\gamma=0$, then $\alpha\in S$. So,
let us consider the non-trivial case where $\gamma\neq 0$. Let $\alpha_{i}$,
$\beta_{i}$ and $\gamma_{i}$ represent the $i^{\textrm{th}}$ coordinates of
$\alpha$, $\beta$ and $\gamma$ respectively.

Since for any two (possibly identical) exceptional pairs
$(C,C^{\prime}),(\overline{C},\overline{C}^{\prime})$, it follows from the
completeness of the graphs $K_{a+1}$ and $K_{b+1}$ that
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbb{E}_{\overline{C}}+\mathbb{E}_{\overline{C}^{\prime}}\in
S$. Therefore, without loss of generality, for an exceptional pair
$(C,C^{\prime})$ in $G_{a,b}$, we may assume that
$\gamma=\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}$.

Case 1. Let $\alpha_{w}=0$.

We have $\alpha_{w}=0$ and $\gamma\neq 0$ with $\gamma_{w}=0$. Therefore
$\beta_{w}=0$, that is, we are not considering any edge adjacent to the common
vertex $w$. This assures that, both $\sum\limits_{u\in V(K_{a})}\beta_{u}$ and
$\sum\limits_{v\in V(K_{b})}\beta_{v}$ have to be even. Hence, both
$\sum\limits_{u\in V(K_{a})}\alpha_{u}$ and $\sum\limits_{v\in
V(K_{b})}\alpha_{v}$ will be odd. Thus we have $\alpha\in A$ and therefore,
$\alpha\in S\cup A$.

Case 2. Let $\alpha_{w}>0$.

Consider an exceptional pair $(C,C^{\prime})$ in $G_{a,b}$. We have
$\gamma=\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}$. The condition $\alpha_{w}>0$
implies $\beta_{w}>0$. This indicates that there must be at least one edge
adjacent to the common vertex $w$, say $\\{v,w\\}$. For any exceptional pair
$(C,C^{\prime})$ in $G_{a,b}$, by Lemma 3.1, we have
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}\in S.$
Hence, $\alpha=\beta+\gamma\in S$. Thus, it proves that $\alpha\in S\cup A$. ∎

All of the observations we have made so far lead us to the conclusion that,

$S\subset S^{\prime}\subset\overline{S}\subset S\cup A.$

######  Proposition 3.3.

Let $G_{a,b}$ be a simple finite connected graph with $3\leq a\leq b$ and
$|V(G_{a,b})|=a+b+1=d$, such that $G_{a,b}$ (Figure 1) consists of two
complete graphs $K_{a+1}$ and $K_{b+1}$ joined at a common vertex $w$. Let
$K[G_{a,b}]$ be the edge ring of the graph $G_{a,b}$. Then, $K[G_{a,b}]$ is
non-normal and satisfies $(S_{2})$-condition.

###### Proof.

Since $G_{a,b}$ is the union of two complete graphs with a common vertex $w$,
it is assured that all the pairs of odd cycles of the form
($\\{u_{i},u_{i+1},u_{i+2}\\},\\{v_{j},v_{j+1},v_{j+2}\\}$) where $1\leq i\leq
a-2$ and $1\leq j\leq b-2$ are exceptional. Therefore, the graph $G_{a,b}$
does not satisfy the odd cycle condition and by Theorem 2.1, we conclude that
the edge ring $K[G_{a,b}]$ is non-normal.

Let us consider an element from the set $A$, say
$\alpha=(x_{u_{1}},\dots,x_{u_{a}},0,x_{v_{1}},\dots,x_{v_{b}})$ such that
$\alpha\in\overline{S}\backslash S$. We have seen that the common vertex $w$
is regular in $G_{a,b}$ and corresponding to this regular vertex we have
$S\cap F_{w}=\mathbb{Z}_{\geq 0}\mathcal{A}_{G_{a,b}\backslash w}$. For any
$\beta\in S\cap F_{w},$ let $\beta_{i}$ represent the $i^{\textrm{th}}$
coordinate of $\beta$. We observe that $\beta_{w}=0$ and both
$\sum\limits_{i=1}^{a}\beta_{u_{i}}$, and $\sum\limits_{j=1}^{b}\beta_{v_{j}}$
are even. Therefore, for all $\beta\in S\cap F_{w}$, we have $\alpha+\beta\in
A$ and not in $S$. Thus, there exists no $\beta\in S\cap F_{w}$, such that
$\alpha+\beta\in S$. Therefore, $\alpha\notin S_{w}$. Hence,

$\alpha\notin\bigcap\limits_{F_{i}\in\mathcal{F}(G_{a,b})}S_{i}=S^{\prime}.$

This implies that, for any $\alpha\in\overline{S}\backslash S$, we have
$\alpha\notin S^{\prime}$. Hence, $(\overline{S}\backslash S)\cap
S^{\prime}=\emptyset$ and $S^{\prime}\subset S.$ We know that $S\subset
S^{\prime}.$ Therefore, $S^{\prime}=S.$ ∎

We have proved that $K[G_{a,b}]$ is non-normal and satisfies
$(S_{2})$-condition. Now, we are interested in modifying the graph $G_{a,b}$,
to see how the behaviour of the corresponding edge ring varies.

##  4\. Removing edges of $G_{a,b}$ and $(S_{2})$-condition

In Section 3, we have studied the graph $G_{a,b}$ in detail. In this section,
we will investigate whether we can remove edges of $G_{a,b}$ to obtain
$\widetilde{G}$, a subgraph of $G_{a,b}$, with $V(\widetilde{G})=V(G_{a,b})$
and $|E(\widetilde{G})|=d+1$ such that the edge ring $K[\widetilde{G}]$ is
non-normal and satisfies $(S_{2})$-condition. We will modify a method of
eliminating edges of $G_{a,b}$ so that the common vertex $w$ remains regular
in any graph created using this method. By the end of this section, we prove
that $K[\widetilde{G}]$ is non-normal and satisfies $(S_{2})$-condition.

Figure 2. The graph $G_{a-1}^{u_{a-2}}$

By eliminating one edge from the graph $G_{a,b}$ per step, we will gradually
build up $\widetilde{G}$. First of all, we will be removing edges of the graph
$K_{a+1}$ and will not alter the graph $K_{b+1}$. Let us denote
$u_{0}\coloneqq w$ and $G^{u_{1}}_{0}\coloneqq G_{a,b}$. We construct a new
subgraph of $G_{a,b}$ through an edge removal process such that for each
$1\leq i\leq a-3$,

  * •

we remove the edge $\\{u_{0},u_{i}\\}$ from $G^{u_{i}}_{0}$ to obtain
$G^{u_{i}}_{i}$, and

  * •

remove the edge $\\{u_{i},u_{j}\\}$ from $G^{u_{i}}_{j-1}$ to obtain
$G^{u_{i}}_{j}$, $\forall\ i+1\leq j\leq a-1$.

Let us denote $G^{u_{i}}_{0}:=G^{u_{i-1}}_{a-1}$, $\forall\ 2\leq i\leq a-2$.
By construction, we observe that

$E(G^{u_{i}}_{0})=E(G_{a,b})\backslash\bigcup\limits_{p=1}^{i-1}\bigg{\\{}\\{u_{p},u_{q}\\}\colon
q\neq p,0\leq q\leq a-1\bigg{\\}},\hskip 5.69046pt\forall\ 2\leq i\leq a-2.$

For $i=a-2$, the construction of the subgraph $G^{u_{i}}_{j}$, $a-2\leq j\leq
a-1$ is as follows:

  * •

the subgraph $G^{u_{a-2}}_{a-2}$ is constructed by removing the edge
$\\{u_{0},u_{a-2}\\}$ from $G^{u_{a-2}}_{0}$;

  * •

the edge $\\{u_{0},u_{a-1}\\}$ is removed from $G^{u_{a-2}}_{a-2}$, to obtain
the subgraph $G^{u_{a-2}}_{a-1}$.

An example of the sequence of subgraphs $G^{u_{i}}_{j}$; $1\leq i\leq 2$ and
$i\leq j\leq 3$ that is constructed from the graph $G_{4,3}$ using the edge
removal process defined above is illustrated in Figure 3.

${{G_{4,3}\eqqcolon
G^{u_{1}}_{0}}}$${G^{u_{1}}_{1}}$${G^{u_{1}}_{2}}$${G^{u_{1}}_{3}\eqqcolon
G^{u_{2}}_{0}}$${G^{u_{2}}_{2}}$${G^{u_{2}}_{3}}$$\leftarrow$$\rightarrow$$\scriptstyle{-\\{u_{0}\mathpunct{\raisebox{0.0pt}{,}}u_{1}\\}}$$\leftarrow$$\rightarrow$$\scriptstyle{-\\{u_{1}\mathpunct{\raisebox{0.0pt}{,}}u_{2}\\}}$$\leftarrow$$\rightarrow$$\scriptstyle{-\\{u_{1}\mathpunct{\raisebox{0.0pt}{,}}u_{3}\\}}$$\leftarrow$$\rightarrow$$\scriptstyle{-\\{u_{0}\mathpunct{\raisebox{0.0pt}{,}}u_{2}\\}}$$\leftarrow$$\rightarrow$$\scriptstyle{-\\{u_{0}\mathpunct{\raisebox{0.0pt}{,}}u_{3}\\}}$
Figure 3. A sequence of subgraphs constructed from $G_{4,3}$

According to our construction, $V(G^{u_{i}}_{j})=V(G_{a,b})$, $\forall\ 1\leq
i\leq a-2,\ i\leq j\leq a-1$. By the end of this entire process, we construct
the subgraph of $G_{a,b}$, as shown in Figure 2.

Let $C=\\{u_{i_{1}},u_{i_{2}},\dots,u_{i_{2l+1}}\\}$ be an odd cycle in
$G^{u_{i}}_{j}$, such that $2l+1\geq 5$ and $1\leq
i_{1}<i_{2}<\cdots<i_{2l+1}$. We have $\\{u_{i_{1}},u_{i_{2}}\\}\in
E(G^{u_{i}}_{j})$ and $\\{u_{i_{1}},u_{i_{2l+1}}\\}\in E(G^{u_{i}}_{j})$. Thus
according to our construction, $\\{u_{i_{1}},u_{k}\\}\in E(G^{u_{i}}_{j}),$
for all $i_{1}<k\leq i_{2l+1}$. Hence, for all $1\leq i\leq a-2$; $i\leq j\leq
a-1$, the minimal odd cycles of $G^{u_{i}}_{j}$ are cycles of length three.

######  Remark 4.1.

Let $C=\\{u_{i_{1}},u_{i_{2}},u_{i_{3}}\\}$ be an odd cycle in
$G^{u_{i}}_{j}$, where $1\leq i\leq a-3$; $i\leq j\leq a-1$ and $V(C)\subset
V(K_{a})$. Let $i_{1}<i_{2}<i_{3}$. Existence of edges
$\\{u_{i_{1}},u_{i_{2}}\\}$ and $\\{u_{i_{1}},u_{i_{3}}\\}$ indicates that $w$
is adjacent to vertices $u_{i_{2}}$ and $u_{i_{3}}$. And, for the graph
$G^{u_{a-2}}_{j}$, with $a-2\leq j\leq a-1$, the only odd cycle $C$ with
$V(C)\subset V(K_{a})$ is $C=\\{u_{a-2},u_{a-1},u_{a}\\}$ with $u_{a}$
adjacent to $w$. Since $K_{b+1}$ is not altered during the edge removal
process, all $v_{k}\in V(K_{b})$ is adjacent to $w$ in $G^{u_{i}}_{j}$ for all
$1\leq i\leq a-2$, $i\leq j\leq a-1$. As a result, at least one of the
vertices of any odd cycle in $G^{u_{i}}_{j}$, with $1\leq i\leq a-2$ and
$i\leq j\leq a-1$, will be adjacent to $w$.

######  Remark 4.2.

Suppose we have $\\{w,u_{k}\\}\in E(G^{u_{i}}_{j})$ for some $u_{k}\in
V(K_{a})$, where $1\leq i\leq a-2$, and $i\leq j\leq a-1$. Then,
$\\{u_{k},u_{k^{\prime}}\\}\in E(G^{u_{i}}_{j})$, for all $k+1\leq
k^{\prime}\leq a$. Let $C$ and $\overline{C}$ be two minimal odd cycles in
$G^{u_{i}}_{j}$ with $V(C)\cup V(\overline{C})\subset V(K_{a})$. Then by
Remark 4.1 and from the above observation, there exists at least one edge
$\\{u_{p},u_{q}\\}\in E(G^{u_{i}}_{j})$ such that $u_{p}\in V(C)$ and
$u_{q}\in V(\overline{C})$ or vice versa, where $1\leq i\leq a-2$, and $i\leq
j\leq a-1$.

######  Lemma 4.3.

Let $(C,C^{\prime})$ be exceptional in $G^{u_{i}}_{j}$, $1\leq i\leq a-2$ and
$i\leq j\leq a-1$. If $\\{w,v\\}\in E(G^{u_{i}}_{j})$, then for all $1\leq
i\leq a-2$, and $i\leq j\leq a-1$, we have

$\mathbb{E}_{C}\ +\ \mathbb{E}_{C^{\prime}}\ +\ \mathbf{e}_{w}\ +\
\mathbf{e}_{v}\in S_{G^{u_{i}}_{j}},$

where $\mathbf{e}_{w}$ and $\mathbf{e}_{v}$ are the canonical unit vectors of
$\mathbb{R}^{d}$ corresponding to vertices $w$ and $v$ respectively.

###### Proof.

We consider an exceptional pair $(C,C^{\prime})$ in $G^{u_{i}}_{j}$, where
$1\leq i\leq a-2$ and $i\leq j\leq a-1$. Since $(C,C^{\prime})$ is exceptional
in $G^{u_{i}}_{j}$, we have $V(C)\cap V(C^{\prime})=\emptyset$ and $w\notin
V(C)\cup V(C^{\prime})$, for all $1\leq i\leq a-2$, $i\leq j\leq a-1$. Without
loss of generality, let $C=\\{u_{i_{1}},u_{i_{2}},u_{i_{3}}\\}$ be a minimal
odd cycle with $V(C)\subset V(K_{a})$ and
$C^{\prime}=\\{v_{j_{1}},v_{j_{2}},v_{j_{3}}\\}$ be a minimal odd cycle with
$V(C^{\prime})\subset V(K_{b})$.

Let us assume that $v=u_{k}\in V(K_{a})$. The existence of the edge
$\\{w,u_{k}\\}$ in $G^{u_{i}}_{j}$ implies that $\\{u_{k},u_{k^{\prime}}\\}\in
E(G^{u_{i}}_{j})$, for all $k+1\leq k^{\prime}\leq a$. Hence, if $k<i_{l}$,
for some $1\leq l\leq 3,$ then we have $\\{u_{i_{l}},u_{k}\\}\in
E(G^{u_{i}}_{j}).$ By Remark 4.1, for any odd cycle in $G^{u_{i}}_{j}$, we
know that at least one of its vertices is adjacent to $w$, $\forall\ 1\leq
i\leq a-2$, $i\leq j\leq a-1$. Let $u_{i_{l}}$ be adjacent to $w$, for some
$1\leq l\leq 3$. Then, for $k>i_{l}$, we have $\\{u_{i_{l}},u_{k}\\}\in
E(G^{u_{i}}_{j}),$ $1\leq i\leq a-2$, $i\leq j\leq a-1$. Remark 4.1 also
indicates that for any $v_{j_{k}}\in V(C^{\prime})$, we have
$\\{w,v_{j_{k}}\\}\in E(G^{u_{i}}_{j})$, for all $1\leq i\leq a-2$ and $i\leq
j\leq a-1$. Suppose, we choose $u_{i_{3}}\neq u_{k}$. Then we can express

$\begin{array}[]{lcl}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{u_{k}}&=&\sum\limits_{l=1}^{3}\mathbf{e}_{u_{i_{l}}}+\sum\limits_{l=1}^{3}\mathbf{e}_{v_{j_{l}}}+\mathbf{e}_{w}+\mathbf{e}_{u_{k}}\\\
\\\
&=&\sum\limits_{l=1}^{2}\mathbf{e}_{u_{i_{l}}}+(\mathbf{e}_{u_{k}}+\mathbf{e}_{u_{i_{3}}})+\sum\limits_{l=1}^{2}\mathbf{e}_{v_{j_{l}}}+(\mathbf{e}_{v_{j_{3}}}+\mathbf{e}_{w}).\end{array}$

This can be written as,

$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{u_{k}}=\rho\big{(}\\{u_{i_{1}},u_{i_{2}}\\}\big{)}+\rho\big{(}\\{u_{k},u_{i_{3}}\\}\big{)}+\rho\big{(}\\{v_{j_{1}},v_{j_{2}}\\}\big{)}+\rho\big{(}\\{v_{j_{3}},w\\}\big{)}.$

Thus, the expression
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{u_{k}}$ can
be written as a linear combination of some $\rho(e),$ where $e\in
E(G^{u_{i}}_{j})$, $1\leq i\leq a-2$ and $i\leq j\leq a-1$.

Now, let us consider that $v\in V(K_{b})$. As per Remark 4.1, without loss of
generality, we assume that $u_{i_{3}}$ is adjacent to $w$. Due to the
completeness property of $K_{b}$, the vertex $v$ has to be adjacent to any
$v_{j_{l}}\in V(C^{\prime})$. Therefore we can express,
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{v}=\sum\limits_{l=1}^{2}\mathbf{e}_{u_{i_{l}}}+(\mathbf{e}_{w}+\mathbf{e}_{u_{i_{3}}})+\sum\limits_{l=1}^{2}\mathbf{e}_{v_{j_{l}}}+(\mathbf{e}_{v_{j_{3}}}+\mathbf{e}_{v}).$
Moreover, this can be expressed as,

$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{v}=\rho\big{(}\\{u_{i_{1}},u_{i_{2}}\\}\big{)}+\rho\big{(}\\{w,u_{i_{3}}\\}\big{)}+\rho\big{(}\\{v_{j_{1}},v_{j_{2}}\\}\big{)}+\rho\big{(}\\{v_{j_{3}},v\\}\big{)}.$

Thus, the expression
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{v}$ can be
written as a linear combination of some $\rho(e),$ where $e\in
E(G^{u_{i}}_{j})$, $1\leq i\leq a-2$ and $i\leq j\leq a-1$.

Therefore, for any $\\{w,v\\}\in E(G^{u_{i}}_{j})$, we have
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}\in
S_{G^{u_{i}}_{j}}$, where $1\leq i\leq a-2$ and $i\leq j\leq a-1$. ∎

For the graph $G^{u_{i}}_{j}$, where $1\leq i\leq a-2$, $i\leq j\leq a-1$ and
the set $A$ as defined in Section 3, we have the following lemma.

######  Lemma 4.4.

$\overline{S_{G^{u_{i}}_{j}}}\subset S_{G^{u_{i}}_{j}}\cup A$, for all $1\leq
i\leq a-2$ and $i\leq j\leq a-1$.

###### Proof.

Let $\alpha$ be an arbitrary element in $\overline{S_{G^{u_{i}}_{j}}}$, where
$1\leq i\leq a-2$, $i\leq j\leq a-1$. The normalization of the edge ring
$K[G^{u_{i}}_{j}]$ can be expressed as

$\overline{S_{G^{u_{i}}_{j}}}=S_{G^{u_{i}}_{j}}\ +\ \mathbb{Z}_{\geq
0}\big{\\{}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\colon(C,C^{\prime})\textrm{
is exceptional in }G^{u_{i}}_{j}\big{\\}},$

where $1\leq i\leq a-2$, and $i\leq j\leq a-1$. Therefore, any
$\alpha\in\overline{S_{G^{u_{i}}_{j}}}$ can be expressed as
$\alpha=\beta+\gamma$, where $\beta\in S_{G^{u_{i}}_{j}}$ and
$\gamma\in\mathbb{Z}_{\geq
0}\big{\\{}\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\colon(C,C^{\prime})\textrm{
is exceptional in }G^{u_{i}}_{j}\big{\\}},$ for all $1\leq i\leq a-2$ and
$i\leq j\leq a-1$. If $\gamma=0$, then $\alpha\in S_{G^{u_{i}}_{j}}$. So, let
us consider the non-trivial case where $\gamma\neq 0$. Let $\alpha_{k}$,
$\beta_{k}$ and $\gamma_{k}$ represent the $k^{\textrm{th}}$ coordinates of
$\alpha$, $\beta$ and $\gamma$ respectively.

For any two (possibly identical) exceptional pairs
$(C,C^{\prime}),(\overline{C},\overline{C}^{\prime})$, using Remark 4.2 and
from the completeness of $K_{b+1}$, we have
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbb{E}_{\overline{C}}+\mathbb{E}_{\overline{C}^{\prime}}\in
S_{G^{u_{i}}_{j}}$ for all $1\leq i\leq a-2$ and $i\leq j\leq a-1$. Therefore,
without loss of generality, for an exceptional pair $(C,C^{\prime})$ in
$G^{u_{i}}_{j}$, $\forall\ 1\leq i\leq a-2$, $i\leq j\leq a-1$, we may assume
that $\gamma=\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}$.

Case 1. Let $\alpha_{w}=0$.

We have $\gamma_{w}=0$ and $\alpha_{w}=0$. Therefore $\beta_{w}=0$, that is,
we are not considering any edge adjacent to the common vertex $w$. This
assures that, both $\sum\limits_{u\in V(K_{a})}\beta_{u}$ and
$\sum\limits_{v\in V(K_{b})}\beta_{v}$ have to be even. Hence, both
$\sum\limits_{u\in V(K_{a})}\alpha_{u}$ and $\sum\limits_{v\in
V(K_{b})}\alpha_{v}$ will be odd. Thus we have $\alpha\in A$.

Case 2. Let $\alpha_{w}>0$.

The condition $\alpha_{w}>0$ implies $\beta_{w}>0$. This indicates that there
must be at least one edge adjacent to $w$, say $\\{w,v\\}$. For any
exceptional pair $(C,C^{\prime})$ in $G^{u_{i}}_{j}$, by Lemma 4.3,
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{v}\in
S_{G^{u_{i}}_{j}},$ and thus $\alpha=\beta+\gamma\in S_{G^{u_{i}}_{j}}$, for
all $1\leq i\leq a-2$, $i\leq j\leq a-1$. ∎

Therefore, for all $1\leq i\leq a-2$, and $i\leq j\leq a-1$, we can observe
that,

$S_{G^{u_{i}}_{j}}\subset
S_{G^{u_{i}}_{j}}^{\prime}\subset\overline{S_{G^{u_{i}}_{j}}}\subset
S_{G^{u_{i}}_{j}}\cup A.$

######  Proposition 4.5.

The edge ring $K[G^{u_{i}}_{j}]$ of the graph $G^{u_{i}}_{j}$ is non-normal
and satisfies $(S_{2})$-condition, for all $1\leq i\leq a-2$ and $i\leq j\leq
a-1$.

###### Proof.

For any $1\leq k\leq b-2$, the pair
$(\\{u_{a-2},u_{a-1},u_{a}\\},\\{v_{k},v_{k+1},v_{k+2}\\})$ is always
exceptional in $G^{u_{i}}_{j}$, for all $1\leq i\leq a-2$ and $i\leq j\leq
a-1$. Hence, $K[G^{u_{i}}_{j}]$ is non-normal for all $1\leq i\leq a-2$, and
$i\leq j\leq a-1$.

Let us consider an element $\alpha\in\overline{S_{G_{j}^{u_{i}}}}\backslash
S_{G_{j}^{u_{i}}}$, where $1\leq i\leq a-2$, and $i\leq j\leq a-1$. By Lemma
4.4, we have $\alpha\in A$ and $\alpha_{w}=0$. We observe that, the common
vertex $w$ is regular in $G^{u_{i}}_{j}$, for all $1\leq i\leq a-2$, $i\leq
j\leq a-1$. Hence, corresponding to $w$, we have $S_{G^{u_{i}}_{j}}\cap
F_{w}:=\mathbb{Z}_{\geq 0}\mathcal{A}_{G^{u_{i}}_{j}\backslash w}$, for all
$1\leq i\leq a-2$, and $i\leq j\leq a-1$. For any $\beta\in
S_{G_{j}^{u_{i}}}\cap F_{w},$ let $\beta_{k}$ be the $k^{\textrm{th}}$
coordinate of $\beta$. We observe that $\beta_{w}=0$ and both
$\sum\limits_{i=1}^{a}\beta_{u_{i}}$, and $\sum\limits_{j=1}^{b}\beta_{v_{j}}$
are even. Therefore, for all $\beta\in S_{G_{j}^{u_{i}}}\cap F_{w}$, we have
$\alpha+\beta\in A$ and not in $S_{G_{j}^{u_{i}}}$, $\forall\ 1\leq i\leq
a-2$, and $i\leq j\leq a-1$. Thus, there exists no $\beta\in
S_{G_{j}^{u_{i}}}\cap F_{w}$, such that $\alpha+\beta\in S_{G_{j}^{u_{i}}}$,
and this implies that, $\alpha\notin S_{G_{j}^{u_{i}}}^{\prime}$, for all
$1\leq i\leq a-2$, $i\leq j\leq a-1$. As a result, we have
$(\overline{S_{G_{j}^{u_{i}}}}\backslash S_{G_{j}^{u_{i}}})\cap
S^{\prime}_{G_{j}^{u_{i}}}=\emptyset$ and $S_{G_{j}^{u_{i}}}^{\prime}\subset
S_{G_{j}^{u_{i}}}$, $\forall\ 1\leq i\leq a-2$ and $i\leq j\leq a-1$.
Therefore,

$S^{\prime}_{G^{u_{i}}_{j}}=S_{G^{u_{i}}_{j}},$

for all $1\leq i\leq a-2\textrm{ and }i\leq j\leq a-1.$ ∎

Now, let us continue a similar edge removal process on $K_{b+1}$ and remove
the maximum number of edges from $K_{b+1}$ resulting in the formation of the
graph $\widetilde{G}$, as per our requirement. Let $v_{0}\coloneqq w$ and
$\widetilde{G}^{v_{1}}_{0}:=G^{u_{a-2}}_{a-1}$. We construct a new subgraph of
$G_{a,b}$ through an edge removal process such that for each $1\leq i\leq
b-3$,

  * •

we remove the edge $\\{v_{0},v_{i}\\}$ from $\widetilde{G}^{v_{i}}_{0}$ to
obtain $\widetilde{G}^{v_{i}}_{i}$, and

  * •

remove the edge $\\{v_{i},v_{j}\\}$ from $\widetilde{G}^{v_{i}}_{j-1}$ to
obtain $\widetilde{G}^{v_{i}}_{j}$, $\forall\ i+1\leq j\leq b-1$.

Let us denote $\widetilde{G}^{v_{i}}_{0}:=\widetilde{G}^{v_{i-1}}_{b-1}$,
$\forall\ 2\leq i\leq b-2$. By construction, we observe that

$E(\widetilde{G}^{v_{i}}_{0})=E(\widetilde{G}^{v_{1}}_{0})\backslash\bigcup\limits_{p=1}^{i-1}\bigg{\\{}\\{v_{p},v_{q}\\}\colon
q\neq p,0\leq q\leq b-1\bigg{\\}},\hskip 5.69046pt\forall\ 2\leq i\leq b-2.$

For $i=b-2$, the construction of the subgraph $\widetilde{G}^{v_{i}}_{j}$,
$b-2\leq j\leq b-1$ is as follows:

  * •

the subgraph $\widetilde{G}^{v_{b-2}}_{b-2}$ is constructed by removing the
edge $\\{v_{0},v_{b-2}\\}$ from $\widetilde{G}^{v_{b-2}}_{0}$, and

  * •

the edge $\\{v_{0},v_{b-1}\\}$ is removed from
$\widetilde{G}^{v_{b-2}}_{b-2}$, to obtain the subgraph
$\widetilde{G}^{v_{b-2}}_{b-1}$.

As per construction, $V(\widetilde{G}^{v_{i}}_{j})=V(G_{a,b})$, $\forall\
1\leq i\leq b-2,\ i\leq j\leq b-1$ and by the end of this removal procedure,
we construct the graph depicted in Figure 4.

Figure 4. The graph $\widetilde{G}$

Since we follow a similar edge removal process as in the case of
$G^{u_{i}}_{j}$, where $1\leq i\leq a-2\textrm{ and }i\leq j\leq a-1,$ we
observe that the minimal odd cycles of $\widetilde{G}^{v_{i}}_{j}$ are also
odd cycles of length three, for all $1\leq i\leq b-2\textrm{ and }i\leq j\leq
b-1$. By construction, $\forall\ 1\leq i\leq b-2;\ i\leq j\leq b-1$, the only
odd cycle $C$ in $\widetilde{G}^{v_{i}}_{j}$ with $V(C)\subset V(K_{a})$ is
$C=\\{u_{a-2},u_{a-1},u_{a}\\}$, with $u_{a}$ adjacent to $w$. For any odd
cycle $\\{v_{j_{1}},v_{j_{2}},v_{j_{3}}\\}$ in $\widetilde{G}^{v_{i}}_{j}$,
with $j_{1}<j_{2}<j_{3}$, the existence of edge $\\{v_{j_{1}},v_{j_{3}}\\}$
indicates that at least $v_{j_{3}}$ is adjacent to $w$, for all $1\leq i\leq
b-2,\ i\leq j\leq b-1$.

######  Lemma 4.6.

Let us consider an exceptional pair $(C,C^{\prime})$ in
$\widetilde{G}^{v_{i}}_{j}$, where $1\leq i\leq b-2$ and $i\leq j\leq b-1$. If
$\\{w,v\\}\in E(\widetilde{G}^{v_{i}}_{j})$, then for all $1\leq i\leq b-2$
and $i\leq j\leq b-1$, we have

$\mathbb{E}_{C}\ +\ \mathbb{E}_{C^{\prime}}\ +\ \mathbf{e}_{w}\ +\
\mathbf{e}_{v}\in S_{\widetilde{G}^{v_{i}}_{j}}.$

###### Proof.

We consider an exceptional pair $(C,C^{\prime})$ in
$\widetilde{G}^{v_{i}}_{j}$, where $1\leq i\leq b-2$ and $i\leq j\leq b-1$.
Without loss of generality, let $C=\\{u_{a-2},u_{a-1},u_{a}\\}$ be the minimal
odd cycle with $V(C)\subset V(K_{a})$ and
$C^{\prime}=\\{v_{j_{1}},v_{j_{2}},v_{j_{3}}\\}$ be a minimal odd cycle with
$V(C^{\prime})\subset V(K_{b})$.

Let $v\in V(K_{a})$. Then by our construction, we have $v=u_{a}$ and at least
one of the vertices in $C^{\prime}$ is adjacent to $w$. Thus, the expression
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{w}+\mathbf{e}_{u_{a}}$ can
be written as a linear combination of some $\rho(e),$ where $e\in
E(\widetilde{G}^{v_{i}}_{j})$, $1\leq i\leq b-2$ and $i\leq j\leq b-1$.

Let us consider $v=v_{k}\in V(K_{b})$. Since we follow a similar edge removal
process, the proof is similar to that of Lemma 4.3. Therefore, for any
$\\{w,v\\}\in E(\widetilde{G}^{v_{i}}_{j})$, we have
$\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}+\mathbf{e}_{v}+\mathbf{e}_{w}\in
S_{\widetilde{G}^{v_{i}}_{j}}$, for all $1\leq i\leq b-2$ and $i\leq j\leq
b-1$. ∎

For the set $A$ as defined in Section 3 and the graph
$\widetilde{G}^{v_{i}}_{j}$, where $1\leq i\leq b-2$, and $i\leq j\leq b-1$,
we have the following lemma.

######  Lemma 4.7.

$\overline{S_{\widetilde{G}^{v_{i}}_{j}}}\subset
S_{\widetilde{G}^{v_{i}}_{j}}\cup A$, for all $1\leq i\leq b-2$ and $i\leq
j\leq b-1$.

###### Proof.

Let $\alpha$ be an arbitrary element in
$\overline{S_{\widetilde{G}^{v_{i}}_{j}}}$, where $1\leq i\leq b-2$, and
$i\leq j\leq b-1$. Due to the similar edge removal process, the proof is
similar to that of Lemma 4.4. By similar arguments in the proof of Lemma 4.4,
we can prove that $\alpha\in A$, if $\alpha_{w}=0$. If $\alpha_{w}>0$, then
there exists at least one edge adjacent to $w$ and by Lemma 4.6, we have
$\alpha\in S_{\widetilde{G}^{v_{i}}_{j}}$, $\forall\ 1\leq i\leq b-2,$ and
$i\leq j\leq b-1$. ∎

From the above observations, we have $S_{\widetilde{G}^{v_{i}}_{j}}\subset
S_{\widetilde{G}^{v_{i}}_{j}}^{\prime}\subset\overline{S_{\widetilde{G}^{v_{i}}_{j}}}\subset
S_{\widetilde{G}^{v_{i}}_{j}}\cup A,$ for all $1\leq i\leq b-2$, and $i\leq
j\leq b-1$.

######  Proposition 4.8.

The edge ring $K[\widetilde{G}^{v_{i}}_{j}]$ of the graph
$\widetilde{G}^{v_{i}}_{j}$ is non-normal and satisfies $(S_{2})$-condition,
for all $1\leq i\leq b-2$ and $i\leq j\leq b-1$.

###### Proof.

As per our construction, the pair
$(\\{u_{a-2},u_{a-1},u_{a}\\},\\{v_{b-2},v_{b-1},v_{b}\\})$ is contained in
every $\widetilde{G}^{v_{i}}_{j}$ and is exceptional, for all $1\leq i\leq
b-2$, and $i\leq j\leq b-1$. Hence, $K[\widetilde{G}^{v_{i}}_{j}]$ is non-
normal for all $1\leq i\leq b-2$, $i\leq j\leq b-1$.

Let us consider an element $\alpha\in A$ such that
$\alpha\in\overline{S_{\widetilde{G}_{j}^{v_{i}}}}\backslash
S_{\widetilde{G}_{j}^{v_{i}}}$, where $1\leq i\leq b-2$ and $i\leq j\leq b-1$.
The common vertex $w$ is regular in $\widetilde{G}^{v_{i}}_{j}$, and
corresponding to this regular vertex, we have
$S_{\widetilde{G}_{j}^{v_{i}}}\cap F_{w}:=\mathbb{Z}_{\geq
0}\mathcal{A}_{\widetilde{G}_{j}^{v_{i}}\backslash w}$, for all $1\leq i\leq
b-2$, and $i\leq j\leq b-1$. By a similar proof as that of Proposition 4.5, we
can demonstrate that there exists no $\beta\in
S_{\widetilde{G}_{j}^{v_{i}}}\cap F_{w}$, such that $\alpha+\beta\in
S_{\widetilde{G}_{j}^{v_{i}}}$, and therefore
$S^{\prime}_{\widetilde{G}_{j}^{v_{i}}}=S_{\widetilde{G}_{j}^{v_{i}}}$, for
all $1\leq i\leq b-2,\textrm{ and }i\leq j\leq b-1.$ ∎

Let the graph $\widetilde{G}^{v_{b-2}}_{b-1}:=\widetilde{G}$ (Figure 4). We
observe that, $\widetilde{G}$ is a subgraph of $G_{a,b}$ with
$|V(\widetilde{G})|=|V(G_{a,b})|$ and $|E(\widetilde{G})|=a+b+2=d+1$. By
Proposition 4.8, we know that the edge ring $K[\widetilde{G}]$ is non-normal
and also satisfies $(S_{2})$-condition. Therefore, we observe that
$\widetilde{G}$ is the graph on $d$ vertices with the least number of edges,
$d+1$ edges, such that the edge ring is non-normal and meets
$(S_{2})$-condition. This completes the proof of a part of the statement of
Theorem 1.1.

##  5\. Addition of edges to $G_{a,b}$ violates non-normality or
$(S_{2})$-condition

In this section, we prove that any addition of (one or more) new edges to
$G_{a,b}$ either breaks the non-normality of the edge ring or violates the
$(S_{2})$-condition.

Let us construct a new graph $G^{\prime}$ on the vertex set
$V(G^{\prime})=V(G_{a,b})$, by introducing one or more edges to $G_{a,b}$.
Since $K_{a+1}$ and $K_{b+1}$ are complete graphs, each of the new edges will
be of the form $\\{u_{i},v_{j}\\}$, for some $1\leq i\leq a$ and $1\leq j\leq
b$. For instance, addition of a single edge $\\{u_{2},v_{3}\\}$ to the graph
$G_{a,b}$ is illustrated in Figure 5.

Figure 5. The graph $G^{\prime}$ obtained by adding edge $\\{u_{2},v_{3}\\}$
to $G_{a,b}$

We can observe that for any $G^{\prime}$, all of its vertices are regular and
the fundamental sets are: $\\{i\\},\ \forall\ i\in V(G^{\prime})\textrm{ and
}\\{i,j\\},\ \forall\ \\{i,j\\}\notin E(G^{\prime}).$

######  Proposition 5.1.

Let $G^{\prime}$ be a graph on the vertex set $V(G^{\prime})=V(G_{a,b})$, such
that $G^{\prime}$ is constructed by adding one or more new edges to $G_{a,b}$.
Then for any $G^{\prime}$, the edge ring $K[G^{\prime}]$ is either normal or
it does not satisfy $(S_{2})$-condition.

###### Proof.

Suppose we construct a graph $G^{\prime}$ by adding at least minimal number of
edges $\\{u_{i},v_{j}\\}$, where $1\leq i\leq a$ and $1\leq j\leq b$, such
that we connect all the exceptional pairs of $G_{a,b}$. Thus, $G^{\prime}$
satisfies the odd-cycle condition and therefore the corresponding edge ring
$K[G^{\prime}]$ is normal.

Now, let us consider the case where we construct a graph $G^{\prime}$ such
that $K[G^{\prime}]$ is non-normal. Then, we prove that for any such
$G^{\prime}$, the edge ring $K[G^{\prime}]$ will not satisfy
$(S_{2})$-condition.

Suppose, we construct $G^{\prime}$ by adding new edges to $G_{a,b}$ such that
$G^{\prime}$ consists of at least one pair of $3$-cycles,
$(\\{u_{i_{1}},u_{i_{2}},u_{i_{3}}\\},\\{v_{j_{1}},v_{j_{2}},v_{j_{3}}\\})$
with either $i_{k}\neq i$ or $j_{k}\neq j$ for any $1\leq k\leq 3$. This pair
will be exceptional in $G^{\prime}$ and thus, the corresponding edge ring
$K[G^{\prime}]$ is non-normal.

Now, we consider any exceptional pair $(C,C^{\prime})$ of the graph
$G^{\prime}$. For any regular vertex $v\in V(G^{\prime})\backslash[V(C)\cup
V(C^{\prime})]$ such that $v\neq w$, we observe that $G^{\prime}\backslash v$
is a connected graph with the common vertex $w$. Let us consider the regular
vertex $w\in V(G^{\prime})\backslash[V(C)\cup V(C^{\prime})]$. As per our
construction, the graph $G^{\prime}$ contains edges of the type
$\\{u_{i},v_{j}\\}$, for some $1\leq i\leq a$ and $1\leq j\leq b$. The
existence of such edges in $G^{\prime}$ ensures the connectedness of the graph
$G^{\prime}\backslash w$.

Thus for any regular vertex $v\in V(G)\backslash[V(C)\cup V(C^{\prime})]$, we
observe that the graph $G^{\prime}\backslash v$ is always a connected graph.
Hence both $C$ and $C^{\prime}$ belong to the same connected components of
$G^{\prime}\backslash v$.

For the graph $G^{\prime}$, any $\\{i\\}$ for $i\in V(G^{\prime})$ is a
fundamental set (more specifically, the minimal fundamental set). Since both
$K_{a+1}$ and $K_{b+1}$ are complete graphs, any $u_{i}\in V(K_{a+1})$ or
$v_{j}\in V(K_{b+1})$ is adjacent to all the other vertices of $K_{a+1}$ and
$K_{b+1}$ respectively. Hence for all $i\in V(G^{\prime})$,

$\Big{[}V(C)\cup V(C^{\prime})\Big{]}\cap\Big{[}\\{i\\}\cup
N\big{(}G;\\{i\\}\big{)}\Big{]}\neq\emptyset.$

Therefore, by Theorem 2.4, $\mathbb{E}_{C}+\mathbb{E}_{C^{\prime}}\in
S_{G^{\prime}}^{\prime}$. In particular, $S_{G^{\prime}}\neq
S_{G^{\prime}}^{\prime}$. Hence, the edge ring $K[G^{\prime}]$ does not
satisfy $(S_{2})$-condition. ∎

##  6\. Conclusions

A simple connected finite graph on $d$ vertices with a non-normal edge ring
must contain at least one exceptional pair of odd cycles. Thus the minimal
graph on $d$ vertices satisfying the above condition must be a graph
consisting of two minimal odd cycles and a path (of at least length $2$)
connecting the two cycles. This minimal graph will have exactly $d+1$ number
of edges. In Section 4, we proved the existence of such a minimal graph
$\widetilde{G}$, which satisfies the main theorem (Theorem 1.1).

We have examined the graph $G_{a,b}$ in detail. From Section 5, we can
conclude that any addition of (one or more) new edges to $G_{a,b}$ either
breaks the non-normality of the edge ring or violates $(S_{2})$-condition.
Thus, we may conclude that $G_{a,b}$ is the graph on $d$ vertices with the
maximum number of edges such that, the corresponding edge ring is non-normal
and satisfies $(S_{2})$-condition. For the graph $G_{a,b}$, we have
$|V(G_{a,b})|=d=a+b+1$ and $3\leq a\leq b$. Therefore, in order to maximize
the number of edges in $G_{a,b}$, we have to consider $a=3$ and $b=d-4$. That
is,

$\big{\lvert}E(G_{a,b})\big{\rvert}\leq\binom{4}{2}+\binom{d-3}{2}=\frac{d^{2}-7d+24}{2}.$

This provides us very strong supporting evidence that $\frac{d^{2}-7d+24}{2}$
could be the maximal number of edges possible for a graph on $d$ vertices such
that, its edge ring is non-normal and satisfies $(S_{2})$-condition.

###### Proof of Theorem 1.1.

Let us consider the graph $G_{3,b}$ on $d$ vertices such that $d\geq 7$. We
have $|E(G_{3,b})|=\frac{d^{2}-7d+24}{2}$ and by Proposition 3.3, the edge
ring $K[G_{3,b}]$ is non-normal and satisfies $(S_{2})$-condition.

Through the edge removal processes discussed in Section 4, by eliminating one
edge from the graph $G_{3,b}$ per step, we can gradually build up a graph on
$d$ vertices with $d+1$ edges such that, its edge ring is non-normal and
satisfies $(S_{2})$-condition. Proposition 4.5 and Proposition 4.8 guarantee
that the edge ring of each of the graphs obtained after each removal step is
always non-normal and will satisfy $(S_{2})$-condition.

Therefore we prove that for any given integers $d$ and $n$ such that, $d\geq
7$ and $d+1\leq n\leq\frac{d^{2}-7d+24}{2}$, we can always construct a finite
simple connected graph on $d$ vertices and having $n$ edges such that, the
edge ring of the graph is non-normal and satisfies $(S_{2})$-condition. ∎

## References

  * [1] W. Bruns, J. Herzog, Cohen-Macaulay rings, Revised edition, Cambridge University Press, (1998).
  * [2] S. Goto, K. Watanabe, On Graded rings II ($\mathbb{Z}^{n}$-graded rings), Tokyo J. Math. 1, (1978), 237-261.
  * [3] T. Hibi, L. Katthän, Edge rings satisfying Serre’s condition $(R_{1})$, Proc. Amer. Math. Soc. 142, (2014), 2537-2541.
  * [4] A. Higashitani, K. Kimura, A necessary condition for an edge ring to satisfy Serre’s condition $(S_{2})$, Advanced Studies in Pure Mathematics 77, (2018).
  * [5] M. Hochster, Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes, Ann. of Math. (2) 96, (1972), 318-337.
  * [6] H. Ohsugi, T. Hibi, Normal polytopes arising from finite graphs, J. Algebra 218, (1999), 509-527.
  * [7] U. Schäfer, P. Schenzel, Dualizing complexes of affine semigroup rings, Trans. Amer. Math. Soc. 322, no. 2 (1990), 561-582.
  * [8] A. Simis, W. V. Vasconcelos, R. H. Villarreal, The integral closure of subrings associated to graphs, J. Algebra 199 (1998), 281-289.
  * [9] N. V. Trung, L. T. Hoa, Affine semigroups and Cohen-Macaulay rings generated by monomials, Trans. Amer. Math. Soc. 298, (1986), 145-167.


# Increasing Shape Bias in ImageNet-Trained Networks Using Transfer Learning
and Domain-Adversarial Methods

Francis Brochu

###### Abstract

Convolutional Neural Networks (CNNs) have become the state-of-the-art method
to learn from image data. However, recent research shows that they may include
a texture and colour bias in their representation, contrary to the intuition
that they learn the shapes of the image content and to human biological
learning. Thus, recent works have attempted to increase the shape bias in CNNs
in order to train more robust and accurate networks on tasks. One such
approach uses style-transfer in order to remove texture clues from the data.
This work reproduces this methodology on four image classification datasets,
as well as extends the method to use domain-adversarial training in order to
further increase the shape bias in the learned representation. The results
show the proposed method increases the robustness and shape bias of the CNNs,
while it does not provide a gain in accuracy.

Machine Learning, Deep Learning, Computer Vision

##  1 Introduction

Convolutional Neural Networks (CNNs) have become, in the last few years, the
state-of-the-art method to classify, segment or otherwise learn from the
content of images. (Rawat & Wang, 2017). The rise of CNNs goes back to the
ImageNet competition of 2012 (Krizhevsky et al., 2012). They have then
maintained their domination of that competition in the following years over
other types of methods (Szegedy et al., 2015) (He et al., 2016). A common
explanation for the workings of a CNN is that the successive layers of
convolutions and pooling learn to represent the edges and shapes within the
images, and assemble these representations into more complicated shapes that
mirror the problems (Kriegeskorte, 2015).

However, in recent years, some results have come to challenge this assumption.
Some articles posit that CNNs can still classify images where any object shape
is absent, and where texture information is still present (Gatys et al., 2017)
(Brendel & Bethge, 2019). Moreover, many architectures have difficulty with
sketches, where shape information is clearly present and there are no texture
clues (Ballester & Araujo, 2016).

While many other results also exist to support that CNNs do indeed learn shape
information, there is a question to be raised as to whether CNNs learn a
mixture of the texture information and shape information (Ritter et al.,
2017). It is known that humans learn mainly by shape information (Ritter et
al., 2017). Thus, (Geirhos et al., 2018) explores this problem by comparing
human experimentation and CNNs with images with missing or changed texture
clues conflicting with shape information, as shown in Figure 1. These results
show that CNNs pretrained on ImageNet have learned from texture and colour
information. A workflow to increase the shape-bias of CNNs on ImageNet is then
presented, using mainly style-transfer (Huang & Belongie, 2017). The article
concludes that this workflow increases both the robustness and accuracy of
CNNs.

Figure 1: Example of texture and shape clues conflict (Geirhos et al., 2018)

##  2 Material and Methods

The following section will introduce and describe the different datasets used
for the experiments. The network architectures used will also be described.
Then, the methodology used to reproduce (Geirhos et al., 2018) will be
described. Finally, the domain-adversarial training of neural networks will be
detailed.

###  2.1 Datasets

Four image datasets were chosen to conduct the experiments. For each of these
datasets, there is an associated classification task. Thus, the basic same
architectures can be applied to each dataset, with only the number of classes
varying between them. Each classification task intuitively varies in
difficulty. Let us now consider each dataset in turn, from the easiest to
hardest tasks.

The first is the Dice dataset, taken from Kaggle Datasets (Dice, ). The
dataset is composed of 16 000 images of polyhedral dice. There are thus 6
classes in this dataset: those of d4’s, d6’s, d8’s, d10’s, d12’s and d20’s,
where the number describes the number of faces on the die. The dataset itself
is relatively simple, as it was acquired in very controlled circumstances. The
dataset was generated by rotating video cameras around the dice on a table, at
varying angles and in front of 6 different backgrounds (white, coloured and
wood-textured). Most images were then cropped to $480\times 480$ pixels, and
any image where the die is partially or completely out of crop were removed.
Some images of d6’s and d20’s are $1024\times 1024$, as they were from an
earlier version of the dataset.

The second dataset was the Dogs versus Cats (DvC) dataset, taken from the
Kaggle competition (DvC, ). This dataset is formed of 25 000 labelled images
of cats and dogs. The classification task is thus binary in this case,
predicting whether the image contains a dog or a cat. Most images in this
dataset were of a size greater than $224\times 224$, but some were shorter
along either axis.

These first two tasks are intuitively relatively easy. The Dice dataset is a
relatively artificial dataset, as even if its images are real images, they are
generated in order to form a dataset and are without noise. Each image is
correctly classified, there are no partially cropped or missing dice, and each
image contains a single die. In addition, it is an easy task using only shape
and a human would have a perfect or almost perfect accuracy on the task. The
second task is formed of more real-world images, but it is still a relatively
simple task which would be easy for a person. Also, we can easily imagine that
shape is important, and perhaps all that is necessary, in order to spot
whether an animal is a dog or cat. Still, some images contain multiple animals
(of the same type), or a human in addition to the animals, and a wide variety
of backgrounds.

The third dataset is the Dog Breed Identification (DBI) playground competition
from Kaggle (DBI, ). This dataset is formed of 10 223 images of 120 different
breeds of dogs. The classification task for this dataset is thus to predict
which of the 120 classes the image belongs to. With the relatively low number
of images (the lowest of the datasets), and the high number of classes, this
classification task is much more difficult than the previous two. Moreover,
some of the dog breeds included in the classes are difficult to predict
without error, even for humans. For example, two of the classes are miniature
schnauzers and standard schnauzers, which look practically identical, except
for size. Thus, a lower accuracy is expected on this task. Another measure
than a simple accuracy will be calculated on this dataset for the results.

The final dataset used is the Food101 dataset, found on Kaggle Datasets (Food,
101). This dataset is formed of 101 types of food, with 1000 images per class.
Thus, the total dataset is composed of 101 000 images. As with the DBI
dataset, another measure than accuracy will be used for the predictions on
this dataset, due to the number of classes. Note than multiple classes in this
dataset are close and hard to classify, as there are, for example, 5 different
types of soup in the dataset.

####  2.1.1 Splitting the datasets

Each dataset received the same treatment in order to be split into training,
validation and test sets. First, if the Kaggle dataset was already split into
training and validation sets, they were merged back into a single dataset.
Then, 20% of the images in each class were randomly selected to form the test
set. Afterwards, a further 20% of the remaining samples were randomly selected
to form the validation set. The validation set is thus 16% of the total number
of images per class. The remaining images (64% per class) form the training
set.

###  2.2 Model Architectures

Two model architectures were chosen for the experiments. The first is the
ResNet 34-layer (ResNet-34) architecture (He et al., 2016). This model
contains 34 layers, from a $7\times 7$ convolution layer and max pooling at
the base of the network, and using blocks of $3\times 3$ convolutions layers,
with residual links every 2 layers. The number of channels increase as the
layers near the end of the network. Finally, the classification layers are
formed by an average pooling and a fully connected layer. The architecture
reports a 8.58% Top-5 error on ImageNet. The computational demand per image is
of 3.6 GFLOPs for this network.

The second chosen architecture is the SqueezeNet (1.1) architecture (Iandola
et al., 2016). This model reports AlexNet-level accuracy on the ImageNet
dataset, at 19.38% Top-5 error. However, this architecture is designed to
contain much less parameters, and thus can be trained and can predict much
faster than AlexNet. The article reports SqueezeNet 1.0 as 512x smaller than
AlexNet. SqueezeNet 1.1 reports the same accuracy as SqueezeNet 1.0, but with
a further 2.4 times less calculations, for a total of 0.72 GFLOPs per image.

For the experiments, the pretrained networks were implemented and executed in
PyTorch (Paszke et al., 2017). The final pretrained fully connected layer of
ResNet-34 was replaced by a randomly initialized fully connected layer in
order to adapt it to the number of classes in the given dataset (2, 6, 101 or
120). This random initialization was the default PyTorch initialization. In
the case of SqueezeNet 1.1, the number of Global Average Pools was changed
from 1000 (for ImageNet) to the number of classes in the dataset. These two
architectures were chosen for their relatively small sizes and fast
computations.

###  2.3 Applying Geirhos’ methodology to transfer learning

Firstly, let us consider the reproduction of the results in (Geirhos et al.,
2018). Each dataset will be style-transferred using the same AdaIN
architecture (Huang & Belongie, 2017) and dataset as indicated in the article.
Moreover, this can be easily done as the author have published a git
repository containing all necessary code in order to apply this style transfer
methodology (Geirhos, ). Note that the images generated by this method are
already cropped and resized to $224\times 224$, as the AdaIN architecture uses
a VGG model as an encoder for the images.

Thus, each of the four datasets (Dice, DvC, DBI and Food101) were style-
transferred using this code, and the Paint-by-numbers Kaggle competition
dataset, as described by Geirhos et al.. We thus obtain two versions of the
datasets. The first is the original dataset, which be henceforth be referenced
as the base dataset. The second is the style-transferred dataset, which will
be reffered as the stylized dataset. The combined dataset formed by the union
of the base and stylized dataset is known as the mixed dataset.

Figure 2: Some sample images from the 4 datasets, and their style-transferred
equivalents.

The figure 2 shows some examples from the chosen datasets of base images and
their stylized counterparts. We can see that multiple images are still easy to
recognize and classify, but others will undergo more radical transformations
and may end up being much harder to predict or classify. The second image from
the left in the figure shows the latter case.

####  2.3.1 Training the models

The code used to train the models is available on Github. Each model, for each
experiment type (base, stylized and mixed) was trained in a similar manner.

First, the images were loaded in batches of 64, randomly shuffled for each
epoch. After some early experimentation (results not shown), the data
augmentation was fixed for each dataset. The details of that data augmentation
is shown in the next subsection.

As stated before, the models were implemented in PyTorch, and their pretrained
weights on ImageNet were set using torchvision (except the classification
layer). Since the classification layer was not pretrained, it could have a
specific training rate specified, different that the rest of the dataset. All
experiments were conducted using the Adam optimizer implemented by PyTorch
(Kingma & Ba, 2014). Some combinations of learning rates (classification
learning rate, general learning rate) were tested initially on each dataset,
for each experiment. When the optimal result (on the validation set) was one
of the boundaries of the search space, the search space was expanded by an
order of magnitude. If not, some combinations between the lowest ones observed
were tested. Those default combinations were $(10^{-3},10^{-3})$,
$(10^{-3},10^{-4})$ and $(10^{-4},10^{-4})$. Generally, the
$(10^{-3},10^{-4})$ combination was the best one, as observed on the
validation set.

Additionally, a Multi-Step Learning Rate scheduler was used. The milestones
for the scheduler were added manually, by observing the training losses and
accuracies. The step scheduler was tested with a gamma of $0.2$ and $0.5$.
Note that most models were trained with a gamma of $0.5$ and multiple steps,
as it seemed to yield lower error rates.

Another parameter that was explored was the weight decay (or L2
regularization). Different values were tested between $10^{-3}$ and $10^{-5}$,
with the search space being extended if the optimal parameter value was found
to be at either edge of the space. Most experiments (base, style and mixed)
tended to adopt the same or similar learning rates on the same dataset.

Finally, early stopping was added to the training. This ended the training and
saved the best model observed (on the validation set) if not model performed
better for a number of epochs equal to a specified patience. Depending on the
experiment and dataset, this patience varied mostly within the 20 to 30 range,
with some experiments going as far as 40 or 50 epochs.

####  2.3.2 Data augmentation

Firstly, let us consider the data augmentation on images from the base
datasets. Every image had a 50% chance of being flipped horizontally, in every
dataset. Then, a random choice was introduced in order to obtain a $224\times
224$ pixel image. In all cases, an image could simply be resized to $224\times
224$. Alternatively, a random crop of $224\times 224$ could be applied, with
zero-padding added if necessary. The image could also be treated through a a
random resized crop (as defined by the torchvision library). This random
resized crop was to crop to $224\times 224$ pixels, and would choose a random
proportion of the image. The precise proportion is variable by dataset. In the
DBI dataset, the minimal proportion to be kept was 50%, and the maximal 100%.
In the other datasets, the minimal proportion was of 33%, and the maximum
100%.

The Dice dataset was the only dataset where no image was smaller than
$224\times 224$ pixels. Thus, an additional choice was possible in the data
augmentation. The image could undergo a random rotation of up to $\pm
45^{\circ}$, followed by a center crop of size $224\times 224$.

As the stylized datasets were already cropped to $224\times 224$ pixels by the
style-transfer network, they underwent a reduced data augmentation. The
stylized dataset could then simply be left at their normal size, or undergo a
random resized crop of between 50% and 100% of the image.

Finally, before image resizing or cropping, all the images in the Dice and DvC
datasets received a random color jitter, of up to 25% of brightness, hue,
saturation and contrast. This color jitter was applied in both the base and
stylized datasets.

For the mixed experiments, the data augmentation of the base images is the
same as the base dataset, and that of the stylized images the same as the
stylized dataset.

###  2.4 Domain-Adversarial Training of Networks

A further method to increase shape-bias in the learned representation can be
achieved using _domain-adversarial_ training (Ganin et al., 2016). This type
of neural network architecture and training aims to learn a representation
that can classify the classes within the dataset, while also learning not to
distinguish two _domains_. In the case of the original Domain-Adversarial
Neural Network (DANN) article, this took the form of transfer learning and
source and target domains. The network trained the classification head of the
network on the source domain, while it also trained a domain-adversarial head
using labelled source and target domains. The final model was then used to
predict on the target domain.

Figure 3: A visual representation of the DANN architecture (Ganin et al.,
2016)

The domain-adversarial classifier is the noteworthy part of a DANN
architecture, as shown in Figure 3. It is characterized by two specific
elements. First, a $\lambda$ regularizer is applied to the domain-adversarial
head. This element is present to prevent the head from dominating the training
of the network and completely preventing the classification head from
learning. Secondly, it provides some measure of control over the effect of
this domain classifier over the total representation. While a high $\lambda$
will learn a representation that will not distinguish the domains, it may not
be the best classifier for the class labels. In the reverse case, the domain
classifier will not affect the total representation much, even if it would be
helpful. Thus, the $\lambda$ parameter is an additional hyper-parameter to
tune for the algorithm.

The second element is the _gradient reversal layer_. This layer does not
affect the forward propagation through the network, but will reverse (or
multiply by $-1$) the gradient that comes back through it. This is how the
DANN architecture learns a representation that does not differentiate between
domains, as the gradient goes in a direction where it does not reliably
discern from which domain the examples come.

This general methodology can be applied to the current datasets, with minor
changes. First, instead of source and target domains we can consider the base
domain and the stylized domain. The style-transfer used to create the stylized
domain from the base domain will conserve shape in the images, while changing
or removing colour and texture clues. Thus, a representation that cannot
distinguish between the two domains should be reliant on shape more than other
types of clues. A further change applied to the DANN architecture was that all
samples were used for the label predictors and for the domain classifier.
Thus, the experiments corresponded to the mixed experiments described above,
but with the added element of the DANN domain classifier.

For all experimentations with DANN, the data augmentation was kept for the
datasets as with the mixed experiments. Moreover, the $\lambda$ parameter was
tested in the range of $1^{-3}$ to $1^{-5}$, with the search space being
expanded if the best results on the validation set were obtained on a boundary
value.

##  3 Results and Discussion

###  3.1 Training on Base Datasets

Let us first consider the baseline case, where the models are trained on the
base datasets. These will form our baseline, comparing the robustness and
accuracy of enhanced training methods.

Dataset | Model | Base Accuracy | Stylized Accuracy
---|---|---|---
Dice | ResNet | 99.94% | 50.65%
Dice | SNet | 99.94% | 40.88%
DvC | ResNet | 99.15% | 87.42%
DvC | SNet | 97.73% | 81.03%
DBI | ResNet | 94.58% | 34.52%
DBI | SNet | 84.37% | 22.07%
Food101 | ResNet | 92.90% | 18.16%
Food101 | SNet | 90.09% | 17.31%
Table 1: Baseline results of the models on the datasets. The reported accuracy
corresponds to the Top-5 Accuracy in the case of the DBI and Food101 datasets.
SNet denotes the SqueezeNet model.

Table 1 shows the performance of each model trained on the base data and
tested on the test sets. We can observe high accuracies in all datasets, with
accuracies over 90% on the base test set. However, we can clearly remark the
texture bias, as the accuracies are generally much lower on the stylized test
sets. While the models trained on the DvC dataset keep accuracies of over 80%
on their stylized test sets, the Dice dataset drops below 50% accuracy (on 6
classes).

The DBI and Food101 datasets have their accuracies drop below 35%, even 20% in
the case of Food101. While each of the stylized accuracies are markedly better
than random guessing, they are far below the base accuracy and show that the
models are not adapted to predicting on stylized images. Both the ResNet
architecture and the SqueezeNet architecture show the same trends on the data,
with the ResNet models having a higher accuracy overall.

###  3.2 Training on Stylized Datasets

Dataset | Model | Base Accuracy | Stylized Accuracy
---|---|---|---
Dice | ResNet | 99.76% | 99.49%
Dice | SNet | 96.77% | 97.84%
DvC | ResNet | 97.77% | 96.00%
DvC | SNet | 95.45% | 93.20%
DBI | ResNet | 85.54% | 74.36%
DBI | SNet | 61.99% | 47.35%
Food101 | ResNet | 77.00% | 71.10%
Food101 | SNet | 71.68% | 63.69%
Table 2: Results of the models trained on the stylized datasets. The reported
accuracy corresponds to the Top-5 Accuracy in the case of the DBI and Food101
datasets. SNet denotes the SqueezeNet model.

Table 2 shows the results on the models trained on the stylized datasets.
Here, we see an overall decrease in base test set accuracy. This is expected
however, since the models were not trained on the base images. The accuracy on
the stylized test sets are however largely increased. In the case of the Dice
dataset, we can see accuracies over 97%, equal or exceeding the base accuracy.
The stylized accuracies are also over 90% for the models trained on the DvC
dataset.

For the DBI and Food101 datasets, the stylized test set accuracies are more
modest, between 45% and 75%. They do still represent a significant increase
from the models trained on the base dataset. As mentioned in the datasets
sections, the DBI and Food101 contain some classes that are, in reality, very
similar to each other. Thus, the relatively low accuracy when predicting on
stylized images may simply be due to texture and colour cues that should be
present, but have been removed by the style-transfer.

###  3.3 Training on Mixed Datasets

Dataset | Model | Base Accuracy | Stylized Accuracy
---|---|---|---
Dice | ResNet | 99.97% | 99.76%
Dice | SNet | 99.97% | 97.66%
DvC | ResNet | 99.07% | 96.44%
DvC | SNet | 97.71% | 93.49%
DBI | ResNet | 92.63% | 75.70%
DBI | SNet | 83.87% | 56.82%
Food101 | ResNet | 89.73% | 73.31%
Food101 | SNet | 88.24% | 65.72%
Table 3: Results of the models trained on the mixed datasets. The reported
accuracy corresponds to the Top-5 Accuracy in the case of the DBI and Food101
datasets. SNet denotes the SqueezeNet model.

Table 3 shows the performance of the models when trained on the mix of base
and stylized data, as well as Figure 4 in graphical form. For the Dice
dataset, we can see similar, if slightly better (0.03%), accuracy on the base
testing set. For the stylized test sets, there is a slight gain (0.3%) for the
ResNet architecture. There is however no gain for the SqueezeNet architecture,
compared with the training on stylized data. Still, the mixed training yields
equal or better performance on the base test set, and almost equal performance
on the stylized test set. For the DvC dataset, we see a similar effect. For
both ResNet and SqueezeNet models, the base accuracy is roughly equal
(differences inferior to 0.1%). There are however very clear gains on the test
set accuracy, even compared with the training on stylized datasets. The ResNet
model gains 0.44% accuracy on stylized data, while the SqueezeNet model gains
0.29%. For these two datasets, the models trained on a mix of base and
stylized data seem to have _equal_ accuracy and _increased_ robustness.

Let us now consider the last two datasets. In the case of the DBI dataset, the
ResNet model loses out on base accuracy (1.95% loss), but the accuracy on the
stylized dataset is once again better than when trained on stylized data (by
1.34%). We see a similar trend in the SqueezeNet model, with a slight decrease
in accuracy compared to the base dataset (0.5%). The SqueezeNet model sees an
even greater increase in stylized accuracy, with a gain of 9.47%, compared to
training with stylized data. We see a greater loss in base test set accuracy
in the Food101 dataset, at 3.17% for the ResNet and 1.85% for the SqueezeNet.
Both models do increase their stylized test set accuracy with the mixed
learning however, respectively with increases of 2.21% and 2.03%.

For both these datasets, the models seem to _decrease_ in accuracy compared to
models trained on the base data. Yet, the representation learned by mixed
training is much more _robust_ , with the stylized test set accuracy
increasing compared to training on the stylized data. The second effect was
observed on all four datasets. The conclusion in (Geirhos et al., 2018)
indicated that this type of training should increase both accuracy and
robustness. The current results indeed show an increase in robustness and the
models learning though shape-bias. There is however no clear increase in
accuracy for the models, compared with training on the base dataset.

(a)

(b)

(c)

(d)

Figure 4: Results of base, stylized and mixed learning on the four datasets.
For subfigures (a) and (b), we use the accuracy. For subfigures (c) and (d),
the Top-5 accuracy is shown.

###  3.4 Using Domain-Adversarial Training

Dataset | Base Accuracy | Stylized Accuracy
---|---|---
Dice | 99.97% (0.00%) | 99.70% (-0.06%)
DvC | 98.95% (-0.12%) | 96.10% (-0.34%)
DBI | 93.85% (1.22%) | 77.62% (1.92%)
Food101 | 90.36% (0.63%) | 73.87% (0.56%)
Table 4: Results of the ResNet models trained on the mixed datasets using a
domain-adversarial network. The reported accuracy corresponds to the Top-5
Accuracy in the case of the DBI and Food101 datasets. The percentage in
parentheses is the gain or loss of accuracy compared to mixed training.

The Table 4 shows the results of training the ResNet models with a domain-
adversarial methods, on a mixed dataset of base and stylized data. The
accuracy on each test set is shown, as well as the difference between the
domain-adversarial training and the mixed training of the networks. Note that
the results only include ResNet models, as the SqueezeNet models were not
trained due to time and computational constraints. For the Dice dataset, the
results are equivalent, with a slight change of 0.06% stylized accuracy. This
is however not statistically significant. In the case of the DvC dataset, the
domain-adversarial training causes a slight decrease in both base and stylized
accuracies.

Let us now consider the DBI and Food101 datasets. In both cases, domain-
adversarial training of the network induces increases on the accuracies, for
the base test set and the stylized test set. This increase is greater than 1%
in both the base test set and stylized test set for the DBI dataset. This
results in the best performances for both datasets on the stylized test set.
This suggests that the domain-adversarial training did indeed help the
networks learn a representation that is more robust and dependant upon shape.

Yet, the baseline test for the DBI and Food101 datasets still outperform the
mixed training and the domain-adversarial models. For the DBI dataset, the
baseline was a base accuracy of 94.58%, compared to 93.85% using domain-
adversarial training and style-transferred examples (a difference of 0.73%).
Food101 has a best accuracy of 92.90% in the baseline, compared to a 90.36%,
for a difference of 2.54%. The complete picture, over the different datasets,
thus indicates that using a mix of base and stylized images does not increase
the accuracy of a model, but will increase its robustness and shape-bias.
Moreover, domain-adversarial training over these base and stylized images seem
to further increase the robustness of the model, and increase its accuracy
over simply training on both types of images.

##  4 Conclusion

In conclusion, it is possible to increase the shape bias and robustness of a
model for a given dataset using style-transfer and domain-adversarial
training. Over multiple datasets of varying complexity, we can see that models
trained on a base dataset will have difficulty maintaining their performance
if texture and colour clues are changed in the images. Augmenting the dataset
through a style-transfer will help the model learn a representation that can
predict accurately on both the original dataset and on the stylized version.
While the results of (Geirhos et al., 2018) have not been replicated fully, as
there is no clear gain in accuracy on the base dataset, the result is indeed
more robust models.

Moreover, adding a domain-adversarial element to the training of the model
further increases the robustness of the model and further encourage the
representation learned to be dependant upon shape. The domain-adversarial
component also helps to increase the accuracy of the models, over the mixed
training of base and stylized examples.

Further inquiries in this line of research are possible. Firstly, (Geirhos et
al., 2018) trained their ResNet architecture from scratch during their
experiments on ImageNet. Due to time and computational constraints, the models
presented were pre-trained on ImageNet. It is thus possible a new and possibly
better representation could be found by training the models from scratch using
domain-adversarial methods. Secondly, the current work was performed on
relatively small SqueezeNet 1.1 and ResNet-34 architectures. It is possible
that improvements could be made to the results using larger and higher
performance architectures.

Finally, let us reflect on the significance of these results. As was stated
concerning some of the datasets, it is possible that the best possible answer
to some problems indeed lie in the texture of an image, or its colour. Thus,
it could be better, for some problems, to train a model without using the
proposed methodology. It is also possible to envision the proposed methods as
the basis of a type of data augmentation. Indeed, while this would be very
computationally intensive, it would be possible to style-transfer images at
random during batches in order to augment shape-bias in training. Moreover,
the domain-adversarial element of the network provides regularization through
its multi-task aspect (Evgeniou & Pontil, 2004). Even applied as was
presented, we can see that, for some problems, the methodology provides added
robustness and regularization with little to no decrease in accuracy.

## Acknowledgements

I wish to thank Nicolas Garneau and Frédérik Paradis for their counsel and for
answering some questions about neural network design and implementation for
this project. I also wish to thank François Laviolette and the Groupe de
Recherche en Apprentissage Automatique de l’université Laval (GRAAL) research
group for the use of computing resources. Finally, computations were made on
the supercomputer Helios (Université Laval) and Graham (University of
Waterloo), managed by Calcul Québec and Compute Canada. The operation of this
supercomputer is funded by the Canada Foundation for Innovation (CFI), the
ministère de l’Économie, de la science et de l’innovation du Québec (MESI) and
the Fonds de recherche du Québec - Nature et technologies (FRQ-NT).

## References

  * Ballester & Araujo (2016) Ballester, P. and Araujo, R. M.  On the performance of googlenet and alexnet applied to sketches.  In _Thirtieth AAAI Conference on Artificial Intelligence_ , 2016.
  * Brendel & Bethge (2019) Brendel, W. and Bethge, M.  Approximating cnns with bag-of-local-features models works surprisingly well on imagenet.  _arXiv preprint arXiv:1904.00760_ , 2019.
  * (3) DBI.  Dog breed identification competition, kaggle.  https://www.kaggle.com/c/dog-breed-identification.  Accessed: 2019-04-24.
  * (4) Dice.  Dice dataset, kaggle.  https://www.kaggle.com/ucffool/dice-d4-d6-d8-d10-d12-d20-images.  Accessed: 2019-04-24.
  * (5) DvC.  Dogs versus cats competiton, kaggle.  http//www.kaggle.com/c/dogs-vs-cats:s/data.  Accessed: 2019-04-24.
  * Evgeniou & Pontil (2004) Evgeniou, T. and Pontil, M.  Regularized multi–task learning.  In _Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 109–117. ACM, 2004.
  * Food (101) Food101.  Food101 dataset, kaggle.  https://www.kaggle.com/kmader/food41.  Accessed: 2019-04-24.
  * Ganin et al. (2016) Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., Marchand, M., and Lempitsky, V.  Domain-adversarial training of neural networks.  _The Journal of Machine Learning Research_ , 17(1):2096–2030, 2016.
  * Gatys et al. (2017) Gatys, L. A., Ecker, A. S., and Bethge, M.  Texture and art with deep neural networks.  _Current opinion in neurobiology_ , 46:178–186, 2017.
  * (10) Geirhos, R.  Stylized-imagenet.  https://github.com/rgeirhos/Stylized-ImageNet.  Accessed: 2019-05-04.
  * Geirhos et al. (2018) Geirhos, R., Rubisch, P., Michaelis, C., Bethge, M., Wichmann, F. A., and Brendel, W.  Imagenet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=Bygh9j09KX.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Huang & Belongie (2017) Huang, X. and Belongie, S.  Arbitrary style transfer in real-time with adaptive instance normalization.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1501–1510, 2017.
  * Iandola et al. (2016) Iandola, F. N., Han, S., Moskewicz, M. W., Ashraf, K., Dally, W. J., and Keutzer, K.  Squeezenet: Alexnet-level accuracy with 50x fewer parameters and¡ 0.5 mb model size.  _arXiv preprint arXiv:1602.07360_ , 2016.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kriegeskorte (2015) Kriegeskorte, N.  Deep neural networks: a new framework for modeling biological vision and brain information processing.  _Annual review of vision science_ , 1:417–446, 2015.
  * Krizhevsky et al. (2012) Krizhevsky, A., Sutskever, I., and Hinton, G. E.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pp. 1097–1105, 2012.
  * Paszke et al. (2017) Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A.  Automatic differentiation in pytorch.  2017\.
  * Rawat & Wang (2017) Rawat, W. and Wang, Z.  Deep convolutional neural networks for image classification: A comprehensive review.  _Neural computation_ , 29(9):2352–2449, 2017\.
  * Ritter et al. (2017) Ritter, S., Barrett, D. G., Santoro, A., and Botvinick, M. M.  Cognitive psychology for deep neural networks: A shape bias case study.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 2940–2949. JMLR. org, 2017.
  * Szegedy et al. (2015) Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, S., Anguelov, D., Erhan, D., Vanhoucke, V., and Rabinovich, A.  Going deeper with convolutions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1–9, 2015.