# On the use of local structural properties for improving the efficiency of
hierarchical community detection methods

Julio-Omar Palacio-Niño  Dept. Computer Science and Artificial Intelligence
Universidad de Granada
Granada, Spain
<EMAIL_ADDRESS>Fernando Berzal  Dept. Computer Science and
Artificial Intelligence
Universidad de Granada
Granada, Spain
<EMAIL_ADDRESS>
###### Abstract

Community detection is a fundamental problem in the analysis of complex
networks. It is the analogue of clustering in network data mining. Within
community detection methods, hierarchical algorithms are popular. However,
their iterative nature and the need to recompute the structural properties
used to split the network (i.e. edge betweenness in Girvan and Newman’s
algorithm), make them unsuitable for large network data sets. In this paper,
we study how local structural network properties can be used as proxies to
improve the efficiency of hierarchical community detection while, at the same
time, achieving competitive results in terms of modularity. In particular, we
study the potential use of the structural properties commonly used to perform
local link prediction, a supervised learning problem where community structure
is relevant, as nodes are prone to establish new links with other nodes within
their communities. In addition, we check the performance impact of network
pruning heuristics as an ancillary tactic to make hierarchical community
detection more efficient.

###### Index Terms:

community detection, hierarchical clustering, unsupervised learning, local
structural properties, modularity, betweenness

##  I Introduction

Networks are pervasive and the analysis of networks, therefore, is crucial in
many scientific endeavors, from molecular biology and sociology to
epidemiology and, why not, computer science. Community detection, defined as
an unsupervised machine learning task, is a key problem within network data
mining. Many community detection techniques have been proposed to detect
communities in complex networks [1], but efficiency was, and still is, a great
challenge for community detection algorithms [2].

Community detection methods can be classified attending to the kind of
communities they can detect (overlapping or not), the criteria they use to
detect their existence (local or global), the measure they try to optimize
either explicitly or implicitly (e.g. modularity), or the algorithmic
technique they resort to (hierarchical, partitioning, optimization-based, or
spectral, just to name a few).

Hierarchical community detection, as its traditional counterpart, hierarchical
clustering, is one of the most popular techniques. Newman and Girvan’s
algorithm [3] is a divisive hierarchical algorithm for community detection
that relies on edge betweenness to identify links that serve as bridges for
different communities. Unfortunately, every time such a link is broken, edge
betweenness has to be recomputed and this operation is costly. Radicchi [4]
proposed a more efficient algorithm based on the clustering coefficient, which
can be computed locally and leads to improved efficiency.

In parallel to the development of unsupervised community detection algorithms,
researchers also worked on supervised problems such as link prediction [5]. As
its name implies, link prediction methods try to predict the existence (or
future formation) of a link between a pair of nodes. Many techniques have been
proposed to solve this problem. Some of them resort to network structural
properties, either local or global. For obvious reasons, local properties lead
to more efficient link prediction algorithms, as happened with community
detection methods.

In this paper, we analyze how such local structural properties, originally
devised for a supervised learning problem, can be employed within an
unsupervised learning technique to achieve competitive results and lead to
more efficient hierarchical community detection algorithms.

Our paper is organized as follows. In Section 2, we introduce hierarchical
methods for community detection. In Section 3, we describe the link prediction
problem, focusing on local link prediction, and survey some of the network
structural properties that have been found to be useful for link prediction.
In Section 4, we present the results of the experiments we have performed on
some benchmark network data sets. Finally, Section 5 ends our paper with some
conclusions and recommendations on the use of local structural properties for
community detection.

##  II Hierarchical community detection

Hierarchical clustering, a traditional unsupervised machine learning
technique, proceeds iteratively until it creates a complete hierarchy of
clusters [6]. The resulting hierarchy is typically displayed by a tree, called
dendrogram, where leaves represent individual instances and the root of the
tree covers the whole data set.

The clustering process can follow either a bottom-up approach, from the leaves
to the root, or a top-down approach, from the root to the leaves. In the
former case, the clustering algorithm is agglomerative. In the latter case, it
is divisive. Since we usually start with a large data set and we are typically
interested in a small number of clusters (i.e. communities when we are dealing
with networks), divisive algorithms are often preferred.

###  II-A Girvan and Newman’s community detection method

Girvan and Newman [3] proposed a divisive hierarchical clustering algorithm
for networks. Their algorithm is based on the idea of edge betweenness as a
suitable measure for detecting links that connect different communities. Edge
betweenness counts the number of shortest paths that traverse each edge (or
link). The larger that number, the higher the probability that the link
connects different communities. Hence, edge betweenness can be used to suggest
the order in which links can be cut in a conventional divisive hierarchical
clustering algorithm.

Formally, edge betweenness is defined for each edge $e\in E$ as follows [7]:

$C_{B}(e)=\sum_{u,v\in{V}}\dfrac{g_{e}(u,v)}{g(u,v)}$

Where $g(u,v)$ is the total number of minimum paths between nodes $u$ and $v$,
whereas $g_{e}(u,v)$ is the number of minimum paths between nodes $u$ and $v$
that pass through node $e$.

Small edge betweenness values indicate that edges probably belong to the same
community. In contrast, those edges that connect nodes from different
communities will have higher edge betweenness values [7].

Girvan and Newman’s algorithm starts by computing the edge betweenness for all
the edges in the network. Then, iteratively, while there exists an edge whose
betweenness is above an user-provided threshold, the edge with the highest
betweenness is removed from the network and edge betweenness in recalculated
throughout the network.

Figure 1: Identification of edges with high edge betweenness [8].

One of the major drawbacks of Girvan and Newman’s algorithm is its
computational complexity, since every iteration of the hierarchical algorithms
requires recomputing the edge betweenness for all the edges in the network. In
general, the algorithmic complexity of the algorithm is $O(mn(m+n))$ for a
network with $m$ edges and $n$ nodes. In other words, it can reach $O(n^{3})$
for dense networks, where $m\propto n$. Therefore, this method is not
recommended for large networks [8] despite its good results and intuitive
appeal.

###  II-B Radicchi’s community detection method

Given the computational complexity of Girvan and Newman’s algorithm,
Radicchi[4] proposed a more efficient algorithm based on a simple idea:

A community contains heavily-connected nodes. Therefore, cycles are frequent
within a community. However, links that connect different communities are
involved in a lower number of cycles. In other words, edges connecting
different communities are less likely to be involved in cycles [9].

Following this observation, Radicchi’s algorithm is based on the definition of
an edge clustering coefficient. This coefficient is analogous to the usual
node clustering coefficient, which is the number of triangles including a node
divided by the number of possible triangles that could potentially be formed
with its neighbors. The edge clustering coefficient is, therefore, the number
of triangles to which a given edge belongs, divided by the number of triangles
that might potentially include it, given the degrees of its adjacent nodes.

Figure 2: Schematic illustration of the edge clustering coefficient introduced
by Radicchi [1].

Formally, the edge clustering coefficient for the edge connecting node $i$ to
node $j$ is defined as [9]:

$C_{ij}=\dfrac{z_{ij}+1}{\min(k_{i}-1,k_{j}-1)}$

where $z_{ij}$ is the number of triangles built on that edge (i.e. triangles
containing the edge from node $i$ to node $j$) and $k_{i}$ is the degree of
node $i$. A problem arises when the number of triangles is zero ($z_{ij}=0$
when $\min(k_{i}-1,k_{j}-1)=0$), and the degenerate case is removed by adding
one to the number of triangles in the numerator.

Instead of considering all possible cycles, Radicchi focuses on the shortest
ones, triangles of length 3. Edges that connect different communities tend to
exhibit a small edge clustering coefficient (i.e. they take part in in few or
no triangles at all). Hence, the edge clustering coefficient is a good measure
for detecting bridges between communities.

Whereas Girvan and Newman’s algorithm chose edges with the highest edge
betweenness, Radicchi’s algorithm selects those with the lowest edge
clustering coefficient.

Girvan and Newman’s algorithm was computationally expensive because it
required the repeated computation of a global network property, the edge
betweenness for each edge in the network (a property whose value depends on
the properties of the whole network, which change every time we remove and
edge). However, Radicchi’s algorithm is based on a local property, the edge
clustering coefficient, and is much faster.

The algorithmic complexity of Radicchi’s hierarchical community detection
algorithms is $O(n^{2})$. However, the algorithm tends to fail if the average
clustering coefficient of the network is small and, then, the edge clustering
coefficient is small for all edges [8].

Radicchi’s algorithm works well in networks with many triangles, e.g. social
networks. However, in technological or biological networks, there are fewer of
these structures, which makes it difficult to identify the edges that bridge
different communities [8].

##  III Local link prediction

Link prediction, a widely-studied supervised learning problem, can be useful
for identifying potential candidates to improve the efficiency of Girvan and
Newman’s algorithm and overcome the limitations of Radicchi’s method. Link
prediction explores the intrinsic features of nodes and edges and their
behavior in the past or in the future [10].

Many techniques have been proposed for the prediction of links in complex
networks: local, global, quasi-local, classification-based, metaheuristic, and
factor-based methods [5].

Some studies by Liben-Nowell and Kleinberg [11] and Zhou et al. [12] confirm
that local link prediction methods offer good results with a limited
computational complexity. Their results might not be as accurate as those
obtained by global methods, but global methods are computationally costly
[13].

Obviously, local link prediction methods will never be able to predict the
existence of links between remote nodes. However, most links appear within a
given neighborhood and, given the computational advantage they offer, local
link prediction techniques are ideal candidates for improving the performance
of existing hierarchical community detection methods.

In the following paragraphs, we briefly survey some of the criteria used by
local link prediction methods. They often define a similarity measure $s(x,y)$
between two nodes, $x$ and $y$, to rank potential links and their
computational complexity is usually $O(vk^{3})$, where $v$ is the number of
nodes and $k$ is the maximum degree of the nodes [5].

###  III-A Common neighbors (CN)

The simplest local link prediction method counts the number of neighbors in
common between a pair of nodes $(x,y)$. The greater the number of common
neighbors, the greater the probability of formation of a link between them
[14]:

$s(x,y)=|\Gamma_{x}\cap\Gamma_{y}|$

where, for a node $x$, $\Gamma_{x}$ indicates the set of neighbors of $x$.

###  III-B The Adamic-Adar index (AA)

The Adamic-Adar index evaluates the level of binding between a pair of nodes
from the number of neighbors they share, yet the contribution of each neighbor
is penalized by its degree [15]:

$s(x,y)=\sum_{z\in\Gamma_{x}\cap\Gamma_{y}}\dfrac{1}{\log|\Gamma_{z}|}$

###  III-C The resource allocation index (RA)

The resource allocation index is motivated by the resource allocation process
that takes place in complex networks [12]. It models the transmission of units
of resources between two unconnected nodes $x$ and $y$ through their
neighbors: each neighborhood node gets a unit of resource from $x$ and equally
distributes it to its neighbors. The amount of resources obtained by node $y$
is, therefore, given by:

$s(x,y)=\sum_{z\in\Gamma_{x}\cap\Gamma_{y}}\dfrac{1}{|\Gamma_{z}|}$

###  III-D The preferential attachment index (PA)

The preferential attachment index is a direct result of the well-known
Barabási-Albert complex network formation model [16]. In that model, which
leads to a power law degree distribution, the probability of link formation
between two nodes increases as the degree of these nodes does:

$s(x,y)=|\Gamma_{x}||\Gamma_{y}|$

###  III-E The Jaccard index (JA)

The Jaccard index was proposed to compare the similarity and diversity of two
sets [17]. In our case, the sets of neighbors:

