# DAPlankton: Benchmark Dataset for Multi-instrument Plankton Recognition via
Fine-grained Domain Adaptation

###### Abstract

Plankton recognition provides novel possibilities to study various
environmental aspects and an interesting real-world context to develop domain
adaptation (DA) methods. Different imaging instruments cause domain shift
between datasets hampering the development of general plankton recognition
methods. A promising remedy for this is DA allowing to adapt a model trained
on one instrument to other instruments. In this paper, we present a new DA
dataset called DAPlankton which consists of phytoplankton images obtained with
different instruments. Phytoplankton provides a challenging DA problem due to
the fine-grained nature of the task and high class imbalance in real-world
datasets. DAPlankton consists of two subsets. DAPlanktonLAB contains images of
cultured phytoplankton providing a balanced dataset with minimal label
uncertainty. DAPlanktonSEA consists of images collected from the Baltic Sea
providing challenging real-world data with large intra-class variance and
class imbalance. We further present a benchmark comparison of three widely
used DA methods.

Index Terms—  Plankton recognition, domain adaptation, fine-grained
recognition, benchmark dataset

##  1 INTRODUCTION

In various practical applications of image recognition (e.g., environmental,
industrial, and medical imaging) the data consist of a large pool of
relatively small in-house datasets. There are large domain shifts between
these datasets caused by, for example, different imaging setups and
environments. Despite being able to provide human-level accuracy in restricted
image classification tasks, the learned image representations (e.g., CNNs) are
known to be weak at generalizing beyond the domain they were trained on [1]. A
remedy for this is the unsupervised domain adaptation that allows applying a
method trained on one dataset efficiently to new datasets from a different
domain without having labeled training data in the new domain.

Fig. 1: Phytoplankton images from DAPlanktonLAB. Each column contains a
different imaging instrument (domain) and each row a different phytoplankton
species.

Automatic plankton recognition has the potential to revolutionize plankton
research providing new possibilities to study plankton populations and various
environmental aspects such as marine food webs and CO2 exchange between the
sea and atmosphere. At the same time, plankton recognition provides a good
context for developing domain adaptation methods for image recognition.
Different imaging instruments and local differences in plankton species
composition have caused a large pool of varying plankton image datasets. High-
quality labeled data relies mostly on trained taxonomists, which heavily
limits the amount of training data in datasets lowering the recognition
accuracy of the models. More importantly, new datasets are constantly being
collected and it is not feasible to label training data and to train a model
from scratch for each of them separately. Methods are needed to adapt plankton
recognition for new datasets with minimal supervision.

In this paper, we introduce a new dataset called DAPlankton for developing and
benchmarking domain adaptation methods for image recognition. The data
consists of phytoplankton images captured using different imaging instruments
resulting in domain shift. This provides a challenging and applicationally
relevant dataset that is naturally multi-domain unlike some existing domain
adaptation benchmarks that rely on more artificial settings. Moreover,
phytoplankton image data introduces additional challenges including the fine-
grained nature of the recognition problem and highly unbalanced class
distribution.

The data is divided into two subsets: DAPlanktonLAB and DAPlanktonSEA.
DAPlanktonLAB consists of images captured from multiple mono-specific
phytoplankton cultures, which were analysed using three different imaging
instruments: Imaging FlowCytobot (IFCB) [2], CytoSense (CS) [3], and FlowCam
(FC) [4] each producing cropped images with one plankton particle in each (see
Fig. 1). An expert further verified the class of each image, ensuring that
there was no cross-contamination between different cultures. This process
resulted in a balanced dataset with negligible label uncertainty.
DAPlanktonSEA consists of images captured from water samples collected from
the Baltic Sea using two different imaging instruments: IFCB and CS. Each
image was manually labeled by an expert. DAPlanktonSEA provides a realistic
and more challenging dataset with a large class imbalance and natural intra-
class variance. The DAPlankton dataset has been made publicly available for
research
purposes.111https://doi.org/10.23729/32583bd0-38cd-4532-a8d6-fc9dc5967dce

We provide an evaluation protocol, as well as a preliminary benchmark study on
three widely used domain adaptation methods. We focus on unsupervised closed-
set domain adaptation, that is, each domain (imaging instrument) contains the
same set of classes, and no labels from the target domain are provided for the
adaptation method. The results show that commonly used domain adaptation
methods are not able to tackle the fine-grained nature of the plankton
recognition task. This calls for novel methods that can simultaneously address
the domain shift between different imaging instruments, large intra-class
variation, and small inter-class variation.

##  2 RELATED WORK

###  2.1 Domain adaptation

Domain adaptation (DA) represents a particular case of transfer learning in
which a distribution shift in data between the source and target domains
occurs, but the initial task is shared. Due to the prevalence of domain shift
in various real-world recognition problems, a large number of DA methods have
been proposed. From the methodological perspective, DA approaches can be
categorized into five main categories: 1) instance re-weighting adaptation, 2)
feature adaptation, 3) classifier adaptation, 4) deep network adaptation, and
5) adversarial adaptation [5]. In instance re-weighting, weights of the source
data samples are weighted to better match the distribution of the target data
(e.g., [6]). In feature adaptation, the goal is to learn common feature
representations that have similar source and target distributions (e.g., [7]).
Classifier adaptation aims to learn a generalized classifier, for example,
using dynamic distribution adaptation [8]. Deep network adaptation includes
methods based on maximum mean discrepancy (e.g., [9]) and autoencoders (e.g.,
[10]) aiming to learn a domain-independent encoder in an unsupervised manner.
Finally, methods based on adversarial adaptation follow a similar principle to
generative adversarial networks (GANs). In a typical method, a domain
discriminator is a model that is trained to distinguish between the source and
target domains, and the classification model learns transferable feature
representations that the domain discriminator cannot distinguish (e.g., [11]).
An alternative approach is to use GAN-based style transfer models to perform
the adaptation at the pixel level (see e.g., [12]).

###  2.2 Fine-grained domain adaptation

The fine-grained recognition task further complicates the domain adaptation. A
handful of methods have been proposed to simultaneously address the large
inter-domain variations and small inter-class variations. Most of these
utilize manual annotation of attributes or part landmarks that makes the
method very application-specific and unable to generalize to new recognition
problems (see e.g. [13]). More general methods include domain-specific
transfer learning [14] and progressive adversarial networks [15].

###  2.3 Plankton recognition

The research on automatic plankton image recognition has matured from early
works based on hand-engineered image features [16] to feature learning-based
approaches utilizing deep learning and especially CNNs [17, 18, 19, 20, 21]
and vision transformers [22]. Various custom methods and modifications to
general-purpose techniques have been proposed to address the special
characteristics of plankton image data. For an extensive survey on automatic
plankton recognition, see [23].

Different imaging instruments cause a domain shift between plankton datasets.
This is why most automatic plankton recognition solutions focus on just one
imaging instrument. While domain adaptation has not been widely studied on
plankton recognition, there have been works where multiple plankton image
datasets have been utilized to solve the recognition task. For example,
transfer learning and fine-tuning have been utilized as approaches against the
differences in datasets [17, 24].

Plonus et al. [25] suggest using capsule neural networks combined with
probability filters to address the dataset shift caused by different plankton
imaging instruments. The idea of capsule neural networks is to form groups of
neurons (capsules) that learn the specific properties of the object in the
image. Capsule neural networks can be assumed to be less sensitive to the
changes in the field conditions and therefore able to adapt to different data
distributions.

###  2.4 Existing benchmark datasets

Multiple datasets for domain adaptation exist. These include Office-Home [26],
Office-31 [27], VisDA2017 [28], and DomainNet [29]. One notable drawback of
many existing datasets is that they are based on rather artificial settings
with domains such as drawings and synthetic images in addition to camera
images. Only few datasets for fine-grained domain adaptation exist: CompCars
[30] (78k images from two domains) and CUB-Paintings [15] (15k images from two
domains). In this paper, a fine-grained image recognition dataset that is
naturally multi-domain and provides an environmentally relevant application is
provided to test domain adaptation methods.

##  3 DATA

The data consists of two subsets: DAPlanktonLAB and DAPlanktonSEA.
DAPlanktonLAB consists of mono-specific phytoplankton cultures and
DAPlanktonSEA consists of natural water samples obtained from the Baltic Sea.

###  3.1 Data collection and manual labeling

####  3.1.1 DAPlanktonLAB

Mono-specific phytoplankton cultures, with organisms isolated from the Baltic
Sea (FINMARI Culture Collection/Syke Marine Research Laboratory and Tvärminne
Zoological Station) and Danish coastal waters, were selected to represent
different morphologies and taxonomical groups. Cultures are kept under stable
conditions, optimized for the organisms growth. Aphanizomenon flosaquae
(Cyanophyta), Chrysotila roscoffensis (Haptophyta), Kryptoperidinium
folliaceum (Dinophyta), Levanderina fissa (Dinophyta) and Pseudopedinella sp.
(Ochrophyta) are kept in 6‰ salinity and 16 °C. Apocalathium malmogiense
(Dinophyta), Diatoma tenuis (Bacillariophyta), Gymnodinium corollarium
(Dinophyta), Melosira arctica (Bacillariophyta), Peridiniella catenata
(Dinophyta) and Rhinomonas nottbeckii (Cryptophyta) are kept in 6 ‰ salinity
and 4 °C. Nephroselmis pyriformis (Chlorophyta), Rhodomonas salina
(Cryptophyta), Teleaulax acuta (Cryptophyta) and Tetraselmis sp. (Chlorophyta)
are kept in 12 ‰ salinity and 10 °C. All cultures are maintained at a 14:10
light:dark cycle using $f/2$ medium [31], prepared with filtered and
autoclaved Baltic Sea water (for cultures grown in 6 ‰ salinity) or Baltic Sea
water with adjusted salinity using artificial sea water (for cultures grown in
12 ‰ salinity). Each culture was analysed individually with CytoSense, FlowCam
and IFCB. CytoSense was equipped with two lasers (488 and 594 $nm$), sensors
for light scatter and fluorescence and a high resolution camera (3.6
pixels/$\mu m$). Samples were run using a chlorophyll a fluorescence trigger
and a pump speed of 1 $\mu l/s$. FlowCam analyses were conducted using a
colored camera, flowcell FC100 and a 10$\times$ objective, with images
collected in auto-trigger mode. IFCB samples were run using a chlorophyll a
fluorescence trigger. All images were manually checked to exclude poor-quality
images and potential cross-contamination between cultures and assigned to the
taxonomical classes based on the strain name (Table 1).

####  3.1.2 DAPlanktonSEA

CytoSense images from natural samples from the Baltic Sea were collected
during summer 2020 (July and August) at Utö Atmospheric and Marine Research
Station ($59^{\circ}$$46.84^{\prime}$ N $21^{\circ}$$22.13^{\prime}$ E) – see
[32] for further details. The instrument used had the same laser and sensors
as described above. To optimize different phytoplankton size classes, two runs
were set with different chlorophyll a fluorescence levels (30 and 80 $mV$) and
sampling pump speeds (2 and 5 $\mu l/s$), targeting smaller and larger
organisms, respectively. The IFCB data collection is described in [32] and
[20]. In short, the instrument was used in continuous mode with a new sample
starting every approx. 23 minutes. A chlorophyll a trigger was used and there
was a 150 µm mesh at the instrument inlet to prevent it from clogging. Both
IFCB and CS images were manually sorted by experts, and good-quality images
were assigned to different classes. CS classes followed the ones used in SYKE-
plankton_IFCB_2022
222http://doi.org/10.23728/b2share.abf913e5a6ad47e6baa273ae0ed6617a.

###  3.2 Data composition

####  3.2.1 DAPlanktonLAB

DAPlanktonLAB contains, in total, 47 471 images from 15 phytoplankton species
and 3 different domains (imaging instruments). The number of images per class-
domain combination varies between 286 and 2618 providing a reasonably balanced
dataset. Table 1 shows the classes and the numbers of images for each imaging
instrument. Example images from DAPlanktonLAB are shown in Fig. 2.

CS FC IFCB

Fig. 2: Example images from DAPlanktonLAB. Domains from left to right: CytoSense (CS), FlowCam (FC), and Imaging FlowCytobot (IFCB). Table 1: Composition of DAPlanktonLAB. Class | CS | FC | IFCB
---|---|---|---
Aphanizomenon flosaquae | 926 | 1138 | 1088
Apocalathium malmogiense | 936 | 1647 | 1003
Chrysotila roscoffensis | 701 | 453 | 1064
Diatoma tenuis | 862 | 939 | 1376
Gymnodinium corollarium | 818 | 2618 | 1072
Kryptoperidium foliaceum | 1285 | 1030 | 1075
Levanderina fissa | 870 | 867 | 1001
Melosira arctica | 608 | 826 | 1002
Nephroselmis pyriformis | 826 | 286 | 1326
Peridiniella catenata | 757 | 585 | 1250
Pseudopedinella sp. | 1088 | 1849 | 1018
Rhinomonas nottbecki | 1037 | 1394 | 1001
Rhodomonas salina | 877 | 2232 | 1149
Teleaulax acuta | 762 | 486 | 1011
Tetraselmis sp. | 834 | 1458 | 1040
Total | 13187 | 17808 | 16476

