# Covering hypergraphs are eulerian

Mateja Šajna111Corresponding author. Email<EMAIL_ADDRESS>Mailing
address: Department of Mathematics and Statistics, University of Ottawa, 150
Louis-Pasteur Private, Ottawa, ON, K1N 6N5, Canada. and Andrew Wagner
University of Ottawa

###### Abstract

An Euler tour in a hypergraph (also called a rank-2 universal cycle or
1-overlap cycle in the context of designs) is a closed walk that traverses
every edge exactly once. In this paper, we define a covering k-hypergraph to
be a non-empty $k$-uniform hypergraph in which every $(k-1)$-subset of
vertices appear together in at least one edge. We then show that every
covering $k$-hypergraph, for $k\geq 3$, admits an Euler tour if and only if it
has at least two edges.

Keywords: Covering hypergraph; Euler tour; rank-2 universal cycle; 1-overlap
cycle; Euler family; interchanging cycle.

##  1 Introduction

An Euler tour of a graph or hypergraph is a closed walk that traverses every
edge exactly once. The complete characterization of graphs that admit an Euler
tour, which was conjectured by Euler in 1741 [6], and proved by Hierholzer and
Wiener in 1873 [7], is a fundamental and accessible result in graph theory.
However, analogous results for hypergraphs have only recently begun to be
explored.

To our knowledge, Lonc and Naroski were the first to extend the notion of an
Euler tour to hypergraphs. In a 2010 paper [10] they showed that the problem
of existence of an Euler tour is NP-complete on the set of $k$-uniform
hypergraphs, for any $k\geq 3$, as well as when restricted to a particular
subclass of 3-uniform hypergraphs.

A Steiner triple (quadruple) system is a 3-uniform (4-uniform, respectively)
hypergraph in which every pair (triple, respectively) of vertices lie together
in exactly one edge. Initial results for Euler tours in Steiner triple and
quadruple systems used different terminology. Namely, in 2012, Dewar and
Stevens [5] proved that every cyclic Steiner triple system of order greater
than three, and every cyclic twofold triple system admits a rank-2 universal
cycle (that is, Euler tour), and in 2013, Horan and Hurlbert showed that for
every admissible order greater than four, there exist a Steiner triple system
[9] and a Steiner quadruple system [8] with a 1-overlap cycle (that is, Euler
tour).

We define a covering $k$-hypergraph, for $k\geq 3$, to be a non-empty
$k$-uniform hypergraph in which every $(k-1)$-subset of vertices appear
together in at least one edge.

In a 2015 paper [2], Bahmanian and Šajna embarked on a systematic study of
eulerian properties of general hypergraphs; some of their techniques and
results will be used in this paper. In particular, they introduced the notion
of an Euler family — a collection of closed trails that jointly traverse each
edge exactly once — and showed that the problem of existence of an Euler
family is polynomial on the class of all hypergraphs. In addition, they proved
that every covering 3-hypergraph with at least two edges admits an Euler
family.

Most recently, the present authors gave a short proof [11] to show that every
triple system — that is, a 3-uniform hypergraph in which every pair of
vertices lie together in the same number of edges — admits an Euler tour as
long as it has at least two edges.

The main result of this paper is as follows.

######  Theorem 1.1.

Let $H$ be a covering $k$-hypergraph, for $k\geq 3$. Then $H$ admits an Euler
tour if and only if it has at least two edges.

Thus, Theorem 1.1 represents a significant improvement on [11], as well as on
the above-mentioned result of [2].

The framework for the proof of Theorem 1.1 is presented in Section 3, while
the technical details are given in Section 4. Here, we also introduce our
main, new technique of interchanging cycles, which resembles the technique of
alternating paths in matching theory.

##  2 Preliminaries

We use hypergraph terminology established in [1, 2], which applies to loopless
graphs as well. Any graph theory terms not explained here can be found in [3].

A hypergraph $H$ is a pair $(V,E)$, where $V$ is a non-empty set, and $E$ is a
multiset of elements from $2^{V}$. The elements of $V=V(H)$ and $E=E(H)$ are
called the vertices and edges of $H$, respectively. The order of $H$ is $|V|$.
A hypergraph of order 1 is called trivial, and a hypergraph with no edges is
called empty.

Distinct vertices $u$ and $v$ in a hypergraph $H=(V,E)$ are called adjacent
(or neighbours) if they lie in the same edge, while a vertex $v$ and an edge
$e$ are said to be incident if $v\in e$. The degree of $v$ in $H$, denoted
$\deg_{H}(v)$, is the number of edges of $H$ incident with $v$. A hypergraph
$H$ is called $k$-uniform if every edge of $H$ has cardinality $k$.

A covering $k$-hypergraph, for $k\geq 3$, is a non-empty $k$-uniform
hypergraph with the property that every $(k-1)$-subset of vertices lie
together in at least one edge.

The incidence graph of a hypergraph $H=(V,E)$ is a bipartite simple graph
$\mathcal{G}(H)$ with vertex set $V\cup E$ and bipartition $\\{V,E\\}$ such
that vertices $v\in V$ and $e\in E$ of $\mathcal{G}(H)$ are adjacent if and
only if $v$ is incident with $e$ in $H$. The elements of $V$ and $E$ are
called v-vertices and e-vertices of $\mathcal{G}(H)$, respectively.

A hypergraph $H^{\prime}=(V^{\prime},E^{\prime})$ is called a subhypergraph of
the hypergraph $H=(V,E)$ if $V^{\prime}\subseteq V$ and $E^{\prime}=\\{e\cap
V^{\prime}:e\in E^{\prime\prime}\\}$ for some submultiset $E^{\prime\prime}$
of $E$. For any subset $V^{\prime}\subseteq V$, we define the subhypergraph of
$H$ induced by $V^{\prime}$, denoted $H[V^{\prime}]$, to be the hypergraph
$(V^{\prime},E^{\prime})$ with $E^{\prime}=\\{e\cap V^{\prime}:e\in E,e\cap
V^{\prime}\neq\emptyset\\}$. Thus, we obtain the subhypergraph induced by
$V^{\prime}$ by deleting all vertices in $V{\backslash}V^{\prime}$ from $V$
and from each edge of $H$, and subsequently deleting all empty edges. By
$H-V^{\prime}$ we denote the subhypergraph of $H$ induced by
$V{\backslash}V^{\prime}$, and for $v\in V$, we write shortly $H-v$ instead of
$H-\\{v\\}$. For any subset $E^{\prime}\subseteq E$, we denote the
subhypergraph $(V,E{\backslash}E^{\prime})$ of $H$ by
$H{\backslash}E^{\prime}$, and for $e\in E$, we write $H{\backslash}e$ instead
of $H{\backslash}\\{e\\}$. For any multiset $E^{\prime}$ of $2^{V}$, the
symbol $H+E^{\prime}$ will denote the hypergraph obtained from $H$ by
adjoining all edges in $E^{\prime}$.

A $v_{0}v_{k}$-walk in $H$ is a sequence $W=v_{0}e_{1}v_{1}e_{2}\ldots
e_{k}v_{k}$ such that $v_{0},\ldots,v_{k}\in V$; $e_{1},\ldots,e_{k}\in E$;
and $v_{i-1},v_{i}\in e_{i}$ with $v_{i-1}\neq v_{i}$ for all $i=1,\ldots,k$.
A walk is said to traverse each of the vertices and edges in the sequence. The
vertices $v_{0},v_{1},\ldots,v_{k}$ are called the anchors of $W$. If
$e_{1},e_{2},\ldots,e_{k}$ are pairwise distinct, then $W$ is called a trail
(strict trail in [1, 2]); if $v_{0}=v_{k}$ and $k\geq 2$, then $W$ is closed.
If $W$ is a closed trail and $v_{0},v_{1},\ldots,v_{k-1}$ are pairwise
distinct, then $W$ is called a cycle; more specifically, a cycle of length
$k$, or $k$-cycle.

A hypergraph $H$ is connected if, for any pair $u,v\in V(H)$, there exists a
$uv$-walk in $H$. A connected component is a maximal connected subhypergraph
of $H$ without empty edges. We call $v\in V(H)$ a cut vertex of $H$, and $e\in
E(H)$ a cut edge of $H$, if $H-v$ and $H{\backslash}e$, respectively, have
more connected components than $H$.

An Euler family of a hypergraph $H$ is a collection of pairwise anchor-
disjoint and edge-disjoint closed trails that jointly traverse every edge of
$H$, and an Euler tour is a closed trail that traverses every edge of $H$.
Thus, an Euler family of cardinality 1 corresponds to an Euler tour. The
closed trails in an Euler family $\mathcal{F}$ are called the components of
$\mathcal{F}$, and an Euler family of $H$ with the smallest number of
components is called minimum. A hypergraph that is either empty or admits an
Euler tour (family) is called eulerian (quasi-eulerian).

##  3 Proof of the main result

All of our work in Section 4 will serve to prove the following result.

######  Theorem 3.1.

Let $H$ be a covering 3-hypergraph with at least two edges. Then $H$ is
eulerian.

###### Proof.

Let $n$ be the order of $H$. If $n\geq 7$, then $H$ is eulerian by Theorem
4.13, and if $3\leq n\leq 6$, then $H$ is eulerian by Lemma 4.14. ∎

Theorem 3.1 will now be used as the basis of induction in the proof of our
main result, which we restate below.

######  Theorem 1.1 .

Let $H$ be a covering $k$-hypergraph, for $k\geq 3$. Then $H$ is eulerian if
and only if it has at least two edges.

###### Proof.

By definition, we know $H$ is non-empty. The necessity is then clear.

To prove sufficiency, we use induction on $k$. For $k=3$, Theorem 3.1 implies
that $H$ is eulerian. Suppose that, for some fixed $k\geq 3$, the statement
holds: that is, any covering $k$-hypergraph with at least two edges is
eulerian.

Let $H=(V,E)$ be a covering $(k+1)$-hypergraph with $|E|\geq 2.$ Fix any $v\in
V$, and let $\mathcal{B}=\\{e{\backslash}\\{v\\}:e\in E,v\in e\\}$ and
$E^{\prime}=\\{e\in E:v\not\in e\\}$. Then let $\mathcal{C}$ be a set obtained
from $E^{\prime}$ by removing an arbitrary vertex from each $e\in E^{\prime}$.
Let $H^{*}=(V{\backslash}\\{v\\},\mathcal{B}\cup\mathcal{C}),$ where
$\mathcal{B}\cup\mathcal{C}$ denotes the multiset union of $\mathcal{B}$ and
$\mathcal{C}$. Then $H^{*}$ is a covering $k$-hypergraph. Since
$|E(H^{*})|=|E(H)|\geq 2$, by the induction hypothesis, we have that $H^{*}$
admits an Euler tour $T$. Replacing each edge in $T$ by the corresponding edge
of $H$, we obtain an Euler tour of $H$.

The result follows by induction. ∎

##  4 Covering 3-hypergraphs

###  4.1 The big tools

The following theorem will allow us to translate our analysis from a
hypergraph to its incidence graph.

######  Theorem 4.1.

[2, Theorem 2.18] Let $H$ be a hypergraph and $G$ its incidence graph. Then
the following hold.