$s(x,y)=\dfrac{|\Gamma_{x}\cap\Gamma_{y}|}{|\Gamma_{x}\cup\Gamma_{y}|}$

###  III-F The Sørensen index (SO)

The Sørensen index also assesses the similarity between two sets [18]. It is
very similar to the Jaccard index, yet less sensitive to outliers:

$s(x,y)=\dfrac{2|\Gamma_{x}\cap\Gamma_{y}|}{|\Gamma_{x}|+|\Gamma_{y}|}$

###  III-G The Salton index (SA)

The Salton index [19], also known as cosine similarity, is closely-related to
the Jaccard index:

$s(x,y)=\dfrac{|\Gamma_{x}\cap\Gamma_{y}|}{\sqrt{|\Gamma_{x}|+|\Gamma_{y}|}}$

###  III-H The hub promoted index (HP)

The hub promoted index was the result of a study of modularity in metabolic
networks [20]. Such networks show a hierarchical structure with small highly
internally connected modules that are also highly isolated from each other.
The HP index avoids link formation between hub nodes and promotes link
formation between low-degree nodes and hubs:

$s(x,y)=\dfrac{|\Gamma_{x}\cap\Gamma_{y}|}{\min(|\Gamma_{x}|,|\Gamma_{y}|)}$

###  III-I The hub depressed index (HD)

The hub depressed index was also a result of the same study [20]. The HD index
promotes link formation between hubs and between low-degree nodes, but not
between hubs and low-degree nodes:

$s(x,y)=\dfrac{|\Gamma_{x}\cap\Gamma_{y}|}{\max(|\Gamma_{x}|,|\Gamma_{y}|)}$

###  III-J The local Leicht-Holme-Newman index (LLHN)

The LLHN index is defined as the ratio of actual paths of length two between
two nodes and a value proportional to the expected number of paths of length
two between them. It is similar to the Jaccard and Salton indices, yet more
sensitive as a measure of structural equivalence [21]:

$s(x,y)=\dfrac{|\Gamma_{x}\cap\Gamma_{y}|}{|\Gamma_{x}||\Gamma_{y}|}$

##  IV Experimentation

In our experimentation, we will analyze the results obtained by a hierarchical
community detection algorithm using a dozen different criteria on half a dozen
benchmark data sets. As baseline, we will resort to the edge betweenness of
Girvan and Newman’s method as well as the edge clustering coefficient of
Radicchi’s proposal. We will also evaluate the performance of the 10 different
criteria used by local link prediction methods described in the previous
Section: common neighbors (CN), the Adamic-Adar index (AA), the resource
allocation index (RA), the preferential attachment index (PA), the hub
depressed index (HD), the hub promoted index (HP), the Jaccard index (JA), the
local Leicht-Holme-Newman (LLHN) index, the Salton index (SA), and the
Sørensen index (SO).

###  IV-A Benchmark data sets

The following network data sets were obtained from networkrepository.com [22],
SNAP [23], and Pajek datasets [24]:

  * •

Zachary’s karate club [25]

  * •

Word adjacencies [26]

  * •

Dolphin [27]

  * •

Les Misérables [28]

  * •

U.S. politics [29][30]

  * •

American football [3]

Some key structural properties of those networks are shown in Table I.

###  IV-B Data

Table I: Key structural properties of the networks used in our experiments:
number of nodes ($n$), number of links/edges ($m$), average node degree
($\langle k\rangle$), and average clustering coefficient ($C$).

Network | $n$ | $m$ | $\langle k\rangle$ | $C$ | reference
---|---|---|---|---|---
Zachary’s karate club | 34 | 78 | 4.588 | 0.426 | [25]
Word adjacencies | 112 | 425 | 7.528 | 0.403 | [26]
Dolphin | 62 | 159 | 5.129 | 0.307 | [27]
Les Misérables | 77 | 254 | 6.597 | 0.389 | [28]
US politics | 105 | 441 | 8.400 | 0.330 |  [29][30]
American Football | 115 | 613 | 10.661 | 0.399 | [3]

###  IV-C Edge selection criteria

The dozen different versions of the hierarchical community detection algorithm
were implemented in Python with the help of the following libraries: NumPy
[31] for mathematical computations, NetworkX [32] and NOESIS [33][34] for
network data mining algorithms.

Table II: Lineal correlation between edge betweenness and the different
criteria used by local link prediction techniques.

Network | CN | AA | RA | PA | HD | HP | JA | LLHN | SA | SO | Avg.
---|---|---|---|---|---|---|---|---|---|---|---
Zachary | -0.201 | -0.107 | -0.059 | 0.392 | -0.507 | -0.326 | -0.481 | -0.580 | -0.477 | -0.492 | -0.284
Word | 0.068 | 0.103 | 0.134 | 0.239 | -0.330 | 0.017 | -0.254 | -0.384 | -0.196 | 0.266 | -0.087
Dolphin | -0.431 | -0.410 | -0.384 | -0.098 | -0.469 | -0.490 | -0.465 | -0.466 | -0.486 | -0.484 | -0.418
Misérables | -0.338 | -0.280 | -0.204 | 0.380 | -0.547 | -0.497 | -0.539 | -0.508 | -0.561 | -0.559 | -0.365
Politics | -0.271 | -0.240 | -0.196 | -0.010 | -0.397 | -0.424 | -0.418 | -0.343 | -0.455 | -0.437 | -0.319
Football | -0.777 | -0.779 | -0.780 | -0.016 | -0.785 | -0.787 | -0.757 | -0.790 | -0.787 | 0.787 | -0.704
Average | -0.325 | -0.286 | -0.248 | 0.148 | -0.506 | -0.418 | -0.486 | -0.512 | -0.494 | -0.504 |

First of all, we measured the correlation between edge betweenness (the
criterion used by the original Girvan and Newman’s algorithm) and the 10
different local criteria used by local link prediction techniques. The
correlation is often negative, given that we choose edges that maximize edge
betweenness, whereas we will choose edges that minimize the local structural
property defined by the corresponding local link prediction method. However,
correlation is usually weak, only stronger for the American Football network.

###  IV-D Community detection results

We used 12 different criteria in the hierarchical community detection
algorithm and measured the results in terms of modularity. In optimization-
based community detection algorithms, modularity makes reference to any
numerical measure that is suitable for detecting communities in networks (i.e.
the target of community detection as a numerical optimization problem). Here,
however, we refer to the original modularity $Q$, as defined by Mark E.J.
Newman [35].

The less efficient Girvan and Newman’s algorithm, which resorts to edge
betweenness, is included as a baseline. Radicchi’s edge-clustering-
coefficient-based algorithm is also included in our comparison with 10
different local link prediction indicators.

The results are displayed in Figure 3. The hierarchical clustering results
from 2 to 10 communities are shown for 6 different networks in terms of
Newman’s $Q$ modularity. Results vary depending on the network properties.

In some networks, like adjnoun, only Radicchi’s clustering coefficient and the
preferential attachment index seem to work well (maybe due to the “rich get
richer” effect observed in power law degree distributions that result from a
preferential attachment model of network formation). In other networks, like
football, where there is a strong community structure (regional divisions
within a sport season), any measure is able to detect communities. In general,
however, results vary and some measures fail to detect communities (even
Girvan and Newman’s edge betweenness).

(a) adjnoun (b) dolphins (c) football (d) karate (e) lesmis (f) polbooks

Figure 3: Modularity results using 12 different criteria for hierarchical
community detection.

###  IV-E Network pruning

To improve the results discussed in the previous paragraphs, we proceeded to
prune the networks in a controlled way. The motivation behind that pruning is
that networks often include low degree nodes that do not truly participate in
network community formation and those nodes might be adding noise to the
measures of the local structural properties we use to split the networks.

Our pruning algorithms consists of eliminating those nodes with a low degree,
as well as their adjacent links. Obviously, we safeguard the data
corresponding to those nodes and links, so that the community detection
results are always reported on the whole network, not just on the pruned
network.

We measured the impact of pruning at different levels, i.e. using different
minimum degree thresholds, on the structural properties of networks. In Figure
4, we see how the average node degree and clustering coefficient evolve as
more and more nodes and edges are removed from the original networks.

(a) adjnoun (b) dolphins (c) football (d) karate (e) lesmis (f) polbooks

Figure 4: Evolution of network structural properties as more and more nodes
are pruned from the original networks.

The optimal pruning strategy must be determined individually, taking into
account the specific features of each network. Excessive pruning could distort
the topology of the network when carelessly performed.

###  IV-F Improved community detection results with network pruning

In order to improve the results obtained by hierarchical community detection,
we pruned the networks using the strategy discussed above. The results are
shown in Figure 5.

Comparing Figures 3 and 5, we can see that, as intended, noise has been
reduced when computing local structural properties and the community detection
results have improved in terms of modularity.

(a) adjnoum (b) dolphins (c) football (d) karate (e) lesmis (f) polbooks

Figure 5: Modularity results using 12 different criteria for hierarchical
community detection on pruned networks.

Tables III and IV collect the average modularity obtained by hierarchical
community detection with and without network pruning using 10 different local
link prediction measures.

Table III: Average modularity of hierarchical community detection using local link prediction measures, original networks. | CN | AA | RA | PA | JA | SO | SA | HD | HP | LLHN | avg | max
---|---|---|---|---|---|---|---|---|---|---|---|---
adjnoun | 0.00 | 0.00 | 0.00 | 0.49 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.05 | 0.49
dolphins | 0.01 | 0.01 | 0.01 | 0.53 | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.01 | 0.06 | 0.53
football | 0.47 | 0.55 | 0.55 | 0.50 | 0.61 | 0.61 | 0.60 | 0.54 | 0.62 | 0.59 | 0.56 | 0.62
karate | 0.00 | 0.00 | 0.00 | 0.63 | 0.38 | 0.38 | 0.38 | 0.10 | 0.39 | 0.38 | 0.26 | 0.63
lesmis | 0.00 | 0.00 | 0.00 | 0.53 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.05 | 0.53
polbook | 0.00 | 0.00 | 0.00 | 0.43 | 0.15 | 0.15 | 0.43 | 0.05 | 0.46 | 0.54 | 0.22 | 0.54
Table IV: Average modularity of hierarchical community detection using local link prediction measures, pruned networks. | CN | AA | RA | PA | JA | SO | SA | HD | HP | LLHN | avg | max
---|---|---|---|---|---|---|---|---|---|---|---|---
adjnoun | 0.00 | 0.00 | 0.00 | 0.61 | 0.03 | 0.03 | 0.00 | 0.03 | 0.00 | 0.11 | 0.08 | 0.61
dolphins | 0.39 | 0.27 | 0.28 | 0.59 | 0.56 | 0.56 | 0.56 | 0.35 | 0.54 | 0.57 | 0.47 | 0.59
football | 0.35 | 0.46 | 0.46 | 0.60 | 0.57 | 0.57 | 0.58 | 0.46 | 0.57 | 0.58 | 0.52 | 0.60
karate | 0.29 | 0.12 | 0.12 | 0.65 | 0.49 | 0.49 | 0.50 | 0.31 | 0.45 | 0.50 | 0.39 | 0.65
lesmis | 0.07 | 0.11 | 0.11 | 0.44 | 0.23 | 0.23 | 0.37 | 0.17 | 0.50 | 0.41 | 0.26 | 0.50
polbook | 0.26 | 0.27 | 0.10 | 0.48 | 0.46 | 0.46 | 0.51 | 0.40 | 0.52 | 0.56 | 0.40 | 0.56