####  3.2.2 DAPlanktonSEA

DAPlanktonSEA contains, in total, 64 453 images from 31 plankton classes and 2
different domains. Table 2 shows the classes and the numbers of images for
each imaging instrument. As can be seen, the class distribution is
considerably less balanced (the number of images per class-domain combination
varies between 5 and 12 280) as the class sizes correspond to the true rarity
of the plankton class. Moreover, the intra-class variance is larger as can be
seen in Fig. 3.

Table 2: Composition of DAPlanktonSEA. Class | CS | IFCB
---|---|---
Aphanizomenon flosaquae | 2027 | 6989
Centrales sp. | 33 | 480
Chaetoceros sp. | 43 | 1382
Chaetoceros sp. single | 5 | 213
Chlorococcales | 17 | 95
Chroococcales | 938 | 142
Ciliata | 174 | 243
Cryptomonadales | 177 | 713
Cryptophyceae Teleaulax | 5443 | 6830
Cyclotella choctawhatcheeana | 33 | 102
Dinophyceae | 275 | 1433
Dinophysis acuminata | 7 | 217
Dolichospermum Anabaenopsis | 109 | 12280
Dolichospermum Anabaenopsis coiled | 165 | 2504
Euglenophyceae | 67 | 102
Eutreptiella sp. | 1027 | 2247
Gymnodiniales | 7 | 69
Gymnodinium like | 44 | 158
Heterocapsa rotundata | 330 | 614
Heterocapsa triquetra | 96 | 3276
Heterocyte | 240 | 263
Katablepharis remigera | 14 | 54
Mesodinium rubrum | 27 | 1132
Monoraphidium contortum | 352 | 327
Nitzschia paleacea | 11 | 65
Nodularia spumigena | 66 | 169
Oocystis sp. | 100 | 842
Pseudopedinella sp. | 57 | 379
Pyramimonas sp. | 851 | 1224
Skeletonema marinoi | 35 | 4128
Snowella Woronichinia | 61 | 2950
Total | 12831 | 51622

CS

IFCB

(a)

(b)

(c)

Fig. 3: Example images from the DAPlanktonSEA dataset. Notice the large intra-
class variation: (a) Chaetoceros sp.; (b) Chlorococcales; (c) Nodularia
spumigena.

##  4 BASELINE METHODS

Three commonly used domain adaptation methods are included as baseline
methods: Deep Correlation Alignment (Deep CORAL) [7], Conditional Adversarial
Domain Adaptation (CDAN) [11], and Manifold Embedded Distribution Alignment
(Deep MEDA) [8]. These were selected to have representative examples from the
three main approaches for domain adaptation: feature adaptation (Deep CORAL),
adversarial learning (CDAN), and classifier adaptation (MEDA).

###  4.1 Deep CORAL

The main idea behind Deep CORAL [7] is to learn domain invariant image
features. This is achieved by using CORAL loss that minimizes the difference
in second-order statistic (convariances) between source and target feature
distributions, and this way, reduces the domain gap.

###  4.2 CDAN

CDAN [11] is an example of adversarial learning-based domain adaptation, where
a domain discriminator is trained to distinguish between the source and target
domains, and the classification model learns transferable feature
representations that the domain discriminator cannot distinguish. CDAN further
conditions the domain discriminator on the cross-covariance of domain-specific
feature representations and classifier predictions.

###  4.3 Deep MEDA

MEDA [8] relies on geodesic flow kernel for bridging the domains in Grassmann
manifold, and maximum mean discrepancy to measure a divergence between domain
in the transformed feature subspaces. The feature representations embedded in
Grassmannians contribute to more accurate reflection of domain properties and
structure preventing feature distortion. The deep version of MEDA relies on
CNN features.

Table 3: Results on DAPlanktonLAB. Method | Backbone |  IFCB $\rightarrow$ CS |  IFCB $\rightarrow$ FC |  CS $\rightarrow$ IFCB |  CS $\rightarrow$ FC |  FC $\rightarrow$ IFCB |  FC $\rightarrow$ CS | Average
---|---|---|---|---|---|---|---|---
No adaptation | AlexNet |  64.5 $\pm$ 0.8 |  31.7 $\pm$ 0.9 |  51.6 $\pm$ 0.5 |  19.0 $\pm$ 1.4 |  38.5 $\pm$ 0.3 |  25.9 $\pm$ 1.4 |  38.5 $\pm$ 0.6
| ResNet |  40.1 $\pm$ 1.1 |  13.8 $\pm$ 1.0 |  48.5 $\pm$ 2.3 |  6.3 $\pm$ 1.7 |  39.3 $\pm$ 2.4 |  25.4 $\pm$ 2.0 |  28.9 $\pm$ 0.5
Deep CORAL | AlexNet |  69.8 $\pm$ 0.4 |  38.5 $\pm$ 2.2 |  69.7 $\pm$ 0.6 |  25.3 $\pm$ 2.1 |  49.9 $\pm$ 2.0 |  36.1 $\pm$ 0.5 |  48.2 $\pm$ 0.5
| ResNet |  63.1 $\pm$ 0.5 |  22.9 $\pm$ 1.5 |  69.1 $\pm$ 1.6 |  19.1 $\pm$ 1.8 |  38.9 $\pm$ 1.8 |  27.7 $\pm$ 4.0 |  40.1 $\pm$ 0.4
CDAN | AlexNet | 84.7 $\pm$ 1.6 |  29.6 $\pm$ 1.5 |  86.9 $\pm$ 0.9 |  17.9 $\pm$ 2.0 |  44.7 $\pm$ 3.7 |  33.6 $\pm$ 0.9 |  49.5 $\pm$ 1.1
| ResNet |  44.5 $\pm$ 0.7 |  20.4 $\pm$ 0.9 |  50.4 $\pm$ 0.6 |  16.9 $\pm$ 1.2 |  40.3 $\pm$ 0.9 |  17.5 $\pm$ 2.0 |  31.7 $\pm$ 0.5
Deep MEDA | AlexNet |  81.3 $\pm$ 0.8 |  54.8 $\pm$ 1.8 | 87.7 $\pm$ 1.2 | 47.4 $\pm$ 4.3 |  71.3 $\pm$ 2.1 |  45.5 $\pm$ 3.1 |  64.7 $\pm$ 1.2
| ResNet |  81.1 $\pm$ 1.3 | 55.5 $\pm$ 3.1 |  87.6 $\pm$ 0.9 |  43.1 $\pm$ 5.4 | 73.8 $\pm$ 5.7 | 60.9 $\pm$ 2.6 | 67.0 $\pm$ 1.6
Table 4: Results on DAPlanktonSEA. Method | Backbone | IFCB $\rightarrow$ CS | CS $\rightarrow$ IFCB | Average
---|---|---|---|---
No adaptation | AlexNet | 51.1 $\pm$ 2.4 | 61.7 $\pm$ 1.0 | 56.4 $\pm$ 1.6
| ResNet | 32.5 $\pm$ 3.3 | 50.3 $\pm$ 3.3 | 41.4 $\pm$ 1.4
Deep CORAL | AlexNet | 42.9 $\pm$ 1.2 | 53.8 $\pm$ 2.7 | 48.3 $\pm$ 1.1
| ResNet | 41.8 $\pm$ 1.6 | 46.8 $\pm$ 1.0 | 44.3 $\pm$ 0.7
CDAN | AlexNet | 76.3 $\pm$ 0.9 | 64.8 $\pm$ 1.4 | 70.6 $\pm$ 1.0
| ResNet | 25.9 $\pm$ 3.3 | 62.3 $\pm$ 2.4 | 44.1 $\pm$ 2.4
Deep MEDA | AlexNet | 51.9 $\pm$ 0.5 | 57.3 $\pm$ 0.9 | 54.6 $\pm$ 0.3
| ResNet | 53.4 $\pm$ 0.6 | 59.9 $\pm$ 0.3 | 56.6 $\pm$ 0.2

##  5 EVALUATION PROTOCOL

For evaluation, each subset-domain combination is divided into training, and
test set using the following split: 80% for training and 20% for testing. We
consider unsupervised domain adaptation, i.e. the domain adaptation model does
not have access to any labels from the target domain during the training
phase. For each experiment, the evaluated model is trained using all the data
in the source domain with ground truth labels and training subset of the
target domain without ground truth labels. The evaluation is carried out using
the test subset in the target domain.

The recognition results are evaluated using classification accuracy defined as
follows:

$\mathrm{accuracy}=\frac{|\\{\mathbf{x}|\mathbf{x}_{i}\in\mathcal{D}_{\mathrm{test}}\wedge
f(\mathbf{x}_{i})=y_{i}\\}|}{|\mathcal{D}_{\mathrm{test}}|},$ (1)

where $\mathbf{x}_{i}$ is the input instance (image),
$\mathcal{D}_{\mathrm{test}}$ is the test set of the target domain,
$f(\mathbf{x}_{i})$ is the model prediction and $y_{i}$ is the corresponding
ground truth label.

The accuracy is computed for all tasks, that is source domain and target
domain combinations denoted as Source $\rightarrow$ Target. DAPlanktonLAB has
3 domains resulting in $3\times 2=6$ tasks. DAPlanktonSEA has 2 tasks: IFCB
$\rightarrow$ CS and CS $\rightarrow$ IFCB. The evaluation is repeated for
each model and task 5 times with different training set/test set splits and
the average accuracies and standard deviations are calculated.

##  6 RESULTS AND DISCUSSION

The three selected domain adaptation methods were applied with two backbone
architectures: AlexNet and ResNet-18. These were selected since AlexNet and
ResNet are the backbones utilized in the original implementations of the
selected methods. Moreover, ResNet-18 has been shown to achieve a high
plankton recognition accuracy [20]. The need for domain adaptation was further
demonstrated by training the model on the source dataset and applied to target
dataset as-is (no adaptation). The results are shown in Tables 3 and 4.

While the domain adaptation methods outperform the recognition models applied
without adaptation, the accuracies are still rather low. This implies that
these commonly used unsupervised domain adaptation methods are not able to
tackle the fine-grained recognition task, i.e. the small inter-class variation
and large intra-class variation. Adaptation between IFCB and CS results in
higher accuracy than between FC and the other modalities. This is expected as
the domain gap between the IFCB and CS is considerably smaller (see Fig. 1).

CDAN produced the best results when adapting between IFCB and CS in both
DAPlanktonLAB and DAPlanktonSEA, however, the accuracy drops significantly
when the domain gap increases (see e.g. CS $\rightarrow$ FC). This is most
likely due to the domain discriminator module and the adversarial learning. A
known problem with adversarial-based alignment methods is that the global
alignment strategy does not take into account the class-level distributions
[33]. Because of this, the classes that are well aligned between the source
and target domain can be incorrectly mapped. This effect is emphasized when
the domain gap is large and the inter-class variation is small.

Overall, the best method for DAPlanktonLAB was Deep MEDA providing similar
accuracy to CDAN when the domain gap is small and outperforming the other
methods when the domain gap is large (adapting from and to FC). However, a
clear drop in accuracy compared to CDAN is observed when applying the methods
to DAPlanktonSEA. This is likely due to the larger intra-class variance and
its effect on the dynamic distribution alignment that Deep MEDA utilizes.

A surprising result is that the AlexNet backbone outperforms ResNet-18 for
most methods and tasks. It is possible that the deeper ResNet model learns
more domain-specific image features while the shallower AlexNet learns more
generalizable features. Also, it is good to note that Deep CORAL was
originally developed for AlexNet, and therefore, some design choices might be
more suited for that backbone architecture.

##  7 CONCLUSIONS

This paper describes a novel benchmark dataset for fine-grained domain
adaptation called DAPlankton. The dataset consists of over 110k expert-labeled
phytoplankton images captured with different imaging instruments representing
the domains. Plankton provides a naturally multi-domain and challenging
dataset that is characterized by the fine-grained nature of the recognition
problem. The dataset was designed to develop and evaluate unsupervised domain
adaptation methods, i.e. given a source dataset with expert labels and a
target dataset without labels, the task is to adapt the recognition model
trained on the source dataset to the target dataset. We further provided an
evaluation protocol and performed a preliminary benchmark study on three
commonly used domain adaptation methods. The results suggest that these
methods are not capable of tackling the domain shift between different imaging
instruments, large intra-class variation, and small inter-class variation.
This calls for novel methods for the fine-grained domain adaptation.

##  8 ACKNOWLEDGMENTS

The research was carried out in the FASTVISION and FASTVISION-plus projects
funded by the Academy of Finland (Decision numbers 321980, 321991, 339612, and
339355). Lumi Haraguchi was supported by OBAMA-NEXT (grant agreement no.
101081642), funded by the European Union under the Horizon Europe program.