(1)

$H$ is quasi-eulerian if and only if $G$ has a spanning subgraph $G^{\prime}$
such that $\text{deg}_{G^{\prime}}(e)=2$ for all $e\in E(H)$, and
$\text{deg}_{G^{\prime}}(v)$ is even for all $v\in V(H)$.

(2)

$H$ is eulerian if and only if $G$ has a spanning subgraph $G^{\prime}$ with
at most one non-trivial connected component such that
$\text{deg}_{G^{\prime}}(e)=2$ for all $e\in E(H)$, and
$\text{deg}_{G^{\prime}}(v)$ is even for all $v\in V(H)$.∎

aaa

The proof of Theorem 4.1 reveals that each edge $ve$ of $G^{\prime}$
corresponds to a sequence $ve$ or $ev$ in a component of the Euler family
$\mathcal{F}$. Consequently, the components of $\mathcal{F}$ are in bijective
correspondence with the non-trivial connected components of $G^{\prime}$. We
will henceforth call $G^{\prime}$ the subgraph of $G$ corresponding to
$\mathcal{F}$, and denote it by $G_{\mathcal{F}}$. An edge $e\in E(G)$ will be
called a $G_{\mathcal{F}}$-edge if $e\in E(G_{\mathcal{F}})$, and a
non-$G_{\mathcal{F}}$-edge otherwise.

We are now prepared to introduce the main tool that will be used throughout
this section. Note that we define the symmetric difference of simple graphs
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, denoted $G_{1}\Delta G_{2}$,
as the graph $(V_{1}\cup V_{2},E_{1}\Delta E_{2})$, where $E_{1}\Delta E_{2}$
is the symmetric difference of $E_{1}$ and $E_{2}$.

Figure 1: The incidence graph of a 3-uniform hypegraph with subgraphs
$G_{\mathcal{F}}$ (left) and $G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta
C$ (right). Black (grey) edges are those in (not in) the subgraph
corresponding to the Euler family, and dashed edges represent the
$\mathcal{F}$-interchanging (in fact, $\mathcal{F}$-diminishing) cycle $C$.

######  Definition 4.2.

Let $H$ be a hypergraph with an Euler family $\mathcal{F}$ and incidence graph
$G$, and let $G_{\mathcal{F}}$ be the subgraph of $G$ corresponding to
$\mathcal{F}$.

A cycle $C$ of $G$ is called $\mathcal{F}$-interchanging if
$\deg_{G_{\mathcal{F}}\cap C}(e)=1$ for all e-vertices $e\in E(H)\cap V(C)$.
If $C$ is an $\mathcal{F}$-interchanging cycle of $G$ and
$G_{\mathcal{F}}\Delta C$ has fewer non-trivial connected components than
$G_{\mathcal{F}}$, then $C$ is an $\mathcal{F}$-diminishing cycle of $G$.

See Figure 1 for an example of an $\mathcal{F}$-interchanging (in fact,
$\mathcal{F}$-diminishing) cycle. Note that in all figures, the incidence
graph of a hypergraph will be drawn with v-vertices on the left.

######  Lemma 4.3.

Let $H$ be a hypergraph with an Euler family $\mathcal{F}$ and incidence graph
$G$, and let $G_{\mathcal{F}}$ be the subgraph of $G$ corresponding to
$\mathcal{F}$.

If $C$ is an $\mathcal{F}$-interchanging cycle of $G$, then
$G_{\mathcal{F}}\Delta C$ is a subgraph of $G$ corresponding to an Euler
family of $H$.

###### Proof.

For all $x\in V(G)$, we have that

$\deg_{G_{\mathcal{F}}\Delta
C}(x)=\deg_{G_{\mathcal{F}}}(x)+\deg_{C}(x)-2\deg_{G_{\mathcal{F}}\cap C}(x),$

so it is clear that in $G_{\mathcal{F}}\Delta C$, every v-vertex has even
degree, and every e-vertex has degree 2. Hence, by Theorem 4.1, the subgraph
$G_{\mathcal{F}}\Delta C$ corresponds to an Euler family of $H$. ∎

The general approach to proving Theorem 3.1 will be as follows: we start with
an Euler family $\mathcal{F}$ of $H$, which is guaranteed to exist by Theorem
4.4 below, and then use an $\mathcal{F}$-diminishing cycle to construct an
Euler family with fewer components.

######  Theorem 4.4.

[2, Corollary 5.3] Let $H$ be a covering 3-hypergraph with at least two edges.
Then $H$ is quasi-eulerian.∎

###  4.2 Technical lemmas

In this section, we state the technical lemmas needed to prove Theorem 3.1.

######  Lemma 4.5.

Let $G$ be a connected loopless graph. If $G$ has a block of order $k\geq 2$,
then it has at least $k$ vertices that are not cut vertices.

###### Proof.

Let ${\cal B}$ be the block tree of $G$; that is, the bipartite graph whose
vertices are the blocks and the cut vertices of $G$, with $v$ and $B$ adjacent
in ${\cal B}$ if and only if $v$ is a cut vertex of $G$ and $B$ is a block of
$G$ containing $v$. Choose a block $B$ of order $k$ to be the root of the tree
${\cal B}$, and observe that any leaf of ${\cal B}$ must be a block. If $v\in
V(B)$ is a cut vertex of $G$, consider any block $B^{\prime}$ that is a leaf
in the subtree of ${\cal B}$ rooted at $v$. Since $G$ is loopless,
$B^{\prime}$ has at least two vertices, and since $B^{\prime}$ is a leaf in
${\cal B}$, only one of them is a cut vertex of $G$. Hence each $v\in V(B)$ is
either not a cut vertex of $G$, or else the subtree rooted at $v$ contains a
vertex that is not a cut vertex of $G$. The result follows. ∎

For the following four results — Corollary 4.6 through Corollary 4.9 — we
assume that $H$ is an arbitrary hypergraph (not necessarily covering or
3-uniform) with an Euler family $\mathcal{F}$ and incidence graph $G$, and
$G_{\mathcal{F}}$ is the subgraph of $G$ corresponding to $\mathcal{F}$.

######  Corollary 4.6.

Let $G_{1}$ be a non-trivial connected component of $G_{\mathcal{F}}$. Then at
least two v-vertices of $G_{1}$ are not cut vertices of $G_{\mathcal{F}}$.
Furthermore, if $G_{1}$ has a cycle of length $2k$, then at least $k$
v-vertices of $G_{1}$ are not cut vertices of $G_{\mathcal{F}}$.

###### Proof.

Since the e-vertices of $G_{\mathcal{F}}$ each have degree 2, observe that
$G_{\mathcal{F}}$ is the incidence graph of a loopless graph (2-uniform
hypergraph) $H$, and $G_{1}$ is the incidence graph of a non-trivial connected
component $H_{1}$ of $H$. A cycle $C$ of $G_{1}$ corresponds to a cycle of
$H_{1}$ whose anchors are the v-vertices of $C$ [1, Lemma 3.6], and cut
vertices of $G_{1}$ that are v-vertices correspond to cut vertices of $H_{1}$
[1, Theorem 3.23]. Since $H_{1}$ has a block of order at least 2, and any
cycle of $H_{1}$ is contained in a block, the result follows by applying Lemma
4.5 to $H_{1}$. ∎

a

######  Lemma 4.7.

Let $C$ be an $\mathcal{F}$-interchanging cycle in $G$, and let
$G_{1},\ldots,G_{k}$ be all of the connected components of $G_{\mathcal{F}}$
that contain the vertices of $C$. Assume that $G_{i}{\backslash}E(C)$, for
each $i=1,\ldots,k$, has at most one non-trivial connected component. Then
$G^{*}=(G_{\mathcal{F}}\Delta C)[V(G_{1})\cup\ldots\cup V(G_{k})]$ has at most
one non-trivial connected component.

###### Proof.

Write $C$ as

$C=u_{0}W_{0}v_{0}u_{1}W_{1}v_{1}\ldots u_{\ell-1}W_{\ell-1}v_{\ell-1}u_{0},$

where each $W_{i}$, for $i\in\mathds{Z}_{\ell}$, is a maximal subwalk of $C$
whose vertices lie in a single connected component of $G_{\mathcal{F}}$, and
$u_{i}$ and $v_{i}$ are its endpoints. Let $G_{j_{i}}$ be the connected
component of $G_{\mathcal{F}}$ containing the $u_{i}v_{i}$-walk $W_{i}$, and
suppose $G_{j_{i}}$ is non-trivial. Then $u_{i}$ and $v_{i}$ cannot be
isolated in $G_{j_{i}}$. If they were isolated in $G_{j_{i}}{\backslash}E(C)$,
then each would be incident with two $G_{\mathcal{F}}$-edges of $C$ because
$G_{j_{i}}$ is an even graph — a contradiction. Hence $u_{i}$ and $v_{i}$ lie
in the unique non-trivial connected component of $G_{j_{i}}{\backslash}E(C)$.

Thus $C$ traverses vertices in all of the non-trivial connected components of
$G_{i}{\backslash}E(C)$, for $i=1,\ldots,k$. Since the edges
$v_{0}u_{1},v_{1}u_{2},\ldots,v_{\ell-1}u_{0}$ link these non-trivial
components in a circular fashion,
$G^{*}=\bigcup_{i=1}^{k}(G_{i}{\backslash}E(C))+\\{v_{i}u_{i+1}:i\in\mathds{Z}_{\ell}\\}$
has at most one non-trivial connected component. ∎

a

######  Corollary 4.8.

Let $C$ be an $\mathcal{F}$-interchanging cycle of $G$. If the
$G_{\mathcal{F}}$-edges of $C$ lie in distinct connected components of
$G_{\mathcal{F}}$, then $C$ is an $\mathcal{F}$-diminishing cycle.

###### Proof.

Since $C$ has at least two $G_{\mathcal{F}}$-edges, it traverses vertices from
at least two non-trivial connected components of $G_{\mathcal{F}}$. Each such
component $G_{i}$ is an even graph with $|E(G_{i})\cap E(C)|\leq 1$, so
$G_{i}{\backslash}E(C)$ is connected. Applying Lemma 4.7, we conclude that the
number of non-trivial connected components of $G_{\mathcal{F}}\Delta C$ is
less than that of $G_{\mathcal{F}}$, so $C$ is an $\mathcal{F}$-diminishing
cycle. ∎

a

######  Corollary 4.9.

Let $C$ be an $\mathcal{F}$-interchanging cycle in $G$.

(1)

If the v-vertices of $C$ lie in distinct connected components
$G_{1},\ldots,G_{k}$ of $G_{\mathcal{F}}$, at least two of which are non-
trivial, and none of these v-vertices are cut vertices of $G_{\mathcal{F}}$,
then $C$ is an $\mathcal{F}$-diminishing cycle.

(2)

If in addition, $C$ traverses a v-vertex in every non-trivial connected
component of $G_{\mathcal{F}}$, then $G_{\mathcal{F}}\Delta C$ is a subgraph
of $G$ corresponding to an Euler tour of $H$.

###### Proof.