Tables V, VI, and VII include the results of the statistical tests we
performed to verify whether the observed improvements on similarity were
statistically significant. These tests compare the original edge-betweenness-
based hierarchical community detection with the different hierarchical
community detection methods that result from resorting to local link
prediction heuristics, using both Student’s t-test and Wilcoxon’s test.

Table V: Student’s t-tests performed to check the differences between the original algorithm, based on edge betweenness, and the algorithms based on local link prediction measures (with network pruning). Student’s t-test | adjnoun | dolphins | football | karate | lesmis | polbook
---|---|---|---|---|---|---
Bn vs CN2 | 0.000109 | 0.000087 | 0.001195 | 0.000001 | 0.000000 | 0.000607
Bn vs AA2 | 0.001536 | 0.003542 | 0.008012 | 0.000003 | 0.000003 | 0.002095
Bn vs RA2 | 0.007567 | 0.000515 | 0.006797 | 0.000003 | 0.000010 | 0.000015
Bn vs PA2 | 0.000000 | 0.005556 | 0.003528 | 0.000000 | 0.004172 | 0.039515
Bn vs JA2 | 0.000196 | 0.018640 | 0.034081 | 0.000020 | 0.007429 | 0.042177
Bn vs SO2 | 0.000196 | 0.018640 | 0.034081 | 0.000020 | 0.007429 | 0.042177
Bn vs SA2 | 0.000033 | 0.010934 | 0.046849 | 0.000029 | 0.071101 | 0.000239
Bn vs HD2 | 0.000006 | 0.008057 | 0.007651 | 0.000017 | 0.001801 | 0.000643
Bn vs HP2 | 0.001209 | 0.146216 | 0.031129 | 0.000005 | 0.198531 | 0.000649
Bn vs LLHN2 | 0.000022 | 0.210601 | 0.070239 | 0.000052 | 0.690262 | 0.000270
Table VI: Wilcoxon’s tests performed to check the differences between the original algorithm, based on edge betweenness, and the algorithms based on local link prediction measures (with network pruning). Wilcoxon’s test | adjnoun | dolphins | football | karate | lesmis | polbook
---|---|---|---|---|---|---
Bn vs CN2 | 0.000625 | 0.000132 | 0.000132 | 0.000182 | 0.000132 | 0.000132
Bn vs AA2 | 0.003307 | 0.000132 | 0.000132 | 0.000132 | 0.000132 | 0.000132
Bn vs RA2 | 0.019593 | 0.000132 | 0.000155 | 0.000132 | 0.000132 | 0.000132
Bn vs PA2 | 0.000132 | 0.003762 | 0.000132 | 0.000155 | 0.019593 | 0.044208
Bn vs JA2 | 0.000132 | 0.004274 | 0.000293 | 0.001116 | 0.003762 | 0.000837
Bn vs SO2 | 0.000132 | 0.004274 | 0.000293 | 0.001116 | 0.003762 | 0.000837
Bn vs SA2 | 0.000342 | 0.004274 | 0.000342 | 0.000724 | 0.107466 | 0.001116
Bn vs HD2 | 0.000132 | 0.000155 | 0.000155 | 0.000182 | 0.000724 | 0.000132
Bn vs HP2 | 0.001285 | 0.019593 | 0.070157 | 0.000625 | 0.658009 | 0.024224
Bn vs LLHN2 | 0.000132 | 0.098957 | 0.227330 | 0.000724 | 0.277241 | 0.002225
Table VII: Statistical tests performed to check the impact of network pruning on the results obtained by hierarchical community detection using different local link prediction heuristics. Student’s t-test | adjnoun | dolphins | football | karate | lesmis | polbook
---|---|---|---|---|---|---
CN1 vs CN2 | 0.067889 | 0.000196 | 0.001285 | 0.000000 | 0.000196 | 0.000438
AA1 vs AA2 | 0.003346 | 0.000196 | 0.021802 | 0.000010 | 0.000982 | 0.000655
RA1 vs RA2 | 0.007686 | 0.000196 | 0.040136 | 0.000007 | 0.000982 | 0.002218
PA1 vs PA2 | 0.136498 | 0.053406 | 0.003307 | 0.035732 | 0.007013 | 0.197833
JA1 vs JA2 | 0.000132 | 0.000132 | 0.001944 | 0.285207 | 0.000196 | 0.077767
SO1 vs SO2 | 0.000132 | 0.000132 | 0.001944 | 0.285207 | 0.000196 | 0.077767
SA1 vs SA2 | 0.108809 | 0.000132 | 0.000967 | 0.390730 | 0.000196 | 0.809204
HD1 vs HD2 | 0.000132 | 0.000132 | 0.002902 | 0.021373 | 0.000293 | 0.005684
HP1 vs HP2 | 0.043114 | 0.000196 | 0.026876 | 0.647238 | 0.000132 | 0.070157
LLHN1 vs LLHN2 | 0.000132 | 0.000132 | 0.021802 | 0.083299 | 0.000196 | 0.872118

##  V Conclusion

In this paper, we have advocated for the use of the local network structural
properties employed by local link prediction methods in hierarchical community
detection.

The original Girvan and Newman’s algorithm, based on edge betweenness, obtains
excellent results but is too costly from a computational point of view.
Radicchi’s alternative proposal, based on an edge clustering coefficient, is
more efficient yet fails sometimes. In our experiments, we have shown how
local link prediction provides the key to both quality results and efficient
algorithms.

Given that hierarchical community detection is an iterative greedy algorithm,
when basing our decisions on local network properties, we run the risk of
taking the wrong decisions due to noise in our local measurements. We have
also shown that network pruning can help reduce such noise and improve the
results of hierarchical community detection based on local link prediction
measures.

## References

  * [1] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, pp. 75–174, Feb. 2010.
  * [2] W. Liu, M. Chen, H. Miao, Y. Zhou, and X. Chen, “A fast community detection algorithm,” in 2016 5th International Conference on Computer Science and Network Technology (ICCSNT), pp. 345–349, Dec. 2016.
  * [3] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, pp. 7821–7826, June 2002.
  * [4] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, “Defining and identifying communities in networks,” Proceedings of the National Academy of Sciences, vol. 101, pp. 2658–2663, Mar. 2004.
  * [5] V. Martínez, F. Berzal, and J.-C. Cubero, “A Survey of Link Prediction in Complex Networks,” ACM Computing Surveys, vol. 49, pp. 1–33, Dec. 2016.
  * [6] B. Liu, Web data mining: exploring hyperlinks, contents, and usage data.  Data-centric systems and applications, Heidelberg ; New York: Springer, 2nd ed ed., 2011.
  * [7] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, p. 026113, Feb. 2004.
  * [8] M. Newman, Networks: An Introduction.  Oxford University Press, Mar. 2010.
  * [9] M. E. J. Newman, “Detecting community structure in networks,” The European Physical Journal B, vol. 38, pp. 321–330, Mar. 2004.
  * [10] A. Clauset, C. Moore, and M. E. J. Newman, “Hierarchical structure and the prediction of missing links in networks,” Nature, vol. 453, pp. 98–101, May 2008.
  * [11] D. Liben-Nowell and J. Kleinberg, “The Link Prediction Problem for Social Networks,” in Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM ’03, (New York, NY, USA), pp. 556–559, ACM, 2003.  event-place: New Orleans, LA, USA.
  * [12] T. Zhou, L. Lü, and Y.-C. Zhang, “Predicting missing links via local information,” The European Physical Journal B, vol. 71, pp. 623–630, Oct. 2009.
  * [13] J. C. Valverde-Rebaza and A. de Andrade Lopes, “Link Prediction in Complex Networks Based on Cluster Information,” in Advances in Artificial Intelligence - SBIA 2012 (L. N. Barros, M. Finger, A. T. Pozo, G. A. Gimenénez-Lugo, and M. Castilho, eds.), Lecture Notes in Computer Science, pp. 92–101, Springer Berlin Heidelberg, 2012.
  * [14] L. Lü and T. Zhou, “Link prediction in complex networks: A survey,” Physica A: Statistical Mechanics and its Applications, vol. 390, pp. 1150–1170, Mar. 2011.
  * [15] L. A. Adamic and E. Adar, “Friends and neighbors on the Web,” Social Networks, vol. 25, pp. 211–230, July 2003.
  * [16] A.-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, vol. 286, pp. 509–512, Oct. 1999.
  * [17] P. Jaccard, “Étude de la distribution florale dans une portion des Alpes et du Jura,” Bulletin de la Société vaudoise des sciences naturelles, vol. 37, no. 142, pp. 547–579, 1901.
  * [18] T. Sørensen, A method for establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons, vol. V of Det Kongelige Danske Videnskabernes Selskab Biologiske Skrifter.  Denmark: Bianco Lunos Bogtrykkeeri, 1948.
  * [19] G. Salton and M. J. McGill, Introduction to Modern Information Retrieval.  New York, NY, USA: McGraw-Hill, Inc., 1986.
  * [20] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabási, “Hierarchical Organization of Modularity in Metabolic Networks,” Science, vol. 297, pp. 1551–1555, Aug. 2002.
  * [21] E. A. Leicht, P. Holme, and M. E. J. Newman, “Vertex similarity in networks,” Physical Review E, vol. 73, p. 026120, Feb. 2006.  arXiv: physics/0510143.
  * [22] R. A. Rossi and N. K. Ahmed, “The Network Data Repository with Interactive Graph Analytics and Visualization,” 2015.
  * [23] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford Large Network Dataset Collection,” June 2014.
  * [24] V. Batagelj and A. Mrvar, “Pajek datasets,” 2006.
  * [25] W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, vol. 33, no. 4, pp. 452–473, 1977.
  * [26] M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Physical Review E, vol. 74, p. 036104, Sept. 2006.
  * [27] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behavioral Ecology and Sociobiology, vol. 54, pp. 396–405, Sept. 2003.
  * [28] D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing.  New York, NY, USA: ACM, 1993.
  * [29] E. Eakin, “Study Finds a Nation of Polarized Readers,” The New York Times, Mar. 2004.
  * [30] V. Krebs, “Political Polarization During the 2008 US Presidential Campaign,” 2008.
  * [31] S. v. d. Walt, S. C. Colbert, and G. Varoquaux, “The NumPy Array: A Structure for Efficient Numerical Computation,” Computing in Science & Engineering, vol. 13, pp. 22–30, Mar. 2011.
  * [32] A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring Network Structure, Dynamics, and Function using NetworkX,” p. 5, 2008.
  * [33] V. Martínez, F. Berzal, and J. Cubero, “The NOESIS open source framework for network data mining,” in 2015 7th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management (IC3K), vol. 01, pp. 316–321, Nov. 2015.
  * [34] V. Martínez, F. Berzal, and J. C. C. Talavera, “NOESIS: A framework for complex network data analysis,” Complexity, vol. 2019, pp. 1439415:1–1439415:14, 2019.
  * [35] M. E. J. Newman, “Modularity and community structure in networks,” Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577–8582, 2006.


# A Jordan Curve that cannot be Crossed by Rectifiable Arcs on a set of Zero
Length

Jack Burkart  Department of Mathematics, Stony Brook University, Stony Brook,
NY 11794<EMAIL_ADDRESS>
###### Abstract.

We construct a Jordan curve $\Gamma\subset\mathbb{C}$ so that for any
rectifiable arc $\sigma$ with endpoints in distinct complementary components
of $\Gamma$, $H^{1}(\sigma\cap\Gamma)>0$.

##  1\. Introduction and Motivation