## References

  * [1] I. Gulrajani and D. Lopez-Paz,  “In search of lost domain generalization,”  arXiv:2007.01434, 2020.
  * [2] R.J. Olson and H.M. Sosik,  “A submersible imaging-in-flow instrument to analyze nano-and microplankton: Imaging flowcytobot,”  Limnology and Oceanography: Methods, vol. 5, no. 6, pp. 195–203, 2007.
  * [3] G.B.J. Dubelaar, P.L. Gerritzen, A.E.R. Beeker, R.R. Jonker, and K. Tangen,  “Design and first results of CytoBuoy: A wireless flow cytometer for in situ analysis of marine and fresh waters,”  Cytometry, vol. 37, no. 4, pp. 247–254, 1999.
  * [4] C.K. Sieracki, M.E. Sieracki, and C.S. Yentsch,  “An imaging-in-flow system for automated analysis of marine microplankton,”  Marine Ecology Progress Series, vol. 168, pp. 285–296, 1998.
  * [5] L. Zhang and X. Gao,  “Transfer adaptation learning: A decade survey,”  IEEE Trans. on Neural Networks and Learning Systems, 2022.
  * [6] H. Yan, Y. Ding, P. Li, Q. Wang, Y. Xu, and W. Zuo,  “Mind the class weight bias: Weighted maximum mean discrepancy for unsupervised domain adaptation,”  in CVPR, 2017, pp. 2272–2281.
  * [7] B. Sun and K. Saenko,  “Deep CORAL: Correlation alignment for deep domain adaptation,”  in ECCV Workshops, 2016, pp. 443–450.
  * [8] J. Wang, Y. Chen, W. Feng, H. Yu, M. Huang, and Q. Yang,  “Transfer learning with dynamic distribution adaptation,”  ACM Trans. on Intelligent Systems and Technology, vol. 11, no. 1, pp. 1–25, 2020.
  * [9] M. Long, H. Zhu, J. Wang, and M.I. Jordan,  “Deep transfer learning with joint adaptation networks,”  in ICML, 2017, pp. 2208–2217.
  * [10] M. Ghifary, W.B. Kleijn, M. Zhang, D. Balduzzi, and W. Li,  “Deep reconstruction-classification networks for unsupervised domain adaptation,”  in ECCV, 2016, pp. 597–613.
  * [11] M. Long, Z. Cao, J. Wang, and M.I. Jordan,  “Conditional adversarial domain adaptation,”  NIPS, vol. 31, 2018.
  * [12] Z. Murez, S. Kolouri, D. Kriegman, R. Ramamoorthi, and K. Kim,  “Image to image translation for domain adaptation,”  in CVPR, 2018, pp. 4500–4509.
  * [13] T. Gebru, J. Hoffman, and L. Fei-Fei,  “Fine-grained recognition in the wild: A multi-task domain adaptation approach,”  in ICCV, 2017, pp. 1349–1358.
  * [14] Y. Cui, Y. Song, C. Sun, A. Howard, and S. Belongie,  “Large scale fine-grained categorization and domain-specific transfer learning,”  in CVPR, 2018, pp. 4109–4118.
  * [15] S. Wang, X. Chen, Y. Wang, M. Long, and J. Wang,  “Progressive adversarial networks for fine-grained domain adaptation,”  in CVPR, 2020, pp. 9213–9222.
  * [16] H.M. Sosik and R.J. Olson,  “Automated taxonomic classification of phytoplankton sampled with imaging-in-flow cytometry,”  Limnology and Oceanography: Methods, vol. 5, pp. 204–216, 2007.
  * [17] E.C. Orenstein and O. Beijbom,  “Transfer learning and deep feature extraction for planktonic image data sets,”  in WACV, 2017, pp. 1082–1088.
  * [18] A. Lumini and L. Nanni,  “Deep learning and transfer learning features for plankton classification,”  Ecological Informatics, vol. 51, pp. 33–43, 2019.
  * [19] J. Bureš, T. Eerola, L. Lensu, H. Kälviäinen, and P. Zemčík,  “Plankton recognition in images with varying size,”  in ICPR Workshops, 2021, pp. 110–120.
  * [20] K Kraft et al.,  “Towards operational phytoplankton recognition with automated high-throughput imaging, near-real-time data processing, and convolutional neural networks,”  Frontiers in Marine Science, vol. 9, 2022.
  * [21] O. Badreldeen, T. Eerola, K. Kraft, L. Lensu, and H. Kälviäinen,  “Open-set plankton recognition using similarity learning,”  in ISVC, 2022, pp. 174–183.
  * [22] A. Maracani, V.P. Pastore, L. Natale, L. Rosasco, and F. Odone,  “In-domain versus out-of-domain transfer learning in plankton image classification,”  Scientific Reports, vol. 13, no. 1, 2023.
  * [23] T. Eerola et al.,  “Survey of automatic plankton image recognition: Challenges, existing solutions and future perspectives,”  arXiv:2305.11739, 2023.
  * [24] J. Guo, W. Li, J. Guan, H. Gao, B. Liu, and L. Gong,  “CDFM: A cross-domain few-shot model for marine plankton classification,”  IET Computer Vision, 2022.
  * [25] R.-M. Plonus, J. Conradt, A. Harmer, S. Janßen, and J. Floeter,  “Automatic plankton image classification –Can capsules and filters help cope with data set shift?,”  Limnology and Oceanography: Methods, vol. 19, no. 3, pp. 176–195, 2021.
  * [26] H. Venkateswara, J. Eusebio, S. Chakraborty, and S. Panchanathan,  “Deep hashing network for unsupervised domain adaptation,”  in CVPR, 2017, pp. 5018–5027.
  * [27] K. Saenko, B. Kulis, M. Fritz, and T. Darrell,  “Adapting visual category models to new domains,”  in ECCV, 2010, pp. 213–226.
  * [28] X. Peng, B. Usman, N. Kaushik, J. Hoffman, D. Wang, and K. Saenko,  “VisDA: The visual domain adaptation challenge,”  arXiv:1710.06924, 2017.
  * [29] X. Peng, Q. Bai, X. Xia, Z. Huang, K. Saenko, and B. Wang,  “Moment matching for multi-source domain adaptation,”  in ICCV, 2019, pp. 1406–1415.
  * [30] L. Yang, P. Luo, C. Change Loy, and X. Tang,  “A large-scale car dataset for fine-grained categorization and verification,”  in CVPR, 2015, pp. 3973–3981.
  * [31] R.R.L. Guillard and J.H. Ryther,  “Studies of marine planktonic diatoms: I. cyclotella nana hustedt, and detonula confervacea (cleve) gran.,”  Canadian journal of microbiology, vol. 8, no. 2, pp. 229–239, 1962.
  * [32] K. Kraft et al.,  “First application of IFCB high-frequency imaging-in-flow cytometry to investigate bloom-forming filamentous cyanobacteria in the Baltic sea,”  Frontiers in Marine Science, vol. 8, pp. 282, 2021.
  * [33] Y. Luo, L. Zheng, T. Guan, J. Yu, and Y. Yang,  “Taking a closer look at domain shift: Category-level adversaries for semantics consistent domain adaptation,”  in CVPR, 2019, pp. 2507–2516.


#  X-haul Outage Compensation in 5G/6G Using Reconfigurable Intelligent
Surfaces

Mohamed Y. Selim1, Ahmed E. Kamal1, and Farid Nait-Abdesselam4 Emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>1Electrical and Computer
Engineering Department, Iowa State University, Iowa, USA.
4Electrical and Computer Engineering Department, University of Missouri Kansas
City, USA.

###### Abstract

5G network operators consider the dense deployment of small base-stations
(SBSs) to increase network coverage and capacity. Hence, operators face the
challenge of X-hauling, i.e., backhauling or fronthauling, their traffic to
the core network. Also, SBSs densification will increase the possibility of
failure of these X-haul links. To cope with this problem, an X-haul outage
compensation scheme with the assistance of Reconfigurable Intelligent Surfaces
(RIS) is proposed to mitigate or at least alleviate the effect of X-haul
failure. The RIS is a newly adopted technology that is able to improve the
performance of wireless networks. In this paper, we present and evaluate an
X-haul outage compensation scheme based on placing a number of RIS panels in
pre-planned locations to mitigate the effect of X-haul failure. This
evaluation is done using frequencies below and beyond 6 GHz. Based on our
analytical results, the proposed RIS scheme shows that placing a sufficient
number of RIS elements in proximity to the failed SBS under certain conditions
can help acquire the same X-haul rate before the occurrence of the failure.
Also, we show that for high X-haul spectral density, the RIS-assisted
transmission with a certain number of elements can be more energy-efficient
than line-of-sight and non-line-of-sight transmissions. Finally, the system’s
energy efficiency is addressed with and without RIS, and the optimal number of
RIS reflecting elements is derived.

###### Index Terms:

Reconfigurable Intelligent Surfaces, X-haul Outage Compensation, Self-healing
in 5G/6G Networks.

##  I Introduction

The 5G Radio Access Network is commercially deployed in many countries.
Service providers are faced with new technologies, access methods,
applications, and traffic compared to past generations. They will troubleshoot
both known and never-before-seen issues in previous cellular generations or
the rigorous R&D validation environment. 5G introduces millimeter-waves
(mmWaves), wider bandwidths, massive multi-antenna schemes, Small Base-
stations (SBSs), and network function virtualization and orchestration [1].

According to the small cell forum [2], deployments of 5G SBSs will rise
steeply to reach 5.2 million in 2025. Besides, the international organization
named GSMA, which represents the interests of more than 750 cellular operators
and manufacturers (www.gsma.com), states that 5G total connections will pass
the 1 billion mark by the end of 2024. As adoption grows, 5G revenues will
swell, reaching $1.15 trillion by 2025.

Therefore, SBSs densification in a given area is a promising technique that
provides a huge capacity gain and brings SBSs closer to Users Equipment (UEs).
This means that 5G/6G networks will have to handle more SBSs and X-haul, i.e.,
backhaul or fronthaul, links than before [3]. A survey [4] showed that 56% of
operators consider backhaul as one of the most significant challenges in 5G/6G
networks. This is mainly because most of the SBSs do not always have access to
wired backhaul.

Self-healing is the execution of actions that keep the network operational
and/or prevent disruptive problems from arising. Self-healing, or
specifically, cell outage compensation, executes actions to mitigate or, at
least, alleviate the effect of most failures. In the literature, a significant
amount of work [5]-[7] addressed the mitigation of the failure of the BS
itself. However, few works addressed the X-haul, i.e., backhaul/fronthaul,
outage compensation. The 5G-xHaul project [8] proposed the use of a redundant
mmWave X-haul link. This solution is excellent for low latency applications;
however, it will consume double the resources. The authors in [9] proposed to
use additional radio named self-healing radio to be used only in case of
backhaul failure. To the best of our knowledge, our work is the first to
address RIS usage to mitigate backhaul failure.

Recently, RIS has arisen as a promising technology that reconfigures the
propagation environment to improve wireless networks’ performance. RIS is a
planar surface that contains a large number of passive, low-cost reflecting
elements. Each element is able to induce a change in the amplitude and/or the
phase of the incident signal, which proactively changes the wireless channel
via its controllable reflecting surface. This provides a new degree of freedom
for the enhancement of the 5G performance and paves the way to a programmable
wireless environment. Since RIS eliminates the use of transmitting RF chains
and operates in short-range, it can be densely deployed with scalable cost and
low energy consumption, yet without the need for interference management among
RIS elements [10, 11].

The three surveys, [12, 13, 14], and the references therein, cover different
aspects of RIS technology, including channel modeling and estimation,
performance evaluation, optimization, resource allocation, and early trials of
the technology. It is worth noticing that DOCOMO NTT [15] conducted the
world’s first prototype trial of dynamic metasurfaces using 28 GHz radio
signals. This means that we expect to see an RIS panel as a commercial product
over the upcoming few months. Also, the authors in [16] evaluate the RIS
placement near the user and near the BS. They also proposed a new hybrid RIS
deployment strategy by combining the previous two strategies to deliver the
best signal-noise-ratio to the end-user. In [17], the authors considered
deploying RIS panels for wireless backhauling of multiple BSs connected in a
mesh topology. They showed that the RIS-mesh backhauling has several desired
features that can be exploited to overcome some of the backhauling challenges.

Based on the authors’ conclusion in [18] where they showed that with very high
rates and many RIS elements, RIS-assisted communications could beat decode-
and-forward relay communications, we propose to use RIS to help mitigate the
failure of the X-haul links in dense urban areas. Our proposed scheme aims to
provide the failed BS with an alternate X-haul connection from any neighboring
BS with the RIS aid. Our scheme will be analytically verified to highlight our
proposed X-haul scheme’s practicality, which is compared to Line-of-sight
(LoS) and Non-LoS (NLoS) alternate X-hauling.

The main contributions of our proposed X-haul outage scheme can be summarized
as follows:

  * •

The total received power, power consumption, and spectral density in the
presence of RIS are derived.

  * •

A closed-form expression is derived for the optimal number of RIS reflecting
elements with respect to the total consumed power, considering the dissipated
power per RIS element caused by the circuitry required for the adaptive phase
shift.

  * •

We present the benefit of using RIS for X-haul outage compensation and its
optimal location with respect to the source and the destination. Also, we show
that at a given distance and with a large number of RIS reflecting elements,
the RIS can fully recover the failed X-haul rate.

