# A bijection between rooted planar maps and generalized fighting fish

Enrica Duchi  IRIF, Université Paris Cité, France<EMAIL_ADDRESS>and  Corentin
Henriet  IRIF, Université Paris Cité, France<EMAIL_ADDRESS>
###### Abstract.

The class of fighting fish is a recently introduced model of branching
surfaces generalizing parallelogram polyominoes. We can alternatively see them
as gluings of cells, walks on the square lattice confined to the quadrant or
shuffle of Dyck words. With these different points of view, we introduce a
natural extension of fighting fish that we call _generalized fighting fish_.
We show that generalized fighting fish are exactly the Mullin codes of rooted
planar maps endowed with their unique rightmost depth-first search spanning
tree, also known as Lehman-Lenormand code. In particular, this correspondence
gives a bijection between fighting fish and nonseparable rooted planar maps,
enriching the garden of bijections between classes of objects enumerated by
the sequence $\frac{2}{(n+1)(2n+1)}\binom{3n}{n}$.
Key words : bijective combinatorics, fighting fish, Tamari intervals, Tamari
distance

Fighting fish were first defined in 2016 by Duchi et al. in [5] as a model of
branching surfaces that is a generalization of parallelogram polyominoes.
While parallelogram polyominoes are enumerated according to their
halfperimeter by the Catalan numbers, fighting fish are counted by the
sequence $\frac{2}{(n+1)(2n+1)}\binom{3n}{n},n\geq 1$. It is the sequence
$A000139$ of the OEIS [19] and it counts some other combinatorial objects :
nonseparable planar maps, synchronized intervals of the Tamari lattice, left
ternary trees, two-stack sortable permutations. In the last few years, a
growing number of articles has been dealing with the problem of connecting
bijectively these different classes of objects in order to have a better
combinatorial understanding of this family. The following diagram summarizes
the currently known bijections, dashed (resp. plain) arrows indicating
recursive (resp. direct) bijections.

${\begin{subarray}{c}\text{nonseparable rooted}\\\ \text{planar
maps}\end{subarray}}$left ternary treesfighting
fish${\begin{subarray}{c}\text{synchronized intervals}\\\ \text{of the Tamari
lattice}\end{subarray}}$${\begin{subarray}{c}{}\\\ {}\\\ {}\\\
\text{\cite[cite]{[\@@bibref{}{GW96}{}{}]},
\cite[cite]{[\@@bibref{}{DGW96}{}{}]}}\end{subarray}}$${\begin{subarray}{c}\text{two-
stack sortable}\\\ \text{permutations}\end{subarray}}$[4], [13], [16]this
article[10][11][7]

The present article is the second chapter of an extended version of a 12 page
article accepted at the FPSAC 2022 conference [8], the first chapter being [7]
dealing with the bijective link between fighting fish and intervals of the
Tamari lattice. The objective of this writing is twofold. The first purpose is
to obtain a direct bijection between fighting fish and nonseparable planar
maps. This bijection is in fact not new : it is the restriction of a
construction proposed by Mullin 50 years ago encoding a planar map with a
distinguished spanning tree by its contour word. However, it was not realized
before that Mullin’s bijection is mapping nonseparable planar maps (endowed
with their rightmost depth-first search spanning tree) to fighting fish. In a
second time, we define a natural generalization of fighting fish that we call
generalized fighting fish, and we prove that they are exactly the Mullin
encodings of rooted planar maps endowed with their rightmost DFS spanning tree
also known as Lehman-Lenormand code [14], see also [3, Chapter 2, II.3]. It is
important to remark that while the first article [7] deals with _extended_
fighting fish, this one introduces _generalized_ fighting fish : these two
classes of objects are two different extensions of the previously known class
of fighting fish.

##  1\. Introduction and motivation

###  1.1. Fighting fish

A complete presentation of fighting fish has been made in the introductive
articles [5] and [6], and we restate here their definitions in the language of
cell gluings used in these papers.

Figure 1. A cell and operations of upper, lower and double gluing.

A _cell_ is a 45 degree tilted unit square whose boundary is made out of four
edges called _left lower edge_ , _right lower edge_ , _right upper edge_ and
_left upper edge_. We intend to build fighting fish as sets of cells glued
together along some of their edges, so we define an edge of a cell to be
_free_ if it is not glued to the edge of another cell. A _fighting fish_ is a
finite set of cells constructed starting with an initial cell (the _head_),
then attaching one by one new cells using one of the three following
operations (represented in Figure 1) :

  * •

_Upper gluing_ : Let $a$ be a cell in a fish whose right upper edge is free ;
we glue the left lower edge of a new cell $b$ to the right upper edge of $a$.

  * •

_Lower gluing_ : Let $a$ be a cell in a fish whose right lower edge is free ;
we glue the left upper edge of a new cell $b$ to the right lower edge of $a$.

  * •

_Double gluing_ : Let $a$, $b$ and $c$ three cells in a fish such that $b$
(resp. $c$) has its left lower (resp. upper) edge glued to the right upper
(resp. lower) edge of $a$, and the right lower (resp. upper) edge of $b$
(resp. $c$) is free ; we glue both the left upper and left lower edges of a
new cell $d$ respectively to the right lower edge of $b$ and to the right
upper edge of $c$.

The _size_ of a fighting fish is the number of its free lower or upper edges,
that is half of the length of its boundary. We denote by $\mathcal{FF}$ the
class of fighting fish. Moreover, we denote by ${ff}_{n}=|\mathcal{FF}_{n}|$
the number of fighting fish with size $n$ and by
${ff}_{i,j}=|\mathcal{FF}_{i,j}|$ the number of fighting fish with $i$ left
lower free edges (or $i$ left upper free edges) and $j$ right lower free edges
(or $j$ right upper free edges).

While the description of fighting fish is iterative, we are interested in
these objects independently of the order in which they are constructed. There
can then be multiple ways to grow a given fighting fish with these operations.
We also want to emphasize that fighting fish are not planar objects in the
sense that we cannot always fit them in the plane because some unit squares
would represent two or more different cells. Still, we will present them in
our two-dimensional pictures by taking care of showing which cells are glued
together (Figure 2) provides an example of two possible representations of the
same fighting fish).

Figure 2. Two representations of the same fighting fish of size 6 and a
fighting fish of size 23.

Let us call _nose_ the leftmost point of the head of a fighting fish. Another
way to think of a fighting fish is to perform its counterclockwise tour : if
we follow the boundary of a fighting fish counterclockwise, starting from the
nose, we encounter all its free edges once until getting back to it. By
encoding each type of free edge by a step in $\\{E,N,W,S\\}$ : $E=(1,0)$
(resp. $S=(0,-1)$) for a left lower (resp. upper) one and $N=(0,1)$ (resp.
$W=(-1,0)$) for a right lower (resp. upper) one obtains an excursion (walk
starting and ending at the origin) on the square lattice $\mathbb{Z}^{2}$
confined to the quadrant $\\{x,y\geq 0\\}$. Then we can see fighting fish as
excursions or words on the alphabet $\\{E,N,W,S\\}$, obtained from the word
$ENWS$ using the three operations :

  * •

Upper gluing : replace a subword $W$ by $NWS$.

  * •

Lower gluing : replace a subword $N$ by $ENW$.

  * •

Double gluing : replace a subword $WN$ by $NW$.

For a word $w\in\\{E,N,W,S,V\\}^{*}$, we define its _latitude_ and _longitude_
to be the $x$ and $y$ coordinates of the endpoint of its corresponding walk on
$\mathbb{N}^{2}$ starting from $(0,0)$. We then have :

$\displaystyle\operatorname{\textup{{lat}}}(w)$
$\displaystyle=|w|_{N}-|w|_{S}$
$\displaystyle\operatorname{\textup{{long}}}(w)$
$\displaystyle=|w|_{E}-|w|_{W}$

###  1.2. Planar maps

Planar maps are classical objects in combinatorics (see [18] for more details)
and while many equivalent definitions are possible, we present them as graph
embeddings on the plane in order to be as graphical as possible in our
setting.

######  Definition 1.2.1.

A planar map is a proper embedding of a connected graph on the plane, defined
up to continuous deformations. A planar map splits the plane into _edges_ ,
_vertices_ and _faces_ , where faces are the connected components of the plane
deprived of edges and vertices. A _corner_ is an incidence between a vertex
and a face. As usual we consider rooted planar maps, where a corner on the
boundary of the infinite face is distinguished. This corner is called the
root, while the infinite face is also called the root face, the edge
preceeding the root in counterclockwise order on the boundary of the infinite
face is called the root edge and the vertex in the root corner is called the
root vertex. We denote by $\mathcal{M}$ the class of rooted planar maps (see
Figure 3$(a)$) for an example), by $\mathcal{M}_{n}$ the set of planar maps
with $n$ edges, and by $\mathcal{M}_{i,j}$ the set of planar maps with $i+1$
vertices and $j+1$ faces (that have hence $i+j$ edges from the Euler
relation).

Figure 3. $(a)$ A rooted planar map with its separable vertices in red ; $(b)$
a rooted nonseparable planar map

A nonseparable planar map is a rooted planar map without separable vertices,
i.e. vertices that can be cut to disconnect the map (see Figure 3$(b)$ for an
example). We denote by $\mathcal{NS}$ the class of nonseparable planar maps,
by $\mathcal{NS}_{n}$ the set of nonseparable planar maps with $n$ edges, and
by $\mathcal{NS}_{i,j}$ the set of nonseparable planar maps with $i+1$
vertices and $j+1$ faces.
For a rooted planar map $\operatorname{\textup{{M}}}$, its _dual map_
$\operatorname{\textup{{M}}}^{*}$ (see Figure 4) is the planar map whose
vertices are the faces of $\operatorname{\textup{{M}}}$ whose set of edges is
built in the following way : to each edge $e$ of
$\operatorname{\textup{{M}}}$, if we denote by $f_{1}$ and $f_{2}$ the two
faces adjacent to $e$, there is an edge $e^{*}$ in
$\operatorname{\textup{{M}}}^{*}$ linking the vertices $v_{f_{1}}$ and
$v_{f_{2}}$ respectively corresponding to faces $f_{1}$ and $f_{2}$ of
$\operatorname{\textup{{M}}}$. A corner corresponding to an incidence between
a vertex and a face, the root corner of $\operatorname{\textup{{M}}}^{*}$ is
chosen to be the same vertex-face incidence taken as root for
$\operatorname{\textup{{M}}}$ (interchanging the roles of face and vertex).

Figure 4. A rooted planar map in black then gray with its dual map drawn over
it in red

Let us remark that because it is embedded on the plane, a planar map defines a
cyclic ordering of the edges and the corners around each vertex and the same
is true around each face. Hence the edge following a corner in
counterclockwise direction around a vertex is well-defined as well as the
corner following that edge around the same vertex. We will call them
respectively the vertex-following edge and the vertex-following corner of a
corner. We define similarly the face-following edge and the face-following
corner of a given corner, but this time in a clockwise direction around the
face.

In the following sections, we will endow rooted planar maps with a particular
spanning tree called the _rightmost depth-first search spanning tree_ and we
will denote it for short as the rightmost DFS spanning tree. For a rooted
planar map $\operatorname{\textup{{M}}}$, it is the following spanning tree
$T$ obtained by an exploration of the corners of $\operatorname{\textup{{M}}}$
using the following procedure :

  * •

Initialization : Set the tree $T$ as the tree containing the root vertex of
$\operatorname{\textup{{M}}}$ and no edge, and set the active corner to be the
root corner. Set also the set of visited edges to be empty.

  * •

Core : Consider the active corner $c$ : it is incident to a unique vertex $v$
and to a unique face $f$, and we denote by $e$ the vertex-following edge of
$c$. There are 4 possible cases :

    * –

if $e$ is not a visited edge and the face-following corner $c^{\prime}$ of $c$
is incident to a vertex that does not belong to $T$, then add the edge $e$ to
$T$ and to the set of visited edges and set the active corner to be
$c^{\prime}$ ;

    * –

if $e$ is not a visited edge and the face-following corner of $c$ is incident
to a vertex that belongs to $T$, then add the edge $e$ to the set of visited
edges and set the active corner to be the vertex-following corner of $c$ ;

    * –

if $e$ is a visited edge and $e$ is an edge of $T$, then set the active corner
to be the face-following corner of $c$ ;

    * –