A Jordan curve is an injective image of the unit circle in the plane. The
Jordan Curve Theorem asserts that a Jordan curve separates the plane into
exactly two complementary components, a bounded interior component and an
unbounded exterior component. This gives Jordan curves rather simple topology,
but their geometry can be exotic. We say an arc crosses a Jordan curve
$\Gamma$ if its endpoints belong in different complementary components of
$\Gamma$. Let $H^{1}$ denote the Hausdorff $1$-measure. In this paper, we
prove the following theorem, answering a question posed by Sauter in [Sau18].

######  Theorem 1.1.

There exists a Jordan curve $\Gamma$ so that if $\sigma$ is a rectifiable
(finite length) arc crossing $\Gamma$, $H^{1}(\sigma\cap\Gamma)>0$.

We would like to make some more general remarks about Theorem 1.1. It is a
straightforward calculation from the construction that $\Gamma$ will have
positive area, but a simple argument using Fubini’s theorem and integrating
over a family of line segments shows that any $\Gamma$ satisfying the
conclusion of Theorem 1.1 must have positive area.

By the Riemann mapping theorem and Caratheodory’s theorem, any Jordan curve
can be crossed by an arc of $\sigma$-finite length that intersects the Jordan
curve at exactly one point. Such an arc is analytic everywhere except possibly
at the point where it crosses the boundary. In this sense, the hypothesis of
rectifiablility is the weakest hypothesis on $\sigma$ so that the conclusion
of Theorem 1.1 will hold.

Theorem 1.1 has been addressed in other contexts, both in the class of arcs
$\sigma$ considered and the size of the intersection of $\sigma\cap\Gamma$.
Examples of Jordan curves $\Gamma$ that cannot be crossed by line segments at
only one point seem well known, see for example [Pet]. In [Bis], Bishop
constructs a Jordan curve so that if $\sigma$ is a line segment crossing
$\Gamma$, the Hausdorff dimension of $\sigma\cap\Gamma$ is $1$, but the case
of positive length is not addressed. Motivated by questions about ordinary
differential equations, in [PW12], Pugh and Wu show that Jordan curves that
cannot be crossed by rectifiable arcs at exactly one point exist and are
actually generic (in a Baire sense) in the space of Jordan curves in the plane
(equipped with an appropriate metric).

The curve $\Gamma$ also has connections to conformal welding. If $\Gamma$ is a
Jordan curve in the plane, let $\Omega$ denote its bounded complementary
component. Then there are conformal mappings $f:\mathbb{D}\rightarrow\Omega$
and
$g:\mathbb{C}\setminus\overline{\mathbb{D}}\rightarrow\mathbb{C}\setminus\overline{\Omega}$
which induce a circle homeomorphism $h:g\circ
f^{-1}:\partial\mathbb{D}\rightarrow\partial\mathbb{D}$ which we call a
conformal welding. $\Gamma$ is called log-singular if there is a Borel set $E$
so that $E$ and $h(S^{1}\setminus E)$ both have zero logarithmic capacity (for
the definition of logarithmic capacity, see Chapter III of [GM05]). Results of
Buerling in [Beu40] show that if $\varphi:\mathbb{D}\rightarrow\Omega$ is a
conformal mapping onto a Jordan domain $\Omega$, and $\zeta\in S^{1}$.

$\int_{0}^{1}|\varphi^{\prime}(r\zeta)|dr<\infty$

except perhaps on a set of zero logarithmic capacity (see also 23(a), p. 127,
in [GM05]). It follows that outside of this exceptional set, the image of the
hyperbolic geodesic rays $[0,\zeta)$ have finite length. Applying this result
to both $f$ and $g$, it follows from Theorem 1.1 that $\Gamma$ is log-
singular. Otherwise, by using a pair of two finite length geodesics with the
same endpoint on $\Gamma$, we could construct a finite length arc crossing
$\Gamma$ at exactly one point. Our example gives the first explicit
construction of a log singular curve. For more on log-singular curves and
conformal welding, see [Bis94] and [Bis07].

We will construct the curve $\Gamma=\bigcap_{n=1}^{\infty}\Gamma_{n}$ in
Theorem 1.1 as a nested intersection of axis aligned tubes which we call
plumbings. Given a plumbing, we will use a Lakes of Wada type of construction
to construct a new plumbing which weaves back and forth inside of itself, see
Figure 1. For a rectifiable curve $\sigma$ that passes from the interior
boundary component to the exterior boundary component of $\Gamma$, we let
$l_{n}=H^{1}(\Gamma_{n}\cap\sigma).$ In order for $l_{n+1}$ to be much smaller
than $l_{n}$, $\sigma$ must weave back and forth horizontally so that it can
pass through the vertical gaps, as seen in Figure 1. We will tune the
parameters defining the plumbings $\Gamma_{n}$ so that $\sigma$ can only pass
through a increasingly smaller percentage of the vertical gaps of $\Gamma_{n}$
as $n\rightarrow\infty$. It will follow that most of the time, the connected
components of $\sigma\cap\Gamma_{n+1}$ must pass through those components
approximately as a straight line segment, and we will show directly that a
straight line segment intersects $\Gamma$ with a set of positive length. These
observations combined will allow us to prove Theorem 1.1.

Figure 1. An example of the procedure taking a plumbing $\Gamma_{n}$ (pictured
in gray) to a new plumbing $\Gamma_{n+1}$ (pictured in black). For a
rectifiable curve to intersect $\Gamma$ on a set of zero length, it must
intersect $\Gamma_{n}$ on a set of length which tends to $0$ as
$n\rightarrow\infty$. This requires $\sigma$ to weave back and forth too much
in comparison to the width of the rectangles that define the plumbings, and
this will cost a large amount of length if this happens too often.

The structure of the paper is as follows. In Section 2, we define all the
necessary terminology and reduce Theorem $1.1$ to the case of rectifiable
curves with length $1$. In Section $3$, we carefully define plumbings and
discuss their properties. In Sections 4 and 5, we show how to create new
plumbings from old to create the limiting Jordan curve $\Gamma$. In Section 6,
we show that the Jordan curve cannot be crossed at a single point by
rectifiable curves, and in Section 7 we refine this to show the intersection
of the rectifiable curve with the Jordan curve has positive area.

##  2\. Preliminaries and Generalities

A curve is a continuous function $\sigma:[0,1]\rightarrow\mathbb{C}$. If
$\sigma$ is a curve with $\sigma(0)=\sigma(1)$ we call $\sigma$ closed. We
will sometimes refer to curves that are not closed as arcs. A curve $\sigma$
is called simple if for all $t_{1}\neq t_{2}\in[0,1]$, we have
$\sigma(t_{1})\neq\sigma(t_{2})$. Similarly, we call a closed curve simple if
for all $t_{1}\neq t_{2}\in[0,1)$, we have $\sigma(t_{1})\neq\sigma(t_{2})$. A
Jordan curve is a simple closed curve. The image
$\sigma([0,1])\subset\mathbb{C}$ is the trace of $\sigma$. When it will not
cause confusion, we will refer the trace of a curve $\sigma$ and the curve
$\sigma$ interchangeably. Recall that the length of a curve $\sigma$ is
defined to be

$l(\sigma)=\sup_{0=t_{0}\leq t_{1}\leq\dots\leq
t_{n}=1}\sum_{k=1}^{n}|\sigma(t_{k})-\sigma(t_{k-1})|.$

If $l(\sigma)<\infty$, we call the curve or arc $\sigma$ rectifiable.

######  Definition 2.1.

Let $\Gamma\subset\mathbb{C}$ be a Jordan curve. We say that an arc $\sigma$
crosses $\Gamma$ if $\sigma(0)$ and $\sigma(1)$ are in distinct complementary
components of $\Gamma$.

If $\sigma$ crosses $\Gamma$, we are interested in the subset of points where
$\sigma$ passes from one complimentary component of $\Gamma$ to the other.

######  Definition 2.2.

We say that $\sigma$ pierces $\Gamma$ at $x$ if for every $\epsilon>0$,
$B(x,\epsilon)\cap\sigma$ contains points in both complementary components of
$\Gamma$. If $\sigma$ crosses $\Gamma$, the piercing set of $\sigma$,
$\mathcal{P}(\sigma)$, is the nonempty set of all points $x\in\Gamma$ where
$\sigma$ pierces $\Gamma$ at $x$. $\Gamma$ is called pierceable by rectifiable
curves if there exists a rectifiable curve $\sigma$ crossing $\Gamma$ so that
$\mathcal{P}(\sigma)$ is exactly one point. Otherwise $\Gamma$ is unpierceable
by rectifiable curves.

The definition of pierceability can be easily adjusted to include other
families of curves, such as line segments, simple rectifiable curves, and
rectifiable curves of some given length. If $\Gamma$ is unpierceable by
rectifiable curves, the piercing set is nontrivial.

######  Lemma 2.3.

Let $\Gamma$ be a Jordan curve. The following are equivalent:

  1. (1)

$\Gamma$ is unpierceable by rectifiable arcs.

  2. (2)

$\Gamma$ is unpierceable by simple rectifiable arcs.

  3. (3)

$\Gamma$ is unpierceable by simple rectifiable arcs with length $\leq 1$

  4. (4)

For any simple rectifiable $\sigma$ crossing $\Gamma$, $\mathcal{P}(\sigma)$
is uncountable.

  5. (5)

For any rectifiable $\sigma$ crossing $\Gamma$, $\mathcal{P}(\sigma)$ is
uncountable.

###### Proof.

It is easy to see that $(1)\Rightarrow(2)\Rightarrow(3)$ and obviously
$(5)\Rightarrow(1)$. $(4)\Rightarrow(5)$ because if $\sigma$ is a rectifiable
arc, there exists a simple rectifiable arc $\sigma^{\prime}$ which is a subset
of the trace of $\sigma$ with the same endpoints. So it is sufficient to show
that $(3)\Rightarrow(4)$.

First observe that $\mathcal{P}(\sigma)$ cannot have any isolated points,
otherwise there exists a sub-curve $\sigma^{\prime}\subset\sigma$ in a
neighborhood of the isolated point that pierces $\Gamma$ at exactly one point.
Since closed countable sets must have isolated points, it will be sufficient
to show that $\mathcal{P}(\sigma)$ is closed.

Let $\Omega_{1}$ be the bounded complementary component of $\Gamma$, and
$\Omega_{2}$ be the unbounded complementary component of $\Gamma$. Write
$\sigma:[0,1]\rightarrow\mathbb{C}$. Let $A=\sigma^{-1}(\Omega_{1})$ and
$B=\sigma^{-1}(\Omega_{2})$. $A$ and $B$ are disjoint open subsets of $[0,1]$.
We claim that

(2.1) $\mathcal{P}(\sigma)=\sigma(\overline{A}\cap\overline{B}).$

If $x\in\mathcal{P}(\sigma)$, there exists sequences
$z_{n}\subset\sigma\cap\Omega_{1}$ and $w_{n}\subset\sigma\cap\Omega_{2}$ so
that $z_{n}\rightarrow x$ and $w_{n}\rightarrow x$. Since $\sigma$ is simple,
if $\sigma(t)=x$, there are corresponding sequences $t_{n}$ and
$t_{n}^{\prime}$ so that $z_{n}=\sigma(t_{n})$,
$w_{n}=\sigma(t_{n}^{\prime})$, and both $t_{n},t_{n}^{\prime}\rightarrow t$.
So $t\in\overline{A}\cap\overline{B}$, and therefore
$\sigma(t)=x\in\sigma(\overline{A}\cap\overline{B})$.

