$x$-edge, $e_{y}$ the $y$-edge, $e_{y}^{\prime}$ the second $y$-edge, and $e$
the unique middle edge of $P_{xy}^{\prime}$.

Suppose that $|M_{1}\cap E(P_{xy}^{\prime})|$ is odd. If $|M_{1}\cap
E(P_{xy}^{\prime})|=3$, then $M_{1}\cap
E(P_{xy}^{\prime})=\\{e_{x},e,e_{y}\\}$, because $\\{e_{x},e,e_{y}\\}$ is the
unique matching of $P_{xy}^{\prime}$ of size three. Since $M_{1}\cap
E(P_{xy}^{\prime})\neq M_{2}\cap E(P_{xy}^{\prime})$, we obtain that
$|M_{2}\cap E(P_{xy}^{\prime})|=1$. In particular, either $e_{x}\notin M_{2}$
or $e_{y}\notin M_{2}$. Assume by symmetry, that $e_{x}\notin M_{2}$. However,
by condition (iii)(a) of the definition of equivalency, the $x$-edge of
$P_{xy}$ is in $M^{\prime}$ if and only if $x$-edge of $P_{xy}^{\prime}$ in
$M_{1}$ and $M_{2}$; a contradiction. Hence, we can assume that $|M_{1}\cap
E(P_{xy}^{\prime})|=|M_{2}\cap E(P_{xy}^{\prime})|=1$. If either $M_{1}\cap
P_{xy}^{\prime}$ or $M_{2}\cap E(P_{xy}^{\prime})$ consists of the $x$-edge or
the $y$-edge of $P_{xy}^{\prime}$, we use the same arguments as above. This
means that both $M_{1}$ and $M_{2}$ contains a unique edge of
$P_{xy}^{\prime}$ that belongs to $\\{e_{x}^{\prime},e,e_{y}^{\prime}\\}$.
Suppose that $e_{x}^{\prime}\in M_{1}$ but $e_{x}^{\prime}\notin M_{2}$.
However, this contradicts (iii)(d). By symmetry, we obtain that
$e_{x}^{\prime}\notin M_{1},M_{2}$ and $e_{y}^{\prime}\notin M_{1},M_{2}$.
This means that $M_{1}\cap E(P_{xy}^{\prime})=M_{2}\cap
E(P_{xy}^{\prime})=\\{e\\}$ contradicting that the sets are distinct.

Assume that $|M_{1}\cap E(P_{xy}^{\prime})|$ is even. Since $M_{1}\cap
E(P_{xy}^{\prime})$ and $M_{2}\cap E(P_{xy}^{\prime})|$ are nonempty,
$|M_{1}\cap E(P_{xy}^{\prime})|=|M_{2}\cap E(P_{xy}^{\prime})|=2$. As we
already observe in the previous case, $e_{x}\in M_{1}$ ($e_{y}\in M_{1}$,
respectively) if and only if $e_{x}\in M_{2}$ ($e_{y}\in M_{2}$,
respectively). In particular, if $M_{1}\cap
E(P_{xy}^{\prime})=\\{e_{x},e_{y}\\}$, then $M_{2}\cap
E(P_{xy}^{\prime})=\\{e_{x},e_{y}\\}$; a contradiction. Notice that if
$e_{x},e_{y}\notin M_{1}$, then $M_{1}\cap
E(P_{xy}^{\prime})=\\{e_{x}^{\prime},e_{y}^{\prime}\\}$. Then we obtain that
$M_{2}\cap E(P_{xy}^{\prime})=\\{e_{x}^{\prime},e_{y}^{\prime}\\}$; a
contradiction. This implies that either $e_{x}\in M_{1},M_{2}$ and
$e_{y}\notin M_{1},M_{2}$ or, symmetrically, $e_{x}\notin M_{1},M_{2}$ and
$e_{y}\in M_{1},M_{2}$. In both cases
$|M_{1}\cap\\{e_{x}^{\prime},e,e_{y}^{\prime}\\}|=|M_{2}\cap\\{e_{x}^{\prime},e,e_{y}^{\prime}\\}|=1$
and we obtain a contradiction using (iii)(d) in exactly the same way as in the
previous case when .$|M_{1}\cap E(P_{xy}^{\prime})|$ is odd. This completes
the proof of (iii).

Finally, we show (iv). Let $M^{\prime}$ be a nonempty matching cut of
$G^{\prime}$. We show that $H$ has a nonempty matching cut $M$ that is
equivalent to $M^{\prime}$. We construct $M$ as follows. First, we include in
$M$ the edges of $M^{\prime}\cap E(G[Y])$. Then for every long path
$P_{xy}\in\mathcal{P}$, we do the following. Denote by $e_{x}$ the $x$-edge,
$e_{x}^{\prime}$ the second $x$-edge, $e_{y}$ the $y$-edge, $e_{y}^{\prime}$
the second $y$-edge, and $e$ the unique middle edge of $P_{xy}^{\prime}$.

  * •

If $e_{x}\in M^{\prime}$ ($e_{y}\in M^{\prime}$, respectively), then include
$e_{x}$ ($e_{y}$, respectively) in $M^{\prime}$.

  * •

If $e_{x},e_{y}\in M^{\prime}$ and $|M^{\prime}\cap E(P_{xy})|$ is odd, then
include $e\in M$. If $e_{x},e_{y}\in M^{\prime}$ and $|M^{\prime}\cap
E(P_{xy})|$ is even, then no other edge of $P_{xy}^{\prime}$ is included in
$M$, that is, $M\cap E(P_{xy}^{\prime})=\\{e_{x},e_{y}\\}$.

  * •

If $e_{x}\in M^{\prime}$ and $e_{y}\notin M^{\prime}$, then

    * –

if $|M^{\prime}\cap E(P_{xy})|$ is odd, then no other edge of
$P_{xy}^{\prime}$ is included in $M$, that is, $M\cap
E(P_{xy}^{\prime})=\\{e_{x}\\}$,

    * –

if $|M^{\prime}\cap E(P_{xy})|$ is even, then $e_{y}^{\prime}$ is included in
$M$ if $e_{y}^{\prime}\in M^{\prime}$ and $e$ is included in $M$ if
$e_{y}^{\prime}\notin M^{\prime}$.

  * •

If $e_{x}\notin M^{\prime}$ and $e_{y}\in M^{\prime}$, then

    * –

if $|M^{\prime}\cap E(P_{xy})|$ is odd, then no other edge of
$P_{xy}^{\prime}$ is included in $M$, that is, $M\cap
E(P_{xy}^{\prime})=\\{e_{y}\\}$,

    * –

if $|M^{\prime}\cap E(P_{xy})|$ is even, then $e_{x}^{\prime}$ is included in
$M$ if $e_{x}^{\prime}\in M^{\prime}$ and $e$ is included in $M$ if
$e_{x}^{\prime}\notin M^{\prime}$.

  * •

If $e_{x},e_{y}\notin M^{\prime}$, then

    * –

if $|M^{\prime}\cap E(P_{xy})|$ is even, then $e_{x}^{\prime}$ and
$e_{y}^{\prime}$ are included in $M$,

    * –

if $|M^{\prime}\cap E(P_{xy})|$ is odd, then $e_{x}^{\prime}$ is included in
$M$ if $e_{x}^{\prime}\in M^{\prime}$ and $e_{y}^{\prime}\notin M^{\prime}$,
$e_{y}^{\prime}$ is included in $M$ if $e_{x}^{\prime}\notin M^{\prime}$ and
$e_{y}^{\prime}\in M^{\prime}$, and $e$ is included in $M$ if either
$e_{x}^{\prime},e_{y}^{\prime}\in M^{\prime}$ or
$e_{x}^{\prime},e_{y}^{\prime}\notin M^{\prime}$.

It is straightforward to verify that $M$ is a matching of $H$ satisfying
conditions (i)–(iii) of the definition of equivalency. Then using exactly the
same argument as in the proof of (ii) we observe that $M$ is a matching cut of
$H$. This concludes the proof of (iv). ∎

Claim 13.1 allows us to construct the solution-lifting algorithm for nonempty
matching cuts of $H$ that outputs nonempty matching cuts from
$\mathcal{M}_{2}$. For each nonempty matching cut $M$ of $H$, the algorithm
lists the matching cuts $M^{\prime}$ of $G^{\prime}$ such that $M^{\prime}$ is
equivalent to $M$. Then for each $M^{\prime}$, we extend $M^{\prime}$ to
matching cuts of $G$ by adding matchings of $F=G-E(G^{\prime})$. For this, we
consider the algorithm $\textsc{EnumPath}(P_{x,y},A,B,C,h)$ that given a path
$P_{xy}\in\mathcal{P}$, disjoint sets $A,B,C\subseteq E(P_{xy})$, and an
integer $h\in\\{0,1\\}$, enumerates with polynomial delay all nonempty
matchings $M$ of $P_{xy}$ such that $A\subseteq M$, $B\cap M=\emptyset$,
either $C\subseteq M$ or $C\cap M=\emptyset$, and $|M|\mod 2=h$. Such an
algorithm exists by Observation 12. We also use the algorithm
$\textsc{EnumMatchF}(M)$ that, given a matching cut $M$ of $G^{\prime}$, lists
all matching cuts of $G$ of the form $M\cup M^{\prime}$, where $M^{\prime}$ is
a matching of $F$. $\textsc{EnumMatchF}(M)$ is constructed as follows. Let $A$
be the set of edges of $F$ incident to the end-vertices of $F$ (recall that
each connected component of $F$ contains at most one vertex of
$V(G^{\prime})$). Then we enumerate the matchings $M^{\prime}$ of $F$ such
that $M^{\prime}\cap A=\emptyset$. This can be done with polynomial delay by
Observation 12.

We use EnumPath and EnumMatchF as subroutines of the recursive branching
algorithm EnumEquivalent (see Algorithm 3) that, given a matching $M$ of $H$,
takes as an input a matching $L$ of $G$ and $\mathcal{R}\subseteq\mathcal{P}$
and outputs the matching cuts $M^{\prime}$ of $G$ such that (i) $L\subseteq
M^{\prime}$, (ii) $M^{\prime}$ is equivalent to $M$, and (iii) the constructed
matchings $M^{\prime}$ differ only by some edges of the paths
$P_{xy}\in\mathcal{R}$. To initiate the computations, we construct the initial
matching $L^{\prime}$ of $G$ and the initial set of paths
$\mathcal{R}^{\prime}\subseteq\mathcal{P}$ as follows. We define
$\mathcal{R}^{\prime}\subseteq\mathcal{P}$ to be the set of long paths
$P_{xy}\subseteq\mathcal{P}$ such that $P_{xy}^{\prime}\cap M\neq\emptyset$.
Then $L^{\prime}\subseteq M$ is the set of edges of $M$ that are not in the
paths of $\mathcal{R}^{\prime}$. Recall that as an intermediate step, we
enumerate nonempty matching cuts of $G^{\prime}$ that are equivalent to $M$.
Then it can be noted that to do this, we have to enumerate all possible
extensions of $M$ to $M^{\prime}$ satisfying condition (iii) of the
equivalence definition. Therefore, we call
$\textsc{EnumEquivalent}(L^{\prime},\mathcal{R}^{\prime})$ to solve the
enumeration problem.

1 if  _$\mathcal{R}=\emptyset$_ then

2 call $\textsc{EnumMatchF}(M)$;

3 return every matching cut $M^{\prime}$ generated by the algorithm and quit

4 end if

5 else if  _$\mathcal{R}\neq\emptyset$_ then

6 select arbitrary $P_{xy}\in\mathcal{R}$;

7 set $A:=\emptyset$; $B:=\emptyset$; $C:=\emptyset$; $h:=|M\cap
E(P_{xy}^{\prime})|\mod 2$;

8 if  _$e_{x}\in M$_ then set $A:=A\cup\\{e_{x}\\}$;

9 if  _$e_{y}\in M$_ then set $A:=A\cup\\{e_{y}\\}$;

10 if  _$e_{x}^{\prime}\in M$ and $e,e_{y}^{\prime}\notin M$_ then set
$A:=A\cup\\{e_{x}^{\prime}\\}$ and $B:=B\cup\\{e_{y}^{\prime}\\}$;

11 if  _$e_{y}^{\prime}\in M$ and $e,e_{x}^{\prime}\notin M$_ then set
$A:=A\cup\\{e_{y}^{\prime}\\}$ and $B:=B\cup\\{e_{x}^{\prime}\\}$;

12 if  _$e\in M$ and $e_{x}^{\prime},e_{y}^{\prime}\notin M$_ then set
$C:=C\cup\\{e_{x}^{\prime},e_{y}^{\prime}\\}$;

13 call $\textsc{EnumPath}(P_{x,y},A,B,C,h)$;

14 foreach  _nonempty matching $Z$ generated by
$\textsc{EnumPath}(P_{x,y},A,B,C,h)$_ do

15 $\textsc{EnumEquivalent}(L\cup Z,\mathcal{R}\setminus\\{P_{xy}\\})$

16 end foreach

17

18 end if

Algorithm 3 $\textsc{EnumEquivalent}(L,\mathcal{R})$

Let us remark that when we call $\textsc{EnumMatchF}(M)$ in line (2), we
immediately return each matching cut $M^{\prime}$ produced by the algorithm.
Similarly, when we call $\textsc{EnumPath}(P_{xy},A,B,C,h)$ in line (13), we
immediately execute the loop in lines (14)–(16) for each generated matching
$Z$.

It can be seen from the description that EnumEquivalent is a backtracking
enumeration algorithm. It picks $P_{xy}\in\mathcal{R}$ and produces nonempty
matchings of $P_{xy}$. Notice that the sets of edges $A$, $B$, and $C$, the
parity of the number of edges in a matching are assigned in lines (7)–(12)
exactly as it is prescribed in condition (iii) of the equivalency definition.
Then the algorithm branches on all possible selections of the matchings of
$P_{xy}$.The depth of the recursion is upper-bounded by $n$. This implies that
$\textsc{EnumEquivalent}(L^{\prime},\mathcal{R}^{\prime})$ enumerates with
polynomial delay all nonempty matching cuts $M\in\mathcal{M}_{2}$ such that
$M^{\prime}\cap E(G^{\prime})$ is a nonempty matching cut of $G^{\prime}$
equivalent to $M$ withe that are equivalent to $M^{\prime}$.