if $e$ is a visited edge and $e$ is not an edge of $T$, then set the active
corner to be the vertex-following corner of $c$.

Repeat until the active corner is the root corner again.

  * •

End : Return $T$

Figure 5. The rightmost depth-first search spanning tree of a rooted planar
map

Let us prove that $T$ is indeed a spanning tree of the map
$\operatorname{\textup{{M}}}$. First, $T$ is a tree, because every edge
inserted in it during the procedure leads to a vertex that was not visited
before, hence creating no cycle. Also, every corner around each vertex of $T$
is explored, and every edge is visited two times during the procedure : it is
true at the leaves of $T$ and for the edges leading to it, so it is also true
for vertices of $T$ having only leaves children, and so on up to the root.
This property coupled with the fact that $\operatorname{\textup{{M}}}$ is
connected ensures that $T$ is spanning. A consequence is that all corners of
the map are encountered during the exploration.

###  1.3. Mullin’s encoding and our result

We now recall an encoding of tree-rooted planar maps due to Lehman [14], see
also [20], as shuffles of two Dyck words, or parenthesis-integer systems in
their notation. To be precise about the origin of the encoding, Mullin was the
first to notice that tree-rooted planar maps could be encoded as intertwined
Catalan structures in his article [15] about the enumeration of tree-rooted
planar maps. Our presentation of the result follows closely the approach of
Schaeffer in a book chapter about planar maps [18], and we will adopt the same
denomination of Mullin’s encoding.

Let $\operatorname{\textup{{M}}}$ be a rooted planar map, that we endow with a
spanning tree $T$ which we consider rooted at the same corner as
$\operatorname{\textup{{M}}}$. The couple $(\operatorname{\textup{{M}}},T)$ is
called a _tree-rooted planar map_. The _dual_ of a tree-rooted planar map
$(\operatorname{\textup{{M}}},T)$ is the tree-rooted planar map
$(\operatorname{\textup{{M}}}^{*},T^{*})$, with
$\operatorname{\textup{{M}}}^{*}$ being the dual map of $M$ and $T^{*}$ the
spanning tree of $\operatorname{\textup{{M}}}^{*}$ formed by the edges dual of
the ones in $\operatorname{\textup{{M}}}$ that do not belong to $T$. We create
the _blossoming tree_ associated to the couple
$(\operatorname{\textup{{M}}},T)$ by performing the _counterclockwise tour_ of
$\operatorname{\textup{{M}}}$ around $T$ : we start from the root corner of
$\operatorname{\textup{{M}}}$ then visit all the corners of
$\operatorname{\textup{{M}}}$ by traveling on the border of the tree $T$ in
counterclockwise direction until we get back to the root corner. Each time we
encounter an edge that does not belong to $T$ we put an opening or closing
stem and we continue traveling around the stem: when we encounter such an edge
for the first time, we put an opening stem on the considered vertex along the
considered edge, otherwise we put a closing stem in the same manner. We then
forget the edges not belonging to $T$ to get the blossoming tree associated to
$(\operatorname{\textup{{M}}},T)$ : it is the rooted plane tree $T$ decorated
on its vertices with opening and closing stems. We define then the
_counterclockwise code_ $\Gamma(\operatorname{\textup{{M}}},T)$ of the tree-
rooted planar map $(\operatorname{\textup{{M}}},T)$ as the word in
$\\{E,N,W,S\\}^{*}$ obtained via the following procedure : perform the
counterclockwise tour of the associated blossoming tree starting from the root
corner, then encode the first visit of an edge in $T$ by $E$, the second visit
of an edge in $T$ by $W$, an opening stem by $N$ and a closing stem by $S$,
and stop when returning at the root corner. Such a word in $\\{E,N,W,S\\}^{*}$
can be seen as a walk on the square lattice $\mathbb{Z}^{2}$ by sending each
letter to its corresponding unit cardinal step. Let us remark that it is also
to be seen as a shuffle of two Dyck words, one on the letters $\\{E,W\\}$, the
other on the letters $\\{N,S\\}$. The _dual_ of a word in $\\{E,N,W,S\\}^{*}$
is obtained by reversing the word and replacing an occurrence of $E$ (resp.
$N$, $W$, $S$) by an occurrence of $S$ (resp. $W$, $N$, $E$) : it corresponds
to reversing the timeline of the corresponding walk on $\mathbb{Z}^{2}$ while
symmetrizing it with respect to the line $y=x$.

Figure 6. $(a)$ A tree-rooted planar map ; $(b)$ the beginning of the
counterclockwise tour ; $(c)$ the associated blossoming tree ; $(d)$ the
blossoming tree with the letters of the counterclockwise word.

In [20] Walsh and Lehman extend to higher genus Mullin’s decomposition of
tree-rooted maps and explicitely describe it in terms of shuffles of Dyck
words. While their description of his bijection is made in a more word
theoretic fashion, we state an equivalent formulation of his result here, and
we refer to the review of Schaeffer in [18] (subsection 1.2.1) for a more in-
depth treatment of the subject.

######  Theorem 1.

(Mullin [15]) The counterclockwise code is a bijection between tree-rooted
planar maps with $n$ edges and excursions of length $2n$, starting from the
origin and confined to the first quadrant. This bijection also preserves
duality, which means that the following diagram commutes :

${(\operatorname{\textup{{M}}},T)}$${(\operatorname{\textup{{M}}}^{*},T^{*})}$${\Gamma(\operatorname{\textup{{M}}},T)}$${\Gamma(\operatorname{\textup{{M}}}^{*},T^{*})}$map
duality$\scriptstyle{\Gamma}$$\scriptstyle{\Gamma}$excursion duality

Concerning statistics, a tree-rooted planar map $(M,T)$ having $i$ vertices,
$j$ faces has a counterclockwise code with $i$ $E$ steps and $j$ $N$ steps.

We organize the next sections as follows. In Section 2 we give a bijection
between fighting fish and nonseparable planar maps. The bijection is based on
a new decomposition of fighting fish that is isomorphic to the classical one
of nonseparable planar maps. In Section 3 we introduce the class of
generalized fighting fish, counted by the same numbers as rooted planar maps,
and we also give a decomposition isomorphic to the classical one of rooted
planar maps and a direct bijection. The very enlightening result is that, for
both the bijections involving nonseparable planar maps and rooted planar maps,
the corresponding fighting fish through the bijections is a particular Mullin
encoding of the original map, the one associated with the rightmost depth-
first search spanning tree.

##  2\. A bijection between fighting fish and nonseparable planar maps

The purpose of this section is to present a bijection between fighting fish
and nonseparable planar maps, already announced in [8].

###  2.1. A decomposition of fighting fish

The _jaw_ $\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}})$ is,
starting from the nose in counterclockwise order, the length of the first
sequence of left lower free edges.

We now present a decomposition of fighting fish that has been introduced in a
companion paper exploring the connection between fighting fish and
synchronized Tamari intervals [7]. Let us present the two operations involved
in this decomposition :

  * •

the _concatenation_
$\operatorname{\textup{{F}}}_{1}\odot\operatorname{\textup{{F}}}_{2}$ (see
Figure 7) of two fighting fish $\operatorname{\textup{{F}}}_{1}$ and
$\operatorname{\textup{{F}}}_{2}$ is obtained by gluing the right lower free
edge ending the jaw of $\operatorname{\textup{{F}}}_{1}$ to the leftmost upper
free edge of $\operatorname{\textup{{F}}}_{2}$.

Figure 7. Concatenation of fighting fish

  * •

the _$i$ -augmentation_ $\maltese_{i}(\operatorname{\textup{{F}}})$ of a
fighting fish $\operatorname{\textup{{F}}}$ (see Figure 8), for $i$ being an
integer between 1 and
$\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}})$, is obtained in
the following way : we glue the left lower free edge of each one of the first
$i$ cells of the jaw of $\operatorname{\textup{{F}}}$ to a new cell and then
glue the right lower edge and the left upper edge of all pairs of adjacent new
cells.

Figure 8. Some augmentations of a fighting fish

######  Proposition 1.

For every fighting fish $\operatorname{\textup{{F}}}$,
$\operatorname{\textup{{F}}}_{1}$ and $\operatorname{\textup{{F}}}_{2}$, and
for every $1\leq
i\leq\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}})$, we have :

$\displaystyle\operatorname{\textup{{size}}}(\maltese_{i}(\operatorname{\textup{{F}}}))$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}})+1$
$\displaystyle\operatorname{\textup{{jaw}}}(\maltese_{i}(\operatorname{\textup{{F}}}))$
$\displaystyle=i$
$\displaystyle\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}}_{1}\odot\operatorname{\textup{{F}}}_{2})$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}}_{1})+\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}}_{2})-1$
$\displaystyle\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}}_{1}\odot\operatorname{\textup{{F}}}_{2})$
$\displaystyle=\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}}_{1})+\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}}_{2})$

Figure 9. A decomposition on fighting fish

Consider now a fighting fish $\operatorname{\textup{{F}}}$. Then exactly one
of the following cases occur (see Figure 9) :

  * •

Case I : $\operatorname{\textup{{F}}}=ENWS$ is the Head (only one empty
component).

  * •

Case II :
$\operatorname{\textup{{F}}}=\maltese_{i}(\operatorname{\textup{{F}}}_{1})$
for some fighting fish $\operatorname{\textup{{F}}}_{1}$ and some $1\leq
i\leq\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}}_{1})$ (only one
non-empty component).

  * •

Case III :
$\operatorname{\textup{{F}}}=ENWS\odot\operatorname{\textup{{F}}}_{2}$ for
some fighting fish $\operatorname{\textup{{F}}}_{2}$ (more than two
components, the last one being empty).

  * •

Case IV :
$\operatorname{\textup{{F}}}=\maltese_{i}(\operatorname{\textup{{F}}}_{1})\odot\operatorname{\textup{{F}}}_{2}$
for some fighting fish $\operatorname{\textup{{F}}}_{1}$ and
$\operatorname{\textup{{F}}}_{2}$ and some $1\leq
i\leq\operatorname{\textup{{jaw}}}(\operatorname{\textup{{F}}}_{1})$ (more
than two components, the last one being non-empty).

###  2.2. A decomposition of nonseparable planar maps

The _reduced outer degree_
$\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}})$ of a nonseparable
planar map $\operatorname{\textup{{M}}}$ is the number of non-root corners
incident to the root face. Note that we can assign an integer from $1$ to
$\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}})$ to each non-root
corner in the root face according to its position in the counterclockwise tour
of the root face. We define now two operations on nonseparable planar maps :

  * •

the _concatenation_
$\operatorname{\textup{{M}}}_{1}\odot\operatorname{\textup{{M}}}_{2}$ (see
Figure 10) of two nonseparable planar maps $\operatorname{\textup{{M}}}_{1}$
and $\operatorname{\textup{{M}}}_{2}$ having respective root edges
$e_{1}=u_{1}\rightarrow v_{1}$ and $e_{2}=u_{2}\rightarrow v_{2}$ is obtained
by identifying $v_{2}$ and $u_{1}$, then deleting the root edge of
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$ and
creating a new root edge from $u_{2}$ to $v_{1}$.

Figure 10. Concatenation of nonseparable planar maps.

  * •

the _$i$ -augmentation_ $\maltese_{i}(\operatorname{\textup{{M}}})$ of a
nonseparable planar map $\operatorname{\textup{{M}}}$ (see Figure 11), for $i$
being an integer between 1 and
$\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}})$, is obtained by
adding an edge between the $i^{\rm{th}}$ non-root vertex incident to the root
face and the root vertex so that the root edge of
$\operatorname{\textup{{M}}}$ is no more incident to the root face, and the
added edge is the new root edge.

Figure 11. The three possible augmentations of some nonseparable planar map.

######  Proposition 2.

For every nonseparable planar maps $\operatorname{\textup{{M}}}$,
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$, and
for every $1\leq
i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}})$, we have :

$\displaystyle\operatorname{\textup{{size}}}(\maltese_{i}(\operatorname{\textup{{M}}}))$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}})+1$
$\displaystyle\operatorname{\textup{{out}}}(\maltese_{i}(\operatorname{\textup{{M}}}))$
$\displaystyle=i$
$\displaystyle\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}}_{1}\odot\operatorname{\textup{{M}}}_{2})$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}}_{1})+\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}}_{2})-1$
$\displaystyle\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1}\odot\operatorname{\textup{{M}}}_{2})$
$\displaystyle=\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})+\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{2})$