The rest of the paper is organized as follows. Section II presents the X-haul
outage compensation scheme. Section III introduces the proposed system model
with a detailed analytical model. In Section IV, we provide an analysis of the
X-haul rate and power in addition to finding the optimal number of RIS
elements. In Section V, we present the numerical results and analysis of the
proposed scheme. Finally, we conclude the paper in Section VI.

##  II X-haul Outage Compensation Scheme

We consider an ultra-dense network configuration for our X-haul outage
compensation scheme where SBSs are distributed in the street level in the
presence of different shaped buildings. For clarification, we define three
types of SBSs: 1) the Donor SBS (DBS), 2) the Failed SBS (FBS), and the
neighboring SBS (NBS). The DBS is considered as the BS that provides the
X-haul connection to the FBS before the occurrence of the failure. This
connection can be wired or wireless. Although our scheme is activated after
the occurrence of the failure, we consider the connection from the DBS to the
FBS and compare it to the compensation connection(s) to understand the degree
of recovery from the failure using this scheme. The FBS is the BS that lost
its X-haul connection from the DBS. There are many reasons for this connection
to fail, including equipment failure from the DBS side. Finally, the NBS is
the BS that will heal the failed X-haul connection of the FBS. We assume that
there is no LoS between NBS and FBS.

Fig. 1 shows the system model where we consider the previously mentioned three
SBSs in addition to several buildings, one of them is equipped with an RIS
panel. We have three different connection scenarios here in this figure: 1)
DBS-FBS, 2) NBS-FBS, and 3) NBS-RIS-FBS. For the first scenario, i.e., DBS-
FBS, this is considered as the no-failure scenario where the FBS is receiving
its X-haul LoS connection from DBS. The remaining two scenarios are going to
occur after the X-haul failure between DBS and FBS. For the second scenario,
i.e., NBS-FBS (NLoS), the NBS will provide the alternate X-haul connection to
the FBS. Since there is no LoS between the two SBSs (based on our assumption),
this connection is considered to be NLoS. For the third scenario, i.e., NBS-
RIS-FBS, the NBS will provide the alternate X-haul connection to the FBS with
the RIS panel’s assistance. Note that for this scenario, the connection from
NBS to FBS is NLoS; however, the connections from the NBS to RIS and from the
RIS to FBS are LoS.

It is obvious that scenario one will give the highest X-haul rate, given the
LoS connectivity, followed by scenario three, and the lowest rate is
achievable in scenario two. Scenarios one and two are considered upper and
lower X-haul rate bounds to the third scenario. The third scenario is the same
as the second scenario with the addition of the X-haul rate acquired by the
FBS from the directed reflection coming from the RIS panel. Moreover, we would
like to investigate where we have to place the RIS panel and how many RIS
elements need to be used to achieve an LoS like X-haul rate or, in other
words, how we can recover the failed X-haul or so that the X-haul failure will
not affect the achievable rate of the users associated with the FBS.

Figure 1:  : The system model.

##  III System Model

We consider the communication before the X-haul failure to be between the DBS
and the FBS. The LoS communication between DBS and FBS (denoted as subscript
DF) using single antenna, can be expressed as:

$y_{DF}^{LoS}=h_{DF}^{LoS}\sqrt{p}s+\tilde{n},$ (1)

where $h_{DF}^{LoS}$ is the deterministic flat-fading channel gain between DBS
and FBS, $p$ is the transmitted power, s is the unit power information signal,
and $\tilde{n}$ is the receiver noise, which is assumed to be additive white
Gaussian noise.

The X-haul achievable rate of this channel can be expressed as:

$R_{DF}^{LoS}=\log_{2}(1+\frac{p|h_{DF}^{LoS}|^{2}}{\sigma^{2}})$ (2)

where $\sigma^{2}$ is the noise variance.

This X-haul rate is considered as the maximum achievable capacity by the FBS
(before failure) acquired from the DBS. Note that once this X-haul connection
fails, the FBS will not be able to serve its users until it acquires another
X-haul connection. Note that this paper is concerned mainly with the proof of
the concept, this is why we didn’t consider the interference from the
neighboring BSs. However, we are considering the interference in a future
extension of this paper.

This paper proposes that the healing X-haul connection will be acquired from
an NBS where there is no LoS between the FBS and the NBS. In this case, the
healing X-haul capacity between the FBS and the NBS is expressed as:

$R_{NF}^{NLoS}=\log_{2}(1+\frac{p|h_{NF}^{NLoS}|^{2}}{\sigma^{2}})$ (3)

where $h_{NF}^{NLoS}$ is the deterministic flat-fading channel gain between
NBS and FBS.

It is worth pointing out that if there is a LoS between the FBS and the NBS,
our proposed approach will give a better X-haul rate. This is why we build our
model based on the worst case, i.e., no LoS.

Consider an RIS presence that will aid the communication between the NBS and
the FBS. The RIS is equipped with $N_{x}$ discrete reflecting elements. In
this case, the channel from NBS to RIS is indicated by
$\textbf{h}_{NI}^{NLoS}\in\mathbb{C}$, where $[\textbf{h}_{NI}^{NLoS}]_{n}$
denotes the nth component. The channel between the RIS and the NBS is denoted
by $\textbf{h}_{IF}^{NLoS}\in\mathbb{C}$, where $[\textbf{h}_{IF}^{NLoS}]_{n}$
denotes the nth component. Each element in the RIS has a size that is smaller
than the wavelength $\lambda$; consequently, the incoming signal is scattered
with a constant gain in all directions of interest [19]. The following
diagonal matrix represents the properties of the RIS:

$\mathbf{\Phi}=diag(\epsilon e^{j\phi_{1}},\dots,\epsilon e^{j\phi^{N_{x}}})$
(4)

where $\epsilon\in(0,1]$ is the fixed amplitude reflection coefficient and
$\phi_{1},\dots,\phi_{N}$ are the phase shift variables which are
controlled/optimized by the RIS.

The received signal between the NBS and the FBS now consists of two
components; 1) the NLoS component based on the direct communication between
NBS and FBS and 2) the reflected signal from the RIS and received by the FBS.
Hence, the received signal is given as:

$y_{NIF}^{NLoS}=(h_{NF}^{NLoS}+\mathbf{h}_{NI}^{T}\mathbf{\Phi}\mathbf{h}_{IF})\sqrt{p}s+n,$
(5)

We consider the channel deterministic since the RIS elements reflect passively
using a certain phase shift, and these elements do not have any signal
processing capabilities. The destination, i.e., FBS, is supposed to know the
channel, and the phase shift can be optimized. This assumption is considered
since the channel estimation for RIS is non-trivial; however, the recent work
presented in [20] introduced a general framework for estimating the channel.
Also, the authors in [21] proposed to include non-uniformly distributed active
elements in the RIS panel in order to train/estimate the channel by leveraging
deep learning tools.

The X-haul capacity of the communication between NBS and FBS with the support
of RIS is given by:

$\displaystyle R_{NIF}=$
$\displaystyle\underset{\phi_{1},\dots,\phi_{N}}{\text{max}}\log_{2}\bigg{(}1+\frac{p|h_{NF}^{NLoS}+\mathbf{h}_{NI}^{T}\mathbf{\Phi}\mathbf{h}_{IF}|^{2}}{\sigma^{2}}\bigg{)}$
(6) $\displaystyle=$
$\displaystyle\log_{2}\bigg{(}1+\frac{p(|h_{NF}^{NLoS}|+\epsilon\sum_{n=1}^{N_{x}}|[\mathbf{h}_{NI}]_{n}[\mathbf{h}_{IF}]_{n}|)^{2}}{\sigma^{2}}\bigg{)}$
(7)

where $N_{x}$ is the number of reflecting elements in the RIS panel.

The steps of deriving Eq. (7) from Eq. (6) can be found in [11]. It is worth
pointing out that
$\mathbf{h}_{NI}^{T}\mathbf{\Phi}\mathbf{h}_{IF}=\epsilon\sum_{n=1}^{N_{x}}e^{j\phi_{n}}[\mathbf{h}_{NI}]_{n}[\mathbf{h}_{IF}]_{n}$.
The maximum X-haul capacity is achieved when the phase shifts are selected as
follows:

$\phi_{n}=arg(h_{NF})-arg([\mathbf{h}_{NI}]_{n}[\mathbf{h}_{IF}]_{n})$ (8)

This phase shift will give the same phase as $h_{NF}$ to every term in the
sum. This proof follows the steps in [11]. Note that the term
$[\mathbf{h}_{NI}]_{n}[\mathbf{h}_{IF}]_{n}$ contains the transmit beamforming
and the NBS-RIS channel. which can be considered as the RIS effective channel
perceived by nth element. Hence, Eq. (8) recommends that the n${}^{\text{th}}$
phase shift must be tuned so that the phase of the signal that passes through
the RIS is aligned with that of the signal over the NBS-FBS to achieve the
best coherent combining at FBS.

To present the X-haul achievable rate equations in a more compact form, we
introduce the notation $h_{NF}$ = $\sqrt{\beta_{NF}}$, $h_{NI}$ =
$\sqrt{\beta_{NI}}$, $h_{IF}$ = $\sqrt{\beta_{IF}}$, and
$\frac{1}{N}\sum_{n=1}^{N_{x}}|[\mathbf{h}_{NI}]_{n}[\mathbf{h}_{IF}]_{n}|$ =
$\sqrt{\beta_{NIF}}$. Hence, Eqs. (2), (10), and (7) can be rewritten as:

$R_{DF}^{LoS}=\log_{2}(1+\frac{p\beta_{DF}^{LoS}}{\sigma^{2}})$ (9)

$R_{NF}^{NLoS}=\log_{2}(1+\frac{p\beta_{NF}^{NLoS}}{\sigma^{2}})$ (10)

$R_{NIF}=\log_{2}(1+\frac{p\bigg{(}\sqrt{\beta_{NF}^{NLoS}}+\epsilon~{}N_{x}\sqrt{\beta_{NIF}^{LoS}}\bigg{)}^{2}}{\sigma^{2}})$
(11)

The 3GPP Urban Micro (UMi) is used to model the channel gains [22] given that
the used carrier frequency is the 3 GHz C-band. We also used 28 GHz mmW band
for comparison purpose. As modeled in the previous equations, we will use both
the LoS and NLoS versions of the model, which are defined for distances
greater than or equal to 10 m. We denote the antenna gain of the transmitter
BS and receiver BS as $G_{t}$ and $G_{r}$, respectively. Hence, the channel
gain as a function of the distance for LoS and NLoS can be expressed as:

$\beta^{LoS}(d)[dB]=G_{t}+G_{r}-37.5-22\log_{10}(\frac{d}{d_{o}})$ (12)

$\beta^{NLoS}(d)[dB]=G_{t}+G_{r}-35.1-36.7\log_{10}(\frac{d}{d_{o}})$ (13)

where $d_{o}$ is the reference distance, which is considered in the UMi model
as 1m.

Note that in case of LoS between NBS-RIS-FBS, the channel gain
$\beta_{NIF}^{LoS}$ can be expressed as:

$\beta_{NIF}^{LoS}=\beta_{NI}^{LoS}\beta_{IF}^{LoS}$ (14)

##  IV Analysis of X-haul Rate and Power

We consider that the FBS requires a minimum X-haul rate, i.e., $\bar{R}$, to
satisfy its users’ requirements. Based on that, the X-haul capacity for
equations (9)-(11) can identify the required power for each of the three
scenarios, i.e., DBS-FBS LoS, NBS-FBS NLoS, and NBS-RIS-FBS NLoS scenarios.
For each scenario, the required power is given as follows:

$p_{DF}^{LoS}=(2^{\bar{R}}-1)\frac{\sigma^{2}}{\beta_{DF}^{LoS}}$ (15)

$p_{NF}^{NLoS}=(2^{\bar{R}}-1)\frac{\sigma^{2}}{\beta_{NF}^{NLoS}}$ (16)

$p_{NIF}(N)=(2^{\bar{R}}-1)\frac{\sigma^{2}}{(\sqrt{\beta_{NF}^{NLoS}}+\epsilon
N\sqrt{\beta_{NIF}^{LoS}})^{2}}$ (17)

The total power consumption, $P^{tot}$, of the BS consists of two components;
1) the transmit power and 2) power dissipated in hardware components. The
total power for the first scenario, i.e., DBS-FBS, is given as follows:

$P_{DF}^{tot}=\frac{p_{DF}^{LoS}}{\nu}+P_{D}+P_{F}$ (18)

where $\nu\in(0,1]$ is the power amplifier efficiency while $P_{D}$ and
$P_{F}$ are the power dissipated in the hardware at the DBS and FBS,
respectively. Similarly, the total power for the second scenario, i.e., NBS-
FBS, can be expressed as:

$P_{NF}^{tot}=\frac{p_{NF}^{NLoS}}{\nu}+P_{N}+P_{F}$ (19)

where $P_{N}$ is the hardware dissipated power at the NBS. Finally, for the
third scenario, i.e., NBS-RIS-FBS, the total power is given as:

$P_{NIF}^{tot}(N)=\frac{p_{NIF}(N)}{\nu}+P_{N}+P_{F}+NP_{e}$ (20)

where $P_{e}$ is the dissipated power per RIS element caused by the circuitry
required for the adaptive phase shift.

To find the optimal number of RIS elements given a certain X-haul rate
$\bar{R}$, an optimization problem can be solved aiming to minimize the total
power of the RIS scenario. The total power is a convex function in N since
$\frac{\partial^{2}}{\partial N^{2}}P_{NIF}^{tot}(N)>0$. Then the optimal
number of RIS elements, $N_{x}^{*}$ can be obtained from
$\frac{\partial}{\partial N}P_{NIF}^{tot}(N)=0$ which can be evaluated as:

$N^{*}=\sqrt[3]{\frac{(2^{\bar{R}}-1)\sigma^{2}}{\epsilon^{2}\beta_{NIF}^{LoS}P_{e}}}-\frac{1}{\epsilon}\sqrt{\frac{\beta_{NF}^{NLoS}}{\beta_{NIF}^{LoS}}}$
(21)

It is worth pointing out that the above solution is optimal under the
assumption that $\beta_{NIF}^{LoS}$ is independent of $N_{x}$. Also, the
optimal number of RIS elements in (21) in general is not an integer, hence,
the true optimal solution is either $\lfloor N^{*}\rfloor$ or $\lceil
N^{*}\rceil$. Note that in the presence of LoS between NBS-RIS and RIS-FBS,
$\beta_{NIF}^{LoS}$ is independent of $N_{x}$ and hence
$\beta_{NIF}^{LoS}=\beta_{NI}^{LoS}\beta_{IF}^{LoS}$.

##  V Simulation Results

This section presents the numerical results generated using MATLAB to
illustrate our proposed scheme’s effectiveness and investigate the benefits of
utilizing RIS to mitigate X-haul failures in 5G/6G networks. The simulation
model consists of one DBS, one NBS, and one FBS each of them is having a
single antenna. Also, we assume that only one building’s facade is equipped
with RIS, as shown earlier in Fig. 1. To clarify the comparison, we assumed
that the distance between the DBS-FBS is the same as that of NBS-FBS. Fig. 2
shows the simulation setup where the distance between the NBS and the FBS is
fixed and equals 100 m. Also, the vertical distance, d, between the RIS and
both NBS and FBS is fixed to two values; 15 m and 60 m. We vary the horizontal
distance between the FBS/NBS and the RIS, i.e., $d_{IF}$, (the RIS is moving
on the x-axis from $d_{IF}$= 0 m and $d_{IF}$= 200 m) to evaluate our model.
The simulation parameters are summarized in Table I.

We are considering three different scenarios where; the first one is before
failure between DBS and FBS (there is an LoS link between them). The second
scenario considers the failure of the X-haul link transmitted from the DBS. In
this case, NBS will heal FBS via an NLoS link only. The third scenario is
based on the same setup as the second scenario. Besides, the RIS is added to
aid the healing X-haul transmission from NBS to FBS. For all generated
figures, we used the carrier 3 GHz carrier frequency except for Fig. 3 we used
both 3GHz and 28 GHz.

Fig. 3 shows the X-haul achievable rate when changing the RIS panel position
on the x-axis from x=0 m to x=200 m and h = 15 m. The NBS-FBS LoS and the NBS-
FBS NLoS curves are not varying with the x-axis because the distance between
NBS and FBS is fixed and equals 100 m. The threshold rate is an arbitrary
value chosen to represent the acceptable X-haul rate during failure (can be
tuned by the network operator). However, we choose it to be around 50% of the
rate before failure. The X-haul rate before the occurrence of failure, i.e.,
DBS-FBS LoS curve (also known as NBS-FBS LoS), is around 3.25 bits/s/Hz. Once
the failure occurs and without RIS, the NLoS X-haul link between the NBS and
the FBS, i.e., NBS-FBS NLoS curve, is very close to 0 bits/s/Hz, which shows
that without using the RIS panel, the FBS will not achieve the minimum
required threshold rate and hence will not be able to serve its users.

Figure 2:  : The Simulation Setup.

The three double hump-shaped curves represent the X-haul achievable rate when
using RIS with 200, 500, and 1000 reflecting elements. It is observed that
there are two peaks at x = 0 m and x = 100 m where the NBS and FBS are
located, respectively. This shows that the optimal location for the RIS is to
be placed near either of them. Therefore, the optimal location for the RIS
panel is either near the transmitter or the receiver. Also, for N = 200, we
can achieve the X-haul threshold rate at these two locations only. When N =
500, the X-haul achievable rate exceeds that of the LoS rate at x = 0 m and x
= 100 m. This occurs under the condition that all reflecting elements are
dedicated to reflecting the received signal from the NBS to the FBS. When
doubling the number of reflecting elements, the X-haul achievable rate
outperforms that of the LoS even if the RIS panel is not located at the two
identified optimal locations. Although 1000 reflecting elements may sound
uncanny, covering a building’s facade by an RIS panel, similar to Fig. 1, will
accommodate 1000 reflecting elements or more. The only drawback of including a
large number of elements is interfacing them to the smart controller; however,
this issue can be alleviated by controlling each cluster of ten elements or
more by one interface or limiting the available phase shifts.

TABLE I: : Simulation Parameters Parameter | Value | Parameter | Value
---|---|---|---
Carrier Frequency | 3, 28 GHz | $P_{e}$ | 5 mW
Bandwidth | 10 MHz | $P_{D}$ | 100 mW
Noise Figure | 10 dB | $P_{N}$ | 100 mW
Antenna Gain | 5 dBi | $P_{F}$ | 100 mW
$\epsilon$ | 1 | $\nu$ | 0.5

Fig. 3 has the same simulation setup as Fig. 3 except that the vertical
distance between the FBS/NBS and the RIS panel is increased from 15 m to 60 m.
This increase changed the double hump-shaped curves into concave curves, which
means that the RIS panel should be placed in the mid-distance between the
source and destination. This infers that the optimal location of the RIS panel
is heavily dependent on the vertical distance h. Also, the only RIS panel that
satisfies the threshold rate is the one equipped with 1000 reflecting
elements.

Fig. 3 shows the transmit power needed by the DBS/NBS to deliver an X-haul
rate of $\bar{R}=4$ bit/s/Hz to the FBS for two different carrier frequencies,
i.e., 3 GHz and 28 GHz. The NBS-FBS NLoS link is consuming most of the power
of the NBS to achieve the target X-haul rate. Meanwhile, the RIS with 1000
reflecting elements requires the least amount of transmit power and
outperforms the amount of power needed for LoS when the RIS panel is located
anywhere between the NBS and the FBS. When the number of reflecting elements
is reduced, more power is needed to achieve the same target X-haul rate. It is
worth noting that when the RIS panel and NBS or FBS are aligned on the same
vertical line, the transmit power is minimal. For 28 GHz related results, the
transmit power increases dramatically due to the high attenuation of this
range carrier frequencies exceeding the threshold power, i.e., 30 dBm, of the
SBS. Using Multiple-Input-Multiple-Output (MIMO) or massive MIMO antennas with
active beamforming can reduce the needed transmit power to acceptable limits.
Meanwhile, without using MIMO, the RIS panel with 1000 reflecting elements can
achieve the target X-haul rate without exceeding the maximum power of the SBS,
given that the panel is located anywhere between x = 0 m or x = 100 m.

Fig. 4 investigates the Energy Efficiency (EE) performance for the considered
RIS-based scenario. The EE is defined as the ratio between the X-haul
achievable rate and total power consumption, i.e., $EE=BW*R/P_{tot}$ where BW
is the transmission bandwidth.

(a) X-haul achievable rate for h = 15 m

(b) X-haul achievable rate for h = 60 m

(c) Transmit power for $R=4$ bit/s/Hz

Figure 3:  : Simulation results for X-haul achievable rate and power using RIS
Figure 4:  : The energy efficiency vs. spectral efficiency

Fig. 4 shows the EE versus the X-haul achievable rate when optimizing the
number of RIS elements with respect to the transmit power based on Eqs. (20)
and (21). It is shown that the optimal number of RIS elements is zero when the
X-haul rate is 5 bit/s/Hz or less. This means that it is not recommended to
use RIS if the FBS’s required X-haul spectral efficiency is less than or equal
to 5 bit/s/Hz.

As the X-haul spectral efficiency increases beyond 5 bit/s/Hz, the EE of the
NBS-RIS-FBS scenario outperforms that of the NBS-FBS scenario. Although the
DBS-FBS LoS scenario is the most EE, it degrades dramatically by increasing
the spectral density. When the spectral density is greater than 20 bit/s/Hz,
the NBS-RIS-FBS scenario outperforms the LoS scenario. Also, on the second
y-axis, the number of RIS elements increases exponentially, inferring the
impracticality of using RIS when the X-haul rate is greater than 25 bit/s/Hz.
In addition, when increasing the required X-haul rate from 20 bit/s/Hz to 25
bit/s/Hz, the optimal number of reflecting elements will increase from 1000 to
3000 reflecting elements.

##  VI Conclusions

5G cellular networks are being deployed to promise that they will deliver
significantly faster and more responsive mobile broadband experiences.
However, based on the 5G network’s densifying concept, the number of failures
of X-haul links will increase. We proposed Reconfigurable Intelligent Surfaces
(RIS) usage to help mitigate X-haul failure/outages in dense and ultra-dense
networks. Our proposed scheme, along with the presented analytical results,
showed that using RIS can mitigate or at least alleviate the effect of X-haul
failures. Moreover, using the RIS with a certain number of reflecting
elements, our proposed solution can deliver approximately the same X-haul rate
achieved before failure. We also showed that under certain conditions, the
proposed RIS X-haul solution could deliver more rate and be more energy-
efficient than the line-of-sight and the non-line-of-sight solutions. Finally,
if the associated issues with increasing the number of reflecting elements are
resolved, the RIS panel with a large number of reflecting elements, i.e., 1000
or more, can compensates any failed X-haul link regardless the frequency band
used, i.e., below or above 6 GHz, given that the panel is placed in its
optimal location.

## References

  * [1] X. Lin et al., “5G New Radio: Unveiling the Essentials of the Next Generation Wireless Access Technology,” in IEEE Communications Standards Magazine, vol. 3, no. 3, pp. 30-37, September 2019.
  * [2] Small Cell Forum, https://www.smallcellforum.org/, last accessed: May 01, 2022.
  * [3] A. Asghar, H. Farooq and A. Imran, “Self-Healing in Emerging Cellular Networks: Review, Challenges and Research Directions,” IEEE Comm. Surveys & Tutorials, Apr. 2018.
  * [4] A. Jafari, et al. “Small cell backhaul: challenges and prospective solutions”, Journal on Wireless Communications and Network”, Aug. 2015.
  * [5] P. Yu, et al. “Deep Reinforcement Learning Aided Cell Outage Compensation Framework in 5G C-RAN”, Mobile Network App., Jul. 2020.
  * [6] Yu Jie, A. Alsharoa, A. Kamal, “A CoMP-Based outage compensation solution for heterogeneous femtocell networks”, Computer Netoworks Journal, Feb. 2020.
  * [7] Lan Zou, Kai Zhang, “Method and device for handling cell outage”, US patent, Patent number: US10659979B2, May 2020.
  * [8] 5G Xhaul Project www.5g-xhaul-project.eu, ess Dec. 20 2020.
  * [9] M. Y. Selim, et al., “Fronthaul cell outage compensation for 5G networks,” IEEE Communications Magazine, vol. 54, no. 8, Aug. 2016.
  * [10] Q. Wu, R. Zhang, “Towards Smart and Reconfigurable Environment: Intelligent Reflecting Surface Aided Wireless Network,” in IEEE Communications Magazine, vol. 58, no. 1, Jan. 2020.
  * [11] Q. Wu, Rui Zhang, “IRS Enhanced Wireless Network via Joint Active and Passive Beamforming”, IEEE Trans. on Wireless Comm., Nov. 2019.
  * [12] Y. Liu, X. Liu, X. Mu, T. Hou, J. Xu, Z. Qin, M. Di Renzo, and N. Al-Dhahir, “Reconﬁgurable Intelligent Surfaces: Principles and Opportunities”, arXiv, July 2020. Available at https://arxiv.org/abs/2007.03435.
  * [13] M. Di Renzo et al., “Smart Radio Environments Empowered by Reconfigurable Intelligent Surfaces: How It Works, State of Research, and The Road Ahead,” in IEEE Journal on Selected Areas in Communications, vol. 38, no. 11, pp. 2450-2525, Nov. 2020.
  * [14] X. Yuan, Y. -J. A. Zhang, Y. Shi, W. Yan and H. Liu, “Reconfigurable-Intelligent-Surface Empowered Wireless Communications: Challenges and Opportunities,” In IEEE Wireless Communications, Apr. 2021,
  * [15] DOCOMO NTT https://www.nttdocomo.co.jp/english/info/media_center/pr/2020/0117_00.html.
  * [16] C. You, B. Zheng, R. Zhang, “How to Deploy Intelligent Reflecting Surfaces in Wireless Network: BS-side, User-side, or Both Sides?”, arXiv, December 2020. Available at https://arxiv.org/abs/2012.03403.
  * [17] M. Al-Jarrah, E. Alsusa, A. Al-Dweik, M. Alouini, “Performance Analysis of Wireless Mesh Backhauling Using Intelligent Reflecting Surfaces,” in IEEE Transactions on Wireless Communications, early access, 2021.
  * [18] E. Björnson, Ö. Özdogan, E. Larsson, “Intelligent Reflecting Surface Versus Decode-and-Forward: How Large Surfaces are Needed to Beat Relaying?,” in IEEE Wireless Communications Letters, Feb. 2020
  * [19] Ö. Özdogan, E. Björnson, E. Larsson, “IRS: Physics, Propagation, and Pathloss Modeling,” in IEEE Wireless Comm. Letters, May 2020.
  * [20] Z.-Q. He, X. Yuan, “Cascaded channel estimation for large intelligent metasurface assisted massive MIMO”, CoRR, vol. abs/1905.07948, 2019.
  * [21] A. Taha, M. Alrabeiah, A. Alkhateeb, “Deep Learning for Large Intelligent Surfaces in Millimeter Wave and Massive MIMO Systems,” 2019 IEEE Global Communications Conference, Waikoloa, HI, USA, 2019.
  * [22] 3GPP, “Study on channel model for frequencies from 0.5 to 100 GHz,” 3rd Generation Partnership Project (3GPP), TR 38.901 V14.0.0, May. 2017. [Online]. Available: http://www.3gpp.org/DynaReport/38901.htm, last accessed: May 01, 2022.