To summarize, recall that if $H$ is connected and has a vertex of degree one,
we used the matching cut $\\{e^{*}\\}$ to list the matching cuts formed by the
edges of $F=G-E(G^{\prime})$. Clearly, $\\{e^{*}\\}$ is generated by
$\textsc{EnumEquivalent}(L^{\prime},\mathcal{R}^{\prime})$ for $L^{\prime}$
and $\mathcal{R}^{\prime}$ constructed for $M=\\{e^{*}\\}$. Therefore, we
conclude that the solution-lifting algorithm satisfies condition (ii∗) of the
definition of a polynomial-delay enumeration kernel. This finishes the proof
of the theorem. ∎

Using Theorems 11, 13, 4, and 2, we obtain the following corollary.

######  Corollary 3.

The (minimal) matching cuts of an $n$-vertex graph $G$ can be enumerated with
$2^{\mathcal{O}({\sf fn}(G))}\cdot n^{\mathcal{O}(1)}$ delay.

##  7 Enumeration Kernels for the Parameterization by the Clique Partition
Number

A partition $\\{Q_{1},\ldots,Q_{k}\\}$ of the vertex set of a graph $G$ is
said to be a _clique partition_ of $G$ if $Q_{1},\ldots,Q_{k}$ are cliques.
The _clique partition_ number of $G$, denoted by $\theta(G)$, is the minimum
$k$ such that $G$ has a clique partition with $k$ cliques. Notice that the
clique partition number of $G$ is exactly the chromatic number of its
complement $\overline{G}$. In particular, this means that deciding whether
$\theta(G)\leq k$ is $\operatorname{{\sf NP}}$-complete for any fixed $k\geq
3$ [22]. Therefore, throughout this section, we assume that the input graphs
are given together with their clique decompositions. With this assumption, we
show that the matching cut enumeration problems admit bijective kernels when
parameterized by the clique partition number. Our result uses the following
straightforward observation.

######  Observation 14.

Let $K$ be a clique of a graph $G$ such that $|K|\neq 2$. Then for every
partition $\\{A,B\\}$ of $V(G)$ such that $E(A,B)$ is a matching, either
$K\subseteq A$ or $K\subseteq B$.

######  Theorem 15.

Enum MC (Enum Minimal MC, Enum Maximal MC, respectively) admits a bijective
enumeration kernel with $\mathcal{O}(k^{3})$ vertices if the input graph is
given together with a clique partition of size at most $k$.

###### Proof.

We show a bijective enumeration kernel for Enum MC. Let $G$ be a graph and let
$\mathcal{Q}$ be a clique partition of $G$ of size at most $k$. We apply a
series of reduction rules.

First, we get rid of cliques of size two in $\mathcal{Q}$ to be able to use
Observation 14. We exhaustively apply the following rule.

######  Reduction Rule 15.1.

If $\mathcal{Q}$ contains a clique $Q=\\{x,y\\}$ of size two, then replace $Q$
by $Q_{1}=\\{x\\}$ and $Q_{2}=\\{y\\}$.

The rule does not affect $G$ and, therefore, it does not influence matching
cuts of $G$. To simplify notation, we use $\mathcal{Q}$ for the obtained
clique partition of $G$. Note that $|\mathcal{Q}|\leq 2k$.

By the next rule, we unify cliques that cannot be separated by a matching cut.

######  Reduction Rule 15.2.

If $\mathcal{Q}$ contains distinct cliques $Q_{1}$ and $Q_{2}$ such that
$E(Q_{1},Q_{2})$ is nonempty and is not a matching, then make each vertex of
$Q_{1}$ adjacent to every vertex of $Q_{2}$ and replace $Q_{1},Q_{2}$ by the
clique $Q=Q_{1}\cup Q_{2}$ in $\mathcal{Q}$.

To see that the rule is safe, notice that if there are two distinct cliques
$Q_{1},Q_{2}\in\mathcal{Q}$ such $E(Q_{1},Q_{2})$ is nonempty and is not a
matching, then for every partition $\\{A,B\\}$ of $V(G)$ such that $E(A,B)$ is
a matching cut, either $Q_{1},Q_{2}\subseteq A$ or $Q_{1},Q_{2}\subseteq B$,
because by Observation 14, each clique of $\mathcal{Q}$ is either completely
in $A$ or in $B$. This means that if $G^{\prime}$ is obtained from $G$ by the
application of Rule 15.2, then $M$ is a matching cut of $G^{\prime}$ if and
only if $M$ is a matching cut of $G$. Therefore, enumerating matching cuts of
$G$ is equivalent to enumerating matching cuts of $G^{\prime}$.

We apply Rule 15.2 exhaustively. Denote by $\hat{G}$ the obtained graph and by
$\hat{\mathcal{Q}}$ the obtained clique partition. Notice that the rule is
never applied for a pair of cliques of size one and, therefore,
$\hat{\mathcal{Q}}$ does not contain cliques of size two.

In the next step, we use the following marking procedure to label some
vertices of $\hat{G}$.

### Marking procedure.

  * (i)

For each pair $\\{Q_{1},Q_{2}\\}$ of distinct cliques of $\hat{\mathcal{Q}}$
such that $E(Q_{1},Q_{2})\neq\emptyset$, select arbitrarily an edge $uv\in
E(\hat{G})$ such that $u\in Q_{1}$ and $v\in Q_{2}$, and _mark_ $u$ and $v$.

  * (ii)

For each triple $Q,Q_{1},Q_{2}$ of distinct cliques of $\hat{\mathcal{Q}}$
such that some vertex of $Q$ is adjacent to a vertex in $Q_{1}$ and to a
vertex of $Q_{2}$, select arbitrarily $u\in Q$, $x\in Q_{1}$ and $y\in Q_{2}$
such that $ux,uy\in E(\hat{G})$, and then _mark_ $u,x,y$.

Notice that a vertex may be marked several times.

Our final rule reduces the size of the graph by deleting some unmarked
vertices.

######  Reduction Rule 15.3.

For every clique $Q\in\hat{\mathcal{Q}}$ of size at least three, consider the
set $X$ of unmarked vertices of $Q$ and delete arbitrary $\min\\{|X|,|Q|-3\\}$
vertices of $X$.

Denote by $\tilde{G}$ the obtained graph and denote by $\tilde{\mathcal{Q}}$
the corresponding clique partition of $\tilde{G}$ such that every clique of
$\tilde{\mathcal{Q}}$ is obtained by the deletion of unmarked vertices from a
clique of $\hat{\mathcal{Q}}$. Our kernelization algorithm return $\tilde{G}$
together with $\tilde{\mathcal{Q}}$ (recall that by our convention each
instance should be supplied with a clique partition of the input graph).

To upper bound the size of the obtained kernel, we show the following claim.

######  Claim 15.1.

The graph $\tilde{G}$ has at most $4k(3k^{2}-2k+1)$ vertices.

###### Proof of Claim 15.1.

Let $r=|\hat{\mathcal{Q}}|\leq 2k$. In Step (i) of the marking procedure, we
consider $\binom{r}{2}$ pairs of cliques of $\hat{\mathcal{Q}}$ and mark at
most $2\binom{r}{2}\leq 2k(2k-1)$ vertices in total. In Step (ii), we consider
$r$ cliques $Q$, and for each $Q$, we consider $\binom{r-1}{2}$ pairs
$\\{Q_{1},Q_{2}\\}$. This implies that we mark at most $3r\binom{r-1}{2}\leq
3k(2k-1)(2k-2)$ vertices in this step. Hence, the total number of marked
vertices is at most $3k(2k-1)(2k-2)+2k(2k-1)=2k(2k-1)(3k-2)$. Since each
clique of $\tilde{\mathcal{Q}}$ contains at most three unmarked vertices by
Rule 15.3, $|V(\tilde{G})|\leq 2k(2k-1)(3k-2)+3r\leq
2k(2k-1)(3k-2)+6k=4k(3k^{2}-2k+1)$. ∎

This completes the description of the kernelization algorithm. Now we show a
bijection between matching cuts of $G$ and $\tilde{G}$, and construct our
solution-lifting algorithm. Note that we already established that $M$ is a
matching cut of $\hat{G}$ if and only if $M$ is a matching cut of $G$.
Therefore, it is sufficient to construct a bijective mapping of the matching
cuts of $\tilde{G}$ to the matching cuts of $\hat{G}$.

Let $\hat{\mathcal{Q}}=\\{\hat{Q}_{1},\ldots,\hat{Q}_{r}\\}$ and
$\tilde{\mathcal{Q}}=\\{\tilde{Q}_{1},\ldots,\tilde{Q}_{r}\\}$, where
$\tilde{Q}_{i}\subseteq\hat{Q}_{i}$ for $i\in\\{1,\ldots,r\\}$. Notice that
$\hat{\mathcal{Q}}$ and $\tilde{\mathcal{Q}}$ have no cliques of size two.
Hence, we can use Observation 14. We show the following claim.

######  Claim 15.2.

For every partition $\\{I,J\\}$ of $\\{1,\ldots,r\\}$, $\hat{M}=E(\cup_{i\in
I}\hat{Q}_{i},\cup_{j\in J}\hat{Q}_{j})$ is a matching cut of $\hat{G}$ if and
only if $\tilde{M}=E(\cup_{i\in I}\tilde{Q}_{i},\cup_{j\in J}\tilde{Q}_{j})$
is a matching cut of $\tilde{G}$. Moreover, $\hat{M}=\emptyset$ if and only if
$\tilde{M}=\emptyset$.

###### Proof of Claim 15.2.

If $\hat{M}=E(\cup_{i\in I}\hat{Q}_{i},\cup_{j\in J}\hat{Q}_{j})$ is a
matching cut of $\hat{G}$, then $\tilde{M}$ is a matching cut of $\tilde{G}$,
because $\tilde{Q}_{i}\subseteq\hat{Q}_{i}$ for $i\in\\{1,\ldots,r\\}$.

For the opposite direction, assume that $\tilde{M}=E(\cup_{i\in
I}\tilde{Q}_{i},\cup_{j\in J}\tilde{Q}_{j})$ is a matching cut of $\tilde{G}$.
For the sake of contradiction, suppose that $\hat{M}=E(\cup_{i\in
I}\hat{Q}_{i},\cup_{j\in J}\hat{Q}_{j})$ is not a matching cut of $\hat{G}$.
This means that there is a vertex that is incident to at least two edges of
$\hat{M}$. By symmetry, we can assume without loss of generality that there is
$h\in I$ and $u\in\hat{Q}_{h}$ such that $u$ is adjacent to distinct vertices
$x$ and $y$, where $x\in\hat{Q}_{i}$ and $y\in\hat{Q}_{j}$ for some $i,j\in
J$.

Suppose that $i=j$, that is, $x$ and $y$ are in the same clique $\hat{Q}_{i}$.
Then, however, $E(\hat{Q}_{h},\hat{Q}_{i})$ is not a matching and we would be
able to apply Rule 15.2. Since Rule 15.2 was applied exhaustively to obtain
$\hat{G}$ and $\hat{\mathcal{Q}}$, this cannot happen. We conclude that $i\neq
j$.

By Step (ii) of the marking procedure, there is $u^{\prime}\in\hat{Q}_{h}$,
$x\in\hat{Q}_{i}$ and $y^{\prime}\in\hat{Q}_{j}$ such that
$u^{\prime}x^{\prime},u^{\prime}y^{\prime}\in E(\hat{G})$ and the vertices
$u^{\prime},x^{\prime},y^{\prime}$ are marked. This means that
$u^{\prime}\in\tilde{Q}_{h}$, $x^{\prime}\in\tilde{Q}_{i}$ and
$y^{\prime}\in\tilde{Q}_{j}$. Then
$u^{\prime}x^{\prime},u^{\prime}y^{\prime}\in\tilde{M}$ and $\tilde{M}$ is not
a matching; a contradiction. The obtained contradiction concludes the proof.

Finally, we show that $\hat{M}=\emptyset$ if and only if
$\tilde{M}=\emptyset$. Clearly, if $\hat{M}=\emptyset$, then
$\tilde{M}=\emptyset$. Suppose that $\hat{M}\neq\emptyset$. Then there are
$i\in I$ and $j\in J$ such that $uv\in\hat{M}$ for some $u\in\hat{Q}_{i}$ and
$v\in\hat{Q}_{j}$. By Step (i) of the marking procedure, there are
$u^{\prime}\in\hat{Q_{i}}$ and $v^{\prime}\in\hat{Q}_{j}$ such that
$u^{\prime}v^{\prime}\in E(\hat{G})$ and $u^{\prime},v^{\prime}$ are marked.
Then $u^{\prime}v^{\prime}\in E(\tilde{G})$ and
$u^{\prime}v^{\prime}\in\tilde{M}$ by the definition of $\tilde{M}$. Hence,
$\tilde{M}\neq\emptyset$. ∎

Using Claim 15.2, we are able to describe our solution-lifting algorithm. Let
$\tilde{M}$ be a matching cut of $\tilde{G}$. Let $\\{A,B\\}$ be a partition
of $V(\tilde{G})$ such that $\tilde{M}=E(A,B)$. By Observation 14, there is a
partition $\\{I,J\\}$ of $\\{1,\ldots,r\\}$ such that $A=\cup_{i\in
I}\tilde{Q}_{i}$ and $B=\cup_{j\in J}\tilde{Q}_{j}$. The solution-lifting
algorithm outputs $\hat{M}=E(\cup_{i\in I}\hat{Q}_{i},\cup_{j\in
J}\hat{Q}_{j})$.

To see correctness, note that $\hat{M}=E(\cup_{i\in I}\hat{Q}_{i},\cup_{j\in
J}\hat{Q}_{j})$ is a matching cut of $\hat{G}$ by Claim 15.2. Moreover, for
distinct matching cuts $\tilde{M}_{1}$ and $\tilde{M}_{2}$ of $\tilde{G}$, the
constructed matching cuts $\hat{M}_{1}$ and $\hat{M}_{2}$, respectively, of
$\hat{G}$ are distinct, that is, the matching cuts of $\tilde{G}$ are mapped
to the matching cuts of $\hat{G}$ injectively. Finally, to show that the
mapping is bijective, consider a matching cut $\hat{M}$ of $\hat{G}$. Let
$\\{A,B\\}$ be a partition of $V(\hat{G})$ with $\hat{M}=E(A,B)$. By
Observation 14, there is a partition $\\{I,J\\}$ of $\\{1,\ldots,r\\}$ such
that $A=\cup_{i\in I}\hat{Q}_{i}$ and $B=\cup_{j\in J}\hat{Q}_{j}$. Then
$\tilde{M}=E(\cup_{i\in I}\tilde{Q}_{i},\cup_{j\in J}\tilde{Q}_{j})$ is a
matching cut of $\tilde{G}$ by Claim 15.2, and it remains to observe that
$\hat{M}$ is constructed by the solution-lifting algorithm from $\tilde{M}$.