Figure 12. A decomposition on nonseparable planar maps

We now recall a classical decomposition of nonseparable planar maps called the
_series decomposition_ (see Figure 12). It was first stated by Brown in [2].
Consider a nonseparable planar map $\operatorname{\textup{{M}}}$ and delete
its root edge to obtain an unrooted planar map
$\operatorname{\textup{{M}}}^{\prime}$ that may have separable vertices. By
cutting $\operatorname{\textup{{M}}}^{\prime}$ at its separable vertices, we
obtain a tuple of planar maps that are either nonseparable or the one edge
planar map with two distinct vertices (that we call _Bridge_ and note $B$).
Then exactly one of the following four cases occurs :

  * •

Case I : $\operatorname{\textup{{M}}}$ is the only nonseparable map with two
edges (that we will denote by $D$ in the following)
($\operatorname{\textup{{M}}}^{\prime}$ has only one component and it is a
Bridge).

  * •

Case II :
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})$
for some nonseparable planar map $\operatorname{\textup{{M}}}_{1}$ and some
$1\leq i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$
($\operatorname{\textup{{M}}}^{\prime}$ has only one component and it is not a
Bridge).

  * •

Case III : $\operatorname{\textup{{M}}}=B\odot\operatorname{\textup{{M}}}_{2}$
for some nonseparable planar map $\operatorname{\textup{{M}}}_{2}$
($\operatorname{\textup{{M}}}^{\prime}$ has more than two components and the
last one is a Bridge).

  * •

Case IV :
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})\odot\operatorname{\textup{{M}}}_{2}$
for some nonseparable planar maps $\operatorname{\textup{{M}}}_{1}$ and
$\operatorname{\textup{{M}}}_{2}$ and some $1\leq
i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$
($\operatorname{\textup{{M}}}^{\prime}$ has more than two components and the
last one is not a Bridge).

###  2.3. The bijection

In the last two subsections, we presented two recursive decompositions for
fighting fish and for nonseparable planar maps. Since these two decompositions
are isomorphic, we are now able to define a bijection $\Phi$ from nonseparable
planar maps to fighting fish. Let $\operatorname{\textup{{M}}}$ be a
nonseparable planar map, we examine all possible cases :

  * •

Case I : if $\operatorname{\textup{{M}}}=D$, we set
$\Phi(\operatorname{\textup{{M}}})=ENWS$.

  * •

Case II : if
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})$
for some nonseparable planar map $\operatorname{\textup{{M}}}_{1}$ and some
$1\leq i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$,
we set
$\Phi(\operatorname{\textup{{M}}})=\maltese_{i}(\Phi(\operatorname{\textup{{M}}}_{1}))$.

  * •

Case III : if
$\operatorname{\textup{{M}}}=D\odot\operatorname{\textup{{M}}}_{2}$ for some
nonseparable planar map $\operatorname{\textup{{M}}}_{2}$, we set
$\Phi(\operatorname{\textup{{M}}})=ENWS\odot\Phi(\operatorname{\textup{{M}}}_{2})$.

  * •

Case IV : if
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})\odot\operatorname{\textup{{M}}}_{2}$
for some nonseparable planar maps $\operatorname{\textup{{M}}}_{1}$ and
$\operatorname{\textup{{M}}}_{2}$ and some $1\leq
i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$, we set
$\Phi(\operatorname{\textup{{M}}})=\maltese_{i}(\Phi(\operatorname{\textup{{M}}}_{1}))\odot\Phi(\operatorname{\textup{{M}}}_{2})$.

######  Theorem 2.

$\Phi$ is a bijection between nonseparable planar maps with $n$ edges, $i+1$
vertices, $j+1$ faces and outer degree $k$ and fighting fish of size $n$ with
$i$ left lower free edges, $j$ right lower free edges and jaw length $k$.
Moreover, for a nonseparable planar map $\operatorname{\textup{{M}}}$,
$\Phi(\operatorname{\textup{{M}}})$ is the Mullin encoding of the tree-rooted
planar map $(\operatorname{\textup{{M}}},T)$ where $T$ is the rightmost depth-
first search spanning tree of $\operatorname{\textup{{M}}}$. As a consequence,
$\Phi$ preserves duality.

Figure 13. The bijection $\Phi$ applied to some nonseparable planar map

###### Proof.

Since the two recursive decompositions are isomorphic, $\Phi$ is a well-
defined bijection between nonseparable planar maps with $n$ edges and out
degree $k$ and fighting fish of size $n$ and jaw length $k$. We proceed by
induction on the size of nonseparable planar maps to prove that $\Phi$ maps
nonseparable planar maps to their rightmost depth-first search Mullin
encoding. Let $\operatorname{\textup{{M}}}$ be a nonseparable planar map. We
distinguish between the four possible cases :

  * •

Case I : if $\operatorname{\textup{{M}}}=D$, then
$\Phi(\operatorname{\textup{{M}}})=ENWS$ is indeed the Mullin encoding of
$(\operatorname{\textup{{M}}},T)$ where $T$ is the rightmost DFS tree of
$\operatorname{\textup{{M}}}$.

  * •

Case II : if
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})$
for some nonseparable planar map $\operatorname{\textup{{M}}}_{1}$ and some
$1\leq i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$,
then by the induction hypothesis, $\Phi(\operatorname{\textup{{M}}}_{1})$ is
the Mullin encoding of $\operatorname{\textup{{M}}}_{1}$ endowed with its
rightmost DFS spanning tree $T_{1}$. Then the rightmost DFS spanning tree of
$\operatorname{\textup{{M}}}$ is also $T_{1}$ since
$\operatorname{\textup{{M}}}$ is obtained by adding an edge towards the root,
that is an already visited vertex. Hence, if we write
$\Phi(\operatorname{\textup{{M}}}_{1})=E^{k_{1}}\operatorname{\textup{{G}}}$
with $k_{1}=\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$,
the Mullin encoding of $(\operatorname{\textup{{M}}},T_{1})$ is
$E^{i}NE^{k_{1}-i}\operatorname{\textup{{G}}}S$, that is exactly
$\maltese_{i}(\Phi(\operatorname{\textup{{M}}}_{1}))=\Phi(\operatorname{\textup{{M}}})$.

  * •

Case III : if
$\operatorname{\textup{{M}}}=D\odot\operatorname{\textup{{M}}}_{2}$ for some
nonseparable planar map $\operatorname{\textup{{M}}}_{2}$, then by the
induction hypothesis, $\Phi(\operatorname{\textup{{M}}}_{2})$ is the Mullin
encoding of $\operatorname{\textup{{M}}}_{2}$ endowed with its rightmost DFS
spanning tree $T_{2}$. The rightmost DFS spanning tree $T$ of
$\operatorname{\textup{{M}}}$ consists of a root vertx with a pending edge on
which $T_{2}$ is attached. Writing
$\Phi(\operatorname{\textup{{M}}}_{2})=\operatorname{\textup{{G}}}S$, the
Mullin encoding of $(\operatorname{\textup{{M}}},T)$ is then
$E\operatorname{\textup{{G}}}WS$, that is exactly
$ENWS\odot\Phi(\operatorname{\textup{{M}}}_{2})=\Phi(\operatorname{\textup{{M}}})$.

  * •

Case IV : if
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})\odot\operatorname{\textup{{M}}}_{2}$
for some nonseparable planar maps $\operatorname{\textup{{M}}}_{1}$ and
$\operatorname{\textup{{M}}}_{2}$ and some $1\leq
i\leq\operatorname{\textup{{out}}}(\operatorname{\textup{{M}}}_{1})$, then by
the induction hypothesis, $\Phi(\operatorname{\textup{{M}}}_{1})$ and
$\Phi(\operatorname{\textup{{M}}}_{2})$ are the respective Mullin encodings of
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$
endowed with their respective rightmost DFS spanning tree $T_{1}$ and $T_{2}$.
Then the rightmost DFS spanning tree $T$ of $\operatorname{\textup{{M}}}$ is
obtained by gluing the root of $T_{2}$ onto the $k$-th corner of the righmost
branch of $T_{1}$, with
$k+\operatorname{\textup{{out}}}(T2)=\operatorname{\textup{{out}}}(T_{1})$.
Let us write
$\Phi(\operatorname{\textup{{M}}}_{1})=E^{k}\operatorname{\textup{{G}}}_{1}$
and $\Phi(\operatorname{\textup{{M}}}_{2})=\operatorname{\textup{{G}}}_{2}S$.
Performing the counterclockwise tour of $\operatorname{\textup{{M}}}$ around
$T$, we get the Mullin encoding of $(\operatorname{\textup{{M}}},T)$
$E^{k}\operatorname{\textup{{G}}}_{2}\operatorname{\textup{{G}}}_{1}S$, which
is exactly
$\maltese_{i}(\Phi(\operatorname{\textup{{M}}}_{1}))\odot\Phi(\operatorname{\textup{{M}}}_{2})=\Phi(\operatorname{\textup{{M}}})$.

∎

###  2.4. Enumeration results

For the sake of completeness, we recall now some enumeration results, which
have been known for a long time for nonseparable planar maps (see [1] for
example). Concerning fighting fish, the counting has been made analytically in
[6], and the preceeding bijection makes it more enlightening combinatorially.

######  Theorem 3.

The number of rooted nonseparable planar maps having $n+1$ edges, or
equivalently the number of fighting fish of size $n+1$ is :

$\frac{2(3n)!}{(n+1)!(2n+1)!}$

The number of rooted nonseparable planar maps having $i+1$ vertices and $j+1$
faces, or equivalently the number of fighting fish with $i+1$ $E$ steps and
$j+1$ $N$ steps is :

$\frac{(2i+j-2)!(2j+i-2)!}{i!j!(2i-1)!(2j-1)!}$

##  3\. Generalized fighting fish

Let us now present an alternative definition of fighting fish in terms that
will enable us to generalize it.

######  Proposition 3.

Fighting fish are exactly finite sets of cells that can be built starting from
the head, then attaching new cells using one of the following two operations :

  * •

_Upper strip gluing_ : Let $a_{1},a_{2},...,a_{k}$, $k\geq 1$ be cells such
that $a_{i}$ has its right lower edge glued to the left upper edge of
$a_{i+1}$ for all $1\leq i\leq k-1$, and such that all $a_{i}$ have their
right upper edge free ; for every $i$, we glue the right upper edge of $a_{i}$
to the left lower edge of a new cell $b_{i}$ while gluing the right lower edge
of $b_{i}$ to the left upper edge of $b_{i+1}$ for $1\leq i\leq k-1$.

  * •

_Lower strip gluing_ : Let $a_{1},a_{2},...,a_{k}$, $k\geq 1$ be cells such
that $a_{i}$ has its right upper edge glued to the left lower edge of
$a_{i+1}$ for all $1\leq i\leq k-1$, and such that all $a_{i}$ have their
right lower edge free ; for every $i$, we glue the right lower edge of $a_{i}$
to the left upper edge of a new cell $b_{i}$ while gluing the right upper edge
of $b_{i}$ to the left lower edge of $b_{i+1}$ for $1\leq i\leq k-1$.

###### Proof.