If $x\notin\mathcal{P}(\sigma)$, then there exists an $\epsilon>0$ so that
either $B(x,\epsilon)\cap\sigma$ does not contain any points in $\Omega_{1}$,
or $B(x,\epsilon)\cap\sigma$ does not contain any points in $\Omega_{2}$. If
$B(x,\epsilon)\cap\sigma$ does not contain any points in $\Omega_{1}$, and if
$\sigma(t)=x$, then there exists a $\delta>0$ so that
$\sigma(t-\delta,t+\delta)\subset B(x,\epsilon/2)$ which implies that
$\sigma(t-\delta,t+\delta)\cap\Omega_{1}$ is empty. It follows that
$t\notin\overline{B}$, and since $\sigma$ is simple it follows that
$x\notin\sigma(\overline{A}\cap\overline{B})$. The argument is exactly the
same if $B(x,\epsilon)\cap\sigma$ does not contain any points in $\Omega_{2}$.
Therefore, (2.1) holds.

Since $\overline{A}\cap\overline{B}$ is compact and $\sigma$ is continuous,
$\mathcal{P}(\sigma)$ is compact and therefore must be closed. This proves the
claim. ∎

In fact, it is not difficult to see additionally that $\mathcal{P}(\sigma)$ is
a Cantor set: compact, uncountable, totally disconnected, and no isolated
points.

##  3\. Plumbing

The curve $\Gamma$ we construct will be the nested intersection of a sequence
of topological annuli which we call plumbings. We first define the two basic
pieces that determine a plumbing. See Figure 2.

Figure 2. Plumbings are constructed by alternating straight pieces and corner
pieces, and gluing them together by arc length. The boundary sides are filled
in and the openings are denoted by the dotted lines.

To form a straight piece, start with a rectangle with sides parallel to the
coordinate axes, and remove two of the opposite sides. We call the remaining
sides the boundary sides of the straight piece and the sides we removed the
openings of the straight piece. We call the boundary side that is a subset of
the interior boundary component of the plumbing the top of the straight piece,
and the boundary side which is a subset of the exterior boundary component of
the plumbing the bottom of the straight piece. Whenever we need to analyze a
specific straight piece, we will orient our point of view to justify these
names.

Corner pieces are formed by taking an axis aligned rectangle and removing two
adjacent sides, but keeping the mutual vertex of the two removed sides. This
vertex is called an inner corner for the corner piece, and the remaining sides
are similarly called boundary sides and openings. Plumbings are formed by
alternating straight and corner pieces and gluing together their openings by
arc length. See Figure 3 for an example of a plumbing.

######  Definition 3.1.

A plumbing $P$ is a closed topological annulus obtained by gluing together
straight pieces and corner pieces so that between every two corner pieces
there exists exactly one straight piece.

Figure 3. An example of plumbing.

We define the following geometric quantities associated to a plumbing. The
width of a straight piece is defined to be the distance between its boundary
sides. The width of a plumbing is defined to be the maximum of the widths of
the straight pieces in the plumbing. The length of a straight piece is the
distance between its openings. The min-length of a plumbing is the minimum of
the lengths of its straight pieces.

Figure 4. A plumbing with its core curve in the middle, oriented
counterclockwise.

Plumbings come with a natural foliation of axis aligned polygonal curves that
follow the inner and outermost boundary. Start with a plumbing $P$, and let
$\gamma_{0}$ and $\gamma_{1}$ denote the outermost and innermost boundary
components, respectively. Decompose $P$ into its straight and corner pieces.
Given a straight piece $S$ and a number $t\in(0,1)$, let $w$ denote its width.
Let $s_{t}$ denote the line segment parallel to the boundary sides of $S$ with
distance $t\cdot w$ from $\gamma_{0}$. Draw this line segment for all straight
pieces in $P$. Any corner piece is adjacent to two straight pieces, and each
of its openings contains an endpoint of some $s_{t}$ and some
$s_{t}^{\prime}$. Continue the segments $s_{t}$ and $s_{t}^{\prime}$ until
they intersect (this point of intersection will be on the diagonal that
separates the openings of the corner piece) and repeat this for all corner
pieces to form a Jordan curve $\gamma_{t}$. We define $\gamma_{1/2}$ to be the
core curve of $P$. We call $\\{\gamma_{t}\\}$ the plumbing foliation of $P$.
Whenever we parameterize the elements of a plumbing foliation, we do so
counterclockwise, so that the inner boundary component is always to the left
of the curve in the foliation. See Figure 4.

Figure 5. An illustration of some elements of the plumbing foliation, with
orientation.

.

A point on the core curve of $P$ where the core curve changes from a vertical
segment to a horizontal segment or vice versa is called a bend point. Two bend
points are called adjacent if there is no bend point between them. Every bend
point is adjacent to exactly two other bend points. Let $z$ and $w$ be two
adjacent bend points of $P$, so that the core curve passes through $z$ first.
The $(z,w)$-junction is the union of the two corner pieces containing $z$ and
$w$, and the straight piece that is between $z$ and $w$. Each $(z,w)$ junction
takes two possible forms, depending on how the openings of the corner pieces
are configured. We call the junctions $U$-junctions and $Z$-junctions,
respectively. When considered with respect to the orientation of the core
curve, there are four junctions to consider. See Figure 6.

Figure 6. Accounting for orientation, there are two Z-junctions and two
U-junctions. The pictures have been oriented so that the top boundary side of
the straight piece is a subset of the innermost boundary of the plumbing. In
fact, since a plumbing is axis aligned, we can always orient our view of a
straight piece or junction in this way.

##  4\. Creating New Plumbing from Old

In this section we define a procedure which takes a plumbing $\Gamma_{n}$ and
creates a plumbing $\Gamma_{n+1}$ contained inside of $\Gamma_{n}$ taking up
most of the area of $\Gamma_{n}$, but having a much smaller width. Roughly
put, we will insert very thin vertical and horizontal rectangles segments
inside of $\Gamma_{n}$ to form a new plumbing. This procedure will form the
basis of our construction.

Let $\Gamma_{n}$ be a plumbing. Define

(4.1) $d_{n}:=\min\\{l_{n},w_{n}\\}$

where $l_{n}$ is the min-length of $\Gamma_{n}$ and $w_{n}$ is the width of
$\Gamma_{n}$. Subdivide $\Gamma_{n}$ into straight pieces and corner pieces,
and denote the plumbing foliation of $\Gamma_{n}$ by $\\{\gamma^{n}_{t}\\}$.
Parameterize $\gamma^{n}_{1/2}$ as a Jordan curve, say, by arc length. Denote
$P_{0}$ as the unique plumbing piece of $\Gamma_{n}$ so that
$\gamma^{n}_{1/2}(0)\in P_{0}$ and so that there exists $\delta>0$ so that
$\gamma^{n}_{1/2}:[0,\delta)\rightarrow P_{0}$. Label the rest of the plumbing
pieces $\\{P_{i}\\}_{i=0}^{m-1}$ according to the order $\gamma^{n}_{1/2}(t)$
passes through them. We will consider this list of pieces modulo $m$, so that
$P_{m}=P_{0}$.

Choose some $\delta_{n}\in(0,1/100)$. We are going to subdivide the straight
pieces $P_{i}$ further into rectangles by connecting the boundary sides by
line segments placed distance approximately $\delta_{n}d_{n}$ apart; no line
segment will be farther than $2\delta_{n}d_{n}$ from the adjacent line
segments we place, and no line segment will be closer than
$1/2\delta_{n}d_{n}$ from the adjacent line segments we place. We will simply
refer to these new rectangles as subdivided rectangles. If $P_{i}$ is the
straight piece of a $U$-junction, we must make sure that the number of
subdivide rectangles of $P_{i}$ is even. If $P_{i}$ is an element of a
$Z$-junction, the number of subdivided rectangles should be odd. See Figure 7.

Figure 7. Illustrated above is a $Z$-junction, with pieces $P_{i-1},P_{i}$ and
$P_{i+1}$. Since the straight piece is in a $Z$-junction, we subdivide $P_{i}$
into an odd number of rectangles. Since the boundary sides of $P_{i-1}$ extend
to the bottom boundary side of $P_{i}$, the first subdivided rectangle will be
labeled as ‘T’. The light gray color coincides with rectangles labeled as ‘T’
and the dark gray color coincides with rectangles labeled as ‘B’. In practice,
$\delta_{n}$ is chosen so that $P_{i}$ is broken into at least 100 rectangles.

Given any $t_{n}\in\mathbb{N}$, we select the elements of the plumbing
foliation $\\{\gamma^{n}_{j/t_{n}}\\}_{j=0}^{t_{n}}.$ We will always assume
that $t_{n}$ is an odd number, so that we are selecting $t_{n}+1$ equally
spaced elements of the foliation. If $w_{n}$ is the width of $\Gamma_{n}$,
then adjacent elements of the plumbing foliation inside of a straight piece
are no more than distance $\frac{w_{n}}{t_{n}}$ apart.

For each straight piece $P_{i}$, we want to assign a labels $T$ and $B$ for
its subdivided rectangles.

  1. (1)

If $P_{i-1}$’s boundary side extends the bottom boundary side of $P_{i}$, the
first subdivided rectangle is marked as T.

  2. (2)

If $P_{i-1}$’s boundary side extends the upper boundary side of $P_{i}$, the
first subdivided rectangle is marked as B.

We alternate T and B until we reach the end of the straight piece.

Given a straight piece $P$, we have $P=\cup R_{i}$, where $R_{i}$ are the
subdivided rectangles of $P$ described above with base approximately
$\delta_{n}d_{n}$ and with height no greater than $w_{n}$. Choose some
positive integer $v_{n}=k^{2}$ for some $k\geq 3$ and then choose some
subdivided rectangle $R_{i}$. Decompose the base of $R_{i}$ into $v_{n}$ many
equal length segments. We will need the following definition and combinatorial
fact.

######  Definition 4.1.

Split the unit square a $v_{n}$ by $v_{n}$ square grid. We define a rook
placement to be a selection of exactly $v_{n}$ many squares, which we call
rooks, in the grid so that:

  1. (1)

Each row in the grid contains exactly one rook.

  2. (2)

Each column in the grid contains exactly one rook.

The following lemma is simple, and we leave its proof to the reader, with
Figure 8 as a hint. A rook placement satisfying the conditions of Lemma 4.2 is
called a good $v_{n}$-rook placement.

######  Lemma 4.2.

Let $v_{n}=k^{2}$ for some integer $k\geq 3$, and suppose the unit square has
been decomposed into a $v_{n}$ by $v_{n}$ square grid. Identify the sides of
the unit square to create a torus. Then there exists a rook placement of the
unit square so that for every rook $Q$, the $8$ adjacent squares, viewed on
the torus, do not contain any other rooks in the rook placement.

Figure 8. A good $v_{n}$-rook placement for $v_{n}=5^{2}$.

Supose that $R_{i}$ is a subdivided rectangle of some straight piece, and that
$R_{i}$ is designated as T. The plumbing foliation cuts $R_{i}$ into $t_{n}$
many rectangles. Orienting our point of view and counting downwards from the
boundary side intersecting the interior complementary component, we call the
first $2v_{n}$ many rectangles a $v_{n}$-slab inside $R_{i}$. A $v_{n}$-slab
decomposes into a $v_{n}$ by $v_{n}$ grid. Rows are determined by every two
elements of the plumbing foliation, and the columns are determined by the
$v_{n}$ equally spaced points on the base of $R_{i}$. We choose a good
$v_{n}$-rook placement for this grid. For each rook in this good $v_{n}$-rook
placement, place a vertical line segment connecting the top and bottom of the
rook through the middle. This segment has endpoints on two elements of the
plumbing foliation for $\Gamma_{n}$ that determine the rows, and passes
through exactly one foliation element between the two. See Figure 9.