It is straightforward to see that both kernelization and solution-lifting
algorithms are polynomial. This concludes the construction of our bijective
enumeration kernel for Enum MC.

For Enum Minimal MC and Enum Maximal MC, the kernels are exactly the same. To
see it, note that our bijective mapping of the matching cuts of $\tilde{G}$ to
the matching cuts of $\hat{G}$ respects the inclusion relation. Namely, if
$\tilde{M}_{1}$ and $\tilde{M}_{2}$ are matching cuts of $\tilde{G}$ and
$\tilde{M}_{1}\subseteq\tilde{M}_{2}$, then $\tilde{M}_{1}$ and
$\tilde{M}_{2}$ are mapped to the matching cuts $\hat{M}_{1}$ and
$\hat{M}_{2}$, respectively, of $\hat{G}$ such that
$\hat{M}_{1}\subseteq\hat{M}_{2}$. This implies that the solution-lifting
algorithm outputs a minimal (maximal, respectively) matching cut of $\hat{G}$
for every minimal (maximal, respectively) matching cut of $\tilde{G}$.
Moreover, every minimal (maximal, respectively) matching cuts of $\hat{G}$ can
be obtained form a minimal (maximal, respectively) matching cut of
$\tilde{G}$. ∎

##  8 Conclusion

We initiated the systematic study of enumeration kernelization for several
variants of the matching cut problem. We obtained fully-polynomial
(polynomial-delay) enumeration kernels for the parameterizations by the vertex
cover number, twin-cover number, neighborhood diversity, modular width, and
feedback edge number. Since the solution-lifting algorithms are simple
branching algorithms, these kernels give a condensed view of the solution sets
which may be interesting in applications where one may want to inspect all
solutions manually. Restricting to polynomial-time and polynomial-delay
solution-lifting algorithms seems helpful in the sense that they will usually
be easier to understand.

There are many topics for further research in enumeration kernelization. For
Matching Cut, it would be interesting to investigate other structural
parameters, like the feedback vertex number (see [10] for the definition).
More generally, the area of enumeration kernelization seems still somewhat
unexplored. It would be interesting to see applications of the various kernel
types to other enumeration problems. For this, it seems to be important to
develop general tools for enumeration kernelizations. For example, is it
possible to establish a framework for enumeration kernelization lower bounds
similar to the techniques used for classical kernels [4, 5] (see also [10,
16])?

Concerning the counting and enumeration of matching cuts, we also proved the
upper bound $F(n+1)-1$ for the maximum number of matching cuts of an
$n$-vertex graph and showed that the bound is tight. What can be said about
the maximum number of minimal and maximal matching cuts? It is not clear
whether our lower bounds given in Propositions 3 and 4 are tight. Finally, it
seems promising to study enumeration kernels for $d$-Cut [23], a
generalization of Matching Cut that has recently received some attention.

## References

  * [1] N. R. Aravind, S. Kalyanasundaram, and A. S. Kare, On structural parameterizations of the matching cut problem, in Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II, X. Gao, H. Du, and M. Han, eds., vol. 10628 of Lecture Notes in Computer Science, 2017, pp. 475–482.
  * [2] M. Bentert, T. Fluschnik, A. Nichterlein, and R. Niedermeier, Parameterized aspects of triangle enumeration, J. Comput. Syst. Sci., 103 (2019), pp. 61–77.
  * [3] H. L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25 (1996), pp. 1305–1317.
  * [4] H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, J. Comput. Syst. Sci., 75 (2009), pp. 423–434.
  * [5] H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, Kernelization lower bounds by cross-composition, SIAM J. Discret. Math., 28 (2014), pp. 277–305.
  * [6] M. Bougeret, B. M. P. Jansen, and I. Sau, Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel, in 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), vol. 168 of LIPIcs, 2020, pp. 16:1–16:19.
  * [7] V. Chvátal, Recognizing decomposable graphs, Journal of Graph Theory, 8 (1984), pp. 51–53.
  * [8] B. Courcelle, Linear delay enumeration and monadic second-order logic, Discret. Appl. Math., 157 (2009), pp. 2675–2700.
  * [9] N. Creignou, A. Meier, J. Müller, J. Schmidt, and H. Vollmer, Paradigms for parameterized enumeration, Theory Comput. Syst., 60 (2017), pp. 737–758.
  * [10] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, 2015\.
  * [11] P. Damaschke, Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theor. Comput. Sci., 351 (2006), pp. 337–350.
  * [12] , Fixed-parameter enumerability of cluster editing and related problems, Theory Comput. Syst., 46 (2010), pp. 261–283.
  * [13] R. Diestel, Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics, Springer, 2012.
  * [14] H. Fernau, On parameterized enumeration, in Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings, vol. 2387 of Lecture Notes in Computer Science, Springer, 2002, pp. 564–573.
  * [15] F. V. Fomin and D. Kratsch, Exact Exponential Algorithms, Texts in Theoretical Computer Science. An EATCS Series, Springer, 2010.
  * [16] F. V. Fomin, D. Lokshtanove, S. Saurabh, and M. Zehavi, Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, Cambridge, 2019.
  * [17] F. V. Fomin, S. Saurabh, and Y. Villanger, A polynomial kernel for proper interval vertex deletion, SIAM J. Discret. Math., 27 (2013), pp. 1964–1976.
  * [18] J. Gajarský, M. Lampis, and S. Ordyniak, Parameterized algorithms for modular-width, in Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, vol. 8246 of Lecture Notes in Computer Science, Springer, 2013, pp. 163–176.
  * [19] R. Ganian, Twin-cover: Beyond vertex cover in parameterized algorithmics, in Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, D. Marx and P. Rossmanith, eds., vol. 7112 of Lecture Notes in Computer Science, Springer, 2011, pp. 259–271.
  * [20] , Using neighborhood diversity to solve hard problems, CoRR, abs/1201.3091 (2012).
  * [21] , Improving vertex cover as a graph parameter, Discret. Math. Theor. Comput. Sci., 17 (2015), pp. 77–100.
  * [22] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
  * [23] G. C. M. Gomes and I. Sau, Finding cuts of bounded degree: Complexity, FPT and exact algorithms, and kernelization, in 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, B. M. P. Jansen and J. A. Telle, eds., vol. 148 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 19:1–19:15.
  * [24] R. L. Graham, On primitive graphs and optimal vertex assignments, Ann. New York Acad. Sci., 175 (1970), pp. 170–186.
  * [25] S. Hsieh, H. Le, V. B. Le, and S. Peng, Matching cut in graphs with large minimum degree, in Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi’an, China, July 29-31, 2019, Proceedings, D. Du, Z. Duan, and C. Tian, eds., vol. 11653 of Lecture Notes in Computer Science, Springer, 2019, pp. 301–312.
  * [26] G. Karakostas, A better approximation ratio for the vertex cover problem, ACM Trans. Algorithms, 5 (2009), pp. 41:1–41:8.
  * [27] C. Komusiewicz, D. Kratsch, and V. B. Le, Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms, Discret. Appl. Math., 283 (2020), pp. 44–58.
  * [28] C. Komusiewicz and J. Uhlmann, A cubic-vertex kernel for flip consensus tree, Algorithmica, 68 (2014), pp. 81–108.
  * [29] D. Kratsch and V. B. Le, Algorithms solving the matching cut problem, Theor. Comput. Sci., 609 (2016), pp. 328–335.
  * [30] S. Kratsch, Recent developments in kernelization: A survey, Bull. EATCS, 113 (2014).
  * [31] M. Lampis, Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64 (2012), pp. 19–37.
  * [32] D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh, Lossy kernelization, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, H. Hatami, P. McKenzie, and V. King, eds., ACM, 2017, pp. 224–237.
  * [33] A. Marino, Analysis and enumeration, vol. 6 of Atlantis Studies in Computing, Atlantis Press, Paris, 2015.  Algorithms for biological graphs, With forewords by Tiziana Calamoneri and Pierluigi Crescenzi.
  * [34] K. Meeks, Randomised enumeration of small witnesses using a decision oracle, Algorithmica, 81 (2019), pp. 519–540.
  * [35] A. Meier, Parametrised enumeration, Habilitation thesis, Leibniz Universität Hannover, 2020.
  * [36] S. Oum, Approximating rank-width and clique-width quickly, ACM Trans. Algorithms, 5 (2008), pp. 10:1–10:20.
  * [37] S. Oum and P. D. Seymour, Approximating clique-width and branch-width, J. Comb. Theory, Ser. B, 96 (2006), pp. 514–528.
  * [38] M. Samer and S. Szeider, Backdoor trees, in Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, D. Fox and C. P. Gomes, eds., AAAI Press, 2008, pp. 363–368.
  * [39] M. Tedder, D. G. Corneil, M. Habib, and C. Paul, Simpler linear-time modular decomposition via recursive factorizing permutations, in Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, vol. 5125 of Lecture Notes in Computer Science, Springer, 2008, pp. 634–645.
  * [40] K. Wasa, Enumeration of enumeration algorithms, CoRR, abs/1605.05102 (2016).


Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC
BY 4.0).

Proceedings of the Iberian Languages Evaluation Forum (IberLEF 2020)

[orcid=0000-0001-5620-4916, ]

[orcid=0000-0001-6830-9176, ]

# Overview of CAPITEL Shared Tasks at IberLEF 2020: Named Entity Recognition
and Universal Dependencies Parsing

Jordi Porta-Zamorano<EMAIL_ADDRESS>Centro de Estudios de la Real Academia
Española, Madrid, Spain  Luis Espinosa-Anke<EMAIL_ADDRESS>School
of Computer Science and Informatics, Cardiff University, UK

(2020)

###### Abstract

We present the results of the CAPITEL-EVAL shared task, held in the context of
the IberLEF 2020 competition series. CAPITEL-EVAL consisted on two subtasks:
(1) Named Entity Recognition and Classification and (2) Universal Dependency
parsing. For both, the source data was a newly annotated corpus, CAPITEL, a
collection of Spanish articles in the newswire domain. A total of seven teams
participated in CAPITEL-EVAL, with a total of 13 runs submitted across all
subtasks. Data, results and further information about this task can be found
at sites.google.com/view/capitel2020.

###### keywords:

IberLEF named entity recognition and classification NERC Universal
Dependencies parsing evaluation

##  1 Introduction