# Some combinatorial problems arising in the dimer model

R. Kenyon  Mathematics Department, Yale University, New Haven
<EMAIL_ADDRESS>
###### 2020 Mathematics Subject Classification:

Primary 82B20

##  1\. Introduction

We collect here a few diverse problems on the dimer model. For background on
dimers one can read for example [6].

Let $\mathcal{G}=(V,E)$ be a finite, connected, bipartite graph. A _dimer
cover_ , or _perfect matching_ , of $\mathcal{G}$ is a collection $m\subset E$
of edges that covers each vertex exactly once. We denote by
$\mathcal{M}=\mathcal{M}(\mathcal{G})$ the set of dimer covers of
$\mathcal{G}$.

Let $c:E\to\mathbb{R}_{>0}$ be a positive weight function edges of
$\mathcal{G}$. If $m\in\mathcal{M}$ is a dimer cover, we define
$c(m)=\prod_{e\in m}c_{e}$ to be the _weight_ of $m$. This weight function
defines a probability measure $\mu=\mu_{c}$ on $\mathcal{M}$, giving a dimer
cover a probability proportional to its weight, that is,
$\mathrm{Pr}(m)=\frac{c(m)}{Z}$, where the constant of proportionality $Z$ is
the _partition function_ : $Z=\sum_{m\in\mathcal{M}}c(m).$

Essentially the most fundamental problem in the dimer model is the following:

######  Problem 0.

For a random dimer cover, compute the edge probabilities, that is, compute the
probability $\mathrm{Pr}(e)$ that any particular edge $e$ is used.

This is easy if we can compute $Z$ as a function of edge weights, since

(1.1) $\mathrm{Pr}(e)=\frac{c_{e}}{Z}\frac{\partial Z}{\partial
c_{e}}=\frac{\partial\log Z}{\partial\log c_{e}}.$

However on general graphs computing $Z$ is hard, even for constant edge
weights: enumerating dimer covers is in fact $\\#$P-complete, by a celebrated
result of Valiant [11]. Note that computing $\mathrm{Pr}(e)$ is in fact just
as hard as computing $Z$, since one can reconstruct $Z$ from integrating
$\mathrm{Pr}(e)$ using (1.1). For planar graphs we can however compute $Z$ and
thus solve the above problem, using Kasteleyn’s method of enumerating dimer
covers with determinants, see [6] and Section 2.2 below.

One useful change of perspective is to consider the edge weights as a
“$\mathbb{C}^{*}$-local system” on $\mathcal{G}$, that is, as a connection on
a line bundle on the graph. This point of view may seem at first just an added
level of abstraction, and to be taking us away from combinatorics. But it
turns out to have a number of advantages, such as:

  1. (1)

It highlights a non-obvious symmetry of the problem: the gauge invariance (see
below).

  2. (2)

It generalizes naturally to other gauge groups such as
$\mathrm{SL}_{n}(\mathbb{R})$, with interesting combinatorial interpretations
(see Sections 6 and 7 below).

  3. (3)

It connects the problem to geometry.

Our choice of problems in this article is (mostly) motivated by this geometric
point of view.

## Acknowledgements

This research was supported by NSF grant DMS-1940932 and the Simons Foundation
grant 327929.

##  2\. Preliminaries

###  2.1. Vector bundles and connections on graphs

What is a bundle with connection on a graph? Fix a vector space $\mathcal{V}$
and assign an isomorphic copy $\mathcal{V}_{v}$ of $\mathcal{V}$ to each
vertex $v\in V$. For each edge $e=uv$ we associate a linear isomorphism
$\phi_{uv}:\mathcal{V}_{u}\to\mathcal{V}_{v}$ of these vector spaces, with
$\phi_{vu}=\phi_{uv}^{-1}$. Generally we have
$\phi_{uv}\in\mathrm{GL}(\mathcal{V})$ but we can restrict if desired to other
subgroups of $\mathrm{GL}(\mathcal{V})$, and even noninvertible endomorphisms
[2]. In this paper we will only use $\mathrm{SL}_{n}(\mathbb{C})$ connections
on $\mathbb{C}^{n}$ or $\mathbb{C}^{*}$-connections on $\mathbb{C}$. (Here
$\mathbb{C}^{*}=\mathbb{C}\setminus\\{0\\}$ is the group of
$\mathbb{C}$-linear automorphisms of $\mathbb{C}$.) These are called,
respectively, $\mathrm{SL}_{n}$-local systems and $\mathbb{C}^{*}$-local
systems. Sometimes we specialize the latter from $\mathbb{C}^{*}$ to
$\mathbb{R}^{*}$.

If we choose a basis for each vector space $\mathcal{V}_{v}$ then each
$\phi_{uv}$ is a matrix. Changing bases by matrices $A_{v}$ at vertices $v$
results in new edge matrices $\phi_{uv}^{\prime}=A_{u}\phi_{uv}A_{v}^{-1}$.
Such changes are called _gauge transformations_. They form a symmetry of the
system.

If $\gamma$ is an oriented loop in $\mathcal{G}$ based at $x_{0}$, the
_monodromy_ $\phi_{\gamma}$ of the connection around $\gamma$ is the
composition of the isomorphisms $\phi_{e}$ along $\gamma$ starting at $x_{0}$.
The conjugacy class of $\phi_{\gamma}$ is invariant under gauge
transformations. Note also that changing the basepoint along $\gamma$
conjugates the monodromy.

For one-dimensional bundles, with $\mathcal{V}=\mathbb{R}$, each
$\phi_{uv}\in\mathbb{R}^{*}$ is a scalar. Since we are assuming $\mathcal{G}$
is bipartite, we can canonically orient the edges from black to white. Then
$\phi_{bw}$ is a scalar quantity associated to edge $bw$ which we call the
_edge weight_. In probability settings we usually take $\phi_{bw}$ positive.
However it is sometimes useful to consider $\mathcal{V}=\mathbb{C}$ and
$\phi_{bw}\in\mathbb{C}^{*}$. Gauge transformations are functions
$A:V\to\mathbb{C}^{*}$ and transform $\phi_{bw}$ into
$\phi_{bw}^{\prime}=A_{b}\phi_{bw}A_{w}^{-1}$.

For an $\mathbb{R}$-bundle, when edge weights $\phi_{bw}$ are positive, we can
associate a probability measure $\mu$ as above. Then positive gauge
transformations (i.e. when the $A_{v}>0$) change the weights of individual
dimer covers but not the probability measure $\mu$: If we multiply the edge
weights of all edges at a single vertex by a constant $\lambda>0$, then the
weight of every dimer cover is multiplied by $\lambda$. This implies that the
probability measure $\mu$ only depends on the equivalence class of edge
weights under gauge transformations, that is, on the “edge weights modulo
gauge”.

###  2.2. Planar bipartite graphs and the Kasteleyn matrix

Let $\mathcal{G}$ be a planar bipartite graph with a $\mathbb{C}^{*}$-local
system $\Phi$ (equivalently, a set of edge weights in $\mathbb{C}^{*}$, see
the previous section). We define a matrix $K$, the _Kasteleyn matrix for
$\mathcal{G}$_, as follows. The matrix $K=(K_{wb})$ has rows indexing white
vertices and columns indexing black vertices, and

$K_{wb}=\begin{cases}\pm\phi_{bw}&b\sim w\\\ 0&\text{otherwise}\end{cases}$

where the signs are chosen by the “Kasteleyn rule”: a face of length $\ell$
has $\frac{\ell}{2}+1\bmod 2$ minus signs. Kasteleyn showed in this case that
the determinant of $K$ counts weighted dimer covers:

######  Theorem 1 ([4, 7]).

$|\det K|=\sum_{m\in\mathcal{M}}c(m).$

As an application, probabilities of one or more edges being in a dimer cover
are minors of the inverse of $K$, see [5].

If $\mathcal{G}$ has an $\mathrm{SL}_{n}$-local system, one can similarly
define a Kasteleyn matrix, whose entries are now $n\times n$ matrices
themselves; see Sections 6.1,7.2 below.

##  3\. From edge weights to probabilities

We wish to study the mapping from edge weights to probabilities. This requires
first defining the correct spaces.

###  3.1. Fractional matchings

A _fractional matching_ of $\mathcal{G}=(V,E)$ is a function $f:E\to[0,1]$
which sums to one at each vertex: $\sum_{u\sim v}f(u)=1$. A dimer cover $m$
determines a fractional matching, by assigning $f(e)=1$ for each $e\in m$ and
$f(e)=0$ otherwise. The set of fractional matchings $\Omega(\mathcal{G})$ is a
convex polytope in $\mathbb{R}^{E}$ (in fact a subset of $[0,1]^{E}$) whose
vertices are exactly the dimer covers of $\mathcal{G}$, see [8].

A probability measure on dimer covers is a probability measure on the vertices
of $\Omega$, and so has a barycenter which is a point in $\Omega$. The
coordinate of this barycenter corresponding to an edge is the probability of
that edge.

So a more elegant statement of Problem  ‣ 1 is

######  Problem 1.

Compute the expected fractional matching.

See an example in Figure 1.

Figure 1. A graph and its expected fractional matching (for uniform edge
weights). This graph has three dimer covers; two of these use the leftmost
vertical edge, so its probability is $2/3$.

###  3.2. Cycles

A _flow_ on a graph $\mathcal{G}$ is a function $f$ on oriented edges
satisfying $f(-e)=-f(e)$ where $-e$ represents the edge with the reversed
orientation. The _cycle space_ $H_{1}(\mathcal{G})$ is the space of
divergence-free flows: flows $f$ satisfying $\sum_{u\sim v}f(vu)=0$ for all
$v$.

Since $\mathcal{G}$ is bipartite, we can orient edges from black to white, and
then for any two fractional matchings $f_{1},f_{2}\in\Omega$, $f_{1}-f_{2}$
represents an element of the cycle space of $\mathcal{G}$, denoted
$[f_{1}-f_{2}]$. Fixing a basepoint $f_{0}\in\Omega$, we can map $\Omega$
linearly and injectively into $H_{1}(\mathcal{G})$ by $f\mapsto[f-f_{0}]$.

We say $\mathcal{G}$ is _nondegenerate_ if $\Omega$ is of dimension
$d=|E|-|V|+1$, the dimension of the cycle space of the graph. A graph is
degenerate (that is, not nondegenerate) if there are unused edges (edges which
participate in no dimer cover) whose removal does not disconnect the graph
[8]. Figure 2 shows a degenerate graph.

Figure 2. A degenerate graph. The dimension of the cycle space is $3$ but
$\Omega$ is of dimension $2$. Note that the two diagonal edges are “unused”,
that is, do not appear in any dimer cover.

###  3.3. Gauge equivalence

For a bipartite graph, the space of equivalence classes of edge weights modulo
gauge transformations, that is, the space of $\mathbb{C}^{*}$-local systems,
is isomorphic to $(\mathbb{C}^{*})^{d}$ where $d$ is the dimension of the
cycle space of the graph. Explicitly, for a cycle $\gamma$ we can define
$X_{\gamma}$ to be the monodromy of the connection around $\gamma$. In terms
of edge weights, $X_{\gamma}$ is the alternating product of edge weights
around $\gamma$: assuming we start at a black vertex, $X_{\gamma}$ is the
first weight, divided by the second, times the third, and so on. Note that
$X_{\gamma}$ is invariant under gauge transformations. Reversing the
orientation inverts the monodromy. If $\gamma$ ranges over a basis for the
cycle space, the set of monodromies $\\{X_{\gamma}\\}$ parameterize the space
of all edge weights modulo gauge, that is, all $\mathbb{C}^{*}$-local systems.