First, the upper strip gluing of $k$ cells $b_{1},...,b_{k}$ to
$a_{1},...,a_{k}$ can be obtained by performing an upper gluing of $b_{1}$ on
$a_{1}$, then performing $k-1$ double gluings of $b_{i+1}$ on $a_{i+1}$ and
$b_{i}$, for $1\leq i\leq k-1$. Similarly, a lower strip gluing of $k$ cells
can be obtained with a lower gluing and $k-1$ double gluings. Hence every
finite set of cells that can be obtained starting from the head and performing
upper and lower strip gluings is a fighting fish.
We will now prove that every fighting fish can be obtained starting from the
head and performing upper and lower strip gluings by induction on the number
$m$ of cells in the fighting fish. For $m=1$, the only fighting fish is the
head, so the property is verified. Suppose that the property is true for
fighting fish having strictly less than $m\geq 2$ cells and let $\mathrm{F}$
be a fighting fish having $m$ cells. If $\mathrm{F}$ is obtained by applying
an upper gluing on a fighting fish $\mathrm{F}_{1}$, then $\mathrm{F}_{1}$ has
$m-1$ cells, so it is constructible using upper and lower strip gluings, and
so is $\mathrm{F}$ by performing one additional upper strip gluing of $1$
cell. The case where $\mathrm{F}$ is obtained with a lower gluing on a
fighting fish $\mathrm{F}_{2}$ is similar. If $\mathrm{F}$ is obtained with a
double gluing of a cell $b$ on two cells $a$ (on the left upper edge of $b$)
and $a^{\prime}$ (on the left lower edge of $b$) of a fighting fish
$\mathrm{F}_{3}$, then $\mathrm{F}_{3}$ has $m-1$ cells so it is constructible
from the head using upper and lower strip gluings. In this construction,
either $a$ is added using an upper strip gluing or $a^{\prime}$ is added using
a lower strip gluing, because in $\mathrm{F}_{3}$ (and in $\mathrm{F}$), the
left lower edge of $a$ and the left upper edge of $a^{\prime}$ are glued
respectively to the right lower edge and to the right upper edge of the same
cell $c$. If $a$ is added using an upper strip gluing in $\mathrm{F}_{3}$,
then $\mathrm{F}$ can be obtained using the same strip construction as for
$\mathrm{F}_{3}$, except we perform an upper strip gluing with the extra cell
$b$ when we glue the upper strip containing $a$. The symmetrical statement is
true if $a^{\prime}$ is added using a lower strip gluing. Finally,
$\mathrm{F}$ is constructible using upper and lower strip gluings and the
induction follows. ∎

If we state this proposition in the word setting, we obtain the following :
fighting fish are exactly the finite words on the alphabet $\\{E,N,W,S\\}$
that can be obtained from the word $ENWS$ using a sequence of the two
operations :

  * •

Upper strip gluing : replace a subword $W^{k}$, $k\geq 1$, by $NW^{k}S$.

  * •

Lower strip gluing : replace a subword $N^{k}$, $k\geq 1$, by $EN^{k}W$.

We can then build a class of walks that includes fighting fish if we allow $k$
to be $0$ in the operations of strip gluing. We will prefer from now on to
work in the words or walks setting since strip gluings with $k=0$ do not add
cells.

######  Definition 3.0.1.

The class of _generalized fighting fish_ , denoted $\mathcal{GFF}$ is the set
of words or walks inductively defined from the empty word $\varepsilon$ with
the help of the following two types of operations :

  * •

operation $\bigtriangledown_{k}$, $k\geq 0$: replace a subword $N^{k}$ by
$EN^{k}W$.

  * •

operation $\bigtriangleup_{k}$, $k\geq 0$: replace a subword $W^{k}$ by
$NW^{k}S$.

Figure 14. Operations $\bigtriangledown_{k}$ and $\bigtriangleup_{k}$

As for fighting fish, the _size_ of a generalized fighting fish $\mathrm{F}$
is half of its length, and we have :

$\operatorname{\textup{{size}}}(\mathrm{F})=\frac{1}{2}(|h|_{E}+|h|_{N}+|h|_{W}+|h|_{S})=|h|_{E}+|h|_{N}=|h|_{W}+|h|_{S}$

Remark that the class of fighting fish is given by those generalized fighting
fish that can be obtained from $EW$ and $NS$ using only operations
$\bigtriangledown_{k}$ and $\bigtriangleup_{k}$, with $k\geq 1$. (See Figure
14 for an example)

We denote by ${gf}_{n}=|\mathcal{GF}_{n}|$ the number of generalized fighting
fish with size $n$ and by ${gf}_{i,j}=|\mathcal{GF}_{i,j}|$ the number of
generalized fighting fish with $i$ $E$ steps (or $i$ $W$ steps) and $j$ $N$
steps (or $j$ $S$ steps).

Generalized fighting fish are defined inductively using the operator
$\bigtriangleup_{k}$ and $\bigtriangledown_{k}$ on words but it is useful to
take advantage of their geometric properties as lattice paths. In particular
the following lemma will be useful, where $P^{<}$ denote the set of points
that can be reached from a point $P$ by $N$ and $E$ steps (ie the $45$ tilted
upper-right quarter plane with origin at $P$):

######  Lemma 1.

Let $\operatorname{\textup{{F}}}$ be a generalized fighting fish with origin
$O$. Then $\operatorname{\textup{{F}}}$ is included in $O^{<}$. Moreover if
$\operatorname{\textup{{F}}}=\operatorname{\textup{{F}}}_{1}\odot\operatorname{\textup{{F}}}_{2}$
with $P$ the endpoint of $\operatorname{\textup{{F}}}_{1}$ then
$\operatorname{\textup{{F}}}_{2}$ remains in $P^{<}$ or exits from the upper
side of $P^{<}$ (that is with a $W$ step, or with a $S$ step originating from
$P$).

###### Proof.

The proof is by recurrence: the fish $\operatorname{\textup{{F}}}$ can be
obtained from a smaller fish $\operatorname{\textup{{F}}}^{\prime}$ by
applying the operation $\bigtriangledown_{k}$ or $\bigtriangleup_{k}$ to a
seed $N^{k}$ or $W^{k}$ in $\operatorname{\textup{{F}}}^{\prime}$. Assume that
$\operatorname{\textup{{F}}}^{\prime}$ satisfies the lemma: then it stays in
$O^{<}$ and this property is preserved by $\bigtriangleup_{k}$ or
$\bigtriangledown_{k}$; moreover if
$\operatorname{\textup{{F}}}=\operatorname{\textup{{F}}}_{1}\odot\operatorname{\textup{{F}}}_{2}$
then
$\operatorname{\textup{{F}}}^{\prime}=\operatorname{\textup{{F}}}^{\prime}_{1}\odot\operatorname{\textup{{F}}}^{\prime}_{2}$
with the seed either in $\operatorname{\textup{{F}}}^{\prime}_{1}$, in
$\operatorname{\textup{{F}}}^{\prime}_{2}$ or spread between the two: in each
case the second property is preserved as well. ∎

##  4\. A bijection between generalized fighting fish and rooted planar maps

###  4.1. A decomposition for generalized fighting fish

In order to present a decomposition for generalized fighting fish we need to
introduce the following operations:

  * •

the concatenation $\oplus$ of two generalized fighting fish
$\operatorname{\textup{{F}}}_{1}$ and $\operatorname{\textup{{F}}}_{2}$, that
is given by
$\operatorname{\textup{{F}}}_{1}\oplus\operatorname{\textup{{F}}}_{2}=\operatorname{\textup{{F}}}_{1}E\operatorname{\textup{{F}}}_{2}W$
(see Figure 15).

Figure 15. The concatenation of two generalized fighting fish
$\operatorname{\textup{{F}}}_{1}$ and $\operatorname{\textup{{F}}}_{2}$.

  * •

let us take a generalized fighting fish $\operatorname{\textup{{F}}}$ and
denote by $\ell$ its number of visits at latitude $0$ minus one, then the _$i$
-augmentation_ $\maltese_{i}(\operatorname{\textup{{F}}})$ of
$\operatorname{\textup{{F}}}$ (see Figure 16), for $i$ being an integer
between $0$ and $\ell$, is obtained by adding a $N$ step after step $i$ at
latitude $0$ and a $S$ step at the end of the walk. More precisely, let
$\operatorname{\textup{{G}}}_{i}$ the subwalk of $\operatorname{\textup{{F}}}$
starting from $0$ and ending at the $i$-th visit, and let us denote by
$\overline{\operatorname{\textup{{G}}}}_{i}$ the remaining subwalk of
$\operatorname{\textup{{F}}}$. Then
$\maltese_{i}(\operatorname{\textup{{F}}})=\operatorname{\textup{{G}}}_{i}N\overline{\operatorname{\textup{{G}}}}_{i}S$.

Figure 16. The $i$-augmentation of a generalized fighting fish, represented
with walks and words.

######  Proposition 4.

For every generalized fighting fish $\operatorname{\textup{{F}}}$ and for
every $0\leq i\leq\ell(\operatorname{\textup{{F}}})$, we have :

$\displaystyle\operatorname{\textup{{size}}}(\maltese_{i}(\operatorname{\textup{{F}}}))$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}})+1$
$\displaystyle\ell(\maltese_{i}(\operatorname{\textup{{F}}}))$
$\displaystyle=i+1$
$\displaystyle\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}}_{1}\oplus\operatorname{\textup{{F}}}_{2})$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}}_{1})+\operatorname{\textup{{size}}}(\operatorname{\textup{{F}}}_{2})+1$
$\displaystyle\ell(\operatorname{\textup{{F}}}_{1}\oplus\operatorname{\textup{{F}}}_{2})$
$\displaystyle=\ell(\operatorname{\textup{{F}}}_{1})+\ell(\operatorname{\textup{{F}}}_{2})+2$

Remark that the $i$-augmentation of a generalized fighting fish is a
generalization of $\maltese_{i}$ defined for fighting fish in 2.1. Indeed for
a fighting fish, the number of points at latitude $0$ corresponds exactly to
the jaw length minus 1.

Given a generalized fighting fish $\operatorname{\textup{{F}}}$ of size $n$,
then we have two possible cases:

Figure 17. A decomposition for generalized fighting fish.

  * •

Case I : $\operatorname{\textup{{F}}}$ ends with a $W$ step. Then we consider
the last step $s$ leaving the origin in the path associated with
$\operatorname{\textup{{F}}}$, then
$\operatorname{\textup{{F}}}=\operatorname{\textup{{F}}}_{1}s\operatorname{\textup{{F}}}_{2}W$.
In view of the growth operations $\bigtriangledown_{k}$ and
$\bigtriangleup_{k}$ $s$ can only be a $E$ or $N$ step. If it was a $N$ step
the quadrant property enounced in lemma 14 applied to
$N\cdot\operatorname{\textup{{F}}}_{2}$ would imply that
$\operatorname{\textup{{F}}}_{2}$ would return to the origin before visiting
any point with $0$ latitude. Therefore $s$ is a $E$ step and
$\operatorname{\textup{{F}}}=\operatorname{\textup{{F}}}_{1}\oplus\operatorname{\textup{{F}}}_{2}=\operatorname{\textup{{F}}}_{1}E\operatorname{\textup{{F}}}_{2}W$
where $\operatorname{\textup{{F}}}_{1}$ and $\operatorname{\textup{{F}}}_{2}$
are possibly empty generalized fighting fish.

  * •

Case II : $\operatorname{\textup{{F}}}$ ends with a $S$ step. Then
$\operatorname{\textup{{F}}}=\maltese_{i}(\operatorname{\textup{{F}}}_{1})$
for some fighting fish $\operatorname{\textup{{F}}}_{1}$ and some $0\leq
i\leq\ell(\operatorname{\textup{{F}}}_{1})$, where
$\ell(\operatorname{\textup{{F}}}_{1})$ is the number of steps starting at
latitude $0$ in $\operatorname{\textup{{F}}}$.

###  4.2. Rooted planar maps and subclasses

###  4.3. A classical decomposition of rooted planar maps

In order to present Tutte’s classical _root edge deletion_ decomposition of a
rooted planar map $\operatorname{\textup{{M}}}$ we need to introduce the
following operations:

  * •

the concatenation
$\operatorname{\textup{{M}}}_{1}\oplus\operatorname{\textup{{M}}}_{2}$ of two
planar maps $\operatorname{\textup{{M}}}_{1}$ and
$\operatorname{\textup{{M}}}_{2}$ is obtained by adding a edge from the root
corner of $\operatorname{\textup{{M}}}_{1}$ to the root of
$\operatorname{\textup{{M}}}_{2}$ and by keeping the root of
$\operatorname{\textup{{M}}}_{1}$ (see Figure 18).

Figure 18.  The concatenation $\oplus$ of two planar maps
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$ and
the Mullin encodings with the rightmost spannig tree..

  * •

let us denote by $c$ the number of corners in the infinite face of a rooted
planar map $\operatorname{\textup{{M}}}$, then the _$i$ -augmentation_
$\maltese_{i}(\operatorname{\textup{{M}}})$ of $\operatorname{\textup{{M}}}$
(see Figure 19), for $i$ an integer between $0$ and $c$, is obtained by adding
a edge from the $i$-th corner to the right of the root of
$\operatorname{\textup{{M}}}$ (observe that we consider two corners around the
root, the one on the left and the one on the right of the arrow indicating the
root corner).

Figure 19.  The $i$-augmentation of a rooted planar map and the Mullin
encodings with the rightmost spanning tree.

Figure 20.  A classical decomposition on rooted planar maps.