Within the framework of the Spanish National Plan for the Advancement of
Language Technologies (PlanTL111https://www.plantl.gob.es), the Royal Spanish
Academy (RAE) and the Secretariat of State for Digital Advancement (SEAD) of
the Ministry of Economy signed an agreement for developing a linguistically
annotated corpus of Spanish news articles, aimed at expanding the language
resource infrastructure for the Spanish language. The name of this corpus is
CAPITEL (Corpus del Plan de Impulso a las Tecnologías del Lenguaje), and is
composed of contemporary news articles thanks to agreements with a number of
news media providers. CAPITEL has three levels of linguistic annotation:
morphosyntactic (with lemmas and Universal Dependencies-style POS tags and
features), syntactic (following Universal Dependencies v2), and named
entities.

The linguistic annotation of a subset of the CAPITEL corpus has been revised
using a machine-annotation-followed-by-human-revision procedure. Manual
revision has been carried out by a team of graduated linguists following a set
of Annotation Guidelines created specifically for CAPITEL. The named entity
and syntactic layers of revised annotations comprise about 1 million words for
the former, and roughly 300,000 for the latter. Due to the size of the corpus
and the nature of the annotations, we proposed two IberLEF sub-tasks under the
more general, umbrella task of CAPITEL @ IberLEF 2020: (1) Named Entity
Recognition and Classification and (2) Universal Dependency Parsing.

##  2 Sub-task 1: NERC

###  2.1 Description

Information extraction tasks, formalized in the late 1980s, are designed to
evaluate systems which capture information present in free text, with the goal
of enabling better and faster information and content access. One important
subset of this information comprises named entities (NE), which, roughly
speaking, are textual elements corresponding to names of people, places,
organizations and others. Three processes can be applied to NEs: recognition
or identification (NER), categorization, i.e., assigning a type according to a
predefined set of semantic categories (NERC), and linking, which consists of
disambiguating the in-text mention against a knowledge base or sense inventory
(NEL). Since their advent, NER tasks have had notable success, but despite the
relative maturity of this subfield, work and research continues to evolve, and
new techniques and models appear alongside challenging datasets in different
languages, domains and textual genres. The aim of this sub-task, thus, was to
challenge participants to apply their systems or solutions to the problem of
identifying and classifying NEs in Spanish news articles. This two-stage
process falls within the NERC evaluation framework.

The following NE categories were evaluated: Person (PER), Location (LOC),
Organization (ORG) and Other (OTH) as defined in the Annotation Guidelines [1]
that were shared with participants. The criteria for the identification and
classification of entities were based on the capitalization chapter of the
Spanish language orthography [2]. The contextual meaning has been considered
in the classification of entities, so that an entity such as _Madrid_ can be
classified as PER (a surname), LOC (the city), ORG (the football team) of even
OTH (a book title). Moreover, in terms of nesting, only the longest-spanning
entities were considered, and coordinated entities are considered one single
entity except for those where the name indicating the nature of the NE is used
in plural to introduce several entities ([_Islas Baleares_]${}_{\textsc{loc}}$
_y_ [_Canarias_]${}_{\textsc{loc}}$).

###  2.2 Dataset

A one-million-word subset of the CAPITEL corpus was randomly sampled into
three subsets: training, development and test. The training set comprises 60%
of the corpus, whereas the development and test sets roughly amount to 20%
each. Descriptive statistics for these splits are provided in Table 1.
Together with the test set release, an additional collection of documents
(background set) was delivered to ensure that participating teams were not be
able to perform manual corrections, and also to encourage features such as
scalability to larger data collections. Finally, all documents were tokenized
and tagged with NEs following an IOBES format.

Table 1: Description of the data for CAPITEL sub-task 1: NERC Dataset | PER | LOC | ORG | OTH | Sents. | Tokens
---|---|---|---|---|---|---
train | 9,087 | 7,513 | 9,285 | 5,426 | 22,647 | 606,418
devel | 2,900 | 2,490 | 3,058 | 1,781 | 7,549 | 202,408
test | 2,996 | 2,348 | 3,143 | 1,739 | 7,549 | 199,773
Total | 14,983 | 12,351 | 15,486 | 8,946 | 37,745 | 1,008,599

###  2.3 Evaluation Metrics

The metrics used for evaluation were Precision (the percentage of named
entities in the system’s output that are correctly recognized and classified),
Recall (the percentage of named entities in the test set that were correctly
recognized and classified) and macro averaged F1 score (the harmonic mean of
Precision and Recall), with the latter being used as the official evaluation
score and for the final ranking of the participating teams.

###  2.4 Systems and Results

We had 22 registrations, 5 final participants with 9 systems submitted and 4
system descriptions.

The Ragerri Team from HiTZ Center-Ixa UPV/EHU presents in [3] the combination
of several systems based on Flair [4] and Transformer architectures [5]. They
perform experiments with Multilingual BERT (mBERT), XML-RoBERTa (base), BETO
(BETO is a BERT-based model pre-trained with Spanish texts [6]), and Flair
off-the-shelf models for Spanish and a monolingual model trained with the
OSCAR corpus. All the individual systems’ F1 were within 88.29-89.95% and the
combination of five of them using a simple agreement scheme of three achieved
the first rank with a 90.30% F1.

The Vicomtech Team presents in [7] a system based on the BERT architecture and
several experiments using multilingual BERT (mBERT) and BETO pre-trained
models. BERT models are used to give each token a contextual embedding that
are then passed to a fully connected layer to classify each of these tokens.
Their work addresses also several interesting issues with the BETO vocabulary
and tokenizer, namely: punctuation marks missing in the tokenizer’s vocabulary
and problems with certain diacritics and characters. Their systems were fine-
tuned with CAPITEL training data and results were 2-3% F1 lower than the best
performing system.

The Yanghao Team from Huawei Translation Service Center presents in [8] a
system that uses Multilingual BERT as encoder and a linear layer as a
classifier, and is trained with additional 38,000 sentences from WMT news
translation corpus [9] annotated using Spacy [10]. Their experimental results
suggest that pre-training with the augmented set and then fine-tune on CAPITEL
improves performance when compared to training on any of them separately or
mixed.

The Lirondos Team from ISI-USC presents in [11] two sequence labelling
systems: A CRF model with handcrafted features and a BiLSTM-CRF model with
word and character embeddings. A feature ablation study demonstrated that all
features contribute positively to the CRF model, with word embeddings being
the most informative feature, yielding an F1 score of 84.39%. On the other
hand, their BiLSTM-CRF model obtained an F1 score of 83.01%. A interesting
error analysis has shown that many of the errors correspond to OTH entities,
contextual annotation of some entities (OTH versus ORG or LOC versus ORG),
nested entities, and person nicknames with unusual typographical shapes.

Finally, the LolaZarra Team was ranked the last and did not submit any system
description paper.

Table 2: Results of the CAPITEL sub-task 1: NERC. Rank | Team | Ref. | Metric | PER | LOC | ORG | OTH | Micro | Macro
---|---|---|---|---|---|---|---|---|---
(1) | ragerri | [3] | P | 96.40 | 90.47 | 88.63 | 83.36 | 90.50 | 90.43
R | 97.46 | 91.74 | 87.31 | 80.68 | 90.17 | 90.17
F1 | 96.93 | 91.10 | 87.96 | 82.00 | 90.34 | 90.30
(2) | ragerri | [3] | P | 96.50 | 90.19 | 88.05 | 84.37 | 90.46 | 90.39
R | 97.46 | 91.27 | 87.21 | 81.02 | 90.09 | 90.09
F1 | 96.98 | 90.73 | 87.63 | 82.66 | 90.27 | 90.23
(3) | ragerri | [3] | P | 96.69 | 90.56 | 88.03 | 83.39 | 90.42 | 90.36
R | 97.60 | 91.14 | 87.24 | 80.56 | 90.04 | 90.04
F1 | 97.14 | 90.85 | 87.63 | 81.95 | 90.23 | 90.19
(4) | mcuadros | [7] | P | 93.48 | 89.36 | 85.76 | 79.63 | 87.88 | 87.81
R | 96.70 | 88.03 | 85.87 | 77.34 | 88.09 | 88.09
F1 | 95.06 | 88.69 | 85.82 | 78.47 | 87.99 | 87.94
(5) | yanghao | [8] | P | 94.30 | 87.30 | 84.99 | 79.52 | 87.38 | 87.32
R | 96.16 | 89.86 | 85.94 | 77.69 | 88.43 | 88.43
F1 | 95.22 | 88.56 | 85.46 | 78.59 | 87.90 | 87.87
(6) | lirondos | [11] | P | 92.48 | 83.42 | 83.76 | 75.03 | 84.93 | 84.75
R | 94.46 | 86.97 | 80.43 | 69.12 | 84.12 | 84.12
F1 | 93.46 | 85.15 | 82.06 | 71.95 | 84.52 | 84.39
(7) | LolaZarra | - | P | 91.52 | 83.39 | 80.10 | 78.31 | 83.93 | 83.90
R | 92.62 | 80.41 | 83.39 | 73.72 | 83.77 | 83.77
F1 | 92.07 | 81.87 | 81.71 | 75.95 | 83.85 | 83.80
(8) | lirondos | [11] | P | 94.37 | 85.68 | 84.20 | 65.47 | 83.93 | 84.33
R | 90.72 | 83.35 | 78.14 | 71.08 | 81.82 | 81.82
F1 | 92.51 | 84.50 | 81.06 | 68.16 | 82.86 | 83.01
(9) | lirondos | [11] | P | 93.23 | 82.05 | 84.55 | 63.89 | 82.67 | 83.01
R | 90.09 | 82.54 | 73.85 | 67.17 | 79.46 | 79.46
F1 | 91.63 | 82.29 | 78.84 | 65.49 | 81.03 | 81.11

##  3 Sub-task 2: UD Parsing

###  3.1 Description

Dependency-based syntactic parsing has become popular in NLP in recent years.
One of the reasons for this popularity is the transparent encoding of
predicate-argument structures, which is useful in many downstream
applications. Another reason is that it is better suited than phrase-structure
grammars for languages with free or flexible word order. Universal
Dependencies (UD) is a framework for consistent annotation of grammar (parts
of speech, morphological features and syntactic dependencies) across different
human languages. Moreover, the UD initiative is an open community effort with
over 200 contributors which has produced more than 100 treebanks in over 70
languages.

The aim of this sub-task was to challenge participants to apply their systems
or solutions to the problem of Universal Dependency parsing of Spanish news
articles as defined in the Annotation Guidelines for the CAPITEL corpus [12].

###  3.2 Dataset

A 300,000-word subset of CAPITEL was provided for this sub-task. In addition
to head and dependency relations in CoNLL-U format, this subset was also
tokenized and annotated with lemmas and UD tags and features. Similarly to the
NERC dataset, we randomly sampled it into three subsets: training, development
and test. The training set comprises about 50% of the corpus, whereas the
development and test sets roughly amount to 25% each. The description of the
data sets can be found in Table 3. In addition, the distribution of labels in
the test set is given in Table 5 along with the results of the sub-task.
Together with the test set release, an additional collection of documents
(background set) were included to ensure that participating teams were not be
able to perform manual corrections, and also to encourage features such as
scalability to larger data collections.

Table 3: Description of the data for CAPITEL sub-task 2: UD Parsing Dataset | Sents. | Tokens
---|---|---
train | 7,086 | 185,560
devel | 2,362 | 61,137
test | 2,363 | 62,682
Total | 11,811 | 309,379

###  3.3 Evaluation Metrics

The metrics for the evaluation phase were Unlabeled Attachment Score (UAS):
The percentage of words that have the correct head, and Labeled Attachment
Score (LAS): The percentage of words that have the correct head and dependency
label, with the latter being used as the official evaluation score, and for
the final ranking of the participating teams.

###  3.4 Systems and Results

We had, in this subtask, 12 registrations, 2 final participants with 4
submitted systems and 2 system descriptions.

The Vicomtech Team presents in [7] a system based on the BERT architecture and
several experiments using multilingual BERT (mBERT) and BETO pre-trained
models. BERT models are used to encode a matrix of all-vs-all token encoding
vectors and then pass to several classification layers predicting the
connectivity of tokens and their relation types. Their work addresses also
some issues that had been explained in 2.1. Their systems were fine-tuned with
CAPITEL training data and results on the development set were slightly better
using BETO (UAS: 91.540, LAS: 88.410) instead of mBERT (UAS: 91.220, LAS:
87.860), so only the BETO results were submitted as their official run.

MartínLendinez Team presents in [13] the combination of the output of
different UD parsing toolkits using a voting scheme and the augmentation of
the training set with 14,305 annotated sentences from the AnCora annotated
corpus [14].222There is also a discussion on some differences in terms of
tokenization and analysis between CAPITEL and AnCora. Three different toolkits
were selected not because of their performance in similar tasks but for their
accessibility and documentation. These toolkits were UDPipe [15], NLP-Cube
[16] and Stanza [17]. As we can see in the summary provided in Table 4, the
final submitted results were obtained with Stanza trained on CAPITEL (4),
Stanza trained on CAPITEL and AnCora (3), and the combination of the previous
two plus NLP-Cube trained on CAPITEL (1).

Table 4: Results of the CAPITEL sub-task 2: UD Parsing Rank | Team | Ref. | UAS | LAS
---|---|---|---|---
(1) | MartinLendinez (CACV) | [13] | 91.935 | 88.660
(2) | Vicomtech (BETO) | [7] | 91.875 | 88.600
(3) | MartinLendinez (CA) | [13] | 91.773 | 88.531
(4) | MartinLendinez (C) | [13] | 91.715 | 88.467

As it can be seen in Table 4, results on this sub-task are very tight, with
first and second systems being only 0.06% apart, and with only 0.193% between
first and fourth. The submission by MartínLendinez was the highest ranked, and
Vicomtech the simplest, and acknowledged and described by the authors as a
sort of BERT-based baseline. We provide a breakdown of the results by relation
type in Table 5.

Table 5: Detailed results of the CAPITEL sub-task 2: UD Parsing | (1) | (2) | (3) | (4)
---|---|---|---|---
Label | Freq. | UAS | LAS | UAS | LAS | UAS | LAS | UAS | LAS
acl | 501 | 80.04 | 65.47 | 82.44 | 67.27 | 80.04 | 65.67 | 79.04 | 65.27
acl:relcl | 1,004 | 74.90 | 73.61 | 79.68 | 78.19 | 75.50 | 74.30 | 74.70 | 73.41
advcl | 1,004 | 79.18 | 73.11 | 78.29 | 71.02 | 78.69 | 73.11 | 79.18 | 73.61
advmod | 2,062 | 87.92 | 85.01 | 87.34 | 83.75 | 86.23 | 83.51 | 87.20 | 83.95
amod | 3,228 | 96.96 | 94.95 | 96.78 | 94.24 | 96.81 | 94.76 | 97.00 | 95.26
appos | 1,090 | 85.50 | 77.61 | 84.22 | 74.50 | 84.40 | 76.70 | 84.86 | 76.79
aux | 259 | 40.93 | 31.27 | 52.51 | 46.72 | 48.26 | 38.22 | 40.93 | 30.89
aux:pass | 56 | 100.00 | 94.64 | 98.21 | 83.93 | 100.00 | 94.64 | 100.00 | 94.64
case | 8,705 | 98.99 | 98.70 | 98.78 | 98.24 | 98.83 | 98.55 | 99.05 | 98.74
cc | 2,018 | 95.29 | 92.86 | 95.00 | 92.72 | 95.14 | 92.77 | 94.50 | 92.02
ccomp | 399 | 90.73 | 83.71 | 90.48 | 84.21 | 90.73 | 83.96 | 88.72 | 81.45
compound | 22 | 63.64 | 18.18 | 81.82 | 45.45 | 59.09 | 13.64 | 68.18 | 27.27
conj | 2,361 | 76.20 | 73.27 | 77.42 | 74.29 | 76.37 | 73.36 | 75.60 | 72.47
cop | 925 | 93.30 | 89.84 | 93.19 | 89.84 | 93.95 | 90.49 | 92.76 | 89.51
csubj | 111 | 81.08 | 60.36 | 83.78 | 63.96 | 82.88 | 62.16 | 79.28 | 52.25
dep | 28 | 75.00 | 7.14 | 67.86 | 3.57 | 75.00 | 7.14 | 71.43 | 7.14
det | 8,840 | 99.42 | 99.37 | 99.29 | 99.17 | 99.33 | 99.29 | 99.38 | 99.32
discourse | 36 | 80.56 | 2.78 | 86.11 | 8.33 | 77.78 | 2.78 | 77.78 | 5.56
expl | 46 | 97.83 | 6.52 | 95.65 | 41.30 | 97.83 | 6.52 | 97.83 | 23.91
expl:impers | 29 | 93.10 | 6.90 | 86.21 | 20.69 | 93.10 | 6.90 | 89.66 | 10.34
expl:pass | 360 | 99.44 | 75.56 | 99.17 | 82.50 | 99.44 | 75.56 | 98.89 | 79.72
expl:pv | 343 | 97.67 | 70.85 | 97.67 | 74.05 | 97.38 | 70.55 | 97.38 | 68.22
fixed | 219 | 71.23 | 68.04 | 71.23 | 65.75 | 70.32 | 66.67 | 71.23 | 68.49
flat | 130 | 92.31 | 45.38 | 88.46 | 53.85 | 91.54 | 45.38 | 90.77 | 50.00
flat:foreign | 409 | 90.71 | 86.80 | 78.48 | 70.17 | 91.44 | 87.53 | 91.69 | 87.29
goeswith | 2 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00
iobj | 329 | 94.22 | 77.51 | 91.19 | 72.95 | 93.62 | 76.90 | 92.40 | 69.91
mark | 1,992 | 91.62 | 85.99 | 92.67 | 86.75 | 92.12 | 86.40 | 91.47 | 85.94
mark:iobj | 9 | 100.00 | 33.33 | 88.89 | 44.44 | 100.00 | 33.33 | 100.00 | 22.22
mark:mod | 282 | 93.97 | 79.79 | 93.97 | 83.69 | 93.62 | 79.43 | 94.33 | 80.85
mark:obj | 119 | 89.92 | 49.58 | 89.92 | 55.46 | 90.76 | 50.42 | 90.76 | 42.86
mark:subj | 816 | 94.24 | 87.99 | 95.10 | 87.01 | 94.61 | 88.36 | 93.87 | 88.36
nmod | 4,609 | 88.24 | 87.18 | 89.48 | 88.15 | 88.28 | 87.22 | 87.85 | 86.77
nsubj | 2,302 | 93.61 | 89.27 | 93.53 | 89.27 | 93.61 | 89.23 | 93.01 | 86.92
nsubj:pass | 29 | 96.55 | 58.62 | 96.55 | 55.17 | 96.55 | 58.62 | 96.55 | 55.17
nummod | 689 | 97.68 | 96.66 | 97.68 | 95.36 | 97.53 | 96.37 | 97.97 | 96.37
obj | 2,235 | 98.61 | 89.80 | 97.67 | 90.65 | 98.39 | 89.75 | 98.30 | 91.50
obl | 3,298 | 87.54 | 81.96 | 87.17 | 81.78 | 87.48 | 82.05 | 87.72 | 82.20
obl:agent | 94 | 98.94 | 86.17 | 97.87 | 85.11 | 100.00 | 87.23 | 97.87 | 90.43
orphan | 17 | 70.59 | 0.00 | 70.59 | 0.00 | 70.59 | 0.00 | 64.71 | 0.00
parataxis | 881 | 74.01 | 59.82 | 72.76 | 60.39 | 72.99 | 58.80 | 74.35 | 61.29
punct | 8,028 | 89.09 | 88.95 | 88.17 | 88.02 | 88.64 | 88.52 | 88.78 | 88.61
root | 2,394 | 93.27 | 93.07 | 93.48 | 93.32 | 93.23 | 93.02 | 92.86 | 92.65
xcomp | 372 | 75.81 | 69.09 | 80.38 | 72.31 | 72.04 | 65.59 | 79.03 | 71.51
Total | 62,682 | 91.935 | 88.660 | 91.875 | 88.600 | 91.773 | 88.531 | 91.715 | 88.467

##  4 Conclusions

Most of the submitted systems obtained good results overall. In both sub-
tasks, the majority of them uses BERT, either multilingual or monolingual and
some systems combines the output of several models. Also the augmentation of
data from other corpora, or produced by other annotation systems, added to the
training data or used to fine-tune the models, despite the heterogeneity of
the annotations or domain differences have shown some modest improvements.

##  5 Acknowledgements

We would like to thank specially to David Pérez Fernández, Doaa Samy, and all
the people involved in the PlanTL, for their contribution in making these
shared tasks possible, and José-Luis Sancho-Sánchez and Rafael-J. Ureña-Ruiz
from the Centro de Estudios de la RAE for their help in preparing the data. We
would also like to thank the task participants who provided helpful inputs to
improve the quality of the dataset and the task itself.

## References

  * Porta-Zamorano and Romeu Fernández [2019] J. Porta-Zamorano, J. Romeu Fernández, Esquema de anotación sintáctica de CAPITEL, Technical Report, Centro de Estudios de la Real Academia Española, 2019.
  * RAE and ASALE [2010] RAE, ASALE, Ortografía de la lengua española, 2010.
  * Agerri and Rigau [2020] R. Agerri, G. Rigau,  Projecting Heterogeneous Annotations for Named Entity Recognition,  in: Proceedings of the Iberian Languages Evaluation Forum (IberLEF 2020), 2020.
  * Akbik et al. [2018] A. Akbik, D. Blythe, R. Vollgraf,  Contextual string embeddings for sequence labeling,  in: Proceedings of the 27th International Conference on Computational Linguistics, 2018.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, I. Polosukhin,  Attention is all you need,  in: Advances in Neural Information Processing Systems 30, 2017.
  * Cañete et al. [2020] J. Cañete, G. Chaperon, R. Fuentes, J. Pérez,  Spanish Pre-Trained BERT Model and Evaluation Data,  in: Proceedings of the Practical ML for Developing Countries Workshop at the Eight International Conference on Learning Representations (ICLR 2020), 2020.
  * García Pablos et al. [2020] A. García Pablos, M. Cuadros, E. Zotova,  Vicomtech at CAPITEL 2020: Facing Entity Recognition and Universal Dependency Parsing of Spanish News Articles with BERT models,  in: Proceedings of the Iberian Languages Evaluation Forum (IberLEF 2020), 2020.
  * Lei et al. [2020] L. Lei, M. Wang, H. Yang, S. Sun, Y. Qin, D. Wei,  System Report of HW-TSC on the CAPITEL NER Evaluation,  in: Proceedings of the Iberian Languages Evaluation Forum (IberLEF 2020), 2020.
  * Tiedemann [2012] J. Tiedemann,  Parallel Data, Tools and Interfaces in OPUS,  in: Proceedings of the Eight International Conference on Language Resources and Evaluation (LREC’12), 2012\.
  * Honnibal and Montani [2017] M. Honnibal, I. Montani, spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing, 2017\.
  * Álvarez Mellado [2020] E. Álvarez Mellado,  Two Models for Named Entity Recognition in Spanish: Submission for the CAPITEL Shared Task at IberLEF 2020,  in: Proceedings of the Iberian Languages Evaluation Forum (IberLEF 2020), 2020.
  * Porta-Zamorano and Romeu Fernández [2019] J. Porta-Zamorano, J. Romeu Fernández, Esquema de anotación de entidades nombradas de CAPITEL, Technical Report, Centro de Estudios de la Real Academia Española, 2019.
  * Sánchez-León [2020] F. Sánchez-León,  Combining Different Parsers and Datasets for CAPITEL UD Parsing,  in: Proceedings of the Iberian Languages Evaluation Forum (IberLEF 2020), 2020.
  * Taulé et al. [2008] M. Taulé, M. A. Martí, M. Recasens,  AnCora: Multilevel Annotated Corpora for Catalan and Spanish,  in: Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC’08), 2008\.
  * Straka and Straková [2017] M. Straka, J. Straková,  Tokenizing, POS Tagging, Lemmatizing and Parsing UD 2.0 with UDPipe,  in: Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, 2017\.
  * Boros et al. [2018] T. Boros, S. D. Dumitrescu, R. Burtica,  NLP-Cube: End-to-End Raw Text Processing With Neural Networks,  in: Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, 2018\.
  * Qi et al. [2020] P. Qi, Y. Zhang, Y. Zhang, J. Bolton, C. D. Manning,  Stanza: A Python Natural Language Processing Toolkit for Many Human Languages,  in: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, 2020\.