(1) Take any $i\in\\{1,\ldots,k\\}$ such that $G_{i}$ is non-trivial, and let
$v$ be a v-vertex in $V(C)\cap V(G_{i})$. Since $v$ is not a cut vertex of
$G_{\mathcal{F}}$, we have that $G_{i}-v$ is connected. It follows that
$G_{i}{\backslash}E(C)$ has at most one non-trivial connected component, and
Lemma 4.7 implies that $(G_{\mathcal{F}}\Delta C)[V(G_{1})\cup\ldots\cup
V(G_{k})]$ has just one non-trivial connected component. Since
$G_{\mathcal{F}}[V(G_{1})\cup\ldots\cup V(G_{k})]$ has at least two non-
trivial connected components, we conclude that $C$ is an
$\mathcal{F}$-diminishing cycle.

(2) Now $(G_{\mathcal{F}}\Delta C)[V(G_{1})\cup\ldots\cup V(G_{k})]$ has
exactly one non-trivial connected component and it contains all vertices of
$G_{\mathcal{F}}\Delta C$ that are not isolated. Hence $G_{\mathcal{F}}\Delta
C$ has exactly one non-trivial connected component, and it corresponds to an
Euler tour of $H$ by Theorem 4.1. ∎

a

######  Corollary 4.10.

Let $H$ be a covering 3-hypergraph with an Euler family $\mathcal{F}$ such
that $G_{\mathcal{F}}$ has at least three connected components. Then $H$ is
eulerian.

###### Proof.

First, observe that $G_{\mathcal{F}}$ has at most one trivial connected
component, for if $u$ and $v$ are distinct v-vertices that are isolated in
$G_{\mathcal{F}}$, then any edge of $H$ containing both $u$ and $v$ is not
traversed by $\mathcal{F}$. Hence $G_{\mathcal{F}}$ has at least two non-
trivial connected components.

Let $G_{1},\ldots,G_{k}$ be the connected components of $G_{\mathcal{F}}$. For
each $i\in\\{1,\ldots,k\\}$, choose a vertex $v_{i}$ in $G_{i}$ such that
$v_{i}$ is not a cut vertex of $G_{i}$. If $G_{i}$ is non-trivial, then this
is possible by Lemma 4.5; otherwise, the unique vertex of $G_{i}$ is not a cut
vertex of $G_{i}$. As no two vertices among $v_{1},\ldots,v_{k}$ lie in the
same connected component of $G_{\mathcal{F}}$, every e-vertex is adjacent in
$G_{\mathcal{F}}$ to at most one of them, and hence no three of these vertices
lie in the same edge of $H$. Therefore, there exist e-vertices
$e_{1},\ldots,e_{k}$ such that $C=v_{1}e_{1}v_{2}\ldots v_{k}e_{k}v_{1}$ is a
cycle in $G$. Moreover, each $e_{i}$ is incident with exactly one
$G_{\mathcal{F}}$-edge of $C$, so $C$ is an $\mathcal{F}$-interchanging cycle.
Since $C$ satisfies the conditions of Corollary 4.9(2), we conclude that $H$
is eulerian. ∎

a

######  Corollary 4.11.

Let $H$ be a covering 3-hypergraph and $\mathcal{F}$ a minimum Euler family of
$H$. If $H$ is not eulerian, then the following hold.

(1)

$|\mathcal{F}|=2$ and $G_{\mathcal{F}}$ has no isolated vertices.

(2)

If $C$ is an $\mathcal{F}$-interchanging cycle of $G$, then
$G_{\mathcal{F}}\Delta C$ corresponds to a minimum Euler family of $H$.

(3)

$G$ has no $\mathcal{F}$-diminishing cycle.

###### Proof.

(1) By Corollary 4.10, $G_{\mathcal{F}}$ has exactly two connected components,
and both must be non-trivial. Hence $|\mathcal{F}|=2$ and $G_{\mathcal{F}}$
has no isolated vertices.

(2) By Lemma 4.3, the graph $G_{\mathcal{F}}\Delta C$ corresponds to an Euler
family $\mathcal{F}^{\prime}$ of $H$, and by Corollary 4.10, it has at most
two connected components. Hence $\mathcal{F}^{\prime}$ is another minimum
Euler family of $H$.

(3) This statement follows immediately from (2). ∎

###  4.3 Case $n\geq 7$

In this section, we prove Theorem 3.1 for $n\geq 7$; that is, we show that all
covering 3-hypergraphs of order at least 7 are eulerian. This case is restated
below as Theorem 4.13.

Lemma 4.12 will furnish our proof with most of the details needed to set up
the case work. In Theorem 4.13, we will begin with a minimum Euler family
$\mathcal{F}$ for $H$ that has two components and minimizes the degree of an
arbitrary, but fixed, vertex $v_{0}$ in the graph $G_{\mathcal{F}}$. By
Corollary 4.11(2), we need only find an $\mathcal{F}$-interchanging cycle $C$
— not necessarily an $\mathcal{F}$-diminishing cycle — that traverses $v_{0}$
and such that the Euler family corresponding to $G_{\mathcal{F}}\Delta C$
contradicts the assumptions on $\mathcal{F}$.

######  Lemma 4.12.

Let $H$ be a covering 3-hypergraph of order $n\geq 7$ that is not eulerian.
Let $G$ be the incidence graph of $H$ and $v_{0}$ a v-vertex of $G$. Let
$\mathcal{F}$ be a minimum Euler family of $H$, and $G_{\mathcal{F}}$ the
subgraph of $G$ corresponding to $\mathcal{F}$, with the property that
$\deg_{G_{\mathcal{F}}}(v_{0})$ is minimum over all minimum Euler families of
$H$.

Assume that $\deg_{G_{\mathcal{F}}}(v_{0})\geq 2$, so there exist distinct
e-vertices $e_{1},e_{2}\in V(G)$ such that $v_{0}e_{1},v_{0}e_{2}\in
E(G_{\mathcal{F}}).$ Let $e_{1}=v_{0}v_{1}a$ and $e_{2}=v_{0}v_{2}b$ for some
$v_{1},v_{2},a,b\in V(H)$ such that $v_{1}e_{1}$ and $v_{2}e_{2}$ are
$G_{\mathcal{F}}$-edges.

Then the following hold.

(1)

Vertices $a$ and $b$ are distinct.

(2)

Suppose there exists an e-vertex $e$ of $G$ with $e\not\in\\{e_{1},e_{2}\\}$
such that $ea,eb\in E(G)$. Then both $ea$ and $eb$ are
$G_{\mathcal{F}}$-edges.

(3)

Vertices $a$ and $b$ are connected in $G_{\mathcal{F}}$.

(4)

Let $x\in V(H){\backslash}\\{v_{0},v_{1},v_{2}\\}$ be a v-vertex disconnected
from $a$ and $b$ in $G_{\mathcal{F}}$. Then there exists an edge $e_{x}=abx$
in $H$. Any edge of $H$ containing $x$ and $a$, or $x$ and $b$, must likewise
contain $a$ and $b$; and $xe_{x}$ is a non-$G_{\mathcal{F}}$-edge.

(5)

Vertices $a$ and $b$ are disconnected from $v_{0}$ in $G_{\mathcal{F}}$.

Figure 2: Relevant subgraphs of $G$ in Lemma 4.12. The set-up (left);
$G_{\mathcal{F}}$ and $C_{1}$ (centre), and
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C_{1}$ and $C_{2}$ (right) in
the proof of (3). Thick black (grey) edges are those in (not in) the subgraph
corresponding to the Euler family; the status of thin edges is unknown. Dashed
edges represent the interchanging cycle. Note that exactly one of the two thin
edges incident with each of $e_{3}$, $e_{4}$, and $e_{5}$ is in
$G_{\mathcal{F}}$ ($G_{\mathcal{F}^{\prime}}$).

###### Proof.

See Figure 2 (left). Note that by Corollary 4.11(1), $G_{\mathcal{F}}$ has
exactly two connected components, both non-trivial, and by Corollary 4.11(2)
and the assumption on $\mathcal{F}$, there is no $\mathcal{F}$-interchanging
cycle $C$ in $G$ such that $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$.

(1) If $a=b$, then $C=v_{0}e_{1}ae_{2}v_{0}$ is an $\mathcal{F}$-interchanging
cycle with $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a contradiction.

(2) If at least one (and hence exactly one) of $ea$ and $eb$ is a
non-$G_{\mathcal{F}}$-edge, then $C=v_{0}e_{1}aebe_{2}v_{0}$ is an
$\mathcal{F}$-interchanging cycle with $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a contradiction. Therefore, both
$ea$ and $eb$ are $G_{\mathcal{F}}$-edges, as claimed.

(3) Suppose $a$ and $b$ are disconnected in $G_{\mathcal{F}}$. Since $H$ is a
covering 3-hypergraph, there exists an edge $e\in E(H)$ containing both $a$
and $b$. By our supposition, one of $ea$ and $eb$ is necessarily a
non-$G_{\mathcal{F}}$-edge, so (2) implies that $e=e_{1}$ or $e=e_{2}$.
Without loss of generality, assume $e=e_{1}$; hence $v_{1}=b$.

Observe that $v_{0},b,$ and $v_{2}$ lie in the same connected component of
$G_{\mathcal{F}}$, so $a$ and $v_{2}$ are disconnected in $G_{\mathcal{F}}$.
Let $e_{3}\in E(H)$ be an edge containing $a$ and $v_{2}$. Then exactly one of
$v_{2}e_{3}$ and $ae_{3}$ is not in $G_{\mathcal{F}}$, and
$C_{1}=ae_{1}be_{2}v_{2}e_{3}a$ is an $\mathcal{F}$-interchanging cycle; see
Figure 2 (centre).

Define $\mathcal{F}^{\prime}$ to be an Euler family corresponding to
$G_{\mathcal{F}}\Delta C_{1}$, so
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C_{1}$. Since $H$ is not
eulerian, Corollary 4.11 implies that $G_{\mathcal{F}^{\prime}}$ has exactly
two connected components, both non-trivial. It is easy to verify — see Figure
2 (right) — that vertices $v_{0}$, $a$, and $b$ are mutually connected in
$G_{\mathcal{F}^{\prime}}$. Since every v-vertex is connected in
$G_{\mathcal{F}}$ to either $a$ or $v_{2}$, if $v_{0}$ and $v_{2}$ are
connected in $G_{\mathcal{F}^{\prime}}$, then $G_{\mathcal{F}^{\prime}}$ is
connected, a contradiction. Thus $v_{0}$ and $v_{2}$ are disconnected in
$G_{\mathcal{F}^{\prime}}$.

By Corollary 4.11(1), vertex $a$ is not isolated in $G_{\mathcal{F}}$. Let
$c\neq a$ be any v-vertex connected to $a$ in $G_{\mathcal{F}}$. We shall
construct an $\mathcal{F}^{\prime}$-interchanging cycle traversing $v_{0}$,
$b$, $v_{2}$, and $c$.