For a planar graph, a basis for the cycle space is the set of cycles around
the bounded faces. Consequently we can take the “face weights”
$\\{X_{f}\\}_{f\in F}$ on the bounded faces of the graph to parameterize the
choices of edge weights modulo gauge.

Now a perhaps more interesting variant of Problem  ‣ 1 is:

######  Problem 2.

For nondegenerate graphs, study the map $\Psi$ from cycle weights
$\\{X_{f}\\}$ to the expected fractional matching.

The domain and range of $\Psi$ have the same dimension: the dimension of the
cycle space of the graph.

######  Theorem 2.

If $\mathcal{G}$ is nondegenerate then $\Psi$ is a diffeomorphism from the
space of cycle weights $(\mathbb{R}_{>0})^{d}$ to $\Omega(\mathcal{G})$.

###### Proof.

Fix the gauge by choosing a spanning tree $T$ of $\mathcal{G}$ and setting
edge weights $1$ on the tree $T$ and weights $c_{e}$ for $e\not\in T$. Let
$Z=Z(\\{c_{e}\\})$ be the associated partition function. Let $p_{e}$ be the
probability of edge $e$ for $e\not\in T$. All the other edge probabilities
(and therefore the fractional matching $f$) are uniquely determined by the
probabilities $\\{p_{e}~{}|~{}e\not\in T\\}$: one can determine the value of
$f$ on the leaves of the tree, then remove these and continue with the leaves
of the subtrees inductively. As in (1.1) we have
$p_{e}=c_{e}\frac{\partial\log Z}{\partial c_{e}}.$ We can write this as
$\vec{p}=\nabla\log Z$ where the gradient is taken with respect to the vector
of “edge energies” $(\log c_{e})_{e\not\in T}$.

Since $Z$ is a positive polynomial (that is, its coefficients are
nonnegative), it is, up to scale, the probability generating function of a
probability measure on $\mathbb{Z}^{d}$ of finite support. The Hessian of
$\log Z$ with respect to the logs of its variables is the covariance matrix of
this probability measure:

$c_{1}c_{2}\frac{\partial^{2}}{\partial c_{1}\partial c_{2}}\log
Z=\frac{c_{1}c_{2}}{Z}\frac{\partial^{2}Z}{\partial c_{1}\partial
c_{2}}-\frac{c_{1}c_{2}Z_{c_{1}}Z_{c_{2}}}{Z^{2}}=\mathbb{E}[X_{1}X_{2}]-\mathbb{E}[X_{1}]\mathbb{E}[X_{2}]$

where $X_{1},X_{2}$ are the indicator functions of edges $1,2$. Any covariance
matrix is positive semidefinite, and thus this Hessian is positive
semidefinite: $\mathrm{Hess}\log Z\geq 0$. In fact it is positive definite as
long as the Newton polytope of $Z$ is of positive volume, that is, if the
exponents of the monomials of $Z$ span the cycle space. But this is guaranteed
by nondegeneracy. Since $\mathrm{Hess}(\log Z)$ is positive definite, $\log Z$
is strictly convex and so $\nabla\log Z$ is a diffeomorphism onto its image. ∎

Note that $\det(\nabla\Psi)$ is a rational function of the $c_{e}$. What is
the degree of $\nabla\Psi$ as a rational map on $\mathbb{C}^{d}$? If we extend
$\Psi$ to all of $\mathbb{C}^{d}$ it appears that the inverse of a point
$\vec{p}\in\Omega$ consists in _real_ values of $c_{e}$ (only one preimage
consists in positive reals, but there can be multiple non-positive preimages;
it is not clear that these are always real, although they are in the small
examples we tried). A similar situation, for resistor networks, where reality
of the other preimages is proved, can be found in [1].

##  4\. Dimer walks

To each dimer cover $m\in\mathcal{M}(\mathcal{G})$ is associated an involution
$\pi_{m}:V\to V$. This is the involution exchanging a vertex with the vertex
it is paired with.

######  Problem 3.

Let $\\{m_{1},m_{2},\dots\\}$ be a sequence of i.i.d. dimer covers of
$\mathcal{G}$. Study the random walks on $S_{V}$, the permutation group on the
vertices, defined by the $\pi_{m_{i}}$.

Another way to state this is to define
$g=\frac{1}{Z}\sum_{m\in\Omega_{1}(\mathcal{G})}\pi(m)\in\mathbb{R}[S_{V}]$,
the element of the group algebra $\mathbb{R}[S_{V}]$ of $S_{V}$ defined by a
random choice of dimer cover. What can be said about $g^{n}$?

As a simple example one can take $\mathcal{G}=K_{4}$ with vertices
$[4]=\\{1,2,3,4\\}$. The three dimer covers correspond to the three
permutations $(12)(34),(13)(24),(14)(23)$ which generate a subgroup of $S_{4}$
isomorphic to $(\mathbb{Z}_{2})^{2}$. The dimer random walk just becomes
simple random walk on this group, where every element is adjacent to any other
element, that is, we have simple random walk on $K_{4}$.

For another simple example, let $\mathcal{G}$ be the $3\times 2$ grid. Rather
than record the element in $S_{6}$, without loss of information we can record
simply the permutations of the $x$-coordinates of the vertices, in $S_{3}$.
There are $3$ dimer covers, and the walk corresponds to multiplication by
$g=\frac{1}{3}(1+e_{(12)}+e_{(23)})$. Its eigenvalues are
$1,\frac{2}{3},\frac{2}{3},-\frac{1}{3},0,0$.

As a more interesting example, when $\mathcal{G}$ is the $n\times n$ grid
graph on a torus, each vertex undergoes a simple random walk on $V$, since
with probability $1/4$ it is matched to any neighbor. These simple random
walks are coupled to avoid each other. How quickly does the process mix? What
is the expected winding of two walks around each other, as a function of time?

##  5\. Magnetic double dimer model

###  5.1. Double dimers

Recall that $\mathcal{M}=\mathcal{M}(\mathcal{G})$ is the set of dimer covers
of $\mathcal{G}$. A _double dimer cover_ is a function $m:E\to\\{0,1,2\\}$
which sums to $2$ at each vertex. See Figure 3.

Figure 3.  A double dimer cover of a grid. Edges of multiplicity $1$ or $2$
are shown.

A union of two single dimer covers determines a double dimer cover, and (for
bipartite graphs) every double dimer cover occurs this way. The map from pairs
of dimer covers to double dimer covers is not, however, injective: each double
dimer cover $m$ arises from $2^{\ell}$ ordered pairs of single dimer covers,
where $\ell$ is the number of cycles in $m$, where the cycles are formed from
the edges of multiplicity $1$.

Let $\mathcal{M}_{2}$ be the set of double dimer covers of $\mathcal{G}$. The
natural probability measure on $\mathcal{M}_{2}$ (for us) is _not_ the uniform
measure. It is, rather, the projection of the uniform measure on
$\mathcal{M}\times\mathcal{M}$ under the standard map
$\mathcal{M}\times\mathcal{M}\to\mathcal{M}_{2}$. Thus a double dimer cover
$m$ has a probability proportional to $2^{\ell}$ where $\ell$ is the number of
cycles (cycles formed from edges of multiplicity $1$; edges of multiplicity
$2$ do not count as cycles). We call $2^{\ell}$ the _weight_ $c(m)$ of $m$.

######  Problem 4.

What can be said about the distribution of loops in the double dimer model on
$\mathbb{Z}^{2}$?

Let $\mathcal{G}$ be a bipartite planar graph, and $q\in\mathbb{C}^{*}$ be a
variable. One can define a $\mathbb{C}^{*}$-connection on $\mathcal{G}$ so
that each face has counterclockwise monodromy $q$, see for example Figure 4.

Figure 4. Connections with monodromy $q$ per face.

Let $K(q)$ be an associated Kasteleyn matrix. For a double-dimer configuration
$m_{2}$ define

(5.1) $c(m_{2})=\prod_{\text{loops $\gamma$ of
$m_{2}$}}(q^{A_{\gamma}}+q^{-A_{\gamma}})$

where $A_{\gamma}$ is the area (number of faces) enclosed by $\gamma$. We then
have

######  Theorem 3.

(5.2) $\det K(q)\det
K(1/q)=\sum_{m_{2}\in\mathcal{M}_{2}}\,\,\prod_{\text{loops $\gamma$ of
$m_{2}$}}(q^{A_{\gamma}}+q^{-A_{\gamma}}).$

###### Proof.

The quantity $\det K(q)\det K(1/q)$ counts pairs of dimer configurations
$(m,m^{\prime})$, where $m^{\prime}$ has the inverted $q$-weight. In the
superposition of $m$ and $m^{\prime}$, we orient $m$’s dimers from black to
white and $m^{\prime}$’s dimers from white to black, reversing the parallel
transport, so that the orientations of loops are consistent. In this way the
weight of an oriented loop is given by its monodromy, that is, $q^{A}$ where
$A$ is the area enclosed by the loop. When we sum over both orientations of
each loop, we find (5.2). ∎

It is tempting to use (5.2) to answer Problem 4. For example one can expand
$\det K(q)\det K(1/q)$ near $q=1$ to get various moments. However extracting
information about the areas from this does not appear easy.

An alternative approach is to invert the standard Kasteleyn matrix (when
$q=1$) and use it to compute the probability of any given shape of loop. For
the square grid $\mathbb{Z}^{2}$, this can be used to compute the expected
density of loops of fixed small area, as follows. The “inverse Kasteleyn
matrix” for $\mathbb{Z}^{2}$ can be obtained as a limit as $n\to\infty$ of
$K^{-1}_{\mathcal{G}_{n}}$ for $\mathcal{G}_{n}$ the $2n\times 2n$ grid, see
[6]. There is an explicit formula: when $b-w=(x,y)\in\mathbb{Z}^{2}$,

$K^{-1}((0,0),(x,y))=\frac{1}{(2\pi
i)^{2}}\iint_{|z|=|w|=1}\frac{z^{(-x+y+1)/2}w^{(-x-y+1)/2}}{1+z+w-zw}\frac{dz}{z}\frac{dw}{w}.$

Minors of this matrix compute edge probabilities for random dimer covers of
$\mathbb{Z}^{2}$, see [5]:

$Pr((w_{1},b_{1}),\dots,(w_{k},b_{k}))=|\det(K^{-1}(b_{j},w_{i})_{1\leq
i,j\leq n})|.$

The expected density of loops of area $1$ (the probability that a given face
is in such a loop) is the probability that for a pair of single dimer models
$(m,m^{\prime})$ on $\mathbb{Z}^{2}$, $m$ contains edges $(0,0)(1,0)$ and
$(0,1)(1,1)$ and $m^{\prime}$ contains edges $(0,0)(0,1)$ and $(1,0)(1,1)$, or
the reverse. The probability that $m$ contains both edges $(0,0)(1,0)$ and
$(0,1)(1,1)$ is, by a short computation, $\frac{1}{8}$. So the expected
density of loops of area $1$ in the double dimer model is
$\frac{2}{8^{2}}=\frac{1}{32}$. Similarly the density of loops of area $2$ can
be computed to be $\frac{(\pi-1)^{2}}{2\pi^{4}}.$ The density for area-$3$
loops is already more complicated:

$\frac{3\left(64-192\pi^{2}+192\pi^{3}-32\pi^{4}-32\pi^{5}+24\pi^{6}-8\pi^{7}+\pi^{8}\right)}{32\pi^{8}}.$

##  6\.  $\text{SL}_{2}$ connections

###  6.1. Kasteleyn matrix

Consider $\mathcal{G}$ a planar bipartite graph with an
$\mathrm{SL}_{2}$-local system $\Phi$. Let $K=(K_{wb})$ be an associated
Kasteleyn matrix for $\mathcal{G}$, that is a matrix with rows indexing white
vertices and columns indexing black vertices, and

$K_{wb}=\begin{cases}\pm\phi_{bw}&b\sim w\\\ 0&\text{otherwise}\end{cases}$

where the signs are chosen by the same Kasteleyn rule as in the scalar case: a
face of length $\ell$ has $\frac{\ell}{2}+1\bmod 2$ minus signs. Here by $0$
we mean the zero matrix in $M_{2}(\mathbb{R})$. Then $K$ is an $N\times N$
matrix with entries in $M_{2}(\mathbb{R})$. Let $\tilde{K}$ be the $2N\times
2N$ matrix obtained from $K$ by replacing each entry with its $2\times 2$
array of real numbers.

By a theorem of [2],

(6.1) $\det\tilde{K}(\Phi)=\sum_{m\in\mathcal{M}_{2}}\prod_{\text{loops in
$m$}}\mathrm{Tr}(\phi_{\gamma}).$

Here $\phi_{\gamma}$ is the monodromy of the connection $\Phi$ around the loop
$\gamma$, and $\mathrm{Tr}(\phi_{\gamma})$ is its trace. Even though
$\phi_{\gamma}$ depends on a starting vertex and the orientation of the loop,
the trace $\mathrm{Tr}(\phi_{\gamma})$ is independent of starting vertex
(since the trace of a matrix only depends on its conjugacy class) and
orientation (since for matrices $A\in\text{SL}_{2}$ we have
$\mathrm{Tr}(A)=\mathrm{Tr}(A^{-1})$).