Figure 9. A good $v_{n}$-rook placement for a $v_{n}$-slab. Each combinatorial
square has base $\delta_{n}d_{n}/v_{n}$ and height $2w_{n}/t_{n}$. The
$v_{n}$-slab the rook placement is inside has width $\delta_{n}d_{n}$ and
height $2v_{n}w_{n}/t_{n}$. The foliation elements that determine the rows of
the $v_{n}$ slab are colored darker than the ones that are skipped and that
the vertical segments intersect.

We can split the rest of $R_{i}$ into $v_{n}$ slabs, going from the top down
and repeating the rook placement of the top $v_{n}$-slab until we reach the
element $\gamma^{n}_{1/t_{n}}$ of the plumbing foliation. We can choose
$t_{n}$ to be larger if we need to so that the final $v_{n}$-slab has a bottom
side determined by $\gamma^{n}_{1/t_{n}}$; we will always assume that $t_{n}$
satisfies this property.

One $v_{n}$ slab forms a rectangle with base length approximately
$\delta_{n}d_{n}$ and height $2v_{n}w_{n}/t_{n}$. In our construction, the
height $2v_{n}w_{n}/t_{n}$ will be much smaller than $\delta_{n}d_{n}$. The
amount of $v_{n}$ slabs we need to stack to form an approximate
$\delta_{n}d_{n}$ by $\delta_{n}d_{n}$ $v_{n}$-square is approximately
$k_{n}$, where,

$\frac{2v_{n}w_{n}}{t_{n}}\cdot k_{n}=\delta_{n}d_{n}.$

Or,

(4.2) $k_{n}=\frac{\delta_{n}d_{n}t_{n}}{2v_{n}w_{n}}.$

We also can see that $R_{i}$ decomposes into approximately

(4.3) $\lambda_{n}=\frac{w_{n}}{\delta_{n}d_{n}}$

many $v_{n}$-squares.

We do the same thing with the rectangles labeled $B$, except instead of
building $v_{n}$-slabs starting from the top down, we build $v_{n}$-slabs
starting from the bottom up. We do not place any segments connecting elements
of the plumbing foliation in corner pieces.

We now draw line segments along the plumbing foliation. In corner pieces, we
add the intersection of all elements in the plumbing foliation with the corner
piece. See Figure 10. In straight pieces, we do the same thing, except we
remove the portion of the plumbing foliation within distance $w_{n}/t_{n}$ of
the center of vertical line segments we placed in the previous step. See
Figure 14.

Figure 10. In the corner pieces of the plumbing, we just fill in the elements
of the plumbing foliation.

With the procedure above of adding in vertical and horizontal line segments
into straight and corner pieces, we have constructed a topological subannulus
contained inside of $\Gamma_{n}$. The only issue remaining is that its
boundary components are not Jordan curves. To do this, we will thicken all of
the segments in the horizontal and vertical directions by a small amount so
that the segments we added become rectangles. The amount we thicken is given
by

(4.4) $\eta_{n}:=\frac{1}{100^{n}}\frac{w_{n}}{\prod_{j=1}^{n}t_{j}}.$

The following theorem is now clear:

######  Theorem 4.3.

$\Gamma_{n+1}$ is a plumbing compactly contained in $\Gamma_{n}$.

The core curve of $\Gamma_{n+1}$ can be visualized in Figure 11.

Figure 11. A visualization of $\Gamma_{n+1}$ inside of a straight piece, with
its core curve in gray. With this point of view, the core curve enters from
the top left hand corner, weaves back and forth between vertical segments we
place down to the bottom, and then weaves back up. This picture was
constructed with one $v_{n}$-square made out of $2$ $v_{n}$-slabs. In
practice, the number of $v_{n}$-slabs and $v_{n}$-squares tends to infinity.

##  5\. The Limiting Object is a Jordan curve

We now construct the Jordan curve $\Gamma$. Fix $\epsilon_{0}>0$ and let
$\Gamma_{0}$ be the topological annulus formed by taking the open square of
side length $2(1+\epsilon_{0})$ centered at the origin and removing the closed
square of side length $2(1-\epsilon_{0})$ centered at the origin. $\Gamma_{0}$
is a square plumbing, and parameterize its core curve using a constant speed
parameterization. Using the procedure in the previous section, we construct a
plumbing with the following parameters. At each stage $n$, we must choose a
parameter $v_{n}$. We assume that $v_{n}$ is strictly increasing, and we
always choose $v_{n}$ to be a perfect square. Moreover, we will demand that

(5.1) $\sum_{n=1}^{\infty}\frac{1}{v_{n}}<\frac{1}{100}.$

We will always assume that the parameters $\delta_{n}$ satisfy

(5.2) $\sum_{n=1}^{\infty}\delta_{n}<\frac{1}{100}.$

Notice that for any valid choice of $t_{n}$, the widths $w_{n}$ will always
satisfy the inequality

(5.3) $w_{n+1}\leq\frac{w_{n}}{t_{n}}.$

Given these above quantities, we will always choose $t_{n}$ large enough so
that it satisfies

(5.4) $\frac{t_{n}}{v_{n}}\cdot\frac{(\delta_{n}d_{n})^{2}}{2w_{n}}\geq 1$

By (5.1) and (5.4) we know that

(5.5) $\sum_{n=1}^{\infty}\frac{1}{t_{n}}<\frac{1}{100}.$

From this it easily follows that

(5.6) $\sum_{n=1}^{\infty}w_{n}<\infty.$

In this section, we will prove the following:

######  Theorem 5.1.

With all the parameters defined as above,

$\Gamma=\bigcap_{n=0}^{\infty}\Gamma_{n}$

is a Jordan curve.

To prove this, the first step is to construct appropriate parameterizations of
$\gamma^{n+1}_{1/2}$ given some parameterization of the core curves
$\gamma^{n}_{1/2}$ of $\Gamma_{n}$. Since we will always work with the core
curves in this section, we will call $\gamma^{n}_{1/2}:=\gamma^{n}$.

Recall that each straight piece $P$ of $\Gamma_{n}$ is decomposed into
subdivided rectangles with base approximately $\delta_{n}d_{n}$ and height
$w_{n}$. We do not decompose the corner pieces and leave them as is. For some
small choice of $\delta$, $\gamma^{n}(0,\delta)$ is contained in one of these
subdivided rectangles or corners, so we denote it as $R_{0}$. We label the
rest of the subdivided rectangles and corner pieces in the order that
$\gamma^{n}$ passes through them. This gives a list of subdivided rectangles
and corners $\\{R_{i}\\}_{i=0}^{m-1}$. We will consider this list modulo $m$,
so that $R_{0}=R_{m}$. Let and $t_{i}\in[0,1]$ for $i=1,\dots m$ be the first
entry time of $\gamma^{n}$ in $R_{i}$. $t_{m}$ will be the exit time for
$R_{m-1}$, which coincides with entering back inside $R_{0}$.
$\gamma^{n}:(t_{m},1]\cup[0,t_{1})$ goes from the end of $R_{m-1}$ to the end
of $R_{0}$.

We’ll show how to parameterize $\gamma^{n+1}$ inside of the intervals
$(t_{i},t_{i+1})$. Here we take the convention that
$(t_{m},t_{m+1})=(t_{m},1]\cup[0,t_{1})$. To do this, we will show where to
place the points $\gamma^{n+1}(t_{i})$ and $\gamma^{n+1}(t_{i+1})$. Then for
the subarc of $\gamma^{n+1}$ in between these points, we will use a constant
speed parameterization. We will handle this with three cases.

For the first case, suppose that $R_{i}$ is a subdivided rectangle of a
straight piece so that $R_{i+1}$ is not a corner piece. Orient $R_{i}$ so that
the top boundary side is a subset of the innermost boundary component of
$\Gamma_{n}$. If $R_{i}$ was labeled as B, then $\gamma^{n+1}(t_{i})$ will be
the point on the intersection of $\gamma^{n+1}$ and the left side of $R_{i}$
between $\gamma^{n}_{\frac{t_{n}-1}{t_{n}}}$ and $\gamma^{n}_{1}$. We let
$\gamma^{n+1}_{1/2}(t_{i+1})$ be the point on the intersection of
$\gamma^{n+1}$ and the right side of $R_{i}$ between
$\gamma^{n}_{\frac{1}{t_{n}}}$ and $\gamma^{n}_{0}$. If $R_{i}$ was labeled as
T, we do the opposite. $\gamma^{n+1}(t_{i})$ will be the point on the
intersection of $\gamma^{n+1}$ and the left side of $R_{i}$ between and
$\gamma^{n}_{\frac{1}{t_{n}}}$ and $\gamma^{n}_{0}$, and
$\gamma^{n+1}(t_{i+1})$ will be be the point on the intersection of
$\gamma^{n+1}$ and the left side of $R_{i}$ between
$\gamma^{n}_{\frac{t_{n}-1}{t_{n}}}$ and $\gamma^{n}_{1}$. See Figure 12.

Suppose that $R_{i}$ is a subdivided rectangle so that $R_{i+1}$ is a corner
boundary piece. Then we label $\gamma^{n+1}(t_{i})$ using the procedure above.
We let $\gamma^{n+1}(t_{i+1})$ be the point in the same straight piece as
$\gamma^{n+1}(t_{i})$ that lies on the right side of $R_{i}$. See Figure 13.

Finally, suppose that $R_{i}$ is a corner piece. Then $R_{i-1}$ and $R_{i+1}$
fall into the above cases, which means that $\gamma^{n+1}(t_{i})$ and
$\gamma^{n+1}(t_{i+1})$ have already been defined. The former corresponds to
the first time that $\gamma^{n+1}$ enters the corner piece, and the latter
corresponds to the last time $\gamma^{n+1}$ exits the corner piece. We again
use the constant speed parameterization to parameterize the subarc between
these two points. See Figure 13.

Figure 12. Parameterizing in straight pieces. Denote the subdivided rectangles
by $R_{i-1},R_{i},R_{i+1}$. The bold curve is $\gamma^{n}$, and
$\gamma^{n}(t_{j})$ is marked for $j=i-1,i,i+1,i+2$. Since $R_{i-1}$ is a T
subdivided rectangle, $\gamma^{n+1}(t_{i-1})$ is the point on $\gamma^{n+1}$
with farthest distance below $\gamma^{n}(t_{i-1})$. Since $R_{i}$ is a B
subdivided rectangle, $\gamma^{n+1}(t_{i})$ is the point on $\gamma^{n+1}$
with farthest distance above $\gamma^{n}(t_{i})$. We parameterize the portion
of the curve between those points with a constant speed parameterization.

Figure 13. Parameterizing near a corner piece. Let $R_{i-1}$ be the subdivided
rectangle to the left of the corner piece, $R_{i}$.
$\gamma^{n+1}:(t_{i-1},t_{i})$ is simply the portion of
$\gamma^{n}(t_{i-1},t_{i})$ translated up to be between the final two elements
of the plumbing foliation. $\gamma^{n+1}(t_{i},t_{i+1})$ is the constant speed
parameterization between the already placed $\gamma^{n+1}(t_{i})$ and
$\gamma^{n+1}(t_{i+1})$.

######  Lemma 5.2.

The sequence of functions $\\{\gamma^{n}\\}_{n=1}^{\infty}$ is uniformly
Cauchy. In fact, for sufficiently large $n$, we have the estimate for all
$t\in[0,1]$