Let $e_{4},e_{5}\in E(H)$ be such that $e_{4}$ contains $b$ and $c$, and
$e_{5}$ contains $v_{2}$ and $c$. As
$e_{4},e_{5}\not\in\\{e_{1},e_{2},e_{3}\\}$, e-vertices $e_{4}$ and $e_{5}$
have the same neighbours in $G_{\mathcal{F}}$ as in
$G_{\mathcal{F}^{\prime}}$. If $e_{4}=e_{5}$, then $be_{4}$ and $v_{2}e_{4}$
are $G_{\mathcal{F}}$-edges, and hence $G_{\mathcal{F}^{\prime}}$-edges, a
contradiction. Hence $e_{4}\neq e_{5}$. Moreover, exactly one of $be_{4}$ and
$ce_{4}$, and exactly one of $v_{2}e_{5}$ and $ce_{5}$, is a
non-$G_{\mathcal{F}}$-edge.

It follows that $C_{2}=v_{0}e_{1}be_{4}ce_{5}v_{2}e_{2}v_{0}$ is an
$\mathcal{F}^{\prime}$-interchanging cycle with
$\deg_{G_{\mathcal{F}^{\prime}}\Delta
C_{2}}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$; see Figure 2 (right). Since
$|\mathcal{F}^{\prime}|=2$ and
$\deg_{G_{\mathcal{F}^{\prime}}}(v_{0})=\deg_{G_{\mathcal{F}}}(v_{0})$,
Corollary 4.11(2) yields a contradiction.

We conclude that $a$ and $b$ are connected in $G_{\mathcal{F}}$.