# Box counting dimensions of generalised fractal nests

Siniša<EMAIL_ADDRESS>
Juraj Dobrila University of Pula
Faculty of Informatics
52 100 Pula, Croatia

###### Abstract

Fractal nests are sets defined as unions of unit $n$-spheres scaled by a
sequence of $k^{-\alpha}$ for some $\alpha>0$. In this article we generalise
the concept to subsets of such spheres and find the formulas for their box
counting dimensions. We introduce some novel classes of parameterised fractal
nests and apply these results to compute the dimensions with respect to these
parameters. We also show that these dimensions can be seen numerically. These
results motivate further research that may explain the unintuitive behaviour
of box counting dimensions for nest-type fractals, and in general the class of
sets where the box-counting dimension differs from the Hausdorff dimension.

##  1 Introduction

Research into rectifiability (eg. [Tri93]) has given some unexpected results
in the differences between the Hausdorff dimension [Fed69, pg. 171] and the
box counting dimension of some countable unions of sets and their smooth
generalisations [Tri93, pg. 121-122], such as unrectifiable spirals. Recently,
progress has been made in the application of the box counting dimension in the
analysis of complex zeta functions, [LRŽ17]. We note especially the discovery
of various interesting properties, including a relationship of Lapidus-style
zeta functions with the Riemann zeta function and the generalisation of the
concept of the box dimension to complex dimensions. Fractal nests, as
presented and analysed in [LRŽ17], behave in an unexpected way with respect to
the appropriate exponents. There are two general types of behaviour of fractal
nests. The well understood type of behaviour of fractal nests concerns sets
that locally resemble Cartesian products of fractals [LRŽ17, pg. 227], [ŽŽ05,
Remark 6.]. In such sets, the dimension behaves naturally as the sum of the
dimensions of “base” sets. What remains less understood are dimensions of
fractal nests of centre type. In this case, the dimension is product-like in
terms of dimensions of underlying elements, lacking an intuitive geometric
interpretation.

This article focuses on a more classical approach to the box-counting
dimension, giving examples that may further the understanding of how the box
counting dimension behaves with respect to countable unions of similar sets.
Whereas in [LRŽ17] and [ŽŽ05] the fractal nests studied are based on
$(n-1)$-spheres (hyper-spheres), we study fractal nests $S_{\alpha}$ based on
fractal subsets of box counting dimension $\delta$ of such spheres under
similar scaling. Our results are compatible with the cited ones, having them
as limit cases of full dimension, $\delta=(n-1)$; notably, the dimension are

$\dim_{B}S_{\alpha}=\frac{\delta+1}{\alpha+1}$

for the centre type and

$\dim_{B}S_{\alpha}=\delta+\frac{1}{\alpha+1}$

for the outer type. The proofs of these results hint at some more general
geometric and topological properties.

This paper is divided into five sections. After this introduction we present
the main concepts and results of this paper – a dimensional analysis of
generalised fractal nests, followed by applications of these results to novel
fractal sets with numerical examples. After that, we provide the proofs of our
main results and in the final section we remark on some issues and problems
that naturally arise from these investigations.

##  2 Generalised fractal nests

###  2.1 Box counting dimension

We start with the definition of the box counting dimension as stated in
[Fal14, pg. 28] as the alternative definition. By an $\epsilon$-mesh in
${\mathbb{R}}^{n}$ we understand the partition of ${\mathbb{R}}^{n}$ into
disjoint (except possibly at the border) $n$-cubes of side $\epsilon$.

######  Definition 1.

Let $S\subseteq{\mathbb{R}}^{n}$ be a bounded Borel set. By $N_{\epsilon}(S)$
we denote the number of such $n$-cubes of the $\epsilon$-mesh of
${\mathbb{R}}^{n}$ that intersect $S$. We define the upper (lower) box
counting dimension of $S$ by

$\displaystyle\overline{\dim}_{B}S$
$\displaystyle=\inf\left\\{\delta\,\Big{|}\,\epsilon^{\delta}N_{\epsilon}(S)\to
0\right\\}.$ $\displaystyle\bigg{(}\underline{\dim}_{B}S$
$\displaystyle=\sup\left\\{\delta\,\Big{|}\,\epsilon^{\delta}N_{\epsilon}(S)\to+\infty\right\\}\bigg{)}.$

######  Example 1.

The unit $m$-cube $K_{m}=[0,1]^{m}\times\\{0\\}^{n-m}$ in ${\mathbb{R}}^{n}$
with $m\leq n$ has

$\overline{\dim}_{B}K_{m}=\underline{\dim}_{B}K_{m}=m$

because it intersects $\left\lceil\epsilon^{-1}\right\rceil^{m}$ $n$-cubes of
side $\epsilon$. Hence, for various $\delta$ we have, as $\epsilon\to 0$,

$\epsilon^{\delta}\left\lceil\epsilon^{-1}\right\rceil^{m}\to\begin{cases}0,\hbox{
for }\delta>m,\\\ 1,\hbox{ for }\delta=m,\\\ +\infty,\hbox{ for
}\delta<m.\end{cases}$

The box counting dimension of a set $S$ can be defined in terms of other
counting functions, such as the maximum number of disjoint $\epsilon$-balls
centred on points of $S$, the minimal number of $\epsilon$-balls needed to
cover $S$, similar constructions in equivalent metrics, etc. [Fal14, pg. 30].

One important reformulation of the box counting dimension is the Minkowski-
Bouligand dimension. It is formulated in terms of the Lebesgue measure in the
ambient space and constructs a natural “contents” function at every dimension,
in that regard similar to the Hausdorff dimension and measure.

As $\epsilon$-balls used here and in other literature correspond to the
Euclidean metric, we need to compensate for the coefficient for volume of the
ball characteristic to this metric and dimension,

$\gamma_{x}=\frac{\pi^{\frac{x}{2}}}{\Gamma(\frac{x}{2}+1)}.$

For further discussion of this coefficient and its use in the Minkowski-
Bouligand dimension, see [Res13] and [KP99, Chapter 3.3].

######  Definition 2.

Let $S\subseteq{\mathbb{R}}^{n}$. For $\epsilon>0$, we define the
$\epsilon$-Minkowski sausage of $S$ as the set

$(S)_{\epsilon}=\left\\{x\in{\mathbb{R}}^{n}\,|\,d(x,S)\leq\epsilon\right\\}.$

Let $\lambda$ be the Lebesgue measure on ${\mathbb{R}}^{n}$ and denote by
$A^{n,d}_{\epsilon}(S)$ the ratio

$A^{n,\delta}_{\epsilon}(S):=\frac{\lambda(S)_{\epsilon}}{\gamma_{n-\delta}\epsilon^{n-\delta}}.$

We say that $d$ is the upper (lower) Minkowski-Bouligand dimension of $S$,
$\overline{\dim}_{MB}S$ ($\underline{\dim}_{MB}S$) if

$\displaystyle d$
$\displaystyle=\inf\left\\{\delta\,\Big{|}\,\lim_{\epsilon\to
0}A_{\epsilon}^{n,\delta}(S)=+\infty\right\\}$ $\displaystyle\bigg{(}d$
$\displaystyle=\sup\left\\{\delta\,\Big{|}\,\lim_{\epsilon\to
0}A_{\epsilon}^{n,\delta}(S)=0\right\\}\bigg{)}.$

A classical result (eg. [Pes97, Ch. I.2], [Fal14, Prop. 2.4]) is that both
upper and lower Minkowski-Bouligand dimensions are exactly equal to the
corresponding upper and lower box counting dimensions, so we will only use the
box-dimension notation for the discussed dimension.

######  Definition 3.

For $S\subseteq{\mathbb{R}}^{n}$, if
$\underline{\dim}_{B}S=\overline{\dim}_{B}S=d$, we say that $S$ is of box
counting dimension $d$, denoting

$\dim_{B}S=d.$

For $S$ of box-dimension $d$, we define the normalised upper (lower) Minkowski
content of $S$ as

$\displaystyle{\mathcal{M}^{*}_{d}}(S)$ $\displaystyle=\limsup_{\epsilon\to
0}A_{\epsilon}^{n,d}(S),$ $\displaystyle\bigg{(}{\mathcal{M}_{*d}}(S)$
$\displaystyle=\liminf_{\epsilon\to 0}A_{\epsilon}^{n,d}(S))\bigg{)}.$