###  6.2. Flat connections and simple laminations

Suppose graph $\mathcal{G}$ is drawn on a multiply-connected planar domain
$\Sigma$, and $\Phi$ is a _flat_ $\mathrm{SL}_{2}$ connection. This means the
monodromy of $\Phi$ around any cycle in $\mathcal{G}$ which is contractible as
a cycle in $\Sigma$, is the identity. In this case the trace of the monodromy
around a loop $\gamma$ only depends on its isotopy class as a loop in
$\Sigma$. In other words two loops in $\mathcal{G}$ which are isotopic as
loops in $\Sigma$, have monodromies with the same trace.

A _simple lamination_ is an isotopy class of finite collections of pairwise
disjoint simple closed loops on $\Sigma$. Let $\Lambda_{2}$ be the collection
of simple laminations.

When $\Phi$ is flat we can group the terms in the sum (6.1) according to their
isotopy classes:

(6.2)
$\det\tilde{K}(\Phi)=\sum_{\lambda\in\Lambda_{2}}C_{\lambda}\mathrm{Tr}(\phi_{\lambda})$

with $C_{\lambda}\in\mathbb{Z}_{\geq 0}$.

By a Theorem of Fock and Goncharov [3], the functions
$\mathrm{Tr}(\phi_{\lambda})$ as $\lambda$ runs over $\Lambda_{2}$, considered
as functions of $\Phi$, are linearly independent and in fact form a linear
basis for the regular (i.e. polynomial) functions on the character variety
(the space of flat $\mathrm{SL}_{2}$-local systems $\Phi$ modulo gauge). As a
consequence $C_{\lambda}$ can be in principle determined from
$\det\tilde{K}(\Phi)$ as $\Phi$ varies over flat connections. Mysteriously,
even though for a finite graph $\det\tilde{K}(\Phi)$ is a polynomial function
of the matrix entries, and the sum (6.2) is a finite sum, it is not at all
clear how to extract the individual $C_{\lambda}$ from it.

######  Problem 5.

How can one extract $C_{\lambda}$ from $\det\tilde{K}(\Phi)$ as in (6.2)?

For an example where we know how to extract these coefficients, consider the
simplest nontrivial case when $\Sigma$ is an annulus. Suppose graph
$\mathcal{G}$ is drawn on an annulus with flat connection having monodromy $A$
around the nontrivial isotopy class $\gamma$, the generator of
$\pi_{1}(\Sigma)$. Then a simple lamination on $\mathcal{G}$ just consists in
some number $n$ of copies of loops each isotopic to $\gamma$ (we are ignoring
orientation). The isotopy classes $\Lambda_{2}$ are thus in correspondence
with the set of nonnegative integers. We can write

$\det\tilde{K}(A)=\sum_{j=0}^{\infty}C_{j}\mathrm{Tr}(A)^{j}.$

From this expression it is easy to extract $C_{j}$: let $\mathrm{Tr}(A)=z$,
then the $C_{j}$ are power series coefficients of $\det\tilde{K}(A)$.

The next simplest planar surface is a disk with two small disks $p_{1},p_{2}$,
removed (also known as a “pair of pants”). In this case the space
$\Lambda_{2}$ has a simple parameterization by $(\mathbb{Z}_{+})^{3}$ where
$(i,j,k)$ corresponds to the lamination with $i,j,$ and $k$ loops surrounding
respectively $p_{1}$ only, $p_{2}$ only or both $p_{1}$ and $p_{2}$, see
Figure 5.

Figure 5. Simple laminations on a pair of pants consist in three kinds of
loops: those surrounding $p_{1},p_{2}$ or both.

If $A,B$ are the monodromies around $p_{1},p_{2}$ respectively then given any
$x,y,z\in\mathbb{C}^{*}$ we can choose $A,B$ in $\mathrm{SL}_{2}(\mathbb{C})$
so that $x=\mathrm{Tr}(A),y=\mathrm{Tr}(B),z=\mathrm{Tr}(AB)$. Then one can
extract $C_{i,j,k}$ by a contour integral

$C_{i,j,k}=\frac{1}{(2\pi i)^{3}}\int_{(S^{1})^{3}}\frac{\det
K(\Phi)}{x^{i}y^{j}z^{j}}\frac{dx}{x}\frac{dy}{y}\frac{dz}{z}.$

For a general punctured surface Fock and Goncharov [3] describe a different
(and orthogonal) basis on the space of laminations, the “Peter-Weyl basis”,
and show that the basis
$\\{\mathrm{Tr}(\phi_{\lambda})\\}_{\lambda\in\Lambda_{2}}$ is obtained from
the Peter-Weyl basis by an upper triangular transformation. One route to
solving Problem 5 would be to write down this base-change matrix.

##  7\. $n$-fold dimer model

###  7.1. $n$-multiwebs

An _$n$ -multiweb_, or _$n$ -fold dimer cover_ in $\mathcal{G}$ is a function
$m:E\to\\{0,1,2,\dots,n\\}$ which sums to $n$ at each vertex. So a
$1$-multiweb is a dimer cover and a $2$-multiweb is a double dimer cover. A
union of $n$ single dimer covers is an $n$-multiweb, and every $n$-multiweb
occurs this way (although not uniquely).

Let $\mathcal{M}_{n}$ be the set of $n$-multiwebs of $\mathcal{G}$. The
natural probability measure on $\mathcal{M}_{n}$ is, like in the double dimer
case, the projection of the uniform measure on $\mathcal{M}^{n}$ under the
standard map $\mathcal{M}^{n}\to\mathcal{M}_{n}$. Unlike the $n=2$ case, the
size of the preimage is difficult to compute in general, in fact
$\\#$P-complete: if $n=3$ and a $3$-multiweb is a trivalent graph (that is,
all edges have multiplicity $1$), then the triples of dimer covers in the
preimage are in bijection with edge $3$-colorings, or Tait colorings. Tait
colorings are colorings of the edges with three colors so that each color
appears at each vertex. For planar graphs Tait colorings are dual to proper
$4$-colorings of the vertices of the dual graph.

###  7.2. Kasteleyn matrix

Consider $\mathcal{G}$ a planar bipartite graph with an
$\mathrm{SL}_{n}$-local system $\Phi$. Let $K=(K_{wb})$ be a Kasteleyn matrix
for $\mathcal{G}$; $K$ is an $N\times N$ matrix with entries in
$M_{n}(\mathbb{R})$. Let $\tilde{K}$ be the $nN\times nN$ matrix obtained from
$K$ by replacing each entry with its $n\times n$ array of reals.

By a theorem of [2],

(7.1) $\det\tilde{K}(\Phi)=\sum_{m\in\mathcal{M}_{n}}\mathrm{Tr}(\phi_{m})$

where we still need to define the trace of an $n$-multiweb with an
$\mathrm{SL}_{n}$-connection; see the next section.

###  7.3. Trace of a $3$-multiweb

The trace of an $n$-multiweb $m$ is not simple to define; it is a contraction
of $n$-tensors defined at each vertex. We refer to [2] for the general
definition and give here a working definition for $n=3$. We cut each edge of
$\mathcal{G}$ into two half-edges, one associated with each of its vertices.
We consider colorings $c$ of the half-edges of $m$ with three colors
$\\{1,2,3\\}$, so that an edge of multiplicity $j\in\\{0,1,2,3\\}$ gets a set
of $j$ colors, and so that all colors appear at each vertex of $\mathcal{G}$.
See Figure 6.

Figure 6. $3$-coloring of the half-edges of $\mathcal{G}$.

Then on an edge $e$ of multiplicity $j$ we have two sets of colors $S,T$ of
size $j$, with $S$ located near the white vertex and $T$ near the black
vertex. We define

(7.2) $Tr(c)=\sum_{\text{colorings $c$}}sgn(c)\prod_{e}(\phi_{bw})_{S}^{T}$

where $(\phi)_{S}^{T}$ denotes the $S,T$ minor of $\phi$. Here $sgn(c)$ is a
sign depending on the cyclic order of colors at each vertex: at a black vertex
if the colors are in counterclockwise order we get sign $+$ and otherwise sign
$-$, and this convention is reversed at a white vertex; the product of these
signs over all vertices is $sgn(c)$. (For edges with multiplicity the colors
are assumed in natural order within that set.)

When $\Phi$ is the identity connection, and $m$ is planar, $|\mathrm{Tr}(m)|$
is the number of Tait colorings of $m$ (see [2]). In other words, all nonzero
terms of (7.2) have the same sign. The global sign of $\mathrm{Tr}(m)$ is
unimportant since it depends on an artificial choice of vertex ordering.

###  7.4. Flat connections and reduced $3$-webs

Suppose $\mathcal{G}$ is drawn on a multiply-connected planar domain $\Sigma$,
and $\Phi$ is a _flat_ $\mathrm{SL}_{3}$ connection.

A vertex in a $3$-multiweb is _trivalent_ if it has three adjacent edges of
multiplicity $1$. A $3$-multiweb consists in a collection of trivalent
vertices connected in pairs by chains of edges with multiplicities alternating
between $1$ and $2$ along the chains.

We say a $3$-multiweb is _reduced_ or _nonelliptic_ if each component,
considered as a planar graph by itself, has no contractible faces with $0,2$
or $4$ trivalent vertices.

There are certain _skein_ relations by which the trace of any $3$-multiweb can
be written as a linear combination of traces of reduced $3$-multiwebs (see
Figure 7).

Figure 7. Relations between $3$-multiwebs: a loop can be removed, increasing
the weight of the remaining web by a factor of $3$; a bigon can be replaced
with a single edge as shown multiplying the weight by $2$; a doubled edge can
be replaced with a single edge as shown, a square face can be resolved into a
linear combination of two webs.

The set of isotopy classes of the reduced $3$-multiwebs which arise from
reducing a given web are well defined.

As a consequence for a flat $SL_{3}$-connection we can group the terms in the
sum (7.1) according to isotopy classes of reduced $3$-multiwebs:

(7.3)
$\det\tilde{K}(\Phi)=\sum_{\lambda\in\Lambda_{3}}C_{\lambda}\mathrm{Tr}(\phi_{\lambda}).$

By a Theorem of Sikora and Westbury [10], the functions $\mathrm{Tr}(\lambda)$
as $\lambda$ runs over $\Lambda_{3}$ form a linear basis for the regular (i.e.
polynomial) functions on the character variety of flat $SL_{3}$-local systems
modulo gauge. As a consequence $C_{\lambda}$ can be in principle determined
from $\det\tilde{K}(\Phi)$ as $\Phi$ varies over flat connections.

######  Problem 6.

How can one extract $C_{\lambda}$ from $\det\tilde{K}(\Phi)$?

Applying the skein relations to a non-reduced $3$-multiweb results in a
collection of reduced webs which depends on the order in which the skein
relations are applied. Even though the isotopy classes of the reduced web are
well-defined, the individual webs themselves will depend on the order. Is
there a way to make a canonical choice in this reduction process, so that
starting from a random $3$-multiweb we arrive at a well-defined, canonical
probability measure on reduced $3$-multiwebs?

## References

  * [1] A. Abrams, R. Kenyon, Fixed-energy harmonic functions. Discrete Anal. 2017, Paper No. 18, 21 pp.
  * [2] D. Douglas, R. Kenyon, H. Shi, Dimers, webs, and local systems, arxiv:2205.05139
  * [3] V. Fock, A. B. Goncharov, Moduli spaces of local systems and higher Teichmüller theory, Publ. Math. Inst. Hautes Études Sci.,103, (2006), pp 1–211
  * [4] P. Kasteleyn, Dimer statistics and phase transitions. J. Mathematical Phys. 4 (1963), 287–293.
  * [5] R. Kenyon, Local statistics of lattice dimers. Ann. Inst. H. Poincaré Probab. Statist. 33 (1997), no. 5, 591–618.
  * [6] R. Kenyon, Lectures on dimers. Statistical mechanics, 191–230, IAS/Park City Math. Ser., 16, Amer. Math. Soc., Providence, RI, 2009.
  * [7] G. Kuperberg, An exploration of the permanent-determinant method. Electron. J. Combin. 5 (1998), no. 1, Research Paper 46, 34 pp.
  * [8] L. Lovasz, M. Plummer, Matching theory. North-Holland Mathematics Studies, 121. Annals of Discrete Mathematics, 29. North-Holland Publishing Co., Amsterdam.
  * [9] A. S. Sikora. $\text{SL}_{n}$-character varieties as spaces of graphs. Trans. Amer. Math. Soc., 353 (2001): 2773â–2804, .
  * [10] A. S. Sikora and B. W. Westbury. Confluence theory for graphs. Algebr. Geom. Topol., 7:439–478, 2007.
  * [11] L. G. Valiant, The Complexity of Computing the Permanent. Theoretical Computer Science. Elsevier. 8 (2): 189–201 (1979)