Tutte’s classical _root edge deletion_ decomposition of a rooted planar map
$\operatorname{\textup{{M}}}$ consists in removing the edge $e$ preceeding the
root corner in counterclockwise order. There are two possible cases,
represented in Figure 20:

  * •

Case I : The edge $e$ is a disconnecting edge, so that there are two possibly
empty rooted planar maps
$(\operatorname{\textup{{M}}}_{1},\operatorname{\textup{{M}}}_{2})$, such that
$\operatorname{\textup{{M}}}=\operatorname{\textup{{M}}}_{1}\oplus\operatorname{\textup{{M}}}_{2}$.

  * •

Case II : The edge $e$ is not disconnecting, then
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})$
for some rooted planar map $\operatorname{\textup{{M}}}_{1}$ and some $0\leq
i\leq c(\operatorname{\textup{{M}}}_{1})$, where
$c(\operatorname{\textup{{M}}}_{1})$ is the number of corners in the infinite
face of $\operatorname{\textup{{M}}}_{1}$.

######  Proposition 5.

For every rooted planar maps $\operatorname{\textup{{M}}}$,
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$, and
for every $1\leq i\leq c(\operatorname{\textup{{M}}})$, we have :

$\displaystyle\operatorname{\textup{{size}}}(\maltese_{i}(\operatorname{\textup{{M}}}))$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}})+1$
$\displaystyle c(\maltese_{i}(\operatorname{\textup{{M}}}))$
$\displaystyle=i+1$
$\displaystyle\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}}_{1}\oplus\operatorname{\textup{{M}}}_{2})$
$\displaystyle=\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}}_{1})+\operatorname{\textup{{size}}}(\operatorname{\textup{{M}}}_{2})+1$
$\displaystyle
c(\operatorname{\textup{{M}}}_{1}\oplus\operatorname{\textup{{M}}}_{2})$
$\displaystyle=c(\operatorname{\textup{{M}}}_{1})+c(\operatorname{\textup{{M}}}_{2})+2$

###  4.4. The bijection

In the last two subsections, we presented a recursive decomposition for
generalized fighting fish and recalled the classical decomposition for rooted
planar maps. Since these two decompositions are isomorphic, we are now able to
define a bijection $\xi$ from rooted planar maps to generalized fighting fish.
Let $\operatorname{\textup{{M}}}$ be a rooted planar map, we examine all
possible cases :

  * •

Case I : the root edge $e$ of $\operatorname{\textup{{M}}}$’ is a
disconnecting one, that is, if removed it disconnects
$\operatorname{\textup{{M}}}$ into two rooted planar maps
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$, then
$\xi(\operatorname{\textup{{M}}})=\xi(\operatorname{\textup{{M}}}_{1})E\xi(\operatorname{\textup{{M}}}_{2})W$.

  * •

Case II : the root edge $e$ of $\operatorname{\textup{{M}}}$ is not a
disconnecting one, that is
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})$
for some rooted planar map $\operatorname{\textup{{M}}}_{1}$ and some $0\leq
i\leq c(\operatorname{\textup{{M}}}_{1})$, then we set
$\xi(\operatorname{\textup{{M}}})=\maltese_{i}(\xi(\operatorname{\textup{{M}}}_{1}))$.

######  Theorem 4.

$\xi$ is a bijection between rooted planar maps with $n$ edges, $i+1$
vertices, $j+1$ faces and $k$ corners in the infinite face and generalized
fighting fish of size $n$ with $i$ left lower free edges, $j$ right lower free
edges and $k$ non-initial visits at latitude $0$. Moreover, for a rooted
planar map $\operatorname{\textup{{M}}}$, $\xi(\operatorname{\textup{{M}}})$
is the Lehman-Lenormand encoding of M, that is the Mullin encoding of the
tree-rooted planar map $(\operatorname{\textup{{M}}},T)$ where $T$ is the
rightmost depth-first search spanning tree of $\operatorname{\textup{{M}}}$.
As a consequence, $\xi$ preserves duality and its restriction to non separable
planar maps is $\Phi$.

###### Proof.

Since the two recursive decompositions are isomorphic, $\xi$ is a well-defined
bijection between rooted planar maps with $n$ edges and $k$ corners in the
infinite face and generalized fighting fish of size $n$ and $k$ points at
latitude $0$. We proceed by induction on the size of rooted planar maps to
prove that $\xi$ maps rooted planar maps to their rightmost depth-first search
Mullin encoding. Let $\operatorname{\textup{{M}}}$ be a rooted planar map. We
distinguish between the two possible cases :

  * •

Case I : the root edge $e$ of $\operatorname{\textup{{M}}}$ is a disconnecting
one, then
$\xi(\operatorname{\textup{{M}}})=\xi(\operatorname{\textup{{M}}}_{1})E\xi(\operatorname{\textup{{M}}}_{2})W$.
Then, by induction hypothesis, $\xi(\operatorname{\textup{{M}}}_{1})$ and
$\xi(\operatorname{\textup{{M}}}_{2})$ are the respective Mullin encodings of
$\operatorname{\textup{{M}}}_{1}$ and $\operatorname{\textup{{M}}}_{2}$
endowed with their respective rightmost DFS spanning tree $T_{1}$ and $T_{2}$.
The rightmost DFS spanning tree $T$ of $\operatorname{\textup{{M}}}$ is
obtained by creating an edge between the root of $T_{1}$ and the root of
$T_{2}$, and by performing the counterclockwise tour of
$\operatorname{\textup{{M}}}$ around $T$, we get that the Mullin encoding of
$(\operatorname{\textup{{M}}},T)$ is exactly
$\xi(\operatorname{\textup{{M}}}_{1})E\xi(\operatorname{\textup{{M}}}_{2})W$,
that is $\xi(\operatorname{\textup{{M}}})$.

  * •

Case II : if
$\operatorname{\textup{{M}}}=\maltese_{i}(\operatorname{\textup{{M}}}_{1})$
for some rooted planar map $\operatorname{\textup{{M}}}_{1}$ and some $0\leq
i\leq c(\operatorname{\textup{{M}}}_{1})$, then by the induction hypothesis,
$\xi(\operatorname{\textup{{M}}}_{1})$ is the Mullin encoding of
$\operatorname{\textup{{M}}}_{1}$ endowed with its rightmost DFS spanning tree
$T_{1}$. Then the rightmost DFS spanning tree of $\operatorname{\textup{{M}}}$
is also $T_{1}$, because the added edge has one extremity which is the last
half edge of the root vertex and it is discovered from its other side in the
DFS.. Performing the counterclockwise tour of $\operatorname{\textup{{M}}}$
around $T$, we get that the Mullin encoding of
$(\operatorname{\textup{{M}}},T)$ is exactly
$\maltese_{i}(\xi(\operatorname{\textup{{M}}}_{1}))$, that is
$\xi(\operatorname{\textup{{M}}})$.

∎

Let us also remark that the bijection $\xi$ preserves the following
statistics:

  * •

The number of _down bridges_ in the generalized fighting fish
$\operatorname{\textup{{F}}}$, _i.e._ the number of places where
$\operatorname{\textup{{F}}}$ can be decomposed as
$\operatorname{\textup{{F}}}=\operatorname{\textup{{F}}}_{1}E\operatorname{\textup{{G}}}W\operatorname{\textup{{F}}}_{2}$
where $\operatorname{\textup{{F}}}_{1}\operatorname{\textup{{F}}}_{2}$ and
$\operatorname{\textup{{G}}}$ are (possibly empty) generalized fighting fish,
corresponds to the number of bridges in the planar map
$\operatorname{\textup{{M}}}$.

  * •

The number of _up bridges_ in the generalized fighting fish
$\operatorname{\textup{{F}}}$, _i.e._ the number of places where
$\operatorname{\textup{{F}}}$ can be decomposed as
$\operatorname{\textup{{F}}}=\operatorname{\textup{{F}}}_{1}N\operatorname{\textup{{G}}}S\operatorname{\textup{{F}}}_{2}$
where $\operatorname{\textup{{F}}}_{1}\operatorname{\textup{{F}}}_{2}$ and
$\operatorname{\textup{{G}}}$ are (possibly empty) generalized fighting fish,
corresponds to the number of loops in the planar map
$\operatorname{\textup{{M}}}$.

######  Definition 4.4.1.

  * •

A generalized fighting fish without up bridges denoted $\mathcal{UF}$ consists
of the generalized fighting fish obtained from the empty path using only
operations $\bigtriangledown_{k}$ with $k\geq 0$ and $\bigtriangleup_{k}$ with
$k\geq 1$.

  * •

A generalized fighting fish without down bridges, denoted $\mathcal{DF}$,
consists of the generalized fighting fish obtained from the empty path using
only operations $\bigtriangledown_{k}$ with $k\geq 1$ and $\bigtriangleup_{k}$
with $k\geq 0$.

  * •

A loopless planar map is a planar map without loops, i.e., edges that start
and end at the same vertex. We denote by $\mathcal{LM}$ the class of loopless
planar maps.

  * •

A bridgeless planar map is a planar map without bridges, i.e., edges whose
deletion disconnects the map. We denote by $\mathcal{BM}$ the class of
bridgeless planar maps.

Figure 21. $(a)$ A loopless planar map and its associated generalized fighting
fish without up bridges; $(b)$ A bridgeless planar map and its associated
fighting fish without down bridges

In Figure 21 there is an example of a loopless and a bridgeless planar maps
and their corresponding generalized fighting fish (in terms of words) by the
bijection $\xi$.

######  Proposition 6.

The previous bijection specializes into bijections between $\mathcal{UF}_{n}$
and $\mathcal{LM}_{n}$, between $\mathcal{BF}_{n}$ and $\mathcal{BM}_{n}$, and
between $\mathcal{FF}_{n}$ and $\mathcal{NS}_{n}$.

We point out that the length of the jaw of the generalized fighting fish, that
is the length of the first sequence of $E$ steps, gives the number of edges of
the infinity face minus $1$. An other nice property of the bijection is that
the notion of duality in maps is translated into the natural notion of
symmetry for generalized fighting fishes : exchange the operations
$\bigtriangleup_{k}$ and $\bigtriangledown_{k}$ during the construction.

Figure 22. A uniform random fighting fish of size 10000.

##  5\. Conclusion and perspectives