We say that the set $S\subseteq{\mathbb{R}}^{n}$ of box-dimension $d$ is
Minkowski-non-degenerate if ${\mathcal{M}^{*}_{d}}(S)<+\infty$ and
${\mathcal{M}_{*d}}(S)>0$ and denote

$\dim_{B}S\equiv d.$

######  Example 2.

As per the earlier discussion in Example 1, it is easy to show that
$K_{m}\subseteq{\mathbb{R}}^{n}$ is of normalised Minkowski content (both
upper and lower) equal to $1$ because

$\frac{\lambda(K_{m})_{\epsilon}}{\epsilon^{n-m}}=\gamma_{n-m}+\sum_{k=0}^{m-1}\gamma_{n-k}\left(\frac{\epsilon}{2}\right)^{m-k}\\!E^{(k)}_{m},$

where $E_{m}^{(k)}$ is the number of $k$-edges of the $m$-cube.

Figure 1: The Minkowski sausage of the unit square in ${\mathbb{R}}^{2}$.

In Figure 1, we have $E_{2}^{(0)}=4$ and $E_{2}^{(1)}=4$ and $\gamma_{0}=1$,
$\gamma_{1}=2$ and $\gamma_{2}=\pi$, so we have
$\lambda(K_{2})_{\epsilon}=\gamma_{0}+\frac{\epsilon}{2}\gamma_{1}E_{2}^{(1)}+\frac{\epsilon^{2}}{4}\gamma_{2}E_{2}^{(0)}=1+4\epsilon+\pi\epsilon^{2}$.

######  Example 3.

The set of points $E_{\alpha}=\\{k^{-\alpha}\,|\,k\in{\mathbb{N}}\\}$ for
$\alpha>0$ is of box counting dimension $\frac{1}{1+\alpha}$, with normalised
Minkowski contents (both upper and lower) equal to

${\mathcal{M}_{d}}S=\left(\frac{2}{\alpha\sqrt{\pi}}\right)^{\frac{\alpha}{\alpha+1}}\\!(\alpha+1)\,\Gamma\left(\frac{\alpha}{2(\alpha+1)}+1\right).$

Figure 2: Sets $E_{\alpha}$ of unit normalised Minkowski contents for
$\alpha\in\\{0.2,0.4,\ldots,5.0\\}$.

Figure 2 shows sets $E_{\alpha}$ of unit normalised Minkowski contents in
dimensions ranging from $5/6$ at the bottom to $1/6$ in the top row.

###  2.2 Fractal analysis of $\alpha$-regular generalised fractal nests

Intuitively, an inner $\alpha$-regular fractal nest is the subset of the union
of circles of radii $n^{-\alpha}$ where subsets per individual circle are
homothetic to each other. The outer $\alpha$-regular fractal nest has radii of
form $1-(k+1)^{-\alpha}$.

For a set $S\subseteq{\mathbb{R}}^{n}$ and $x\geq 0$ we denote by $(x)S$ the
scaling of the set $S$ by $x$.

######  Definition 4.

Let $S\subseteq{\mathbb{S}}^{n-1}$ be a Borel subset of the unit sphere in
${\mathbb{R}}^{n}$. We define the $\alpha$-regular fractal nest of centre
(outer) type as

$\displaystyle{\mathcal{F}}_{\alpha}S$
$\displaystyle=\bigcup_{k=1}^{\infty}(k^{-\alpha})S$
$\displaystyle\bigg{(}{\mathcal{O}}_{\alpha}S$
$\displaystyle=\bigcup_{k=1}^{\infty}(1-k^{-\alpha})S\bigg{)}.$

Note that

${\mathcal{F}}_{\alpha}\\{1\\}=E_{\alpha}$

and

${\mathcal{O}}_{\alpha}\\{1\\}=1-E_{\alpha},$

where for a set $S$ the expression $1-S$ is defined as $\\{1-x\,|\,x\in S\\}$,
with $E_{\alpha}$ defined in Example 3.

######  Theorem 1.

Let $S\subseteq{\mathbb{S}}^{n-1}$ be a Borel subset of the unit hyper-sphere
in ${\mathbb{R}}^{n}$ such that

$\dim_{B}S\equiv\delta\geq 0.$

For every $\alpha>0$ the $\alpha$-regular fractal nest of centre type
generated by $S$ has

$\dim_{B}{\mathcal{F}}_{\alpha}(S)\begin{cases}\equiv\frac{\delta+1}{\alpha+1},\hbox{
for }\alpha\delta<1,\\\ =\delta,\hbox{ for }\alpha\delta=1\\\
\equiv\delta,\hbox{ for }\alpha\delta>1.\end{cases}$

######  Theorem 2.

Let $S\subseteq{\mathbb{S}}^{n-1}$ be a Borel subset of the unit hyper-sphere
in ${\mathbb{R}}^{n}$ such that

$\dim_{B}S\equiv\delta\geq 0.$

For every $\alpha>0$ that the $\alpha$-regular fractal nest of outer type
generated by $S$ has

$\dim_{B}{\mathcal{O}}_{\alpha}S\equiv\delta+\frac{1}{\alpha+1}.$

The proofs of both theorems rely on the well-known technique of separating the
“core” and the “tail” of the set, the “tail” part consisting of the well-
isolated components, and the “core” of the remaining parts.

We take a novel approach to analysing the “core”, where we use the covering
lemma (Lemma 5) to replace the components of the core with well-spaced sets
without losing the asymptotic and hence dimensional properties, including
Minkowski (non)-degeneracy.

##  3 Application of the generalised nest formulas

In this section, we show some applications of our main results to some known
and some novel fractal sets.

###  3.1 Mapping $m$-cubes to $m$-spheres

Let $K_{m}\subset{\mathbb{R}}^{n}$ be a unit $m$-cube as defined in Example 1
with $m<n$. It is easy to show that for limited domains such as a unit
$m$-cube, the mapping

$\displaystyle\Phi_{n-1}\colon(x_{1},\ldots,x_{n-1})\mapsto($
$\displaystyle\cos x_{1},\sin x_{1}\cos x_{2},\ldots,$ $\displaystyle\sin
x_{1}\sin x_{2}\cdots\sin x_{n-1})$

is bi-Lipschitz.

Thus, any subset of the unit hyper-cube can be mapped to a corresponding set
of equal dimension on the hyper-sphere. If we identify $K_{m}$ with its
embedding into ${\mathbb{S}}^{n-1}$, applying Theorem 1 we have that

$\dim_{B}{\mathcal{F}}_{\alpha}K_{m}=\frac{m+1}{\alpha+1}.$

We note that this formula also applies to $m=0$. Also, for the outer nests,
using Theorem 2 we have

$\dim_{B}{\mathcal{O}}_{\alpha}K_{m}=m+\frac{1}{\alpha+1},$

again, compatible with $m=0$.

###  3.2 $(\alpha,\beta)$-bi-fractals

Let $\alpha,\beta>0$. We can identify $E_{\beta}$ with its image on the unit
circle of $\Phi_{1}$. Let $D_{\beta}$ be the union

$D_{\beta}=\Phi_{1}\left(\frac{\pi}{4}(1-E_{\beta})\right)\cup\Phi_{1}\left(\frac{\pi}{4}(1+E_{\beta})\right)\subseteq{\mathbb{S}}^{1}.$

We have that

$\dim_{B}D_{\beta}=\frac{1}{1+\beta}.$

We call the set ${\mathcal{F}}_{\alpha}D_{\beta}$ an _$(\alpha,\beta)$ -bi-
fractal_. Its dimension is given by Theorem 1 as

$\dim_{B}{\mathcal{F}}_{\alpha}D_{\beta}=\frac{\beta+2}{(\beta+1)(\alpha+1)}.$

(a) $\alpha\approx 0.35$

(b) $\alpha\approx 0.67$

(c) $\alpha\approx 1.00$

(d) $\alpha\approx 1.33$

Figure 3: $(\alpha,\beta)$-bi-fractals of dimension $3/4$

(a) $\dim_{B}{\mathcal{F}}_{\alpha}D_{\beta}\approx 0.25$

(b) $\dim_{B}{\mathcal{F}}_{\alpha}D_{\beta}\approx 0.5$

(c) $\dim_{B}{\mathcal{F}}_{\alpha}D_{\beta}\approx 0.75$

(d) $\dim_{B}{\mathcal{F}}_{\alpha}D_{\beta}\approx 1.00$

Figure 4: $(\alpha,\beta)$-bi-fractals of various dimensions.

###  3.3 Uniform Cantor nests

Intuitively, the uniform Cantor set ${\mathcal{C}}_{N}^{C}$ are Cantor sets
“preserving” $N$ copies of themselves totalling $C$ in relative length in each
iteration.

In [Fal14, pg. 71] uniform Cantor sets are defined in terms of the number of
preserved copies $m$ and the relative gap $r$ (see 5). Modifying that
definition to our notation, uniform Cantor sets are defined as follows.

######  Definition 5 (Uniform Cantor set, [Fal14]).

Let $N\geq 2$ be an integer and $0<r<\frac{1}{N}$. We define the set
${\mathcal{C}}_{n}^{r}$ as the set obtained by the construction in which each
basic interval $I$ is replaced by $N$ equally spaced sub-intervals of lengths
$r|I|$, the ends of $I$ coinciding with the ends of the extreme sub-intervals.
The starting interval for ${\mathcal{C}}_{N}^{r}$ is $[0,1]$.

Figure 5: First four iterations of the uniform Cantor set
${\mathcal{C}}_{3}^{1/4}$.

For the standard Cantor set, ${\mathcal{C}}_{2}^{\frac{1}{3}}$ we have, as is
shown in [LP93] and [FC07],

$\dim_{B}{\mathcal{C}}_{2}^{\frac{1}{3}}\equiv\frac{\log 2}{\log 3},$

with different upper and lower Minkowski contents,

${\mathcal{M}^{*}_{d}}{\mathcal{C}}_{2}^{\frac{1}{3}}=\gamma^{-1}_{1-\log_{3}2}4\cdot
2^{-\log_{3}2}\approx 2.27,$

and

${\mathcal{M}_{*d}}{\mathcal{C}}_{2}^{\frac{1}{3}}=2\gamma^{-1}_{1-\log_{3}2}\log_{\frac{3}{2}}3\left(\log_{4}\frac{3}{2}\right)^{\log_{3}2}\\!\approx
2.19.$

An older proof of the following proposition can be found in [FC07], where the
authors use the simpler formula for (both upper and lower) Minkowski contents
omitting the normalising factor.

######  Proposition 1.

The set ${\mathcal{C}}_{N}^{r}\subseteq{\mathbb{R}}$ is Minkowski non-
degenerate with box counting dimension

$\dim_{B}{\mathcal{C}}_{N}^{r}\equiv-\frac{\log N}{\log r}=d.$

The upper Minkowski content at the dimension $d$ is

${\mathcal{M}^{*}_{d}}{\mathcal{C}}_{N}^{r}=2N\left(\frac{s}{2}\right)^{d}\frac{1-r}{1-Nr}\gamma_{1-d}^{-1}$

and the corresponding lower Minkowski content is

${\mathcal{M}_{*d}}{\mathcal{C}}_{N}^{r}=\frac{2}{1-d}\left(\frac{1-d}{2d}\right)^{d}\gamma_{1-d}^{-1}.$

Again, we can use $\Phi_{1}$ to identify ${\mathcal{C}}_{N}^{r}$ with its
image on $S^{1}$, and so we have

$\dim_{B}{\mathcal{F}}_{\alpha}{\mathcal{C}}_{N}^{r}=\frac{1-\log_{r}N}{1+\alpha}$

and

$\dim_{B}{\mathcal{O}}_{\alpha}{\mathcal{C}}_{N}^{r}=\frac{1}{1+\alpha}-\log_{r}N.$

(a) $\alpha\approx 0.33$

(b) $\alpha\approx 0.67$

(c) $\alpha\approx 1.00$

(d) $\alpha\approx 1.33$

Figure 6: ${\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}$ nests of dimension
$3/4$.

(a) $\dim_{B}{\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}\approx 0.25$

(b) $\dim_{B}{\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}\approx 0.50$

(c) $\dim_{B}{\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}\approx 0.75$

(d) $\dim_{B}{\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}\approx 1.00$

Figure 7: ${\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}$ nests.

###  3.4 Numerical verification of the results

Since the main results of this article are asymptotic in nature, there is
always a risk that we will not be able to reproduce such results in numerical
computations. Luckily, as can be seen in figures 8 and 9 we can observe the
dimensions to a reasonable accuracy.

We used the same algorithm for producing figures 3, 4, 6 and 7 and also for
the explicit computation of the dimensions.

We use the same technique used in the proofs of the main results, in
particular we use of Lemma 6 for producing numbers $m_{1}(\epsilon)$ (the
number of isolated components, the “tail” of the fractal) and
$m_{2}(\epsilon)$, the number of $2\epsilon$-separated elements that cover the
“core” of the fractal nest.

For figures 3, 4, 6 and 7 we used a program written in the Python programming
language (version 3.6) that outputs an encapsulated PostScript (eps)
description of the fractal. PostScript is well-suited as a page description
language since it allows for global scaling and setting of line width using
the setlinewidth command that is defined in the standard as “up to two pixels”
[Ado99, pg. 674] best approximation of the Minkowski sausage of half radius of
the given parameter when rendered.

The figures themselves have the half of the line width parameter $\epsilon$
set at $1/300$ of the height and width of the picture.

For $(\alpha,\beta)$-bi-fractals, we first obtain the radius of the element of
the nest using $r^{(1)}_{k}=k^{-\alpha}$ for
$k\in\\{1,\ldots,m_{1}(\epsilon)\\}$ and $r^{(2)}_{k}=2k\epsilon$ for
$k\in\\{1,\ldots,m_{2}(\epsilon)\\}$. Then, at each radius $r_{k}^{(i)}$ we
draw the the set $D_{\beta}$ by the same construction, using
$m_{1}\big{(}\frac{4\epsilon}{\pi r_{k}^{(i)}}\big{)}$ and
$m_{2}\big{(}\frac{4\epsilon}{\pi r_{k}^{(i)}}\big{)}$, both with respect to
the exponent $-\beta$ instead of $-\alpha$.

For uniform Cantor nests, we repeat the same initial part to obtain
$r_{k}^{(i)}$, we use a standard recursive algorithm for describing segments
of the Cantor set, where the number of iterations depends on the radius of the
nest element, since we are interested only in segments that have gaps larger
than $2\epsilon/r_{k}^{(i)}$.