(4) Let $x\in V(H){\backslash}\\{v_{0},v_{1},v_{2}\\}$ be a v-vertex
disconnected in $G_{\mathcal{F}}$ from $a$ and $b$. Since $H$ is a covering
3-hypergraph, there exist edges $e\in E(H)$ containing $a$ and $x$, and
$e^{\prime}\in E(H)$ containing $b$ and $x$. If $e\neq e^{\prime}$, then
$C=v_{0}e_{1}aexe^{\prime}be_{2}v_{0}$ is an $\mathcal{F}$-interchanging cycle
with $\deg_{G_{\mathcal{F}}\Delta C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a
contradiction. Hence $e=abx=e^{\prime}$, and $ae$ and $be$ are
$G_{\mathcal{F}}$-edges by (2), so $xe$ is a non-$G_{\mathcal{F}}$-edge.

Figure 3: $G_{\mathcal{F}}$ and $C$ (left), and
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C$ in the proof of Lemma
4.12(5). Thick black (grey) edges are those in (not in) the subgraph
corresponding to the Euler family, and dashed edges represent the
$\mathcal{F}$-interchanging cycle $C$.

(5) Suppose that $a$ and $b$ lie in the same connected component of
$G_{\mathcal{F}}$ as $v_{0}$. Call this component $G_{1}$, and let $G_{2}$ be
the other connected component. By Corollary 4.11(1), component $G_{2}$ has at
least two v-vertices, say $c$ and $d$. By (4), there are edges $e_{c}=abc$ and
$e_{d}=abd$ of $H$ such that $ce_{c}$ and $de_{d}$ are
non-$G_{\mathcal{F}}$-edges.

Now, there exists an edge $e_{3}\in E(H)$ containing $v_{0}$ and $c$, and
$e_{3}\not\in\\{e_{1},e_{2}\\}$. Let $C=v_{0}e_{1}ae_{c}ce_{3}v_{0}$; see
Figure 3 (left). Then $C$ is an $\mathcal{F}$-interchanging cycle because $c$
and $v_{0}$ are disconnected in $G_{\mathcal{F}}$. If $v_{0}e_{3}\in
V(G_{1})$, then there are two $G_{\mathcal{F}}$-edges of $C$ incident with
$v_{0}$ and so $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a contradiction. Hence $v_{0}e_{3}$
is a non-$G_{\mathcal{F}}$-edge and $e_{3}c\in E(G_{2})$. Since $G_{2}$ is an
even graph and $G_{2}{\backslash}E(C)=G_{2}{\backslash}ce_{3}$, we have that
$G_{2}{\backslash}E(C)$ is connected.

Since $G_{1}$ is an even graph, we have that $G_{1}{\backslash}v_{0}e_{1}$ is
connected, and since $ae_{c}$ is an edge in a cycle of
$G_{1}{\backslash}v_{0}e_{1}$, we have that
$(G_{1}{\backslash}v_{0}e_{1}){\backslash}ae_{c}=G_{1}{\backslash}E(C)$ is
connected; see Figure 3 (right). Then, by Lemma 4.7, $G_{\mathcal{F}}\Delta C$
has just one non-trivial connected component, contradicting the fact that $H$
is not eulerian.

We conclude that $a$ and $b$ are disconnected from $v_{0}$ in
$G_{\mathcal{F}}$. ∎

With the setup afforded by Lemma 4.12, we know a lot about five of the
v-vertices of $G_{\mathcal{F}}$, namely $v_{0},v_{1},v_{2},a,$ and $b$. In
Theorem 4.13, we need only investigate the positions of two other vertices,
and this will be enough to show that there must be an
$\mathcal{F}$-interchanging cycle that contradicts our assumption that $H$ is
not eulerian.

######  Theorem 4.13.

Let $H$ be a covering 3-hypergraph of order $n\geq 7$. Then $H$ is eulerian.

###### Proof.

Suppose $H$ is not eulerian. Let $G$ be the incidence graph of $H$, and fix
some v-vertex $v_{0}$. By Theorem 4.4, $H$ is quasi-eulerian, so let
$\mathcal{F}$ be a minimum Euler family of $H$ with the property that
$\deg_{G_{\mathcal{F}}}(v_{0})$ is minimum over all minimum Euler families of
$H$. By Corollary 4.11, we know that $|\mathcal{F}|=2$ and that $v_{0}$ is not
isolated in $G_{\mathcal{F}}$, so $\deg_{G_{\mathcal{F}}}(v_{0})\geq 2$.
Moreover, by the same corollary, $G$ has no $\mathcal{F}$-diminishing cycle,
and no $\mathcal{F}$-interchanging cycle $C$ such that
$\deg_{G_{\mathcal{F}}\Delta C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$.

We have distinct e-vertices $e_{1},e_{2}\in V(G)$ such that
$v_{0}e_{1},v_{0}e_{2}\in E(G_{\mathcal{F}}).$ Let $e_{1}=v_{0}v_{1}a$ and
$e_{2}=v_{0}v_{2}b$ for some v-vertices $v_{1}$, $a$, $v_{2}$, and $b$.
Without loss of generality, let $v_{1}e_{1}$ and $v_{2}e_{2}$ be
$G_{\mathcal{F}}$-edges, and $ae_{1}$ and $be_{2}$ be
non-$G_{\mathcal{F}}$-edges. Now $H$ satisfies the assumptions of Lemma 4.12
with exactly the same set-up. We have that $v_{0}$, $v_{1},$ and $v_{2}$ lie
in one connected component, $G_{1}$, of $G_{\mathcal{F}}$, and $a$ and $b$ lie
in the other connected component, $G_{2}$, of $G_{\mathcal{F}}$. Note that
$a\neq b$, but it is possible that $v_{1}=v_{2}$.

Since $|V(H)|\geq 7$, we must have at least two v-vertices in
$G_{\mathcal{F}}$ besides $v_{0},v_{1},v_{2},a$, and $b$. We shall complete
the proof by splitting into cases depending on where two of these additional
v-vertices lie.

Case 1: there exist v-vertices $c\in
V(G_{1}){\backslash}\\{v_{0},v_{1},v_{2}\\}$ and $d\in
V(G_{2}){\backslash}\\{a,b\\}$.

Since $c$ is disconnected in $G_{\mathcal{F}}$ from $a$ and $b$, by Lemma
4.12(4), there exists an edge $e_{c}=abc$.

Let $e_{3}\in E(H)$ be an edge containing $a$ and $d$, and suppose $ae_{3}$ or
$de_{3}$ is a non-$G_{\mathcal{F}}$-edge. There exists an edge $f\in E(H)$
containing $c$ and $d$, and $f\neq e_{3}$ because $e_{3}$ must contain three
v-vertices of $G_{2}$. Hence $C=v_{0}e_{1}ae_{3}dfce_{c}be_{2}v_{0}$ is an
$\mathcal{F}$-interchanging cycle with $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a contradiction. Hence $ae_{3}$ and
$de_{3}$ are $G_{\mathcal{F}}$-edges.

Similarly, let $e_{4}\in E(H)$ be an edge containing $b$ and $d$, and conclude
that $be_{4}$ and $de_{4}$ are $G_{\mathcal{F}}$-edges. (Note that this also
implies that $e_{3}\neq e_{4}$.)

Let $x$ be the v-vertex such that $e_{3}=adx$. If $x=b$, then
$C=v_{0}e_{1}ae_{3}be_{2}v_{0}$ is an $\mathcal{F}$-interchanging cycle with
$\deg_{G_{\mathcal{F}}\Delta C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a
contradiction. Hence $x\neq b$.

If $x\in V(G_{2})$ and $f$ is an edge containing $x$ and $c$, then
$C=v_{0}e_{1}ae_{3}xfce_{c}be_{2}v_{0}$ is an $\mathcal{F}$-interchanging
cycle with $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a contradiction. Hence $x\in
V(G_{1})$.

If $x\in\\{v_{0},v_{1}\\}$, then $C=xe_{1}ae_{3}x$ is an
$\mathcal{F}$-interchanging cycle with just one $G_{\mathcal{F}}$-edge in each
of $G_{1}$ and $G_{2}$. By Corollary 4.8, $C$ is an $\mathcal{F}$-diminishing
cycle, a contradiction. Thus $x\not\in\\{v_{0},v_{1}\\}$.

If $x\in V(G_{1}){\backslash}\\{v_{0},v_{1},v_{2}\\}$, then by Lemma 4.12(4),
there exists an edge $e_{x}=abx$, and $xe_{x}$ is a
non-$G_{\mathcal{F}}$-edge. Then $C=v_{0}e_{1}ae_{3}xe_{x}be_{2}v_{0}$ is an
$\mathcal{F}$-interchanging cycle with $\deg_{G_{\mathcal{F}}\Delta
C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a contradiction.

We thus conclude that $x=v_{2}$ (and $v_{1}\neq v_{2}$), so $e_{3}=adv_{2}$.
By an analogous argument (swapping the roles of $a$ and $b$, of $v_{1}$ and
$v_{2}$, and of $e_{1}$ and $e_{2}$), we have that $e_{4}=bdv_{1}$.

Figure 4: $G_{\mathcal{F}}$ (left) and
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C$ (right) in Case 1. Thick
black (grey) edges are those in (not in) the subgraph corresponding to the
Euler family, and dashed edges represent the $\mathcal{F}$-interchanging cycle
$C$. Note that exactly one of the two thin edges incident with $e_{5}$ is in
$G_{\mathcal{F}}$ ($G_{\mathcal{F}^{\prime}}$).

Let $e_{5}$ be an edge containing $c$ and $d$, and note that
$e_{5}\not\in\\{e_{2},e_{c},e_{3}\\}$. Then $C=be_{c}ce_{5}de_{3}v_{2}e_{2}b$.
is an $\mathcal{F}$-interchanging cycle; see Figure 4 (left). Let
$\mathcal{F}^{\prime}$ be an Euler family corresponding to
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C$. By Lemma 4.11,
$G_{\mathcal{F}^{\prime}}$ has exactly two connected components, both non-
trivial, and it can be verified easily — see Figure 4 (right) — that
v-vertices $v_{0}$, $v_{1}$, $b$, and $d$ are mutually connected in
$G_{\mathcal{F}^{\prime}}$, as are $v_{2}$, $a$, and $c$. Since every vertex
is connected in $G_{\mathcal{F}}$, and hence in $G_{\mathcal{F}^{\prime}}$, to
one of these seven v-vertices, we conclude that $v_{0}$, $v_{1}$, $b$, and $d$
lie in one connected component of $G_{\mathcal{F}^{\prime}}$, and $v_{2},a,$
and $c$ lie in the other.

Observe that, since $G_{\mathcal{F}^{\prime}}$ satisfies the initial
assumptions made of $G_{\mathcal{F}}$, we may apply Lemma 4.12 to
$G_{\mathcal{F}^{\prime}}$, with the roles of $v_{2}$ and $b$ swapped. In
addition, what we know so far on Case 1 applies to $G_{\mathcal{F}^{\prime}}$
as well, with the roles of $v_{2}$ and $b$, of $c$ and $d$, and of $e_{c}$ and
$e_{3}$ swapped.

In particular, we deduce that there exists an e-vertex $e_{6}=v_{1}v_{2}c$
that plays the same role in $G_{\mathcal{F}^{\prime}}$ as $e_{4}=v_{1}bd$ does
in $G_{\mathcal{F}}$. Let
$C^{\prime}=v_{0}e_{1}ae_{c}be_{4}v_{1}e_{6}v_{2}e_{2}v_{0}$, and observe that
$C^{\prime}$ is an $\mathcal{F}^{\prime}$-interchanging cycle with
$\deg_{G_{\mathcal{F}^{\prime}}\Delta
C^{\prime}}(v_{0})<\deg_{G_{\mathcal{F}^{\prime}}}(v_{0})$, a contradiction.

Case 2: $a$ and $b$ are the only v-vertices in $G_{2}$.

Let $X=V(H){\backslash}\\{v_{0},v_{1},v_{2},a,b\\}$, so $|X|\geq 2$.

Suppose first that $v_{1}\neq v_{2}$. Let $e$ be an edge of $H$ containing
$v_{2}$ and $a$.

If $e=v_{0}v_{2}a$, then $C=v_{0}e_{1}aev_{0}$ is an
$\mathcal{F}$-interchanging cycle. If $v_{0}e\not\in E(G_{1})$, then $C$ is an
$\mathcal{F}$-diminishing cycle by Corollary 4.8. Otherwise,
$\deg_{G_{\mathcal{F}}\Delta C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, so we
have a contradiction in both cases.

If $e=v_{2}ab$, then $C=v_{2}e_{2}bev_{2}$ is an $\mathcal{F}$-diminishing
cycle by Corollary 4.8, a contradiction.

If $e=v_{2}ax$, for some $x\in X$, then by Lemma 4.12(4), we have $b\in e$, a
contradiction.

Hence $e=v_{1}v_{2}a$, and by symmetry, there is an edge
$e^{\prime}=v_{1}v_{2}b$. Thus $v_{1}ev_{2}e^{\prime}v_{1}$ is a cycle in
$G_{1}$, and $C=v_{1}e_{1}aev_{1}$ is an $\mathcal{F}$-interchanging cycle.
Since $G_{1}{\backslash}E(C)=(G_{1}{\backslash}v_{1}e_{1}){\backslash}v_{1}e$
and $v_{1}e$ lies in a cycle of $G_{1}{\backslash}v_{1}e_{1}$, which is
connected, $G_{\mathcal{F}}\Delta C$ is connected by Lemma 4.7 — a
contradiction.

Hence $v_{1}=v_{2}$, and $v_{0}e_{1}v_{1}e_{2}v_{0}$ is a cycle in $G_{1}$.
Fix some $x\in X$. By Lemma 4.12(4), there is an edge $e_{x}=abx$ in $H$, and
$xe_{x}$ is a non-$G_{\mathcal{F}}$-edge. Let $e$ be an edge of $H$ containing
$v_{1}$ and $x$. By Lemma 4.12(4), we know $a,b\not\in e$.

Suppose $e=v_{1}xy$ for some $y\in X{\backslash}\\{x\\}$. By Lemma 4.12(4),
there is an edge $e_{y}=aby$ in $H$, and $ye_{y}$ is a
non-$G_{\mathcal{F}}$-edge.

If $xe,ye\in E(G_{1})$, then $C=v_{1}e_{1}ae_{x}xev_{1}$ is an
$\mathcal{F}$-interchanging cycle. Since $v_{1}e_{1}$ lies in a cycle of
$G_{1}{\backslash}xe$, we have that
$G_{1}{\backslash}E(C)=(G_{1}{\backslash}xe){\backslash}v_{1}e_{1}$ is
connected. Since $G_{2}{\backslash}E(C)$ is connected as well,
$G_{\mathcal{F}}\Delta C$ is connected by Lemma 4.7 — a contradiction.

Hence $v_{1}e\in E(G_{1})$. If $xe\not\in E(G_{1})$, then let
$C=v_{1}e_{2}be_{x}xev_{1}$; otherwise, let $C=v_{1}e_{2}be_{y}yev_{1}$. In
either case, $C$ is an $\mathcal{F}$-interchanging cycle, and it can be seen
as above that both $G_{1}{\backslash}E(C)$ and $G_{2}{\backslash}E(C)$ are
connected, a contradiction.

We conclude that $e=v_{0}v_{1}x$. If $v_{1}e,v_{1}e\in E(G_{1})$, then
$C=v_{0}e_{1}ae_{x}xev_{0}$ is an $\mathcal{F}$-interchanging cycle with
$\deg_{G_{\mathcal{F}}\Delta C}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$ — a
contradiction.

Hence $xe\in E(G_{1})$. If $v_{0}e\not\in E(G_{1})$, then let
$C=v_{0}exe_{x}ae_{1}v_{0}$; otherwise, let $C=v_{1}exe_{x}ae_{1}v_{1}$. In
either case, $C$ is an $\mathcal{F}$-interchanging cycle, and it can be seen
as above that both $G_{1}{\backslash}E(C)$ and $G_{2}{\backslash}E(C)$ are
connected, a contradiction.

Case 3: $v_{0},v_{1},$ and $v_{2}$ are the only v-vertices of $G_{1}$.

Let $e_{x}=abx$ be an edge of $H$ containing $a$, $b$, and some vertex $x$.
Since $e_{x}\not\in\\{e_{1},e_{2}\\}$, by Lemma 4.12(2), we have that $ae_{x}$
and $be_{x}$ are $G_{\mathcal{F}}$-edges, and hence $xe_{x}$ is a
non-$G_{\mathcal{F}}$-edge.

If $x\in\\{v_{0},v_{1}\\}$, then $C=xe_{1}ae_{x}x$ is an
$\mathcal{F}$-diminishing cycle by Corollory 4.8, a contradiction. Similarly,
if $x=v_{2}$, then $C=v_{2}e_{2}be_{x}v_{2}$ is an $\mathcal{F}$-diminishing
cycle.

Hence $x\in V(G_{2})$. Since, by Corollary 4.6, the graph $G_{1}$ has at least
two v-vertices that are not cut vertices, we may assume there exists
$y\in\\{v_{0},v_{1}\\}$ that is not a cut vertex of $G_{1}$. Let $e_{3}=xyz$
for some $z\in V(H)$. Then $C=ye_{1}ae_{x}xe_{3}y$ is an
$\mathcal{F}$-interchanging cycle. Let $\mathcal{F}^{\prime}$ be an Euler
family corresponding to $G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C$.

Figure 5: $G_{\mathcal{F}}$ (left) and
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C$ (right) in Case 3, for
$y=v_{0}$. Thick black (grey) edges are those in (not in) the subgraph
corresponding to the Euler family, and dashed edges represent the
$\mathcal{F}$-interchanging cycle $C$.

Suppose $y=v_{0}$. If $v_{0}e_{3}$ is a $G_{\mathcal{F}}$-edge, then
$\deg_{G_{\mathcal{F}^{\prime}}}(v_{0})<\deg_{G_{\mathcal{F}}}(v_{0})$, a
contradiction. Hence $v_{0}e_{3}$ is non-$G_{\mathcal{F}}$-edge — see Figure 5
(left) — and $G_{1}{\backslash}E(C)=G_{1}{\backslash}v_{0}e_{1}$ is connected.
By Corollary 4.11(2), $\mathcal{F}^{\prime}$ is a minimum Euler family that
minimizes
$\deg_{G_{\mathcal{F}^{\prime}}}(v_{0})=\deg_{G_{\mathcal{F}}}(v_{0})$, so it
satisfies our assumptions on $\mathcal{F}$. Moreover, the set-up of Lemma 4.12
applies to $\mathcal{F}^{\prime}$, with $v_{0},v_{1},v_{2},a,b,e_{1},e_{2}$
replaced by $v_{0},z,v_{2},x,b,e_{3},e_{2}$, respectively; see Figure 5
(right). Since the connected component of $G_{\mathcal{F}^{\prime}}$
containing $v_{0}$ also contains vertices $v_{1}$ and $a$, we can see that
$G_{\mathcal{F}^{\prime}}$ falls under Case 1 or Case 2 of this proof, both of
which lead to a contradiction.

Figure 6: $G_{\mathcal{F}}$ (left) and
$G_{\mathcal{F}^{\prime}}=G_{\mathcal{F}}\Delta C$ (right) in Case 3, for
$y=v_{1}$. Thick black (grey) edges are those in (not in) the subgraph
corresponding to the Euler family, and dashed edges represent the
$\mathcal{F}$-interchanging cycle $C$. Note that exactly one of the two thin
edges incident with $e_{3}$ is in $G_{\mathcal{F}}$
($G_{\mathcal{F}^{\prime}}$).

Hence $y=v_{1}$; see Figure 6 (left). Suppose first that $v_{1}$ and $b$ are
connected in $G_{\mathcal{F}^{\prime}}$. Since $v_{1}$ is not a cut vertex of
$G_{1}$, either $G_{1}{\backslash}E(C)$ is connected, or
$(G_{1}{\backslash}E(C))-v_{1}$ is connected and $v_{1}$ is isolated in
$G_{1}{\backslash}E(C)$. If $v_{1}$ is isolated in $G_{1}{\backslash}E(C)$,
then it is isolated in $G_{\mathcal{F}^{\prime}}$ as well, a contradiction.
Hence $G_{1}{\backslash}E(C)$ is connected. It is then easy to verify that
$v_{0}$, $v_{1}$, $v_{2}$, $a$, $b$, and $x$ lie in the same connected
component of $G_{\mathcal{F}^{\prime}}$; see Figure 6 (right). Since all other
v-vertices are connected to one of these in $G_{\mathcal{F}^{\prime}}$, we see
that $G_{\mathcal{F}^{\prime}}$ is connected, a contradiction.

Hence $v_{1}$ and $b$ are disconnected in $G_{\mathcal{F}^{\prime}}$. Apply
Lemma 4.12(2) to $G_{\mathcal{F}^{\prime}}$ with the roles of $v_{1}$ and $a$
swapped. Thus $v_{1}$ and $b$ are connected in $G_{\mathcal{F}^{\prime}}$, a
contradiction.

Having reached a contradiction in all cases, we conclude that $H$ is eulerian.
∎

###  4.4 Case $3\leq n\leq 6$

In this section, we prove Theorem 3.1 for the orders that were missed by
Theorem 4.13.

######  Lemma 4.14.

Let $H$ be a covering 3-hypergraph of order $n$, for $3\leq n\leq 6$, and with
at least two edges. Then $H$ is eulerian.

###### Proof.

If $n=3$, then $H$ is a triple system with at least two edges, and hence
eulerian by [11]. Hence assume $n\in\\{4,5,6\\}$.

Let $G$ be the incidence graph of $H$. By Theorem 4.4, $H$ is quasi-eulerian,
so let $\mathcal{F}$ be a minimum Euler family for $H$, with the corresponding
subgraph $G_{\mathcal{F}}$ of $G$. Suppose $H$ is not eulerian; then Corollary
4.11 implies that $G_{\mathcal{F}}$ has exactly two connected components, both
non-trivial, and admits no $\mathcal{F}$-diminishing cycle. Let $G_{1}$ be the
connected component with fewer v-vertices.

Case 1: $G_{1}$ has three v-vertices.

Hence $n=6$. Let $U_{1}=\\{a,b,c\\}$ and $U_{2}=\\{u,v,w\\}$ be the sets of
v-vertices of $G_{1}$ and $G_{2}$, respectively. Since each of the nine pairs
$\\{x_{1},x_{2}\\}$, for $x_{1}\in U_{1}$ and $x_{2}\in U_{2}$ is contained in
some edge of $H$, and every edge of $H$ contains an even number of such pairs,
at least one pair must be contained in two edges.

Without loss of generality, assume that $a,u\in e_{1}\cap e_{2}$ for distinct
edges $e_{1},e_{2}\in E(H)$. Then $C=ae_{1}ue_{2}a$ is an
$\mathcal{F}$-interchanging cycle of $G$. If $e_{1}\in V(G_{1})$ and $e_{2}\in
V(G_{2})$, then $C$ satisfies the assumptions of Corollary 4.8, and so it is
an $\mathcal{F}$-diminishing cycle, a contradiction.

Hence, without loss of generality, $e_{1},e_{2}\in V(G_{1})$. It follows that
$ue_{1}$ and $ue_{2}$ are non-$G_{\mathcal{F}}$-edges, and
$G_{2}{\backslash}E(C)=G_{2}$ is connected.

If $a$ is not a cut vertex of $G_{1}$, then $G_{1}{\backslash}E(C)$ is either
connected, or else has a single non-trivial connected component and an
isolated vertex, $a$. In either case, by Lemma 4.7, $G_{\mathcal{F}}\Delta C$
has a single non-trivial connected component, a contradiction.

Hence $a$ is a cut vertex of $G_{1}$, and by Corollary 4.6, neither $b$ nor
$c$ is. If $e_{1}$ and $e_{2}$ both contain $b$ or both contain $c$, then a
contradiction is obtained as in the previous paragraph, by replacing $a$ in
$C$ with $b$ or $c$, respectively. Since $e_{1},e_{2}\in V(G_{1})$, we may
thus assume $b\in e_{1}$ and $c\in e_{2}$, so that $be_{1}ae_{2}c$ is a path
in $G_{1}$. Since $a$ is a cut vertex, by Corollary 4.6, there is no cycle in
$G_{1}$ containing all of $a$, $b$, and $c$. Therefore, as $G_{1}$ is an even
graph, it has e-vertices $e_{3}$ and $e_{4}$ such that $ae_{1}be_{3}a$ and
$ae_{2}ce_{4}a$ are cycles in $G_{1}$. But then $G_{1}{\backslash}E(C)$ is
connected, yielding a contradiction as above.

Case 2: $G_{1}$ has exactly two v-vertices.

Let $m$ be the number of v-vertices in $G_{2}$, and denote the v-vertices of
$G_{1}$ by $a$ and $b$. Since $G_{1}$ is an even graph, it has an even number
of e-vertices, each of the form $e=abx$ for some v-vertex $x$ of $G_{2}$.

If $e_{1}$ and $e_{2}$ are two e-vertices of $G_{1}$ such that
$e_{1}=abx=e_{2}$, then $C=ae_{1}xe_{2}a$ is an $\mathcal{F}$-interchanging
cycle. Moreover, it is not difficult to verify that $G_{\mathcal{F}}\Delta C$
has just one non-trivial connected component, a contradiction.

It follows that the number of e-vertices of $G_{1}$ is no larger than $m$, the
number of v-vertices in $G_{2}$.

Let $e_{1}=abu$ and $e_{2}=abv$, for distinct v-vertices $u$ and $v$ of
$G_{2}$, be two e-vertices of $G_{1}$. If $G_{2}$ has an e-vertex $e$
containing $a$ and $u$, then $C=ae_{1}uea$ is an $\mathcal{F}$-interchanging
cycle with exactly one $G_{\mathcal{F}}$-edge in each connected component of
$G_{\mathcal{F}}$, so by Corollary 4.8, it is an $\mathcal{F}$-diminishing
cycle, a contradiction. A similar contradiction is obtained if $G_{2}$ has an
e-vertex $e$ containing one of $a$ and $b$, and one of $u$ and $v$. If $m=2$,
then $e$ can be taken to be an edge containing $u$ and $v$, and if $m=3$, then
$e$ can be taken to be an edge containing $a$ and $w$, the third v-vertex in
$G_{2}$.

Hence we may assume that $m=4$, and $G_{2}$ has no e-vertex containing one of
$a$ and $b$, and one of $u$ and $v$. Label the remaining v-vertices of $G_{2}$
by $w$ and $z$, and observe that $G_{1}$ has either exactly two or exactly
four e-vertices.

Suppose first that $G_{1}$ has exactly four e-vertices; namely e-vertices
$e_{3}=abw$ and $e_{4}=abz$, in addition to $e_{1}=abu$ and $e_{2}=abv$. Let
$e_{5}$ be an edge of $H$ containing $u$ and $v$. Without loss of generality,
$e_{5}=uvw$, and $ue_{5}$ and $we_{5}$ are $G_{\mathcal{F}}$-edges. Then
$C=ae_{1}ue_{5}ve_{2}a$ is an $\mathcal{F}$-interchanging cycle, and it is not
difficult to verify that $G_{1}{\backslash}E(C)$ and $G_{2}{\backslash}E(C)$
are connected. Hence by Lemma 4.7, $C$ is an $\mathcal{F}$-diminishing cycle,
a contradiction.

Hence $G_{1}$ has exactly two e-vertices. Since $e_{1}$ and $e_{2}$ are the
only edges of $H$ containing one of $a$ and $b$, and one of $u$ and $v$, any
edge containing $a$ and $w$, or $b$ and $w$, must also contain $z$. Hence we
have edges $e_{3}=awz$ and $e_{4}=bwz$, and $we_{3},we_{4},ze_{3},ze_{4}\in
E(G_{2})$. Let $e_{5}$ be an edge containing $u$ and $v$. Without loss of
generality, $e_{5}=uvw$ and $ue_{5}\in E(G_{2})$.

If $we_{5}\in E(G_{2})$, let $C=be_{2}ve_{5}we_{4}b$, and if $ve_{5}\in
E(G_{2})$, let $C=ae_{1}ue_{5}we_{3}a$. In either case $C$ is an
$\mathcal{F}$-interchanging cycle, and it is straightforward to verify that
$G_{\mathcal{F}}\Delta C$ is connected, a contradiction.

Having reached a contradiction in all cases, we conclude that $H$ is eulerian.
∎

## Acknowledgements

The first author gratefully acknowledges support by the Natural Sciences and
Engineering Research Council of Canada (NSERC), Discovery Grant
RGPIN-2016-04798.

## References

  * [1] M. A. Bahmanian, M. Šajna, Connection and separation in hypergraphs, Theory Appl. Graphs 2 (2015), Art. 5, 24 pp.
  * [2] M. A. Bahmanian, M. Šajna, Quasi-Eulerian hypergraphs, Elec. J. Combin. 24 (2017), #P3.30, 12 pp.
  * [3] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
  * [4] C. J. Colbourn, J. H. Dinitz (eds.), Handbook of Combinatorial Designs, Chapman & Hall/CRC, 2007.
  * [5] M. Dewar, B. Stevens, Ordering Block Designs: Gray Codes, Universal Cycles and Configuration Orderings, CMS Books in Mathematics, Springer, 2012.
  * [6] L. Euler, Solutio problematis ad geometriam situs pertinentis, Comment. Academiae Sci. Petropolitanae 8 (1741), 128–140.
  * [7] C. Hierholzer, C. Wiener, Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Math. Ann. 6 (1873), 30–32.
  * [8] V. Horan, G. Hurlbert, Overlap cycles for Steiner quadruple systems, J. Combin. Des. 22 (2014), 53–70.
  * [9] V. Horan, G. Hurlbert, 1-Overlap cycles for Steiner triple systems, Des. Codes Cryptogr. 72 (2014), 637–651.
  * [10] Z. Lonc, P. Naroski, On tours that contain all edges of a hypergraph, Elec. J. Combin. 17 (2010), #R144, 31 pp.
  * [11] M. Šajna, A. Wagner, Triple systems are eulerian, J. Combin. Des. 25 (2017), 185–191.


# Tech Report:
One-stage Lightweight Object Detectors

Deokki Hong
College of Computing, Yonsei University
<EMAIL_ADDRESS>
Work done during internship in CLOVA ImageVision, NAVER

###### Abstract

This work is for designing one-stage lightweight detectors which perform well
in terms of mAP and latency. With baseline models each of which targets on GPU
and CPU respectively, various operations are applied instead of the main
operations in backbone networks of baseline models. In addition to experiments
about backbone networks and operations, several feature pyramid network (FPN)
architectures are investigated. Benchmarks and proposed detectors are analyzed
in terms of the number of parameters, Gflops, GPU latency, CPU latency and
mAP, on MS COCO dataset which is a benchmark dataset in object detection. This
work propose similar or better network architectures considering the trade-off
between accuracy and latency. For example, our proposed GPU-target backbone
network outperforms that of _YOLOX_ -tiny which is selected as the benchmark
by 1.43x in speed and 0.5 mAP in accuracy on _NVIDIA GeForce RTX 2080 Ti_ GPU.

##  1 Introduction

Object detection [1, 2] is one of the various vision tasks that localizes and
classifies objects in a scene. In recent years, object detection is applied to
numerous fields such as unmanned stores, and face-recognition based security
systems. Early Studies about object detection are based on two-stage detectors
[3], which show high performance but low hardware efficiency. Nowadays, the
more object detection permeates in real life, the higher demand increases for
lightweight detectors. For instance, there may need real-time object detection
in a field of surveillance systems, or some constraints such as battery limit
and computing power can exist in edge devices. However, the efficiency of a
detector is affected by not only operations in the network, but also hardware
architectures that the detector is executed on. For instance, inverted
residual bottleneck, which is proposed in MobileNetv2 [4], is designed for
better efficiency while barely sacrificing accuracy. Meanwhile, Google’s TPU
[5] is one of the most remarkable hardware which is optimized for executing
DNNs. Unfortunately, inverted residual bottleneck performs poorly on TPU for
its architectural advantage is not suitable for exploiting TPU [6]. Therefore,
it is necessary to design networks while considering properties of operations
and hardware architectural features comprehensively.

In this work, we examined novel one-stage lightweight detectors [7, 8] and
various modern operations in terms of accuracy and latency. Based on the
examination, we propose the best operations and architectures on GPU and CPU,
respectively. In GPU experiments, our suggested object detector is based on
_YOLOX_ [7] and it adopts fused inverted residual botteneck [9] in the front
and inverted residual bottleneck in the back. It outperforms YOLOX-tiny 1.43x
in speed and 0.5 mAP in accuracy. In CPU experiments, despite that YOLOX-tiny
is the best in terms of mAP, our suggested one which is based on PP-PicoDet
[8] shows only 74% of the number of parameters and 1.12x in speed while
sacrificing 1.3 mAP in accuracy.

##  2 Related works

###  2.1 One-stage detector

One-stage detector often consists of a backbone network, feature pyramid
network (FPN) [10], and detection head. Backbone network is a general feed-
forward network and it extracts meaningful properties from input images.
Unlike two-stage detectors, one-stage detectors directly use features from
backbone networks in bounding box regression and classification. Thus,
backbone network is highly related to the performance of the detector.

From each stage of a backbone network, various sizes of features are obtained.
High-resolution features from earlier stages have weak semantics, while low-
resolution features from later stages have strong semantics. FPN combines
these various sizes of features and makes features from earlier stages have
rich information.

Detection head is the most important part of detectors. The two tasks of
object detection, bounding box regression and classification, are done in
detection head by using features from backbone network and FPN. Detection head
is highly related to the loss function of the detector.

There are two baselines in this work, each of which targets GPU and CPU,
respectively. YOLOX [7] is one of the latest one-stage object detectors, which
is used as the main baseline for GPU in this work. The backbone network of
YOLOX is CSPDarknet and the FPN of YOLOX is path aggregation feature pyramid
network (PAFPN) [11]. PP-PicoDet [8] is also a novel one-stage detector that
targets on CPU. The backbone network of PP-PicoDet is PP-LCNet (lightweight
CPU convolutional neural network) [12]. The FPN of PP-PicoDet is Lightweight
CPU Path Aggregation Network (LCPAN), which is a variant of PAFPN.

###  2.2 Operations

There are several works that pursue efficiency while trying to barely
sacrifice performance. CSP layer [13], which is the main operation in YOLOX
backbone network, is an architecture for achieving abundant gradient
combinations while reducing computational costs. Depthwise separable
convolution operation, which is the main operation of PP-LCNet, was proposed
in MobileNet [14] which is one of the early works in this field. It reduces
computational costs by using depthwise convolution operation and combines
information among channels with a $1\times 1$ convolution operation.
MobileNetv2 [4] is a follow-up research of MobileNet and it proposed inverted
residual bottleneck architecture, which is a dominant architecture in mobile
settings. Based on depthwise separable convolution, it expands input channels
of the depthwise convolution operation with a $1\times 1$ convolution
operation in front of that. EfficientNetv2 [9] tackled MobileNetv2 that using
inverted residual bottleneck in the whole network is not efficient, and it
proposed fused inverted residual bottleneck architecture, which replaces the
first $1\times 1$ convolution and the depthwise convolution operation of
inverted residual bottleneck with a convolution operation, for replacing
inverted residual bottleneck at the front of networks. X block used in RegNet
[15] is a result of designing generalized architecture across settings, and
sandglass bottleneck [16] is designed to improve inverted residual bottleneck
for mitigating information loss and gradient confusion. Blueprint separable
convolution [17] is a variant of depthwise separable convolution which aims
for improving MobileNet by replacing cross-kernel correlations in depthwise
separable convolution with intra-kernel correlations.

###  2.3 Feature pyramid network

In a general feed-forward neural network, high-resolution features from early
layers have weak semantics while low-resolution features from later layers
have strong semantics. FPN is an architecture for combining various sizes of
features to make all features have strong semantics. The FPN architectures in
both YOLOX and PP-PicoDet are based on PAFPN. PAFPN is based on FPN
architecture which adds bottom-up path augmentation for enhancing semantics of
features by propagating low-level features to others. SepFPN is an FPN
architecture based on PAFPN, which removes the bottom-up path in PAFPN and
adds residual paths from inputs to outputs of FPN. It pursues faster latency
even at the expense of accuracy a little.

##  3 Lightweight detector design

###  3.1 Micro architectures for backbone network

In GPU experiments, CSP layer in CSPDarknet is replaced with several
bottleneck architectures, such as inverted residual bottleneck (MBConv), fused
inverted residual bottleneck, RegNet bottleneck, and sandglass bottleneck to
verify whether CSP layer is the best architecture in YOLOX backbone network.
EfficientNetv2 [9] proposed that using fused inverted residual bottleneck to
the front of networks and inverted residual bottleneck to the rest is good for
both accuracy and efficiency. In this paper, each network that comprises
inverted residual bottleneck only, fused inverted residual bottleneck only,
and use both operations simultaneously are addressed. A policy that uses
inverted residual bottleneck and fused inverted residual bottleneck in a
single network is named mixed inverted residual bottleneck.

In CPU experiments, depthwise separable convolution operation and blueprint
separable convolution operation are examined with PP-PicoDet. For a fair
comparison with YOLOX baseline, channels of each block are set the same as
those of YOLOX. Additionally, FPN architecture and detection head in PP-
PicoDet are replaced with those of YOLOX.

###  3.2 Feature pyramid network

The main operation of YOLOX’s PAFPN is CSP layer and that of LCPAN is
depthwise separable convolution, respectively. In addition, the major
difference between these two FPN is whether channels of input features are
equalized before FPN operation or not. In PAFPN, channels of input features
are not equalized. Rather, channels of FPN outputs are equalized before they
are fed to the detection head. It leads to better performance in terms of
accuracy but is bad for latency because channels in FPN are large. On
contrary, in LCPAN, channels of input features are equalized in front of FPN.
Then, channels of output features are the same, while channels in FPN are
reduced. SepFPN is based on PAFPN of YOLOX. That is, the main operation of
SepFPN is CSP layer and channels of input features are not equalized. In this
work, a modified PAFPN architecture is proposed, which replaces concatenation
operations in FPN with sum. By doing so, channels in FPN can be reduced while
rich semantics in feature maps are expected to preserve. This technique is
applied to both YOLOX’s PAFPN and PP-PicoDet’s LCPAN and examined.

##  4 Experimental results

###  4.1 Experimental settings

For a fair comparison, a detection head from YOLOX is applied in both
baselines. That is, several operations, backbones, and FPN architectures are
targets in this work. In GPU experiments, expand ratios of bottleneck
architectures except sandglass bottleneck are set to 1, and that of sandglass
bottleneck is set to 0.5. Hyperparameters related to network design (e.g., the
number of blocks, channels of each block, etc.) are set as the same with
YOLOX-tiny. While training networks, any other hyperparameters except network
architectures follow the default settings of YOLOX. In GPU experiments,
_NVIDIA GeForce RTX 2080 Ti_ is used to measure GPU latency. In CPU
experiments, _Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz_ is used to measure CPU
latency. While measuring latency, mini batch size and the number of threads
are set to 1.

###  4.2 Baseline latency breakdown

Figure 1: Latency breakdown of baseline model.

Figure 1 shows GPU and CPU latency of the baseline model. The backbone network
accounts for 40% of the total latency on GPU, and 53% on CPU. Thus, it is
critical to reducing backbone latency to lighten detectors. FPN, which is also
the target to improve in this work, accounts for 27% of total latency on GPU
and 18% on CPU. Detection head occupies more compared to FPN. However, because
it is highly related to the loss function of detectors, detection head is
fixed in all experiments for a fair comparison.

###  4.3 GPU-target detector

(a) Backbone GPU Latency - mAP of CSPdarknet backbone and candidate
operations.

(b) Ablation study for mixed inverted residual bottleneck.

Figure 2: Results of GPU experiments.

Figure 2 shows GPU latency of backbone network and mAP depending on the main
operation of backbone networks. As shown in the Figure 2(a), YOLOX tiny is the
best in terms of mAP, but its GPU latency is the worst. A backbone network
that consists of fused inverted residual bottleneck has the largest number of
parameters. However, its GPU latency is the fastest among all settings. Fused
inverted bottleneck is the only one that uses a $3\times 3$ convolution
operation rather than a $3\times 3$ depthwise convolution operation. $3\times
3$ convolution operation is the most basic convolution operation, and it is
highly optimized on GPU. That’s the reason a detector that adopts fused
inverted residual bottleneck as the main operation of the backbone is the
fastest on GPU even though the number of parameters is the largest.

This work focuses on the policy which is proposed in Efficientnetv2 [9]; _Use
fused inverted residual bottleneck to the front of the network and inverted
residual bottleneck to the rest_. In Figure 2(a), mixed inverted residual
bottleneck is noticeable because it is fast, lightweight, and has a lot of
diversity in terms of design. Mixed inverted residual bottleneck can leverage
parallel computing and get better mAP by using fused inverted residual
bottleneck while pursuing lightness by using inverted residual bottleneck.
Also, it has a lot of potential because the number of fused inverted residual
bottleneck operations is an important design policy. CSPDarknet, which is the
backbone network of YOLOX, has 4 blocks. Therefore, networks that use 1 or 2
fused inverted bottlenecks are examined. Furthermore, because the number of
parameters in mixed inverted bottleneck is smaller than that of YOLOX
baseline, networks that set expand ratio to 1.5 is also investigated. Figure
2(b) shows the results of this ablation study. Using 2 fused inverted residual
bottlenecks and 2 inverted residual bottlenecks is better than 1 fused
inverted residual bottleneck and 3 inverted residual bottlenecks, in terms of
latency and mAP. Moreover, a policy that uses a larger expand ratio is still
faster than YOLOX baseline. Therefore, the purple dot in Figure 2(b) is chosen
as the best detector in GPU experiments.

###  4.4 CPU-target detector

(a) Backbone CPU Latency - mAP of PP-LCNet backbone and candidate operations.

(b) Total CPU Latency - mAP of PP-LCNet backbone and candidate operations.

Figure 3: Results of CPU experiments.

In this section, CSPDarknet, which is the backbone network of YOLOX, is
replaced with PP-LCNet in PP-PicoDet. In addition, blueprint separable
convolution operation is applied to PP-LCNet as an alternative of depthwise
separable convolution, which is the main operation of PP-LCNet. The channels
of PP-LCNet are set the same as those of CSPDarknet in order to compare
fairly. However, because PP-LCNet is much smaller than CSPDarknet, detectors
that use twice as large as the default network are also examined. Note that
FPN architecture of these detectors is different from others in order to use
the same detection head for a fair comparison.

Figure 3(a) shows CPU latency of backbone network and mAP of the above
detectors. Using PP-LCNet as the backbone leads to generating lightweight
detectors. Detectors that adopt blueprint separable convolution operation as
the main operation are slower and show higher mAP compared to those which
adopt depthwise separable convolution operation. Unfortunately, detectors that
adopt PP-LCNet as the backbone network show low mAP as much as small the
number of parameters they have compared to that of YOLOX baseline. To improve
mAP, backbone networks with larger channels are also analyzed. They show a lot
of improvement in mAP, while sacrificing latency. Even though the number of
parameters in each backbone is similar to that of YOLOX, either latency or mAP
is worse than that of YOLOX. When the number of channels in the backbone
network is changed, that in FPN also should be changed. However, because
detection head is fixed in all experiments, the output channels of PP-LCNet
with larger channels are equalized and therefore their FPN architectures are
smaller than others. Figure 3(b) shows CPU latency of whole detector and mAP
of the same detectors in Figure 3(a), for taking their FPN architectures into
account. A detector that adopts DSConv as the main operation and has larger
channels shows faster latency and a much less number of parameters compared to
YOLOX baseline. The number of parameters is also a major constraint in real-
world scenarios, and thus this setting can be a good solution when a fast
detector with less number of parameters is needed.

###  4.5 FPN architecture analysis

(a) GPU experiments.

(b) CPU experiments.

Figure 4: Results of FPN experiments.

In this section, the performances of FPN architectures are investigated with
the backbone network which is searched in section 4.3. PAFPN, which is the
default FPN architecture of YOLOX is the best in terms of mAP. LCPAN, which is
the default FPN architecture of PP-PicoDet is the best in terms of the number
of parameters and latency. Proposed FPN architectures (replace concatenation
operation with sum) perform bad compare to baseline. The expected effect of
proposed FPN architectures is preserving semantics while reducing channels in
FPN by summing features from different blocks. However, it doesn’t work as
expected. Especially, PAFPN-based proposed FPN architecture performs badly on
GPU. It means that reducing channels in FPN doesn’t lead to reducing latency
because GPU has huge parallel computing power.

##  5 Conclusion

(a) GPU experiments.

(b) CPU experiments.

Figure 5: Results of searched networks.

This work analyzes the architectural design spaces of a novel one-stage
detector. Optimal architecture design in object detectors depends on target
hardware and purpose. Figure 5 shows searched networks in section 4 along with
YOLOX baseline. Figure 5(a) denotes mAP and latency of the baseline, the GPU
target detector, and the CPU target detector executed on GPU. The GPU target
detector which is marked with an orange dot shows the best mAP while achieving
the best GPU latency, even though the CPU target detector has a less number of
parameters. Therefore, the GPU target detector searched in this paper is the
best in both aspects. Figure 5(a) denotes mAP and latency of detectors the
same as Figure 5(a) executed on CPU. The CPU target detector which is marked
with a blue dot shows the worst mAP, yet it is much faster than others on CPU.
Further, it has a much less number of parameters compared to others.
Therefore, if there is not enough computing power and energy budget, the CPU
target detector can be a good solution. Figure 5 doesn’t plot FPN results.
Nevertheless, FPN is also an important factor in detectors and should be
designed carefully depending on the purpose.

## References

  * [1] R. B. Girshick, J. Donahue, T. Darrell, and J. Malik, “Rich feature hierarchies for accurate object detection and semantic segmentation,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 580–587, 2014.
  * [2] R. B. Girshick, “Fast R-CNN,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 1440–1448, 2015.
  * [3] S. Ren, K. He, R. B. Girshick, and J. Sun, “Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks,” in Advances in Neural Information Processing Systems, 2015.
  * [4] M. Sandler, A. G. Howard, M. Zhu, A. Zhmoginov, and L. Chen, “MobileNetV2: Inverted Residuals and Linear Bottlenecks,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4510–4520, 2018.
  * [5] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, et al., “In-Datacenter Performance Analysis of a Tensor Processing Unit,” in ISCA, 2017.
  * [6] S. Gupta and B. Akin, “Accelerator-aware Neural Network Design using AutoML,” arXiv preprint arXiv:2003.02838, 2020.
  * [7] Z. Ge, S. Liu, F. Wang, Z. Li, and J. Sun, “YOLOX: Exceeding YOLO Series in 2021,” arXiv preprint arXiv:2107.08430, 2021.
  * [8] G. Yu, Q. Chang, W. Lv, C. Xu, C. Cui, W. Ji, Q. Dang, K. Deng, G. Wang, Y. Du, B. Lai, Q. Liu, X. Hu, D. Yu, and Y. Ma, “PP-PicoDet: A Better Real-Time Object Detector on Mobile Devices,” arXiv preprint arXiv:2111.00902, 2021\.
  * [9] M. Tan and Q. Le, “Efficientnetv2: Smaller models and faster training,” in International Conference on Machine Learning, pp. 10096–10106, PMLR, 2021\.
  * [10] T. Lin, P. Dollár, R. B. Girshick, K. He, B. Hariharan, and S. J. Belongie, “Feature Pyramid networks for Object Detection,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2117–2125, 2017.
  * [11] S. Liu, L. Qi, H. Qin, J. Shi, and J. Jia, “Path Aggregation Network for Instance Segmentation,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8759–8768, 2018.
  * [12] C. Cui, T. Gao, S. Wei, Y. Du, R. Guo, S. Dong, B. Lu, Y. Zhou, X. Lv, Q. Liu, X. Hu, D. Yu, and Y. Ma, “PP-LCNet: A Lightweight CPU Convolutional Neural Network,” arXiv preprint arXiv:2109.15099, 2021.
  * [13] C.-Y. Wang, H.-Y. Mark Liao, Y.-H. Wu, P.-Y. Chen, J.-W. Hsieh, and I.-H. Yeh, “CSPNet: A new backbone that can enhance learning capability of CNN,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 390–391, 2020.
  * [14] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications,” arXiv preprint arXiv:1704.04861, 2017.
  * [15] I. Radosavovic, R. P. Kosaraju, R. B. Girshick, K. He, and P. Dollár, “Designing Network Design Spaces,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10428–10436, 2020\.
  * [16] D. Zhou, Q. Hou, Y. Chen, J. Feng, and S. Yan, “Rethinking Bottleneck Structure for Efficient Mobile Network Design,” in European Conference on Computer Vision, pp. 680–697, 2020.
  * [17] D. Haase and M. Amthor, “Rethinking Depthwise Separable Convolutions: How Intra-Kernel Correlations Lead to Improved MobileNets,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14600–14609, 2020.

##  Appendix A Appendix

###  A.1 Experimental results with values

The below tables show the stats of each detector searched in section 4. A bold
value represents the best value in each column.

Architecture |  | backbone # of
---
params (M)
| backbone
---
Gflops
| backbone GPU
---
latency (ms)
mAP
YOLOX tiny | 2.3723 | 2.6648 | 1.7260 | 32.8
Inverted bottleneck | 1.6080 | 1.5884 | 1.2242 | 31.2
Mixed inverted bottleneck | 1.6167 | 1.6953 | 1.2091 | 31.1
Fused inverted bottleneck | 3.7042 | 3.9063 | 1.1431 | 32.3
RegNet bottleneck | 1.6329 | 1.6668 | 1.3197 | 31.3
Sandglass bottleneck | 1.3432 | 1.3997 | 1.4159 | 30.8
Table 1: Results of GPU experiments in Figure 2(a). Architecture |  | backbone # of
---
params (M)
| backbone
---
Gflops
| backbone GPU
---
latency (ms)
mAP
YOLOX tiny | 2.3723 | 2.6648 | 1.7260 | 32.8
Fused 1: Inverted 3, expansion=1.0 | 1.6167 | 1.6953 | 1.2091 | 31.1
Fused 2: Inverted 2, expansion=1.0 | 1.7978 | 2.5971 | 1.1209 | 31.6
Fused 1: Inverted 3, expansion=1.5 | 1.9054 | 2.2505 | 1.2237 | 32.5
Fused 2: Inverted 2, expansion=1.5 | 2.1771 | 3.6032 | 1.2046 | 33.3
Table 2: Results of GPU ablation studies in Figure 2(b). Architecture |  | backbone # of
---
params (M)
| backbone
---
Gflops
| backbone CPU
---
latency (ms)
mAP
YOLOX tiny | 2.3723 | 2.6648 | 39.4991 | 32.8
PP-PicoDet DSconv | 0.5845 | 0.6765 | 15.3962 | 28.2
PP-PicoDet BSconv | 0.6471 | 1.0118 | 24.5329 | 28.2
PP-PicoDet DSconv ($\times$2 channels) | 2.2358 | 2.3710 | 36.2975 | 31.5
PP-PicoDet BSconv ($\times$2 channels) | 2.4718 | 3.6565 | 59.8067 | 32.7
Table 3: Results of CPU experiments in Figure 3(a). Architecture | # of params (M) | Gflops | CPU latency (ms) | mAP
---|---|---|---|---
YOLOX tiny | 5.0559 | 6.4510 | 73.4122 | 32.8
PP-PicoDet DSconv | 3.2680 | 4.4628 | 49.8036 | 28.2
PP-PicoDet BSconv | 3.3307 | 4.7980 | 58.0259 | 29.2
PP-PicoDet DSconv ($\times$2 channels) | 3.7591 | 5.5394 | 65.5060 | 31.5
PP-PicoDet BSconv ($\times$2 channels) | 3.9951 | 6.8249 | 89.5966 | 32.7
Table 4: Results of CPU experiments in Figure 3(b). Architecture | # of params (M) | Gflops | GPU latency (ms) | CPU latency (ms) | mAP
---|---|---|---|---|---
PAFPN | 4.8606 | 7.3894 | 3.6284 | 80.6611 | 33.3
LCPAN | 3.5535 | 6.6907 | 3.2626 | 76.6075 | 31.9
PAFPN (cat to sum) | 4.7224 | 7.2399 | 3.6354 | 79.3600 | 32.0
LCAPN (cat to sum) | 3.3845 | 6.3338 | 3.2180 | 71.4919 | 31.2
SepFPN | 4.3532 | 7.1149 | 3.5134 | 77.9030 | 32.3
Table 5: Results of FPN experiments in Figure 4.

###  A.2 Scale-up

Figure 6: GPU target detectors at scale.

In section 4.3, we designed the GPU target detector which has a similar size
to YOLOX tiny. Figure 6 shows various sizes of YOLOX baseline and the GPU
target detector searched in section 4.3 to verify the design policy
establishsed on section 4.3 is efficient with other sizes. Red dots denote
YOLOX baselines of various sizes and orange dots denote GPU target detectors
which are designed with the policy proposed in section 4.3. As shown in the
figure, orange dots are better than red dots considering the latency-mAP
trade-off. As scaling up, improvements in latency are much better while mAP
increases smoothly compared to YOLOX counterpart. This trend will continue as
the network grows in size.