$|\gamma^{n+1}(t)-\gamma^{n}(t)|\leq 5w_{n}.$

###### Proof.

If $\gamma^{n}(t)\in R_{i}$, and $t\in[t_{i},t_{i+1}]$, observe that the curve
$\gamma^{n+1}_{1/2}:[t_{i},t_{i+1}]$ can only intersect the rectangles
$R_{i-1},R_{i}$ and $R_{i+1}$. Since
$\operatorname{diam}(R_{i})\leq\sqrt{2}w_{n}$ for all corner pieces and
subdivided rectangles, this means that
$\operatorname{diam}(\gamma^{n+1}_{1/2}(t_{i},t_{i+1}))\leq 3\sqrt{2}w_{n}\leq
5w_{n}$. Since $\gamma^{n}(t)\in R_{i}$, it follows that

$|\gamma^{n+1}(t)-\gamma^{n}(t)|\leq 5w_{n}.$

By $(\ref{wnconverges})$, this is a summable estimate independent of
$t\in[0,1]$, so it follows that $\gamma^{n}$ is uniformly Cauchy. ∎

It follows that $\gamma^{n}$ converges uniformly to $\gamma$ for some
continuous function $\gamma:[0,1]\rightarrow\mathbb{C}$. Since $\gamma$ is
continuous and the widths of $\Gamma_{n}$ are strictly decreasing, we must
have $\gamma([0,1])=\Gamma$. So to show $\Gamma$ is a Jordan curve it is
sufficient to show that $\gamma$ is injective.

######  Lemma 5.3.

For all sufficiently large $n$, if $\gamma^{n}(t)\in R_{i}$ for some $i$, then
$\gamma(t)\in R_{i-2},\dots,R_{i+2}$.

###### Proof.

We know that $\gamma^{n+1}(t)\in R_{i-1},R_{i}$, or, $R_{i+1}$. Then we can
estimate using $(\ref{wntn})$ that

$\displaystyle|\gamma(t)-\gamma^{n+1}(t)|$ $\displaystyle\leq$
$\displaystyle\sum_{j=n+1}^{\infty}|\gamma^{j}(t)-\gamma^{j+1}(t)|$
$\displaystyle\leq$ $\displaystyle\sum_{j=n+1}^{\infty}5w_{j}$
$\displaystyle\leq$ $\displaystyle
5w_{n+1}\left(1+\sum_{j=n+1}^{\infty}\frac{1}{\prod_{k=n+1}^{j}t_{k}}\right)$
$\displaystyle\leq$ $\displaystyle 6w_{n+1}$

Next observe that by $(\ref{wntn})$ and $(\ref{biggerthanone})$,

$w_{n+1}\leq\frac{w_{n}}{t_{n}}\leq\frac{(\delta_{n}d_{n})^{2}}{2v_{n}}\leq\frac{1}{100}\delta_{n}d_{n}.$

From this and the construction of $\Gamma$ we deduce that $\gamma(t)\in
R_{i-2},\dots,R_{i+2}$. ∎

######  Lemma 5.4.

There exists $n$ large enough so that if $s\neq t$, $\gamma^{n}_{1/2}(s)$ and
$\gamma^{n}_{1/2}(t)$ are separated by at least $1$ straight piece.

###### Proof.

Suppose that $\gamma^{n}(s)$ and $\gamma^{n}(t)$ belong to the same straight
piece of $\Gamma_{n}$. What happens if $\gamma^{n+1}(s)$ and $\gamma^{n+1}(t)$
belong to the same straight piece of $\Gamma_{n+1}$? Then we must have

(5.7) $|\gamma^{n}(s)-\gamma^{n}(t)|\leq|\gamma^{n+1}(s)-\gamma^{n+1}(t)|$

This is because of how we parameterize $\gamma^{n+1}$ with respect to
$\gamma^{n}$. Indeed, the procedure we used to parameterize the $\gamma^{n}$’s
implies that the length of $\gamma^{n+1}$ restricted to $[t_{i},t_{i+1}]$ is
always bounded below by the length of $\gamma^{n}$ restricted to
$[t_{i},t_{i+1}]$. Since we use the constant speed parameterization to define
$\gamma^{n+1}$ on $[t_{i},t_{i+1}]$, we must have inequality $(\ref{longer})$.

Note that in $\Gamma_{m+1}$ for any $m$, the longest a straight piece can be
is bounded above by $10w_{m}$. This follows from the construction and Lemma
5.3. Combined with $(\ref{longer})$, it follows that $\gamma^{m}(s)$ and
$\gamma^{m}(t)$ cannot belong to the same straight piece for all $m\geq n$. ∎

######  Lemma 5.5.

The limit function $\gamma$ above is injective.

###### Proof.

Choose some $s<t$. By Lemma 5.4, there exists a value $n$ so that
$\gamma^{n}(s)$ and $\gamma^{n}(t)$ are separated by at least $1$ straight
piece. Since $\delta_{n}<\frac{1}{100}$, there are at least $50$ subdivided
rectangles between $\gamma^{n}(s)$ and $\gamma^{n}(t)$. Therefore, Lemma 5.3
says that $\gamma(s)\neq\gamma(t)$. ∎

######  Corollary 5.6.

$\Gamma$ is a Jordan curve.

##  6\. The Jordan curve is non-pierce-able by rectifiable arcs

By Lemma 2.3, to show that $\Gamma$ is non-pierceable by rectifiable arcs, we
only must prove that $\Gamma$ is not pierceable by unit length simple
rectifiable curves which cross $\Gamma$.

######  Lemma 6.1.

Suppose that $\sigma$ is a rectifiable arc which crosses $\Gamma$. Then there
exists $n$ so that the endpoints of $\sigma$ are in distinct complementary
components of $\Gamma_{n}$.

###### Proof.

This follows from the fact that $(\ref{dn})$ tends to $0$ as
$n\rightarrow\infty$. ∎

We will always parameterize $\sigma$ crossing $\Gamma$ so that $\sigma(0)$ is
in the bounded complementary component of $\Gamma$. The following lemma is
easy to visualize, but its proof is cumbersome. The idea is that if $\sigma$
has endpoints in distinct complementary components of $\Gamma_{n}$, to cross
$\Gamma$ at exactly one point, $\sigma$ is forced to remain in the part of
$\Gamma_{n}$ we removed to construct $\Gamma_{n+1}$, otherwise it will cross
more than once. Therefore, such a $\sigma$ must remain inside of one
subdivided rectangle of $\Gamma_{n}$, so that it must completely cross a
$v_{n}$-slab. See Figure 12 and Figure 14.

######  Lemma 6.2.

If $\sigma$ is a rectifiable arc which crosses $\Gamma$ and
$\mathcal{P}(\sigma)$ has only one point, then $\sigma$ must enter every rook
contained in some $v_{n}$-slab of some subdivided rectangle of a straight
piece of $\Gamma_{n}$. Moreover, such a $v_{n}$-slab may be chosen so that it
does not intersect the boundary of $\Gamma_{n}$.

###### Proof.

By equation $(\ref{vn})$, combined with equation $(\ref{biggerthanone})$, we
see that the number of $v_{n}$-slabs contained in a subdivided rectangle in
$\Gamma_{n}$ tends to $\infty$ as $n\rightarrow\infty$. Therefore, we may
always assume that every subdivided rectangle in $\Gamma_{n}$ has at least one
$v_{n}$-slab in each complementary component of the core curve of $\Gamma_{n}$
that does not intersect the boundary of $\Gamma_{n}$.

Suppose that the lemma is false: there is no subdivided rectangle so that
$\sigma$ passes through every single rook of some $v_{n}$-slab contained in
that subdivided rectangle. Then there exists a subdivided rectangle $R$ and a
$v_{n}$-slab $S$ contained in $R$ so that $\sigma$ passes through at least
one, but not all, of the rooks in $S$. We may assume that $S$ is in the
bounded complementary component of the core curve of $\Gamma_{n}$. Indeed, if
no such $v_{n}$-slab existed, then either $\mathcal{P}(\sigma)$ has more than
one element, or the conclusion of the lemma holds.

In this case, two of the opposite sides of a rook of $S$ that $\sigma$ does
not enter are determined by elements of the plumbing foliation
$\gamma^{n}_{j/t_{n}}$ and $\gamma^{n}_{(j+2)/t_{n}}$. Then by the
construction of $\Gamma_{n+1}$ from $\Gamma_{n}$, $\sigma$ must pierce
$\Gamma$ at least once between $\gamma^{n}_{j/t_{n}}$ and
$\gamma^{n}_{(j+2)/t_{n}}$. This must happen either in the subdivided
rectangle $R$, or one of the subdivided rectangles or corner pieces adjacent
to it.

For the exact same reasons as above, there must exist a subdivided rectangle
$R^{\prime}$ and a $v_{n}$-slab $S^{\prime}$ contained in $R^{\prime}$ so that
$\sigma$ passes through at least one, but not all of the rooks in the
$v_{n}$-slab, and this $v_{n}$-slab is in the unbounded complementary
component of the core curve of $\Gamma_{n}$. But then by the same reasoning
$\sigma$ must pierce $\Gamma$ again, contradicting the fact that
$\mathcal{P}(\sigma)$ has only one point. ∎

The statement and proof of Lemma 6.2 apply in exactly the same way if
$v_{n}$-slabs are replaced by $v_{n}$-squares, since equation $(\ref{deltan})$
implies that $\lambda_{n}$, the number of $v_{n}$-squares contained inside of
a subdivided rectangle, also tends to $\infty$ as $n\rightarrow\infty$. This
means we may assume there are many $v_{n}$-squares in the bounded and
unbounded complementary components of the core curve of $\Gamma_{n}$, and the
reasoning of the proof still applies.

In fact, since the number of $v_{n}$-slabs and $v_{n}$-squares tends to
$\infty$, for large enough $n$, the reasoning of Lemma 6.2 allows us to
conclude that there are at least three adjacent $v_{n}$-slabs or
$v_{n}$-squares so that $\sigma$ enters ever single rook of all three
$v_{n}$-slabs or $v_{n}$-squares. We will use this observation in the basic
estimates below.

######  Lemma 6.3.

Suppose that $\sigma$ crosses $\Gamma$ and $\mathcal{P}(\sigma)$ only contains
one point. Then there exists a $v_{n}$-slab $R$ in some $\Gamma_{n}$ so that

  1. (1)

$\sigma$ passes through every rook in the $v_{n}$-slab $R$

  2. (2)

$\sigma$ passes through every rook in the adjacent $v_{n}$-slabs above and
below $R$

Moreover, we have

$l(\sigma\cap R)>\delta_{n}d_{n}.$

###### Proof.

The proof is a picture; see Figure 14. The distance $\sigma$ must travel to go
between two rooks in consecutive rows in the rook placement is at least
$\delta_{n}d_{n}/v_{n}$ distance apart by Lemma 4.2. $\sigma$ must also cross
from the top of $R$ to the bottom of $R$, contributing a length of at least
$v_{n}\cdot\frac{2w_{n}}{t_{n}}$. So we calculate

$l(\sigma\cap R)\geq
v_{n}\cdot\frac{2w_{n}}{t_{n}}+v_{n}\cdot\frac{\delta_{n}d_{n}}{v_{n}}>\delta_{n}d_{n}.$

This proves the claim. ∎

Figure 14. Illustrating Lemma 6.3. We have a $v_{n}$-slab that is a subset of
$\Gamma_{n}$, along with the thin boundary rectangles that form part of the
boundary of $\Gamma_{n+1}$. If $\sigma$ crosses $\Gamma_{n}$ without crossing
$\Gamma$, it must enter all the rook squares (shaded in gray) of every
$v_{n}$-slab it passes through.