In Figures 3 and 6 we show $(\alpha,\beta)$-bi-fractals
${\mathcal{F}}_{\alpha}D_{\beta}$ and uniform Cantor nests
${\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}$ of fixed dimension $d=3/4$ and
various $\alpha$ with $\beta$ and $r$ computed from

$\displaystyle r$ $\displaystyle=N^{-\frac{1}{\delta}}$ (3.1)
$\displaystyle\beta$ $\displaystyle=\frac{1}{\delta}-1$ (3.2)
$\displaystyle\delta$ $\displaystyle=d\alpha+d-1.$ (3.3)

The constraint of the main result that $\alpha$ plays a role in the total
dimension only if $\alpha\delta<1$ limits $\alpha$ to

$\displaystyle\alpha\in\left\langle{\frac{1}{d}-1,\frac{1}{d}}\right\rangle$
(3.4)

In Figures 4 and 7 we vary the total dimension
$d\in\langle\frac{1}{4},1\rangle$ and we set

$\displaystyle\alpha=\frac{1}{d}-\frac{1}{2}$ (3.5)

so that $\alpha$ is always in the centre of the interval given in (3.4). Then
we compute $\delta$ using (3.3), and finally we produce the parameters $\beta$
and $r$ from (3.2) and (3.1).

Figure 8: Relative error for numerical computation of the dimensions of
${\mathcal{F}}_{\alpha}D_{\beta}$ (grey dashed line) and
${\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}$ (black dashed line) for fixed
dimension $3/4$ (bold horizontal line).

For Figure 8 we fix the dimension of the whole fractal nest to be $3/4$ and we
vary the parameter $\alpha$.

We compute the parameters $\beta$ for the $(\alpha,\beta)$-bi-fractal and $r$
for the ${\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}$ Cantor nest. For ten
different values of $\epsilon$ ranging from $2^{-25}$ to $2^{-10}$ we count
the number $N_{\epsilon}$ of points necessary to draw the fractals. Using
Python’s scikit-learn library [PVG+11], we find the slope for the linear
regression of $\ln N_{\epsilon}$ against $-\ln\epsilon$.

As can be seen in Figure 8, the results of these computations come mostly
within 10% precision, with relatively short execution time, finishing within
minutes on a laptop computer. The falling dotted line at the left side of
Figure 8 represents

$\dim_{B}E_{\alpha}=\frac{1}{\alpha+1}$

and the rising dotted line on the right side is $\delta$, the dimension of the
set copied by the nest. The Cantor nests are sensitive in the beginning,
following the $(\alpha+1)^{-1}$ curve. On the right-hand side, as we approach
the Minkowski degenerate point when $\alpha=\delta^{-1}$ we should expect the
error to grow, as it does.

Figure 9: Numerical computation of the dimensions of
${\mathcal{F}}_{\alpha}D_{\beta}$ (grey dashed line) and
${\mathcal{F}}_{\alpha}{\mathcal{C}}_{3}^{r}$ (black dashed line) for varying
dimensions.

In Figure 9, we display the relative error of the same method against a
varying total box counting dimension, $d\in\left\langle 0.25,1\right\rangle$
as in figures 4 and 7, for $\alpha$ defined by (3.5).

Since $\alpha$ here is defined to be quite distant from $\delta^{-1}$ with

$\alpha\delta=\frac{1}{2}-\frac{d}{4},$

we expect the error to be relatively low, with Figure 9 showing the error
under 5% for both types of nests.

Figure 10: Relative deviations of $\ln N_{\epsilon}$ from linear regression
with respect to $-\ln\epsilon$ for $(\alpha,\beta)$-bi-fractals of dimension
$3/4$ with $\alpha=4/5$ (dashed grey line), $\alpha=4/3$ (dashed black line)
and $\alpha=3$ (dotted grey line). Figure 11: Relative deviations of $\ln
N_{\epsilon}$ from linear regression with respect to $-\ln\epsilon$ for
uniform Cantor nests of dimension $3/4$ with $\alpha=4/5$ (dashed grey line),
$\alpha=4/3$ (dashed black line) and $\alpha=3$ (dotted grey line).

To see the behaviour more clearly, in figures 10 and 11 we show the relative
deviations from linear regression for more detailed samples, with 300 samples
for $\epsilon$ between $2^{-5}$ and $2^{-35}$. The dimension of the set is
fixed at $3/4$.

For $\alpha=4/5$ and $\alpha=3$ in both figures the approximation of the
dimension is very good, the numerically obtained dimension is between $0.751$
and $0.754$, while at the critical point (where we lose Minkowski-non-
degeneracy, $\alpha=4/3$), the approximate dimension is around $0.82$. At the
critical point, the relative error shows the most bias in both figures.

In figure 11 we can also observe the effects of uniform Cantor sets having
distinct upper and lower Minkowski content, with visible oscillations of
content at different scales.

##  4 Proofs of main results

In this section we prove the main results. After the introduction of the
asymptotic notation we use and the lemmas necessary for the proof of theorems
1 and 2.

###  4.1 Asymptotic notation

In studying box counting dimensions, asymptotic notation is often useful. Here
we opt for $\sim$-style notation, like in [Tri93] for mutually bounded
sequences and functions, corresponding to $\Theta$ in classical big-Oh
notation [Knu76].

######  Definition 6 (Sequence and function equivalence).

Let $a_{n}$ and $b_{n}$ be two positive sequences. We say that $a_{k}$ and
$b_{k}$ are equivalent and denote it by

$a_{k}\sim_{k}b_{k}$

if there exists a number $M\geq 1$ such that for all $k\in{\mathbb{N}}$,

$M^{-1}a_{k}\leq b_{k}\leq Ma_{k}.$

Similarly, let $I$ be a set and let $f,g\colon I\to{\mathbb{R}}^{+}$. We say
that $f$ and $g$ are equivalent on $I$, denoting

$f(x)\sim_{x\in I}g(x)$

if there exists a constant $M\geq 1$ such that for every $x\in I$ we have

$M^{-1}g(x)\leq f(x)\leq Mg(x).$

When the domain of equivalence is unambiguous, we will use only the symbol
$\sim$ to denote the equivalence.

###  4.2 The lemmas and the proofs

######  Lemma 1.

Let $f,g\colon I\to{\mathbb{R}}$ and let $\phi\colon J\times{\mathbb{N}}\to I$
and $m\colon J\to{\mathbb{N}}$. If

$f(x)\sim_{x\in I}g(x)$

then

$\sum_{k=1}^{m(x)}(g\circ\phi)(x,k)\sim_{x\in
J}\sum_{k=1}^{m(x)}(h\circ\phi)(x,k).$

###### Proof.

Let $x\in J$ and $k\in{\mathbb{N}}$. Since $f\sim_{I}g$ we have

$M^{-1}(g\circ\phi)(x,k)\leq(f\circ\phi)(x,k)\leq M(g\circ\phi)(x,k).$

for some $M\geq 1$. Taking the sum of parts of the inequality to $m(x)$, we
get

$\displaystyle M^{-1}\sum_{k=1}^{m(x)}(g\circ\phi)(x,k)\leq{}$
$\displaystyle\sum_{k=1}^{m(x)}(f\circ\phi)(x,k)$ $\displaystyle\leq
M\sum_{k=1}^{m(x)}(g\circ\phi)(x,k),$

proving the lemma. ∎

The following Minkowski non-degeneracy condition is a useful intuition on what
the box-counting dimension represents, namely that the ambient area of the
Minkowski sausage is asymptotically equivalent to radius to the power of the
“complementary” dimension of the ambient space.

######  Lemma 2.

Let $S\subseteq{\mathbb{R}}^{n}$ be such that $\dim_{B}S\equiv d$ and let
$L>0$. Then that for $\epsilon\langle 0,L]$ we have

$\lambda(S)_{\epsilon}\sim\epsilon^{n-d}.$

###### Proof.

This is an direct consequence of $A_{\epsilon}^{n,d}$ being bounded from both
above and below as $\epsilon\to 0$ and the fact that $\lambda(S)_{\epsilon}$
is continuous and monotonous as a function of $\epsilon$. ∎

######  Lemma 3.

Let $S\subseteq{\mathbb{R}}^{n}$ be a Borel set and let $x,\epsilon>0$. Then,

$((x)S)_{\epsilon}=(x)(S)_{\frac{\epsilon}{x}}$

and, consequently,

$\lambda((x)S)_{\epsilon}=x^{n}\lambda(S)_{\frac{\epsilon}{x}}.$

###### Proof.

Suppose $a\in((x)S)_{\epsilon}$. This is true if and only if

$\inf_{b\in S}\|a-xb\|\leq\epsilon.$

Since $x>0$, we get

$\inf_{b\in S}\left\|{\frac{1}{x}}a-b\right\|\leq\frac{\epsilon}{x},$

so $a\in((x)S)_{\epsilon}$ if and only if
$x^{-1}a\in(S)_{\frac{\epsilon}{x}}$, which is equivalent to
$a\in(x)(S)_{\frac{\epsilon}{x}}$, proving the lemma. ∎

######  Corollary 1.

Under the same assumptions, with $x\geq 1$ ($0<x\leq 1$) we have

$\displaystyle\lambda(S)_{x\epsilon}$ $\displaystyle\leq
x^{n}\lambda(S)_{\epsilon}$ $\displaystyle\bigg{(}\lambda(S)_{x\epsilon}$
$\displaystyle\geq x^{n}\lambda(S)_{\epsilon}\bigg{)}.$

######  Lemma 4.

Let $S\subseteq{\mathbb{R}}^{n}$ be a Borel set and let $\epsilon>0$. For a
sequence $a_{k}\sim_{k}1$,

$\sum_{k=1}^{m}\lambda(S)_{\epsilon a_{k}}\sim_{m}m\lambda(S)_{\epsilon}.$

###### Proof.

Since $M^{-1}\leq a_{k}\leq M$ for some $M\geq 1$, we have that

$\lambda(S)_{\epsilon a_{k}}\leq\lambda(S)_{\epsilon M}\leq
M^{n}\lambda(S)_{\epsilon},$

and likewise for the lower bound, we have

$\lambda(S)_{\epsilon a_{k}}\sim_{k}\lambda(S)_{\epsilon}.$

Taking the sum of both sides from $1$ to $m$, we prove the lemma. ∎

######  Lemma 5 (Dense covering lemma).

Let $S\subseteq{\mathbb{R}}^{n}$ be a Borel set. Suppose that for every
$\epsilon>0$ there is a set $I_{\epsilon}\subseteq{\mathbb{R}}^{+}$ and a
(possibly infinite) sequence $a_{k}^{\epsilon}$, such that

$I_{\epsilon}\subseteq(A^{\epsilon})_{\epsilon}\subseteq(I_{\epsilon})_{\epsilon}.$

where $m(\epsilon)$ is the (possibly infinite) length of $a_{k}^{(\epsilon)}$
and $A^{\epsilon}=\\{a_{k}\,|\,k\leq m(\epsilon)\\}$. Then,

$\lambda\left(\bigcup_{x\in
I_{\epsilon}}(x)S\right)_{\epsilon}\sim\lambda\left(\bigcup_{k=0}^{m(\epsilon)}(a_{k}^{(\epsilon)})S\right)_{\epsilon},$

with respect to $\epsilon$.

###### Proof.

The inclusions

$I_{\epsilon}\subseteq(A^{\epsilon})_{\epsilon}\subseteq(I_{\epsilon})_{\epsilon}$

imply, by triangle inequality,

$(A^{\epsilon})_{\epsilon}\subseteq(I_{\epsilon})_{\epsilon}\subseteq(A^{\epsilon})_{2\epsilon}.$

Hence,

$\left(\bigcup_{x\in
I_{\epsilon}}(x)S\right)_{\epsilon}\subseteq\left(\bigcup_{k=0}^{m(\epsilon)}(a_{k}^{(\epsilon)})S\right)_{2\epsilon},$

and by monotonicity of the Lebesgue measure, and applying Corollary 1 we have

$\lambda\left(\bigcup_{x\in I_{\epsilon}}(x)S\right)_{\epsilon}\leq
2^{n}\lambda\left(\bigcup_{k=0}^{m(\epsilon)}(a_{k}^{(\epsilon)})S\right)_{\epsilon}$

By the same argument applied to
$(A^{\epsilon})_{\epsilon}\subseteq(I_{\epsilon})_{\epsilon}$, we have

$\lambda\left(\bigcup_{k=0}^{m(\epsilon)}(a_{k}^{(\epsilon)})S\right)_{\epsilon}\leq
2^{n}\lambda\left(\bigcup_{x\in I_{\epsilon}}(x)S\right)_{\epsilon},$

proving the lemma. ∎

######  Lemma 6.

Let $\alpha>0$. For every $\epsilon>0$ there exist numbers $m_{1}(\epsilon)$
and $m_{2}(\epsilon)$ (denoted further by $m_{1}$ and $m_{2}$) satisfying:

$\displaystyle(m_{1}+1)^{-\alpha}\\!\\!-(m_{1}+2)^{-\alpha}\\!$
$\displaystyle<\\!2\epsilon\\!\leq m_{1}^{-\alpha}\\!\\!-(m_{1}+1)^{-\alpha}$
$\displaystyle(m_{1}+1)^{-\alpha}$ $\displaystyle\leq 2m_{2}\epsilon\leq
m_{1}^{-\alpha}$

such that

$m_{1}(\epsilon)\sim m_{2}(\epsilon)\sim\epsilon^{\frac{-1}{1+\alpha}}.$

###### Proof.

The existence of $m_{1}$ and the required asymptotic behaviour of $m_{1}$
follows from the fact that

$n^{-\alpha}-(n+1)^{-\alpha}\sim_{n}n^{-(\alpha+1)}.$

For $m_{2}$ we observe that $2\epsilon$ fits between $m_{1}^{-\alpha}$ and
$(m_{1}+1)^{-\alpha}$, so we can construct

$m_{2}(\epsilon)=\left\lceil\frac{(m_{1}(\epsilon)+1)^{-\alpha}}{2\epsilon}\right\rceil\leq\frac{(m_{1}+1)^{-\alpha}}{2\epsilon}+1.$

Suppose $2\epsilon m_{2}>m_{1}^{-\alpha}$. Then