We have shown that Mullin encoding gives, in the special case of Lehman-
Lenormand code, a direct bijection between rooted planar maps and generalized
fighting fish, that further specializes in a bijection between rooted planar
maps and fighting fish. We observe that the Lehman-Lenormand code being based
on a single DFS, it can be performed in linear time: therefore the known
linear time Schaeffer’s random generator [17] for nonseparable planar maps and
rooted planar maps (available at
https://www.lix.polytechnique.fr/Labo/Gilles.Schaeffer/PagesWeb/PlanarMap/)
immediately gives linear random generators for fighting fish and generalized
fighting fish. In Figure 22 we show a random fighting fish of size $10000$
obtained by adapting this generator.

While Lehman-Lenormand code dates back to the early seventies, the main
contribution of this article is to enlighten that the counterclockwise codes
of (nonseparable) rooted planar maps endowed with their rightmost DFS spanning
trees can be given a very natural geometric interpretation as a branching
surface obtained by gluing unit cells. This geometric point of view based on
fighting fish already helped in proving a simple formula for the distance of
intervals in the Tamari lattice, using the correspondence of the area
statistic on fighting fish, where the area of a (generalized) fighting fish is
the number of cells it contains. This raises the problem of finding a natural
definition of the corresponding (by $\xi$) statistic on rooted planar maps.
Another perspective would be to unify the two extensions of fighting fish we
presented in this paper and th preceeding one. Recall that the class of
extended fighting fish is obtained by allowing also the operation of replacing
an occurrence of the substring $WN$ by a vertical step $V$ in the definition
of fighting fish. It would be nice to have a general model of fish embedding
the two classes of generalized and extended fighting fish, and that would fit
nicely with the bijections we defined, either with Tamari intervals and rooted
planar maps.

## References

  * [1] W. G. Brown and W. T. Tutte.  On the enumeration of rooted non-separable planar maps.  Canadian Journal of Mathematics, 16:572–577, 1964.
  * [2] William G. Brown.  Enumeration of non-separable planar maps.  Canadian Journal of Mathematics, 15:526–545, 1963.
  * [3] R. Cori.  Un code pour les graphes planaires et ses applications.  Astérisque, 27:1–169, 1975.
  * [4] A. Del Lungo, F. Del Ristoro, and J.-G. Penaud.  Left ternary trees and non-separable rooted planar maps.  Theoretical Computer Science, 233(1-2), 2000.
  * [5] E. Duchi, V. Guerrini, S. Rinaldi, and G. Schaeffer.  Fighting Fish.  2016\.  Journal of Physics A: Mathematical and Theoretical. Special issue in honor of Anthony Guttmann,.
  * [6] E. Duchi, V. Guerrini, S. Rinaldi, and G. Schaeffer.  Fighting Fish: enumerative properties.  75B(#43), 2017.  Séminaire Lotharingien de Combinatoire,.
  * [7] E. Duchi and C. Henriet.  A bijection between tamari intervals and extended fighting fish.  arXiv:2206.04375, 2022.
  * [8] E. Duchi and C. Henriet.  Bijections between fighting fish, planar maps and tamari intervals.  Accepted to FPSAC 2022, 2022.
  * [9] S. Dulucq, S. Gire, and J. West.  Permutations with forbidden subsequences and nonseparable planar maps.  Discrete Math., 153(1-3):85–103, 1996.
  * [10] Wenjie Fang.  A trinity of duality: Non-separable planar maps, $\beta$(1,0)-trees and synchronized intervals.  Advances in Applied Mathematics, 95:1–30, 2018.
  * [11] Wenjie Fang.  Fighting fish and two-stack sortable permutations.  2019\.
  * [12] Ian P. Goulden and J. West.  Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations.  J. Comb. Theory, Ser. A, 75(2):220–242, 1996.
  * [13] Benjamin Jacquard and Gilles Schaeffer.  A bijective census of nonseparable planar maps.  J. Combin. Theory Ser. A, 83(1):1–20, 1998.
  * [14] A. B. Lehman.  A bijective census of rooted planar maps.  In Communication at Ontario Math. Conf., 1970.
  * [15] R. C. Mullin.  On the enumeration of tree-rooted maps.  Canad. J. Math., 19:174–183, 1967.
  * [16] G. Schaeffer.  Conjugaison d’arbres et cartes combinatoires aléatoires.  PhD thesis, Université Bordeaux I, 1998.
  * [17] G. Schaeffer.  Random sampling of large planar maps and convex polyhedra.  In Proceedings of the ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 760–769 (electronic). ACM, New York, 1999.
  * [18] Gilles Schaeffer.  Planar maps.  In M. Bóna, editor, Handbook of Enumerative Combinatorics, chapter V. Chapman and Hall/CRC, 1st edition, 2015.
  * [19] N. J. A. Sloane.  The on-line encyclopedia of integer sequences, 2011.
  * [20] T. Walsh and Lehman A.B.  Counting rooted maps by genus ii.  Journal of Combinatorial Theory, Series B, 13(2):122–141, 1972\.


# Bio-inspired Min-Nets Improve the Performance and Robustness of Deep
Networks

Philipp Grüning
Institute for Neuro- and Bioinformatics
University of Lübeck
Lübeck, 23562
<EMAIL_ADDRESS>
&Erhardt Barth
Institute for Neuro- and Bioinformatics
University of Lübeck
Lübeck, 23562
<EMAIL_ADDRESS>

###### Abstract

Min-Nets are inspired by end-stopped cortical cells with units that output the
minimum of two learned filters. We insert such Min-units into state-of-the-art
deep networks, such as the popular ResNet and DenseNet, and show that the
resulting Min-Nets perform better on the Cifar-10 benchmark. Moreover, we show
that Min-Nets are more robust against JPEG compression artifacts. We argue
that the minimum operation is the simplest way of implementing an AND
operation on pairs of filters and that such AND operations introduce a bias
that is appropriate given the statistics of natural images.

##  1 Introduction

We present a novel network architecture that is based on the AND combination
of pairs of linear filters. The linear filters in deep networks can be
considered as basic measurements of the input signal, each filter capturing
signal energy along some relevant direction in feature space. In differential
geometry, the basic measurements are the main curvatures. In the case of
2-dimensional manifolds, it is known that the structure of the manifold is
captured by the Gaussian curvature, which is the product of the main
curvatures (do Carmo (1976)). In higher dimensions, the Riemann curvature
tensor captures the structure of the manifold, and it is based on sums of
products of main curvatures (OR combinations of pairwise AND combinations).
Inspired by differential geometry, in computer vision, different algorithms
have been designed to capture interest points in images, for example, by
analysing the invariants and eigenvalues of the Hessian or of the structure
tensor (Guiducci (1988); Jähne (1995)). Both the product and the minimum of
the eigenvalues have been used for the detection of interest points (Shi &
Tomasi (1994)).

In related work on feature product (FP)-nets (Grüning et al. (2021)), the AND
operation has been implemented by using explicit multiplications. FP-nets have
been shown to improve the performance of state-of-the-art networks. Moreover,
FP-units are hyperselective (for more information on hyperselectivity, see
(Paiton et al. (2020)) and (Vilankar & Field (2017))) and thus more robust
against compression artifacts and adversarial attacks (Grüning et al. (2021)).
As an alternative to the computationally more intensive multiplications, the
log-nets introduced in Grüning et al. (2020) are more efficient by using
convolutions in log-space. However, the main feature of both the FP-nets and
the log-nets is that the networks learn appropriate filter pairs to be AND-
combined.

FP-nets and the here proposed Min-Nets are inspired by what is known about
biological vision since the seminal work of Hubel and Wiesel (Hubel & Wiesel
(1965)). They discovered oriented neurons in primary visual cortex V1 but also
end-stopped cells in V1 and V2. End-stopped cells extract features such as
corners and line ends, provide an efficient representation of the visual
input, and can be modelled as AND combinations of linear, oriented filters
(Zetzsche & Barth (1990)). Motion selective neurons have also been modelled by
using AND combinations of linear spatio-temporal filters based on the Riemann
tensor (Barth & Watson (2000)).

The question of why end-stopped neurons and AND combinations of linear filters
are useful for vision can be answered based on the statistics of natural
images. A first useful bias is due to the fact that 0D-features, i.e., local
image patches of uniform intensity or color, are both redundant and frequent
in natural images. Therefore, a representation of images in terms of edges is
efficient; it reduces the entropy of the representation. 1D-features such as
straight edges and lines, however, are also redundant and more frequent in
natural images than 2D-features, such as curved edges and corners. Therefore,
a representation provided by end-stopped units is more efficient than one
provided by oriented filters. Details on the above-summarized statistics and
on why AND combinations are needed to exploit them can be found in Zetzsche et
al. (1993).

However, we do not assume that real neurons would compute ideal
multiplications and strict minimum operations, but that they may approximate
such operations in some way and thus generate AND combinations of filters
instead of just using point-wise non-linearities (see also Paiton et al.
(2020) regarding the limits of point-wise non-linearities). Here, we present
the novel Min-Net architecture that implements the minimum operation as the
simplest kind of AND operation on pairs of learned filters. Moreover, minimum
operations are faster than multiplications and make training easier due to
more conservative gradients.

##  2 Methods

Min-Nets are CNNs containing a certain number of Min-blocks that process an
input Tensor $\mathbf{T}_{0}$ and, via a sequence of different layers,
transform them to a tensor $\mathbf{T}_{out}$. The block structure resembles
the inverted residual block of the well-known MobileNet-V2 (Sandler et al.
(2018)) architecture, with the important extension that it contains two filter
operations that are combined by a minimum operation. In short, the block
consists of (i) a convolution layer with kernel size one, batch normalization,
and ReLU, increasing the number of input feature maps, (ii) two depth-wise
separable (DWS) convolutions, each learning one filter per feature map with
instance normalization and ReLU, the outputs of which are element-wise
combined by the minimum function, (iii) a second $1\times 1$-convolution with
batch normalization and ReLU, recombining the outputs of (ii) to the desired
number of feature maps and, finally, (iv) a residual connection. The next
subsection gives a more detailed description. The middle panel of Figure 1
depicts a Min-block.

###  2.1 Min-blocks

First, $qd_{out}$ feature maps are computed as weighted sums of the $d$
feature maps of $\mathbf{T}_{0}\in\mathbb{R}^{h\times w\times d}$. $q$ is an
expansion factor, and $d_{out}$ the desired number of output feature maps.
Thus, a convolution layer with kernel size one, and subsequent ReLU, computes
the $(i,j)$-th pixel of the $m$-th feature map as:

$\mathbf{T}_{1}[i,j,m]=ReLU(\sum_{n=1}^{d_{in}}w_{m}^{n}\mathbf{T}_{0}[i,j,n]);m=1,...,qd_{out}.$
(1)

Note that before the ReLU, $\mathbf{T}_{1}$ is normalized via batch
normalization. Next, two DWS convolutions are applied: for each feature map
$\mathbf{T}_{1}^{m}$ a filter-pair $\mathbf{V}_{m}$ and
$\mathbf{G}_{m}\in\mathbb{R}^{k\times k}$ is learned. For each pixel $(i,j)$,
the filter operation computes the scalar product of the filter vectors (i.e.,
the vectorized filter kernels $vect(\mathbf{V}_{m})=\mathbf{v}_{m}$ and
$\mathbf{g}_{m}\in\mathbb{R}^{k^{2}}$) and the vectorized feature map patch
$\mathbf{x}_{m}\in\mathbb{R}^{k^{2}}$ with $(i,j)$ being the pixel-coordinates
of the center pixel. Subsequently, instance normalization (Ulyanov et al.
(2016)) is applied with $\mu_{v_{m}}$ and $\sigma_{v_{m}}$ being the mean and
standard deviation of the feature map $\mathbf{T}_{1}^{m}$ filtered with
$\mathbf{v}_{m}$. Again, a ReLU is applied afterwards. Using the min-function,
we combine these two intermediate outputs to
$\mathbf{T}_{2}\in\mathbb{R}^{\frac{h}{s}\times\frac{w}{s}\times qd_{out}}$,
$s$ being the stride of the DWS-convolution that allows for subsampling. The
Min-unit, as the main building block of the proposed network, is defined as:

$\mathbf{T}_{2}[i,j,m]=\min{\left[\frac{ReLU(\mathbf{x_{m}}^{T}\mathbf{v_{m}}-\mu_{v_{m}})}{\sigma_{v_{m}}},\frac{ReLU(\mathbf{g_{m}}^{T}\mathbf{x_{m}}-\mu_{g_{m}})}{\sigma_{g_{m}}}\right]}.$
(2)

Note that such a Min-unit, or Min-neuron, will have a significant output only
if both filters $\mathbf{v_{m}}$ and $\mathbf{g_{m}}$ are activated.

A second linear recombination with batch normalization and ReLU (see Equation
1) creates the tensor
$\mathbf{T}_{3}\in\mathbb{R}^{\frac{h}{s}\times\frac{w}{s}\times d_{out}}$.
Finally, a residual connection adds the original input to $\mathbf{T}_{3}$:

$\mathbf{T}_{out}=\mathbf{T}_{0}+\mathbf{T}_{3}.$ (3)

Some additional computations need to be applied if the dimensions of
$\mathbf{T}_{0}$ and $\mathbf{T}_{3}$ do not match. See the Appendix for
details.

###  2.2 Transforming state-of-the-art CNNs to Min-Nets

In our experiments, we evaluate how the addition of Min-blocks changes the
performance of state-of-the-art CNNs. Networks such as the DenseNet (Huang et
al. (2017)) and the ResNet (He et al. (2016)) have a similar overall
structure: after an initial convolution layer, the networks consists of
several stacks that are larger structures containing a number of blocks.
Analogously, a block contains a number of layers, for example, convolutions,
batch normalization, and non-linearities. After the last stack, global average
pooling is applied with a subsequent linear layer and softmax to compute the
class probabilities. Stacks are separated by a downsampling layer (strided
convolution or a max-pooling layer), except for the first stack after the
initial convolution. When applied to smaller datasets, e.g., Cifar, both the
DenseNet and ResNet consist of three stacks, containing $N$ blocks each, with
the input heights and widths $32\times 32$, $16\times 16$, and $8\times 8$.
Thus, only the second stack and third stack employ downsampling. We use a
simple design rule to enrich these architectures with blocks that directly
compute pairwise AND-combinations: Each first block of a stack is substituted
by a Min-block. Note that this approach was derived empirically. In preceding
experiments, other combinations of Min-blocks and convolutional blocks were
tested but yielded somewhat inferior or equal results. We chose a ResNet
implementation that uses pyramid blocks (Han et al. (2017)) since it performs
better than the original ResNet and is currently often used for different
applications. Here, the sequence of layers consists of batch normalization,
$3\times 3$ convolution, batch normalization, ReLU, $3\times 3$ convolution,
and batch normalization. The sequence output is added to the original input of
the block. As a second reference network, we use the DenseNet-BC. In this
architecture, each so-called bottleneck block consists of batch normalization,
ReLU, and a $1\times 1$ convolution layer, followed by a second batch
normalization and ReLU and a $3\times 3$ convolution layer. A comparison of
the different block structures is given in Figure 1.

Figure 1:  Comparison of different block architectures. The left scheme shows
the basic block of a ResNet adopted from the PyramidNet. The middle scheme
shows the proposed Min-block, the right scheme the DenseNet’s bottleneck
block. Arrows show the data flow; the abbreviations within the boxes denote
different layers and operations. BN: batch normalization, IN: instance
normalization, $3\times 3$: a convolution with kernel size 3, DWS $3\times 3$:
a depthwise-separable convolution with kernel size 3. $d_{in}\rightarrow
d_{out}$ expresses a change in feature maps from $d_{in}$ to $d_{out}$. $k$ is
the growth factor, $q$ is the expansion factor. The plus in the circle is a
residual connection, the min in the circle a minimum operation of two inputs.
$\mathbf{T}_{i}$ denotes the (intermediate) tensor results (see for example
Equation 2). Note that instead of using residual connections, the DenseNet
concatenates feature maps from previous layers – which is not depicted here.

###  2.3 Hyperselectivity

CNNs employ linear neurons with points-wise non-linearities (LN-neurons),
e.g., a ReLU that is applied to each pixel independently. Thus, the direction
of maximal activation, i.e., the optimal stimulus, $\mathbf{x}^{*}$ points in
the same direction as the neuron’s weight vector $\mathbf{w}$. Any deviation
$\mathbf{o}$ orthogonal to the optimal stimulus does not alter the neuron’s
output:
$ReLU(\mathbf{w}^{T}(\mathbf{x}^{*}+\mathbf{o}))=ReLU(\mathbf{w}^{T}\mathbf{x}^{*})$.
In contrast, a neuron $f(\mathbf{x})$ is hyperselective, if there exist
orthogonal perturbations, that reduce the output:

$\textrm{f is hyperselective}\
\Leftrightarrow\exists\mathbf{o}:f(\mathbf{x}^{*}+\mathbf{o})<f(\mathbf{x}^{*});\mathbf{x}^{*T}\mathbf{o}=0$
(4)

For a Min-neuron (see Equation 2), the optimal stimulus is the bisector of the
angle $\gamma$ between the filter vectors $\mathbf{v}$ and $\mathbf{g}$. Any
perturbation within the plane spanned by $\mathbf{v}$ and $\mathbf{g}$ that is
orthogonal to the optimal stimulus reduces the neuron’s output, because one of
the scalar products is smaller than it would be without the perturbation,
e.g.,
$\mathbf{v}^{T}(\mathbf{x}^{*}+\mathbf{o})<\mathbf{v}^{T}\mathbf{x}^{*}$.
Hyperselective neurons are harder to activate by signals that differ from the
optimal stimulus. Thus, unwanted perturbations, such as those due to
adversarial examples (Szegedy et al. (2013); Goodfellow et al. (2014)) or
compression artifacts, have a smaller impact on the neuron’s – and
consequently, the whole network’s – output. Note that an LN-neuron located in
the second or higher layer of a CNN can become hyperselective indirectly when
regarding the pixel space as input. In contrast, a Min-neuron is directly
hyperselective to its input.

##  3 Experiments

We hypothesize that Min-Nets introduce a useful inductive bias to a CNN
architecture: the minimum of a learned filter-pair, a Min-neuron, explicitly
models end-stopped neurons and leads to efficient representations, which are
adapted to the statistics of natural images, thus leading to better
generalization. Furthermore, unlike traditional model neurons, Min-neurons are
hyperselective, a property that should make them more robust, e.g., to
compression artifacts. We ran two experiments to investigate these
conjectures.

###  3.1 Classification performance on Cifar-10

We compared models with different depths created from two reference network
architectures: the ResNet and the DenseNet. For each model, we created a Min-
Net version using our design rule. We compared models with different depths,
defined by the number of blocks per stack. For the ResNets, we created models
with $N\in\\{3,5,7,9\\}$ blocks. We trained DenseNets with $N\in\\{3,9,16\\}$
blocks and a growth-rate $k=12$, corresponding to networks $(L=22,k=12)$,
$(L=58,k=12)$, and $(L=100,k=12)$ in the DenseNet paper’s naming convention.
For all models, we set the expansion factor $q=2$, and we trained and tested
the models on Cifar-10 (Krizhevsky et al. (2021)) with a standard procedure
for data augmentation (see Appendix). Each ResNet was trained for 200 epochs
with a learning rate of 0.1, a weight decay of 0.0001, and using SGD with a
momentum of 0.9. The batch size was 128. After 100 and 150 epochs, the
learning rate was divided by 10. Each net was trained for five random seeds,
altering the batch order and random initialization. We trained the DenseNets
for 300 epochs, where the initial learning rate of 0.1 was divided by ten
after 150 and 225 epochs. Instead of 128, a batch size of 64 was used. In
addition, we used the Nesterov momentum. We trained each network with three
different random seeds. All other parameters were equal to the ResNet
experiments. Note that we did not employ an early stopping strategy but rather
report the final test results after 200 or 300 epochs, respectively.

###  3.2 Robustness to compression artifacts

Since Min-Nets have neurons that are hyperselective, one can expect the
networks to be more robust against perturbations. To evaluate robustness, in a
second experiment, each model trained in the first experiment was tested on
JPEG-compressed versions of the Cifar-10 test set $\mathcal{X}_{test}$. We
created nine additional test sets
$\mathcal{S}_{Q}=\\{JPEG(\mathbf{I},Q):\mathbf{I}\in\mathcal{X}_{test}\\}$
with quality $Q\in\\{90,80,...,10\\}$, $JPEG(\mathbf{I},Q)$ being the
compression function for an input image $\mathbf{I}$. For $Q=100$, the
original image is returned (no compression); $Q=1$ would yield maximal
compression with images that are barely recognizable (see Figure 5 in the
Appendix for examples). As robustness metric, we report the percentage of
changed predictions (POCP), i.e., we compared the model’s predictions with
full quality to the predictions on $\mathcal{S}_{Q}$ and computed the number
of changed predictions divided by the number of images (see Eq. 5 in the
Appendix). Using this metric, we avoid offsets introduced by models with lower
test errors. We used the JPEG algorithm from the OpenCV (Bradski (2000))
library.

##  4 Results

The Cifar-10 test errors of each model are shown in Figure 2. Note that in all
configurations, the Min-Net has a lower mean test error than the corresponding
baseline networks while using fewer parameters.

Next, we analyse the robustness of the networks. Figure 3 shows the POCP
(Equation 5) for the quality levels $Q=90,80,70,60$. Compared to the ResNet
and DenseNet, the Min-Nets are less likely to change their output when
presented with compressed images. However, even the more robust Min-Nets
remain sensitive to compression artifacts given that $8\%$ of the predictions
change with a slightly altered test set (such as $\mathcal{S}_{90}$).

Figure 2: Cifar-10 test error results. Black dashed lines show the baseline
results – solid blue lines the Min-Net results. Each diamond denotes the mean
error of a model with a specific number of blocks. The error bars indicate the
standard deviation of each model. The colored areas show the distance between
the minimum- and maximum values. The x-axis shows the number of parameters,
increasing with the number of blocks. The y-axis is the test error after 200
and 300 epochs for the ResNets (a) and DenseNets (b), respectively. Figure 3:
POCP depending on JPEG quality: the x-axis shows the quality parameter $Q$ for
the JPEG compression algorithm (which can vary from 100 to 1). The y-axis
denotes, in relative terms, how many predictions were different from the
original predictions (with $Q=100$) when using a more compressed test set.

##  5 Discussion

We have presented a novel network architecture and have demonstrated its
competitive performance. We have designed experiments with state-of-the-art
and popular deep networks and showed that we could improve their performance
by substituting original blocks in the network architecture with Min-blocks
that implement a minimum operation on pairs of feature maps. Note that by
using a simple design rule, any traditional network can easily be transformed
into a Min-Net that will most likely perform better. Also, note that we did
not tune hyperparameters specific to the Min-Nets but used the hyperparameters
of the original networks; additional tuning may thus lead to even better
performance of the Min-Nets.

We believe that a bias that is appropriate for natural images leads to the
improvements that we have obtained. As argued in the Introduction, this bias
allows the network to learn more efficient representations based on model
neurons that are end-stopped.

The pairwise minimum operations that we introduce allow for AND rather than OR
combinations of features and make the resulting neurons more selective than
linear filters with only point-wise non-linearities. The demonstrated
increased robustness of the Min-Nets is most likely due to the fact that Min-
units are hyperselective. It has been argued before that hyperselectivity
might be the key to greater robustness (Paiton et al. (2020)).

In previous work, similar results have been obtained with Log-nets and FP-nets
where logarithms and feature products have been used instead of the minimum.
This shows that the key to the improvements demonstrated here is mainly the
AND combination of filters pairs and less the way in which the AND is
implemented. Nevertheless, we are looking forward to more general and even
more effective network architectures that may emerge based on the principle of
using the minimum activation in different feature maps.

## References

  * Barth & Watson (2000) Erhardt Barth and Andrew B. Watson.  A Geometric Framework for Nonlinear Visual Coding.  _Optics Express_ , 7(4):155–165, 2000.
  * Bradski (2000) Gary Bradski.  The OpenCV Library.  _Dr. Dobb’s Journal of Software Tools_ , 2000.
  * do Carmo (1976) Manfredo Perdigão do Carmo.  _Differential Geometry of Curves and Surfaces_.  Prentice-Hall, Englewood Cliffs, NJ, 1976.
  * Goodfellow et al. (2014) Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Grüning et al. (2020) Philipp Grüning, Thomas Martinetz, and Erhardt Barth.  Log-nets: Logarithmic feature-product layers yield more compact networks.  In Igor Farkaš, Paolo Masulli, and Stefan Wermter (eds.), _Artificial Neural Networks and Machine Learning – ICANN 2020_ , pp. 79–91, Cham, 2020. Springer International Publishing.  ISBN 978-3-030-61616-8.
  * Grüning et al. (2021) Philipp Grüning, Thomas Martinetz, and Erhardt Barth.  Fp-nets as novel deep networks inspired by vision.  _Journal of Vision_ , “Accepted for publication in the special issue on deep neural networks and biological vision", 2021.
  * Guiducci (1988) Antonio Guiducci.  Corner characterization by differential geometry techniques.  _Pattern Recognition Letters_ , 8(5):311–318, 1988.
  * Han et al. (2017) Dongyoon Han, Jiwhan Kim, and Junmo Kim.  Deep pyramidal residual networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 5927–5935, 2017.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Huang et al. (2017) Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 4700–4708, 2017.
  * Hubel & Wiesel (1965) David H Hubel and Torsten N Wiesel.  Receptive fields and functional architecture in two nonstriate visual areas (18 and 19) of the cat.  _Journal of neurophysiology_ , 28(2):229–289, 1965.
  * Idelbayev (2020) Yerlan Idelbayev.  Proper ResNet implementation for CIFAR10/CIFAR100 in PyTorch.  https://github.com/akamaster/pytorch_resnet_cifar10, 2020.  Accessed: 2020-12-01.
  * Jähne (1995) Bernd Jähne.  _Digital Image Processing_.  Springer, Berlin, 3rd edition, 1995.
  * Krizhevsky et al. (2021) Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-10 (canadian institute for advanced research).  http://www.cs.toronto.edu/~kriz/cifar.html, 2021.
  * Paiton et al. (2020) Dylan M. Paiton, Charles G. Frye, Sheng Y. Lundquist, Joel D. Bowen, Ryan Zarcone, and Bruno A. Olshausen.  Selectivity and robustness of sparse coding networks.  _Journal of Vision_ , 20(12):10–10, 11 2020.  ISSN 1534-7362.  doi: 10.1167/jov.20.12.10.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Pleiss et al. (2017) Geoff Pleiss, Danlu Chen, Gao Huang, Tongcheng Li, Laurens van der Maaten, and Kilian Q Weinberger.  Memory-efficient implementation of densenets.  _arXiv preprint arXiv:1707.06990_ , 2017.
  * Sandler et al. (2018) Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 4510–4520, 2018.
  * Shi & Tomasi (1994) Jianbo Shi and Carlo Tomasi.  Good features to track.  _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 593–600, 1994.
  * Szegedy et al. (2013) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Ulyanov et al. (2016) Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Instance normalization: The missing ingredient for fast stylization.  _arXiv preprint arXiv:1607.08022_ , 2016.
  * Vilankar & Field (2017) Kedarnath P Vilankar and David J Field.  Selectivity, hyperselectivity, and the tuning of v1 neurons.  _Journal of vision_ , 17(9):9–9, 2017.
  * Zetzsche & Barth (1990) Christoph Zetzsche and Erhardt Barth.  Fundamental limits of linear filters in the visual processing of two-dimensional signals.  _Vision Research_ , 30:1111–1117, 1990.
  * Zetzsche et al. (1993) Christoph Zetzsche, Erhardt Barth, and Bernhard Wegmann.  The importance of intrinsically two-dimensional image features in biological vision and picture coding.  In Andrew B. Watson (ed.), _Digital Images and Human Vision_ , pp. 109–38. MIT Press, 10 1993.

##  Appendix A Appendix

###  A.1 Residual connections

If a stride of two is used ($s=2$), average pooling with a kernel size of two
and stride of two is applied to $\mathbf{T}_{0}$. If $d$ is smaller than
$d_{out}$, $\mathbf{T}_{0}$ is padded with $(d_{out}-d)$ all-zero feature
maps. If $d$ is larger than $d_{out}$, a linear recombination without ReLU and
batch normalization computes a reduced version of $\mathbf{T}_{0}$ with
$d_{out}$ feature maps.

###  A.2 Data augmentation

During training, the images were flipped horizontally with a 50% chance.
Furthermore, they were padded with four pixels on each side and randomly
cropped using a $32\times 32$ window. We normalized each channel of an input
image by subtracting the channel’s mean pixel and dividing by the standard
deviation, all derived from the training set.

###  A.3 Percentage of changed predictions

We computed the POCP depending on $Q$ like this:

$\text{POCP}(f,Q)=\frac{1}{|\mathcal{X}_{C10}|}\sum_{\mathbf{I}\in\mathcal{X}_{C10}}\mathbbm{1}(f(\mathbf{I})\neq
f(JPEG(\mathbf{I},Q)));$ (5)

$\mathbbm{1}(S)$ returns a $1$ if $S$ is true, as $0$ otherwise;
$f(\mathbf{I})$ is the model’s class prediction for the input image
$\mathbf{I}$.

###  A.4 Technical details for training

All experiments were conducted with Pytorch (BSD license) (Paszke et al.
(2019)) version "1.9.0+cu102", on a standard computer running on Linux using
Nvidia RTX 2080 GPUs with CUDA version 11.2. Training a DenseNet
$(L=100,k=12)$ took roughly 21 hours, training a ResNet ($N=9$) 3 hours. The
code creating the ResNet was adapted from Idelbayev (2020) (BSD 2-Clause
"Simplified" License) and from Han et al.
(2017)111https://github.com/dyhan0920/PyramidNet-PyTorch. We adapted the
DenseNet code222https://github.com/gpleiss/efficient_densenet_pytorch from
Pleiss et al. (2017) (MIT License). OpenCV uses the Apache 2 license. We
published our code on
Github333https://github.com/pgruening/bio_inspired_min_nets_improve_the_performance_and_robustness_of_deep_networks

###  A.5 Additional results: Densenet

Table 1 shows additional results for the DenseNet models on the Cifar-10
classification task. When regarding minimal errors over all epochs, i.e., the
best result with early stopping, we obtained similar results for the DenseNet
($L=100,k=12$) as reported in the original paper ($4.51\%$): the minimum error
reached by the baseline DenseNet was $4.56\%$ and $4.36\%$ for the Min-Net.

###  A.6 Additional results: JPEG compression

Figure 4 shows the Cifar-10 test errors depending on the $Q$ value. Note that
these plots only provide the results for $Q=100,90,...,60$, and only for the
largest models of each experiment (ResNet: $N=9$, DenseNet: $k=12,L=100$). The
results for $Q=100,90,...,10$ and for all models are given in the Tables 2,3,
4, and 5. Table 2 shows the test error values for the DenseNet experiment and
Table 3 shows the POCP. The test error and POCP for the ResNet experiments are
given in the Tables 4 and 5, respectively. An example image compressed with
different $Q$-values is shown in Figure 5. Note that the POCP of a specific
$Q^{*}$ can be higher than the respective increase of the test error. For
example, $\Delta(Q^{*})$ – i.e., the test error for $Q^{*}=90$ minus the
original error – is lower than the POCP for $Q=90$ since the POCP measures any
change in classification: apart from correct classifications for $Q=100$ being
incorrect for $Q^{*}$, the POCP also counts classifications that are already
incorrect and are now classified as another false class. Furthermore, a few
previously incorrect examples can become correct and decrease $\Delta(Q)$.

Model | k | # Parameters | L | After 300 epochs | Min. over all epochs
---|---|---|---|---|---
|  |  |  | mean | std | min | max | mean | std | min | max
Min-Net | 12 | 751786 | 100 | 4.55 | 0.14 | 4.39 | 4.64 | 4.51 | 0.13 | 4.36 | 4.59
DenseNet | 12 | 769162 | 100 | 4.79 | 0.06 | 4.74 | 4.86 | 4.62 | 0.06 | 4.56 | 4.66
Min-Net | 12 | 298564 | 58 | 5.67 | 0.07 | 5.62 | 5.75 | 5.51 | 0.07 | 5.46 | 5.59
DenseNet | 12 | 314470 | 58 | 5.90 | 0.30 | 5.72 | 6.25 | 5.65 | 0.14 | 5.51 | 5.78
Min-Net | 12 | 57040 | 22 | 9.22 | 0.17 | 9.03 | 9.33 | 8.78 | 0.10 | 8.72 | 8.89
DenseNet | 12 | 71686 | 22 | 9.76 | 0.19 | 9.57 | 9.94 | 9.39 | 0.13 | 9.27 | 9.52
Table 1: Classification results for the DenseNet experiment. Figure 4:
Cifar-10 test error depending on the compression quality.

Model | L | k | Q=100% | 90% | 80% | 70% | 60% | 50% | 40% | 30% | 20% | 10%
---|---|---|---|---|---|---|---|---|---|---|---|---
DenseNet | 22 | 12 | 9.8 | 15.4 | 20.0 | 24.0 | 27.6 | 30.8 | 34.6 | 39.5 | 47.8 | 64.6
DenseNet | 58 | 12 | 5.9 | 10.9 | 15.7 | 20.0 | 24.3 | 27.3 | 31.3 | 36.4 | 45.9 | 63.0
DenseNet | 100 | 12 | 4.8 | 9.9 | 14.6 | 19.1 | 22.8 | 25.9 | 30.1 | 35.2 | 44.5 | 62.6
Min-Net | 22 | 12 | 9.2 | 14.9 | 19.5 | 23.2 | 26.4 | 29.5 | 32.5 | 37.5 | 44.9 | 60.3
Min-Net | 58 | 12 | 5.7 | 10.4 | 15.0 | 19.0 | 22.6 | 25.4 | 28.6 | 34.0 | 43.1 | 62.5
Min-Net | 100 | 12 | 4.6 | 8.8 | 13.6 | 17.2 | 20.9 | 23.8 | 27.6 | 33.1 | 42.5 | 61.4

Table 2: DenseNet: Mean test error on Cifar-10 for JPEG-compressed test sets
$\mathcal{S}_{Q}$

.

Model | L | k | Q=90% | 80% | 70% | 60% | 50% | 40% | 30% | 20% | 10%
---|---|---|---|---|---|---|---|---|---|---|---
DenseNet | 22 | 12 | 12.1 | 17.6 | 21.9 | 25.8 | 29.3 | 33.4 | 38.3 | 46.8 | 64.2
DenseNet | 58 | 12 | 9.2 | 14.7 | 19.3 | 23.5 | 26.4 | 30.5 | 35.7 | 45.3 | 62.7
DenseNet | 100 | 12 | 8.1 | 13.5 | 18.2 | 21.9 | 25.1 | 29.3 | 34.8 | 44.1 | 62.6
Min-DenseNet | 22 | 12 | 11.7 | 16.9 | 21.4 | 24.8 | 28.0 | 31.2 | 36.3 | 43.9 | 60.0
Min-DenseNet | 58 | 12 | 8.3 | 13.7 | 17.8 | 21.6 | 24.6 | 27.9 | 33.5 | 42.5 | 62.4
Min-DenseNet | 100 | 12 | 7.3 | 12.4 | 16.3 | 20.1 | 23.2 | 27.1 | 32.6 | 42.1 | 61.4

Table 3: DenseNet: Mean number of changed predictions on Cifar-10 for JPEG-
compressed test sets $\mathcal{S}_{Q}$

.

Model | N | 100% | 90% | 80% | 70% | 60% | 50% | 40% | 30% | 20% | 10%
---|---|---|---|---|---|---|---|---|---|---|---
Min-Net | 3 | 8.0 | 12.5 | 16.7 | 20.2 | 23.5 | 26.2 | 29.3 | 34.1 | 42.5 | 59.1
Min-Net | 5 | 6.9 | 11.3 | 15.1 | 18.7 | 22.0 | 24.9 | 27.9 | 33.4 | 42.3 | 59.2
Min-Net | 7 | 6.2 | 10.6 | 14.6 | 17.9 | 21.5 | 24.5 | 27.7 | 32.8 | 42.2 | 59.9
Min-Net | 9 | 6.0 | 10.1 | 14.4 | 18.0 | 21.4 | 24.2 | 27.4 | 32.7 | 41.7 | 58.8
ResNet | 3 | 8.3 | 13.2 | 17.4 | 21.0 | 24.5 | 27.6 | 31.1 | 36.0 | 44.1 | 59.8
ResNet | 5 | 7.2 | 11.8 | 16.3 | 20.0 | 23.6 | 26.6 | 30.0 | 35.4 | 44.0 | 59.6
ResNet | 7 | 6.8 | 11.4 | 15.9 | 19.2 | 22.9 | 26.3 | 29.7 | 35.0 | 43.7 | 60.1
ResNet | 9 | 6.3 | 10.9 | 15.3 | 19.0 | 22.4 | 25.6 | 29.2 | 34.5 | 43.4 | 59.1

Table 4: ResNet: Mean test error on Cifar-10 for JPEG-compressed test sets
$\mathcal{S}_{Q}$

.

Model | N | 90% | 80% | 70% | 60% | 50% | 40% | 30% | 20% | 10%
---|---|---|---|---|---|---|---|---|---|---
Min-Net | 3 | 9.5 | 14.5 | 18.4 | 21.8 | 24.7 | 28.0 | 33.1 | 41.8 | 58.8
Min-Net | 5 | 8.5 | 13.2 | 17.1 | 20.6 | 23.7 | 26.8 | 32.5 | 41.6 | 58.8
Min-Net | 7 | 8.1 | 12.8 | 16.7 | 20.3 | 23.3 | 26.6 | 32.0 | 41.4 | 59.7
Min-Net | 9 | 7.8 | 12.6 | 16.6 | 20.2 | 23.0 | 26.3 | 31.7 | 40.9 | 58.5
ResNet | 3 | 10.1 | 15.1 | 19.3 | 22.9 | 26.2 | 29.9 | 34.8 | 43.3 | 59.3
ResNet | 5 | 9.4 | 14.4 | 18.6 | 22.3 | 25.5 | 29.1 | 34.5 | 43.2 | 59.3
ResNet | 7 | 8.9 | 14.0 | 17.9 | 21.8 | 25.1 | 28.8 | 34.2 | 43.1 | 59.8
ResNet | 9 | 8.5 | 13.6 | 17.6 | 21.1 | 24.5 | 28.2 | 33.6 | 42.7 | 58.7

Table 5: ResNet: Mean number of changed predictions on Cifar-10 for JPEG-
compressed test sets $\mathcal{S}_{Q}$

.

Figure 5: JPEG-compression example for different $Q$ values.