######  Corollary 6.4.

Suppose that $\sigma$ crosses $\Gamma$ and $\mathcal{P}(\sigma)$ only contains
one point. Then there exists a $v_{n}$-square $R$ in some $\Gamma_{n}$ so that

  1. (1)

$\sigma$ passes through every rook in the $v_{n}$-square $R$.

  2. (2)

$\sigma$ passes through and every rook of the $v_{n}$-square above and below
$R$.

Moreover, we have

$l(\sigma\cap R)>1.$

###### Proof.

To cross $R$ in such a way, one must pass through all the rooks in $k_{n}$
many $v_{n}$-slabs without piercing $\Gamma$. Therefore by repeated
applications of Lemma 6.3, and then using (5.4), we have

$l(\sigma\cap R)\geq
k_{n}\delta_{n}v_{n}=\frac{t_{n}}{v_{n}}\cdot\frac{(\delta_{n}d_{n})^{2}}{2w_{n}}>1.$

∎

######  Corollary 6.5.

$\Gamma$ is non-pierceable by rectifiable arcs.

###### Proof.

The follows from immediately from Lemma 2.3, since Lemma 6.4 shows that
$\Gamma$ is non-piercable by simple rectifiable arcs with length bounded by
$1$. ∎

##  7\. Any crossing rectifiable curve intersects on positive length

We would like to focus on a convenient subarc of $\sigma$, which exists by the
following lemma.

######  Lemma 7.1.

Suppose $\sigma$ is simple and rectifiable with length $\leq 1$ and crosses
$\Gamma$. Then there exists an integer $n\geq 0$ and a straight piece $P$ of
$\Gamma_{n}$ so that $\sigma$ enters the top of $P$ and exits out the bottom
of $P$.

###### Proof.

By Lemma 6.1, $\sigma$ must cross $\Gamma_{n}$ for some $n$. If $\sigma$ did
not enter the top and exit out of the bottom of the same straight piece $P$
for $\Gamma_{n+1}$, then similar reasoning to Lemma 6.2 and Lemma 6.3 would
imply that $\sigma$ must enter too many rook squares and must have length
greater than $1$. ∎

We will show that the subarc that begins at the top of a straight piece and
exits at the bottom of a straight piece intersects with positive length. We
first consider the special case that this subarc is a line segment.

######  Lemma 7.2.

If $\sigma$ is a axis aligned line segment that crosses $\Gamma$, then

$H^{1}(\sigma\cap\Gamma)>0.$

Recall that we always may orient our view so that that this axis aligned line
segment is vertical.

###### Proof.

Let $P$ denote the straight piece that $\sigma$ crosses contained in some
$\Gamma_{n}$. We define

$l_{m}:=l(\sigma\cap\Gamma_{m}).$

Then $l_{m}$ is a decreasing sequence and

$\lim_{m\rightarrow\infty}l_{m}=H^{1}(\sigma\cap\Gamma).$

We will estimate the length lost between each stage, $l_{m}-l_{m+1}$. By our
assumptions we have $l_{n}\geq w_{n}$.

$\sigma$ passes through $t_{n}$ many rows in $P$ determined by the plumbing
foliation for $\Gamma_{n}$. The length $l_{n+1}$ can decrease for two reasons.
First, if $\sigma$ passes through a rook square, then it may pass through the
thickened vertical segment placed in that square, which does not belong to
$\Gamma_{n+1}$. The number of rooks a single line segment can pass through is
no more than $k_{n}\lambda_{n}$ (recall that $k_{n}$ and $\lambda_{n}$ are 4.2
and 4.3, respectively). Second, $l_{n}$ can decrease by $\eta_{n}$ for every
element of the plumbing foliation that $\sigma$ passes through. This means
that the amount of length lost can be bounded above by

$l_{n}-l_{n+1}\leq
t_{n}\cdot\eta_{n}+k_{n}\cdot\lambda_{n}\frac{2w_{n}}{t_{n}}\leq\frac{w_{n}}{100^{n}\prod_{j=1}^{n-1}t_{j}}+\frac{w_{n}}{v_{n}}.$

Here we used $(\ref{etan})$, $(\ref{lambdan})$, and $(\ref{kn})$.

Estimating $l_{n+1}-l_{n+2}$ is similar; we just have to count how many
straight pieces $\sigma$ crosses in $\Gamma_{n+1}$. This number is no more
than $t_{n}$. Therefore, we can apply the same estimates above and see that

$\displaystyle l_{n+1}-l_{n+2}$ $\displaystyle\leq$ $\displaystyle
t_{n}\cdot(t_{n+1}\cdot\eta_{n+1})+t_{n}\left(\cdot
k_{n+1}\cdot\lambda_{n+1}\cdot\frac{2w_{n+1}}{t_{n+1}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{w_{n+1}}{100^{n+1}\prod_{j=1}^{n-1}t_{j}}+\frac{t_{n}w_{n+1}}{v_{n+1}}$
$\displaystyle\leq$
$\displaystyle\frac{w_{n}}{100^{n+1}}+\frac{w_{n}}{v_{n+1}}$

In general, we can use this argument to deduce that

(7.1) $l_{m}-l_{m+1}\leq w_{n}\left(\frac{1}{100^{m}}+\frac{1}{v_{m}}\right).$

Putting it all together,

$\displaystyle l_{n}-l(\sigma\cap\Gamma)$ $\displaystyle=$
$\displaystyle\lim_{m\rightarrow\infty}\sum_{j=n}^{m}l_{j}-l_{j+1}$
$\displaystyle\leq$ $\displaystyle
w_{n}\sum_{j=n}^{\infty}\left(\frac{1}{100^{j+1}}+\frac{1}{v_{j}}\right)$
$\displaystyle\leq$ $\displaystyle\frac{w_{n}}{10}.$

Therefore,

$l(\sigma\cap\Gamma)\geq l_{n}-w_{n}/10\geq\frac{9}{10}w_{n}.$

∎

With a little more care, we can upgrade these observations above to the proof
of Theorem 1.1.

######  Lemma 7.3.

Suppose $\sigma$ is a simple rectifiable arc with length $\leq 1$ and crosses
a straight piece $P$ of $\Gamma_{n}$. Then $\sigma$ cannot intersect more than
$k_{n}v_{n}+k_{n}\lambda_{n}$ many thickened vertical segments placed in rooks
in $\Gamma_{n}$.

###### Proof.

Since $\sigma$ must pass through at least $k_{n}\cdot\lambda_{n}$ many
$v_{n}$-slabs, $\sigma$ can intersect exactly one thickened vertical segment
in one rook of each of the $k_{n}\cdot\lambda_{n}$-slabs of $\Gamma_{n}$
without costing any length, just like a vertical segment. Any additional
thickened vertical segments that $\sigma$ can intersect come from $\sigma$
going to additional $v_{n}$-slabs or from $\sigma$ entering multiple thickened
vertical segments in other rooks in the same $v_{n}$-slab.

Suppose that $\sigma$ passes through thickened vertical segments in more than
$k_{n}\cdot\lambda_{n}$ many $v_{n}$ slabs. By Lemma 8, each additional slab
of this type that $\sigma$ passes through must take at least a length of

$\frac{\delta_{n}d_{n}}{2v_{n}}.$

Any additional thickened vertical segments passed through in any of the
$v_{n}$ slabs that $\sigma$ intersects also costs a length of
$\frac{\delta_{n}d_{n}}{2v_{n}}$, again by Lemma 8.

This means the amount of additional thickened vertical segments that $\sigma$
can intersect is no more than $2k_{n}v_{n}$, since $(\ref{biggerthanone})$
implies that

$k_{n}\delta_{n}d_{n}>1$

This is not possible if we assume that $\sigma$ has length $\leq 1$. ∎

If $\sigma$ intersects a thickened line segment in some rook, we will just
assume that $\sigma$ passed through the thickened line segment. This causes
$l_{n+1}$ to decrease, but fortunately this cannot happen often. Indeed, note
that $2k_{n}v_{n}$, is a very small percentage of $t_{n}$, since by
$(\ref{kn})$,

$\frac{2k_{n}v_{n}}{t_{n}}=\frac{\delta_{n}d_{n}}{w_{n}}.$

This quantity tends to $0$ very rapidly by $(\ref{deltan})$.

This observation allows us to prove Theorem 1.1.

###### Proof of the Main Theorem.

Again, let $P$ be the straight piece of $\Gamma_{n}$ that $\sigma$ crosses.
Again we denote $l_{n}=l(\sigma\cap\Gamma_{n})$.

$\sigma$ must travel between each adjacent element of the plumbing foliation
for $\Gamma_{n}$. Therefore, to estimate $l_{m}-l_{m+1}$, we can use all of
the same estimates from Lemma 7.2; we just have to additionally discard the
length of the excess vertical segments that $\sigma$ can visit. But by Lemma
7.3, this number is $2k_{n}v_{n}$, so the amount of excess length discarded is
no more than

$k_{n}v_{n}\cdot\frac{2w_{n}}{t_{n}}=2\delta_{n}d_{n}.$

At the next stage, $\Gamma_{n+1}$, the amount of excess length discarded is no
more than

$t_{n}k_{n+1}v_{n+1}\cdot\frac{2w_{n+1}}{t_{n+1}}\leq
t_{n}\delta_{n+1}d_{n+1}\leq\frac{w_{n}}{w_{n+1}}\delta_{n+1}d_{n+1}\leq
w_{n}\delta_{n+1}.$

We used $(\ref{wntn})$ in the second inequality. Similarly, at the $m$th
stage, the amount of excess length discarded compared to a vertical line
segment is no more than

$w_{n}\delta_{m}.$

So the amount of excess length discarded compared to a vertical segment is no
more than

$w_{n}\sum_{j=n}^{\infty}\delta_{j}<\frac{w_{n}}{100}.$

This combined with the estimates in Lemma 7.2 show that

$l(\sigma\cap\Gamma)>w_{n}\left(\frac{9}{10}-\frac{1}{100}\right)>0$

∎

## References

  * [Beu40] Arne Beurling.  Ensembles exceptionnels.  Acta Math., 72:1–13, 1940.
  * [Bis] Christopher J. Bishop.  A curve with no simple crossings by segments.  Preprint:.
  * [Bis94] Christopher J. Bishop.  Some homeomorphisms of the sphere conformal off a curve.  Ann. Acad. Sci. Fenn. Ser. A I Math., 19(2):323–338, 1994.
  * [Bis07] Christopher J. Bishop.  Conformal welding and Koebe’s theorem.  Ann. of Math. (2), 166(3):613–656, 2007.
  * [GM05] John B. Garnett and Donald E. Marshall.  Harmonic measure, volume 2 of New Mathematical Monographs.  Cambridge University Press, Cambridge, 2005.
  * [Pet] Anton Petrunin.  Answer to: https://mathoverflow.net/questions/100025/how-many-times-line-segments-can-intersect-a-jordan-curve/100035.
  * [PW12] Charles Pugh and Conan Wu.  Jordan curves and funnel sections.  J. Differential Equations, 253(1):225–243, 2012.
  * [Sau18] Manfred Sauter.  How twisted can a Jordan curve be?  In Ulmer Seminare 2016/2017, Funktionalanalysis und Differentialgleichungen, Abschlussband mit Dreizeilenbeweisen und offenen Problemen, volume 20 of Ulmer Seminare, pages 133–140. Institute of Applied Analysis, Ulm University, 2018.