$\displaystyle m_{1}^{-\alpha}$
$\displaystyle<2\epsilon\left(\frac{(m_{1}+1)^{-\alpha}}{2\epsilon}+1\right)$
$\displaystyle=(m_{1}+1)^{-\alpha}+2\epsilon$ $\displaystyle\leq
m_{1}^{-\alpha}$

so we have arrived at a contradiction. ∎

Now we turn to the proofs of our main theorems.

###### Proof of Theorem 1.

Let $\epsilon>0$. We apply Lemma 6 to obtain the functions $m_{1}(\epsilon)$
and $m_{2}(\epsilon)$.

We define the $\epsilon$-tail, ${\mathrm{T}}_{\epsilon}(S)$ as the part of the
nest consisting of $\epsilon$-isolated components,

${\mathrm{T}}_{\epsilon}S=\bigcup_{k=1}^{m_{1}}{\mathrm{(}}k^{-\alpha})S,$

and we define the $\epsilon$-core, ${\mathrm{C}}_{\epsilon}(S)$ as the
remaining components

${\mathrm{C}}_{\epsilon}S=\bigcup_{k>m_{1}}{\mathrm{(}}k^{-\alpha})S.$

Now, we have that

$\lambda\left({\mathcal{F}}_{\alpha}S\right)_{\epsilon}=\lambda\left({\mathrm{T}}_{\epsilon}S\right)_{\epsilon}+\lambda\left({\mathrm{C}}_{\epsilon}S\right)_{\epsilon}.$

By construction, $2\epsilon m_{2}(\epsilon)$ is an upper bound on the
Hausdorff distance of the limit set $\\{0\\}$ of the whole nest and the
$\epsilon$-core.

First, we find the asymptotic behaviour of the core by computing

$\displaystyle\lambda\left({\mathrm{C}}_{\epsilon}S\right)_{\epsilon}={}$
$\displaystyle\lambda\left(\bigcup_{k>m_{1}}(k^{-\alpha})S\right)_{\epsilon}$
$\displaystyle\sim{}\lambda\left(\bigcup_{k=0}^{m_{2}}(2k\epsilon)S\right)_{\epsilon}$
(4.1)
$\displaystyle=\sum_{k=0}^{m_{2}}\lambda\left((2k\epsilon)S\right)_{\epsilon}$
$\displaystyle=\sum_{k=0}^{m_{2}}(2k\epsilon)^{n}\lambda(S)_{\frac{1}{2k}}$
(4.2) $\displaystyle\sim{}$
$\displaystyle\epsilon^{n}\sum_{k=0}^{m_{2}}k^{n}\cdot
k^{\delta-n}\sim{}\epsilon^{n}\sum_{k=0}^{m_{2}}k^{\delta}$ (4.3)
$\displaystyle\sim{}$
$\displaystyle\epsilon^{n}m_{2}^{1+\delta}\sim{}\epsilon^{n-\frac{\delta+1}{\alpha+1}},$

applying Lemma 5 twice at step (4.1), first time to the infinite sequence of
$k^{-\alpha}$ for $k>m_{1}$ and then to the finite sequence $2\epsilon k$. At
step (4.2) we apply Lemma 3 and to obtain (4.3) we apply Proposition 2 and
Lemma 1.

For the tail, we have

$\displaystyle\lambda\left({\mathrm{T}}_{\epsilon}S\right)_{\epsilon}$
$\displaystyle=\sum_{k=1}^{m_{1}}\lambda\left((k^{-\alpha})S\right)_{\epsilon}$
$\displaystyle=\sum_{k=1}^{m_{1}}k^{-n\alpha}\lambda(S)_{k^{\alpha}\epsilon}$
(4.4)
$\displaystyle\sim\sum_{k=1}^{m_{1}}k^{-n\alpha}\left(k^{\alpha}\epsilon\right)^{n-\delta}$
$\displaystyle\sim\epsilon^{n-\delta}\sum_{k=1}^{m_{1}}k^{-\alpha\delta},$
(4.5)

where we apply Lemmas 1 and 3 at step (4.4) and Proposition 2 at step (4.5).

Now, if $\alpha\delta<1$, we have

$\lambda\left({\mathrm{T}}_{\epsilon}S\right)_{\epsilon}\sim\epsilon^{n-\delta}m_{1}^{1-\alpha\delta}\sim\epsilon^{n-\frac{\delta+1}{\alpha+1}},$

in which case we have

$\dim_{B}F_{\alpha}(S)\equiv\frac{\delta+1}{\alpha+1}.$

If $\alpha\delta>1$, we set $\beta=\alpha\delta-1$, and therefore the series
$\sum_{k=1}^{\infty}k^{-\alpha\delta}$ converges, so we have

$\lambda\left({\mathrm{T}}_{\epsilon}S\right)_{\epsilon}\sim\epsilon^{n-\delta},$

and so the total area is

$\lambda\left({\mathcal{F}}_{\alpha}S\right)_{\epsilon}\sim\epsilon^{n-\delta}+\epsilon^{n-\frac{\delta+1}{\alpha+1}}=\epsilon^{n-\delta}(1+\epsilon^{\frac{\beta}{\alpha+1}}),$

proving

$\dim_{B}F_{\alpha}(S)\equiv\delta.$

In the case $\alpha\delta=1$ we have

$\frac{\delta+1}{\alpha+1}=\delta$

so for the total area we have

$\lambda\left({\mathcal{F}}_{\alpha}S\right)_{\epsilon}\sim\epsilon^{n-\delta}(1-\ln\epsilon).$

For any $\zeta>0$ we have

$\frac{\lambda\left({\mathcal{F}}_{\alpha}S\right)_{\epsilon}}{\epsilon^{n-(\delta+\zeta)}}\sim\epsilon^{\zeta}(1-\ln\epsilon)\to
0$

for the upper dimension and

$\frac{\lambda\left({\mathcal{F}}_{\alpha}S\right)_{\epsilon}}{\epsilon^{n-(\delta-\zeta)}}\sim\epsilon^{-\zeta}(1-\ln\epsilon)\to+\infty,$

for the lower dimension, proving

$\dim_{B}F_{\frac{1}{\delta}}S=\delta,$

a Minkowski-degenerate case. ∎

###### Proof of Theorem 2.

Let $\epsilon>0$. Again, we introduce $m_{1}$ and $m_{2}$ using Lemma 6. Also,
as in the previous proof, we define the $\epsilon$-tail and $\epsilon$-core;
the $\epsilon$-tail, ${\mathrm{T}}_{\epsilon}S$ as the part of the nest
consisting of $\epsilon$-isolated components, and the $\epsilon$-core,
${\mathrm{C}}_{\epsilon}(S)$ as the remaining components.

Now, we have that

$\lambda\left({\mathcal{O}}_{\alpha}S\right)_{\epsilon}=\lambda\left({\mathrm{T}}_{\epsilon}S\right)_{\epsilon}+\lambda\left({\mathrm{C}}_{\epsilon}S\right)_{\epsilon}.$

For the tail, we compute

$\displaystyle\lambda\left({\mathrm{T}}_{\epsilon}S\right)_{\epsilon}$
$\displaystyle=\sum_{k=1}^{m_{1}}\lambda\left((1-k^{-\alpha})S\right)_{\epsilon}$
(4.6)
$\displaystyle=\sum_{k=1}^{m_{1}}\left(1-k^{-\alpha}\right)^{n}\lambda(S)_{\epsilon(1-k^{-\alpha})^{-1}}$
(4.7) $\displaystyle\sim
m_{1}\lambda(S)_{\epsilon}\sim\epsilon^{n-\delta-\frac{1}{\alpha+1}},$ (4.8)

applying Lemma 3 at step (4.6) and Lemmas 1 and 4 at step (4.7).

For the core, we have

$\displaystyle\lambda\left({\mathrm{C}}_{\epsilon}S\right)_{\epsilon}={}$
$\displaystyle\lambda\left(\bigcup_{k>m_{1}}(1-k^{-\alpha})S\right)_{\epsilon}$
(4.9) $\displaystyle\sim{}$
$\displaystyle\lambda\left(\bigcup_{k=0}^{m_{2}}{(1-2k\epsilon})S\right)_{\epsilon}$
(4.10)
$\displaystyle=\sum_{k=0}^{m_{2}}(1-2k\epsilon)^{n}\lambda(S)_{\frac{\epsilon}{1-2k\epsilon}}$
(4.11) $\displaystyle\sim{}$ $\displaystyle
m_{2}\lambda(S)_{\epsilon}\sim\epsilon^{n-\delta-\frac{1}{\alpha+1}},$ (4.12)

by applying Lemma 5 at step (4.9), Lemma 3 at step (4.10). To apply Lemma 4 at
step (4.11) we note that

$1-m_{1}^{-\alpha}<1-2k\epsilon\leq 1$

from the defining condition on $m_{2}$ (Lemma 6) on $m_{2}$. At step (4.12) we
also apply Lemma 1.

Thus, we have shown that

$\dim_{B}{\mathcal{O}}_{\alpha}S\equiv\delta+\frac{1}{\alpha+1}.$

∎

##  5 Closing remarks and open problems

In this article we have shown that an $\alpha$-regular fractal nests based on
a set $S$ of non-degenerate box counting dimension $\delta$, has dimensions

$\dim_{B}({\mathcal{F}}_{\alpha}S)=\frac{\delta+1}{\alpha+1}\hbox{ or
}\dim_{B}({\mathcal{F}}_{\alpha}S)=\delta$

for nests of centre type, with $\alpha\delta<1$ for the first case and
$\alpha\delta\geq 1$ for the second, and we have shown

$\dim_{B}({\mathcal{O}}_{\alpha}S)=\delta+\frac{1}{\alpha+1}$

for the outer type.

These results concur with examples given in [LRŽ17] for hyper-spheres
${\mathbb{S}}^{n-1}\subseteq{\mathbb{R}}^{n}$, where

$\displaystyle\dim_{B}{\mathcal{F}}_{\alpha}{\mathbb{S}}^{n-1}$
$\displaystyle=\max\left\\{n-1,\frac{n}{\alpha+1}\right\\},$
$\displaystyle\dim_{B}{\mathcal{O}}_{\alpha}{\mathbb{S}}^{n-1}$
$\displaystyle=n-\frac{\alpha}{\alpha+1}.$

We have also shown that for sets ${\mathcal{F}}_{\alpha}S_{\delta}$ of
dimension $d$ based on Minkowski non-degenerate sets $S_{\delta}$ of dimension
$\delta$ we have the following relations:

$\displaystyle\alpha$
$\displaystyle\in\left\langle{\frac{1}{d}-1,\frac{1}{d}}\right\rangle,$
$\displaystyle\delta$ $\displaystyle=d\alpha+d-1.$

These relationships allow us to study the efficacy of simpler numerical
techniques for fractal sets presented in this article.

It is well known [Fal14, Fed69, Tri93] that the box counting dimension is not
continuous with respect to countable unions. The exact behaviour in examples
given here points to a subtler structure that explains the formulas for
fractal nests.

For the outer type of nests, this has already been discussed in [ŽŽ05, Remark
6], but the behaviour of centre-type nests remains less well understood. The
formula for the centre-type nests obtained here points to a multiplicative
operation on the dimensions. Such behaviour of dimensions is well known mostly
in vector spaces for tensor products. We propose here that there exists an
abstract tensor-like product $\otimes$ on Borel sets such that

${\mathcal{F}}_{\alpha}S\approx(S\times
I)\otimes{\mathcal{F}}_{\alpha}\\{1\\}$

with $\approx$ guaranteeing the existence of a bi-Lipschitz map between the
sets. We expect the following to hold,

$\dim_{B}(A\otimes B)=\dim_{B}A\cdot\dim_{B}B,$

along with $\otimes$ being distributive with respect to Cartesian products
(which behave additively).

Perhaps such a product could be found through an analogy between Lipschitz (or
bi-Lipschitz) maps that don’t increase or preserve the box dimension,
respectively, in uniform spaces [Bou91, Chapter 2] and linear maps in vector
spaces, possibly using a kind of a smash product [Bre93, pg. 435].

## Acknowledgements

I would like to thank Vedran Čačić, Ida Delač Marion, and Irina Pucić for
their helpful input and comments and my wife Marija Galić Miličić for her
patience.

All of the code used to generate the figures in this article is available at
https://github.com/sinisa-milicic/nests1.

## References

  * [Ado99] Adobe Systems Incorporated.  PostScript language reference, third edition.  Addison-Wesley, 1999.
  * [Bou91] Nicolas Bourbaki.  General topology. Chapters 1–4. Springer-Verlag, Heidelberg, 1991.
  * [Bre93] Glen E Bredon.  Topology and Geometry (Graduate Texts in Mathematics).  Springer-Verlag, New York, 1993.
  * [Fal14] Kenneth Falconer.  Fractal Geometry: Mathematical Foundations and Applications, 3rd Edition.  Wiley, Feb 2014.
  * [FC07] Jiang Feng and Shirong Chen.  The Minkowski content of uniform Cantor set.  Acta Mathematica Scientia, 27(4):641–647, 2007.
  * [Fed69] Herbert Federer.  Geometric Measure Theory, volume 153 of Grundlehren der mathematischen Wissenschaften.  Springer-Verlag, Berlin, 1969.
  * [Knu76] Donald E Knuth.  Big omicron and big omega and big theta.  ACM Sigact News, 8(2):18–24, 1976.
  * [KP99] Steven G. Krantz and Harold R. Parks.  The Geometry of domains in space.  Birkh’:auser, Boston, 1999.
  * [LP93] Michel L Lapidus and Carl Pomerance.  The Riemann zeta-function and the one-dimensional Weyl-Berry conjecture for fractal drums.  Proceedings of the London Mathematical Society, 3(1):41–69, 1993\.
  * [LRŽ17] Michel L Lapidus, Goran Radunović, and Darko Žubrinić.  Fractal zeta functions and fractal drums: higher-dimensional theory of complex dimensions.  Springer, 2017.
  * [Pes97] Yakov B Pesin.  Dimension theory in dynamical systems: contemporary views and applications.  University of Chicago Press, 1997.
  * [PVG+11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [Res13] Maja Resman.  Invariance of the normalized Minkowski content with respect to the ambient space.  Chaos, Solitons & Fractals, 57:123–128, 2013.
  * [Tri93] Claude Tricot.  Curves and fractal dimension.  Springer-Verlag, New York, 1993.
  * [ŽŽ05] Darko Žubrinić and Vesna Županović.  Fractal analysis of spiral trajectories of some planar vector fields.  Bulletin des Sciences Mathématiques, 129(6):457–485, 2005.