# Automatic Learning to Detect Concept Drift

Hang Yu1 Tianyu Liu1 Jie Lu1&Guangquan Zhang1 1Australian Artificial
Intelligence Institute, University of Technology Sydney. Australia. {hang.yu,
<EMAIL_ADDRESS>{Jie.Lu<EMAIL_ADDRESS>
###### Abstract

Many methods have been proposed to detect concept drift, i.e., the change in
the distribution of streaming data, due to concept drift causes a decrease in
the prediction accuracy of algorithms. However, the most of current detection
methods are based on the assessment of the degree of change in the data
distribution, cannot identify the type of concept drift. In this paper, we
propose Active Drift Detection with Meta learning (Meta-ADD), a novel
framework that learns to classify concept drift by tracking the changed
pattern of error rates. Specifically, in the training phase, we extract meta-
features based on the error rates of various concept drift, after which a
meta-detector is developed via a prototypical neural network by representing
various concept drift classes as corresponding prototypes. In the detection
phase, the learned meta-detector is fine-tuned to adapt to the corresponding
data stream via stream-based active learning. Hence, Meta-ADD uses machine
learning to learn to detect concept drifts and identify their types
automatically, which can directly support drift understand. The experiment
results verify the effectiveness of Meta-ADD.

##  1 Introduction

Concept drift is a hot research topic in data stream mining He et al. (2019),
incremental learning Losing et al. (2018), nonstationary learning Pratama and
Wang (2019), and it can be further extended to machine learning. In the
machine learning area, concept drift is a phenomenon in which the statistical
properties of the predicted variable change over time in an arbitrary way Lu
et al. (2017). This causes the predictions to become less accurate as time
passes, and therefore needs to be detected. Figure 1 shows the four types of
concept drift, categorized according to the changed pattern of data
distribution Gama et al. (2014).

Figure 1: Types of concept drift.

In the two recent decades, although many methods of detecting concept drift
have been proposed, they all, in general, follow a framework Lu et al. (2019)
which includes four steps: 1) data retrieval aims to retrieve data chunks from
data streams; 2) data modeling aims to abstract the retrieved data and extract
the key features; 3) test statistics calculation is the measurement of
dissimilarity, or distance estimation de Lima Cabral and de Barros (2018); 4)
hypothesis testing uses a specific hypothesis test to evaluate the statistical
significance of the change observed in step 3, or the p-value.

However, this framework faces two drawbacks: the first is the cold start
problem. In current drift detection methods, an initial window is needed to
collect the basic statistic properties for the hypothesis test. As a result,
no detection strategies can be implemented in the initial window, but there
may be concept drift in the initial window. The second is, to the best of our
knowledge, the existing methods can only identify whether concept drift has
occurred, but they are unable to identify what type of concept drift has
occurred. The reason for this is that although the change of data distribution
can be represented by test statistics such as average error rate, test
statistics cannot represent the changed pattern of data distribution, i.e.,
the relationship between concept drift at adjacent timestamps cannot be
captured. In practice, knowing the type of concept drift is useful to
understand them. For example, if a person’s weight suddenly decreases, this
may indicate he has health problems which should be addressed instantly, but
if a person’s weight gradual decreases over a long time, such as over one
year, the situation may be normal because the man is making an effort to lose
weight.

In this paper, we propose a novel framework to learn a meta-detector with the
ability to classify concept drift which can be trained in advance. When a data
stream is inputted, it can be used to directly classify concept drift without
setting an initial window. However, this framework faces two main challenges.
On the one hand, although concept drift can be classified into four types, the
presentations, i.e., changed pattern of data distribution, of one type of
drifts is infinite possibly over 1000000. By contrast, the presentations of
this type of drifts, which are included in training data, are very small
possibly 1000. On the other hand, for each type of concept drift, each data
stream may have its own unique presentation, so the meta-detector must have
the ability to be able to adjust to fit the detected data stream. To address
these two challenges, we propose Active Drift Detection with Meta learning
(Meta-ADD). The contributions of this paper are summarized as follows:

  * •

We propose a framework that learns to detect drift by learning the
presentation of each type of concept drift. As a result, in our framework, not
only can concept drift be detected, the type of drift can also be identified
to help us understand them.

  * •

We propose to transform the pre-training of a meta-detector into a few-shot
learning problem, and thereby proposing a meta-learning method Finn et al.
(2017) based on prototypical-networks Snell et al. (2017) to learn the meta-
detector. In this meta-detector, various concept drift classes can be
represented as a corresponding single prototype.

  * •

To improve the accuracy of detecting concept drift, we propose a stream-based
active learning algorithm (SAL) which is capable of handling various concept
drifts by adapting the meta-detector to the underlying distribution in the
stream.

The rest of this paper is organized as follows. Section 2 presents the related
work. Section 3 provides the details of our proposed Meta-ADD framework.
Section 4 discusses the experiment results for several well-known datasets in
this research area. Finally, Section 5 concludes the paper and presents the
future work.

##  2 Related work

The survey of the literature related to drift detection methods reveals that
in general, these can be divided into three categories:

###  2.1 Error Rate-based Drift Detection

Error rate-based drift detection methods form the largest category of drift
detection algorithms. The intuition behind this type of algorithms is to
monitor fluctuations in the error rate as time passes. Once the change of the
error rate is proven to be statistically significant, a drift alarm will be
triggered. One of the top referenced this type of algorithms is the Drift
Detection Method (DDM) Gama et al. (2004) which was the first algorithm to
contain defined warning and drift levels for signalling concept drift. Many
subsequent algorithms have adopted a similar implementation, e.g., Early Drift
Detection Method (EDDM) Baena-Garcıa et al. (2006), Heoffding’s inequality-
based Drift Detection Method (HDDM) Frías-Blanco et al. (2015) and based on
the Kolmogorov-Smirnov (KS) statistical test. In contrast to methods such as
DDM, a two-time window-based drift detection algorithm called Adaptive
Windowing (ADWIN) Bifet and Gavalda (2007) was proposed. In ADWIN, the size of
the compared windows can be adjusted automatically.

###  2.2 Data Distribution-based Drift Detection

The second largest category of drift detection algorithms is data
distribution-based drift detection. In this category of algorithms, the
dissimilarity between the distribution of new data and historical data is
quantified by using a distance metric. Once the dissimilarity is proven to be
statistically significantly different, a drift alarm will be triggered.
According to the literature, the first formal treatment of change detection in
data streams was proposed by Kifer et al. (2004). Another typical data
distribution-based drift detection algorithm is the Information-Theoretic
Approach (ITA) Dasu et al. (2006). Similar implementations have been adopted
in the Competence Model-based drift detection (CM) Lu et al. (2014), Equal
Density Estimation (EDE) Yu et al. (2020), and Local Drift Degree-based
Density Synchronized Drift Adaptation (LDD-DSDA) Liu et al. (2017).

###  2.3 Multiple Hypothesis Test Drift Detection

Multiple hypothesis test drift detection algorithms apply similar techniques
to those mentioned in the previous two categories. The novelty of this type of
algorithms is that the multiple hypothesis tests is used to detect concept
drift in different ways. For example, the Just-In-Time adaptive classifier
(JIT) Alippi and Roveri (2008) is the first algorithm to set multiple drift
detection hypotheses in this way, but Hierarchical Change-Detection Tests
(HCDTs) Alippi et al. (2017) is the first attempt to address concept drift
using a hierarchical architecture.

##  3 Active Drift Detection with Meta-learning

In this section, we elaborate on the Active Drift Detection with Meta learning
(Meta-ADD). Meta-ADD includes two main phases: training phase and detection
phase. During the training phase, we extract the meta-features of various
concept drifts, and then learn a meta-detector where various concept drift
classes can be represented as a corresponding single prototype Shao et al.
(2018). In the detection phase, the learned meta-detector is used to detect
concept drift and is further fine-tuned via stream-based active learning
Krawczyk and Cano (2019).

###  3.1 Extracting Meta-Features

In this subsection, we describe the extraction of the meta-features that can
be used across different datasets. Although there are four types of concept
drift, the reoccurring concept type focuses on tracking whether an old concept
occurs again. In contrast, our work focuses on detecting concept drift
immediately instead of considering whether a concept is an old concept. So we
did not use the reoccurring concept type and instead used a concept type we
named normal to indicate that there was no concept drift. It is proved that a
change in the data distribution can be represented by a change of error rates,
so intuitively, the change of error rate is critical for deciding which type
of concept drift has occurred:

  * •

Sudden drift: the error rate will decrease sharply within a short time.

  * •

Gradual drift: the error rate will fluctuate over a period of time.

  * •

Incremental drift: the error rate will increase incrementally over a period of
time.

  * •

Normal: the error rate will remain stable.

Based on the intuitions above, we empirically extract the gap between the
average error rates of two windows as meta-features. Specifically, for each
type of concept drift, we first generate $N$ number of data streams. A
prediction model such as Neural network, decision tree or SVR was directly
applied to a data stream to obtain error rate $e_{t}$ at each timestamp $t$.
In addition, we use a window $W_{i}$ with $n$ length, that is, there are $n$
number of samples in $W_{i}$, so the average error rates of $W_{i}$ are
calculated as:

$\hat{e}_{i}=\frac{\sum_{t=1}^{n}e_{i}}{n}$ (1)

Furthermore, the gap between the average error rates of two windows is
calculated as:

$Gap_{i}=\hat{e}_{i+1}-\hat{e}_{i}$ (2)

Assume there are $m=l\times n$ samples in each data stream, so $l$ number of
windows can be obtained, and thereby $l-1$ is the number of $Gap_{i}$ which
can be obtained. Hence, a training sample in meta-training is represented as
$G_{i}:\\{\hat{X}\times\hat{y}\\}\in\mathbb{R}^{l}$, where
$\hat{X}=\left\\{Gap_{1},\ldots,Gap_{l-1}\right\\}$, and $\hat{y}\in
1,\ldots,K$ is the corresponding labels, and thereby an original dataset with
$N$ number of data streams, i.e., $g:\\{X\times y\\}^{N\times m}$, is mapped
to $G:\\{\hat{X}\times\hat{y}\\}\in\mathbb{R}^{N\times l}$, such that $G$ is
less dependent on the dataset.

Note that our framework allows flexibility in the choice of features. For
example, we may be able to improve the performance by using different
predicted models or a more intelligent windowing strategy. To make our
contribution focused, we adopt simple models and tumbling windows in all our
experiments, which results in a reasonable performance based on our empirical
results. How we can better model the transferable information will be
interesting future work to enhance the Meta-ADD framework.

###  3.2 Meta-detector via a Prototypical Neural Network

In this subsection, a prototypical neural network is applied to extract meta
features from various data streams. The concept drift detection issue is
considered to be a classification task by learning a neural network for
mapping the data stream into an embedding space and extracting prototypes for
various concept drift categories to be the mean vector of the embedded support
data stream. The detection of concept drift is performed for the embedded data
stream by selecting the nearest concept drift prototype.

Figure 2: The prototypical neural network. (The left side is the whole
structure of prototypical neural network, which consists of embedding and
clustering phase; in the right side the new sample is classified by finding
the nearest prototype over a distance in the embedding space)

Based on the support dataset $G$, the prototypical neural network consists of
two steps, as illustrated in Figure 2. First, an em embedding neural network
$f_{\theta}:\mathbb{R}^{l}\rightarrow\mathbb{R}^{M}$ with the learnable
parameter $\theta$ maps the stream data $X_{i}$ into the embedding space
$f_{\theta}\left(X_{i}\right)$, then a single prototype representation $c_{k}$
for each class $k$ can be taken as the mean of its support set in the
embedding space:

$c_{k}=\frac{1}{\left|S_{k}\right|}\sum_{\left(X_{i},y_{i}\right)\in
R}f_{\theta}\left(\hat{X}_{i}\right)$

where $S_{k}$ is the set of stream data with label $k$. Given a distance
function $d:\mathbb{R}^{M}\times\mathbb{R}^{M}\rightarrow\mathbb{R}$, eg.
cosine similarity, classification is then performed for a query point $X$ by
finding the nearest prototype $c_{k}$ over a distance in the embedding space:

$p_{\theta}(\hat{y}=k\mid\hat{x})=\frac{\exp\left(-d\left(f_{\theta}(\hat{x}),c_{k}\right)\right)}{\sum_{k^{\prime}}\exp\left(-d\left(f_{\theta}(\hat{x}),c_{k^{\prime}}\right)\right)}$

We then use negative log-likelihood function $J(\theta)=-\log
p_{\theta}(y=k\mid\hat{x})$ as the training objective. During the training
phase, $N_{s}$ examples are selected randomly for each concept drift class to
represent the prototype in the embedding space, then $N_{q}$ samples are
chosen randomly as the query set to measure the estimation accuracy of the
learned meta learner. The pseudocode to train the model is provided in
Algorithm 1.

Algorithm 1 training meta-detector

Input: training data steam
$G:\left\\{\left(X_{1},y_{1}\right),\ldots,\left(X_{l},y_{l}\right)\right\\}$,
where the corresponding label $y_{i}\in 1,\ldots,K$, $D_{k}$ is the set of
stream data with label $k$.
Parameter: the number of support data stream $N_{s}$, the number of query data
stream $N_{q}$, the number of concept drift class $K$.
Output: the training loss of $J(\theta)$
1: for $k$ in $\\{1,\ldots,K\\}$
2: $S_{k}\leftarrow$ RAMDOMSAMPLE $\left(D_{k},N_{s}\right)$
3: $Q_{k}\leftarrow$ RANDOMSAMPLE $\left(D_{k},N_{a}\right)$
4:
$c_{k}=\frac{1}{N_{s}}\sum_{\left(X_{i},y_{i}\right)}f_{\theta}\left(X_{i}\right)$
5: end for
6: $J\leftarrow 0$
7: for $k$ in $\left\\{1,\ldots,N_{q}\right\\}$
8: for $(x,y)$ in $Q_{k}$
8:
$J=J-\frac{1}{KN_{q}}\log\frac{\exp\left(-d\left(f_{\theta}({x}),c_{k}\right)\right)}{\sum_{k^{\prime}}\exp\left(-d\left(f_{\theta}({x}),c_{k^{\prime}}\right)\right)}$
10: end for
11: end for

###  3.3 Active Drift Detection

Although a meta-detector can be obtained in the training process and can be
directly applied to detect concept drift, the representation of each type of
concept drift on different data streams can vary and each has unique
characteristics. Hence, when the meta-detector is applied to a data stream, it
must be able to adapt to this data stream to achieve better performance.

To update the meta-detector, when we collect a sample
$S_{i}=\left\\{e_{i-i},\ldots e_{i}\right\\}$ where $e_{i}$ is the obtained
error rate at timestamp $i$, we need to know the true type of concept drift
which has occurred on this sample to update the meta-detector. However,
unfortunately, the true type of concept drift is unknown. Although the true
type can be inputted manually (label cost), the label cost is too expensive if
the true label is manually input as soon as sample $S_{i}$ is collected.
Hence, only the most valuable samples for labeling to update the meta-detector
are used.

In Meta-ADD, the meta-detector denotes the probability $P(c)$ that sample
$S_{i}$ belongs to class $c$, where $\sum_{c\in C}P(c)=1$. Then, the entropy
of classification can be calculated as:

$H(C)=-\sum_{c\in C}P(c)\log p(c)$ (1)

The entropy means the uncertainty of classification. A larger entropy means
the type of this concept drift is more uncertain, and therefore this type of
concept drift needs to be labelled manually.

The structure of the proposed Meta-ADD algorithm is shown in Figure 3.

Figure 3: Structure of Meta-ADD algorithm.

##  4 Experiments

To evaluate the Meta-ADD, we conducted four experiments. The first two
experiments described in Section 4.1 were designed to analyze the
effectiveness of Meta-ADD in identifying the type of concept drift which has
occurred. The third experiment described in Section 4.2 compares the
difference in the performance of other drift detection algorithms and Meta-ADD
on toy datasets with known drifts. The fourth experiment described in Section
4.3 evaluates the strengths and weaknesses of Meta-ADD on real-world datasets
with unknown drifts. All experiments are implemented in Python 3.7 version on
Windows 10 running on a PC with system configuration Intel Core i7 processor
(2.80 GHz) with 16-GB RAM.

###  4.1 Demonstration of Meta-ADD

####  4.1.1 Experiment 1. Drift detection on data streams with different meta-
learning structures

In this experiment, we focus on investigating how meta-learning impacts
learning performance, because, in our proposed Meta-ADD, the quality of the
detector depends on the results of meta-learning, and the results of meta-
learning depend on the structure of prototypical-networks. Hence, the
intuition is to generate a set of data streams with predefined types of
concept drift, and then observe the results when Meta-ADD with different types
of prototypical-networks and parameters is applied to those streams. We expect
to see that meta-learning enables our detector to classify concept drift.

Experiment Settings. First, based on Python package skmultiflow Montiel et al.
(2018) (version 0.5.3), we generate a total of 8000 data streams, and each
data stream has 2000 instances to simulate the prequential prediction errors
of a learning model. Furthermore, each data stream only has one type of drift.
Then, we select 1250 data streams from each type of concept drift, i.e., a
total of 5000 data streams, as an original training dataset to extract meta-
features. The remaining data streams are mixed as testing datasets. GaussianNB
is imported from sklearn Pedregosa et al. (2011) as the default learning model
because it has a fast-processing speed and a partial fit option. As for the
structures of the prototypical neural network, two embedding functions: a
4-layered fully connected neural network and recurrent neural network are
selected as the nonlinear mapping. In the training phase, for each concept
drift category, 5 support data streams are chosen randomly to act as the
prototype and 15 query data streams are selected to evaluate the performance
of the model. During the testing phase, 20 support data streams are randomly
selected from the training dataset to perform as the final prototype. For all
the experiments, ReLU activations are applied and the distance function is the
cosine similarity function. All our models are trained via SGD with Adam, with
a learning rate of $10^{-3}$.

Type | Network | Acc
---|---|---
Sudden | FCN | 98.5%
RNN | 32.3%
Gradual | FCN | 94.2%
RNN | 53.4%
Incremental | FCN | 91.3%
RNN | 52.1%
Normal | FCN | 93.8%
RNN | 82.2%
Table 1: Accuracy of different deep structures. (Acc is the abbreviation of
accuracy; 50-25 means the number of meta-features is 50 and the sampling
frequency is 25.)

Findings and Discussion. The results of Experiment 1 are shown in Table 1.
From Table 1, we can see Meta-ADD was able to identify the simulated concept
drifts and, overall, the results were in line with expectations, in that the
FCN achieves the better performance because the relationship between samples
in a data stream is not required strong. In addition, we can see each type of
concept drift, with same settings, performed differently.

####  4.1.2 Experiment 2. Drift Detection on data streams with different meta-
features

In this experiment, we focus on investigating how the meta-features impact
learning performance. However, in our proposed Meta-ADD, extracting meta-
features depends on two parameters $l$ and $n$, where $l$ means the number of
meta-features, $n$ means the sampling frequency. Hence, the intuition is to
generate a set of data streams with a predefined type of concept drift, and
then observe the results when Meta-ADD with different $l$ and $n$ is applied
to these streams. We expect to see Meta-ADD with different $l$ and $n$ perform
differently on classifying concept drifts.

Experiment Settings. We again chose GaussianNB as the default learning model
and the same parameter settings as in Experiment 1. Based on the results of
experiment 1, the deep structure of meta-learning is implemented on FCN.
However, to explore the influence of $l$ and $n$ when extracting the meta-
features, the number of meta-features $l$ was changed within the set
$l_{{vaild}}\in\\{50,100,200\\}$, and the sampling frequency $n$ was also
changed within the set $n_{{vaild}}\in\\{1,25,50\\}$.

| $n=1$ | $n=25$ | $n=50$
---|---|---|---
$l=50$ | 71.92% | 86.45% | 92.57%
$l=100$ | 73.83% | 72.53% | 94.56%
$l=200$ | 70.42% | 72.98% | 90.68%
Table 2: Accuracy of different meta-features

Findings and Discussion. The results of Experiment 2 are plotted in Table 2.
From Table 2, two interesting points are worth mentioning: first is we can see
that $l$ and $n$ influence the prediction accuracy. However, the relationship
between the accuracy of the drift detection, the number of meta-features $l$,
and the sampling frequency $n$, respectively, is not the same. When the $n$
increases, the prediction accuracy increases in general. In contrast, when the
$l$ increases, the prediction accuracy may decreases.

###  4.2 Stream Learning on Toy Datasets with Simulated Concept Drift

####  4.2.1 Experiment 3. Drift Detection on Toy Datasets

In this experiment, we focus on investigating the performance of Meta-ADD
compared to current drift detection methods. However, current drift detection
methods cannot classify concept drift, so we only compare the prediction error
based on extreme cases. We generate a set of data streams with a predefined
type of drift, drift frequencies and severities to simulate the prequential
prediction errors of a learning model with different drift detection methods.
If there are less prediction errors, this means that the performance of the
drift detection method is better. We expect to see that the learning model
with our proposed meta-ADD achieves the best performance on different data
streams with different concept drifts.

Experiment Settings. GaussianNB is again choses as the default learning model.
The toy datasets were generated by skmultiflow’s built-in data generation
functions. We chose SEA generator, Rotating Hyperplane generator, AGR
(AGRAWAL) generator, RTG (Random Tree Generator) and RBF generator. All
generators generate 10000 samples. The compared algorithms were ADWIN, DDM,
EDDM, HDDM-A, HDDM-W, Page-Hinkley, KSWIN implemented in skmultiflow with
their advised drift thresholds. We use the parameters with the best
performance in experiment 1 to train the model and set $l$ to 100 and $n$ to 1
to extract the meta-features.

| SEA | HYP | AGR | RBF | RTG
---|---|---|---|---|---
| Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1 | Acc | F1
* | 83.7% | Nan | 81.6% | Nan | 70.3% | Nan | 69.3% | Nan | 64.5% | Nan
*+ADWIN | 84.3% | 0.62 | 81.6% | 0.00 | 71.3% | 0.50 | 69.3% | 0.00 | 64.5% | 0.00
*+DDM | 83.7% | 0.00 | 86.1% | 0.63 | 71.2% | 0.50 | 71.5% | 0.66 | 64.5% | 0.00
*+EDDM | 84.0% | 0.38 | 86.1% | 0.63 | 65.1% | 0.25 | 67.8% | 0.38 | 65.2% | 0.38
*+HDDM-A | 84.7% | 0.69 | 81.6% | 0.00 | 72.3% | 0.63 | 69.3% | 0.00 | 64.5% | 0.00
*+HDDM-W | 84.5% | 0.63 | 86.4% | 0.70 | 72.4% | 0.63 | 69.8% | 0.50 | 66.3% | 0.55
*+Page-Hinkley | 85.0% | 0.71 | 81.6% | 0.00 | 71.4% | 0.50 | 69.3% | 0.00 | 64.5% | 0.00
*+KSWIN | 84.1% | 0.38 | 86.2% | 0.66 | 71.5% | 0.50 | 69.9% | 0.63 | 65.2% | 0.38
*+Meta-DD | 86.1% | 0.77 | 87.8% | 0.83 | 73.2% | 0.69 | 72.2% | 0.71 | 67.4% | 0.70
*+Meta-ADD | 89.2% | 0.85 | 91.1% | 0.89 | 74.6% | 0.79 | 73.7% | 0.74 | 68.9% | 0.75
| * represents the GaussianNB algorithm. Nan means null value, and 0.0
indicates that no drifts have been
---
detected.
Table 3: Experiment results on toy datasets | Elec | Weather | Spam | Air | Poke
---|---|---|---|---|---
| Acc | DN | Acc | DN | Acc | DN | Acc | DN | Acc | DN
* | 73.9% | 0 | 68.7% | 0 | 89.3% | 0 | 58.1% | 0 | 51.2% | 0
*+ADWIN | 79.1% | 46 | 69.5% | 8 | 92.4% | 3 | 62.2% | 70 | 54.2% | 1
*+DDM | 82.1% | 117 | 70.3% | 3 | 91.9% | 8 | 61.9% | 17 | 54.2% | 1
*+EDDM | 82.6% | 115 | 73.7% | 49 | 93.4% | 13 | 61.5% | 178 | 54.2% | 1
*+HDDM-A | 83.0% | 123 | 72.3% | 29 | 92.1% | 4 | 62.6% | 122 | 54.5% | 4
*+HDDM-W | 82.7% | 99 | 72.6% | 38 | 92.2% | 2 | 61.5% | 617 | 52.0% | 604
*+Page-Hinkley | 78.2% | 17 | 69.6% | 5 | 91.8% | 1 | 62.8% | 63 | 54.1% | 15
*+KSWIN | 81.4% | 91 | 67.8% | 45 | 92.4% | 5 | 61.3% | 664 | 53.6% | 306
*+Meta-DD | 83.5% | 125 | 74.0% | 50 | 94.5% | 12 | 63.9% | 155 | 55.7% | 267
*+Meta-ADD | 85.7% | 101 | 76.1% | 55 | 95.2% | 11 | 64.7% | 136 | 56.1% | 202
DN represents the number of detected drifts.
Table 4: Experiment results on real-world datasets

Findings and Discussion. The results of Experiment 3 are shown in Table 3. In
general, the prediction accuracy of Meta-Add is better than the other drift
detection methods over all data streams. In addition, Table 3 also shows Meta-
ADD has the largest F1 score, i.e., detecting concept drift by Meta-ADD is
more authentic. Thus, our proposed Me-ta-ADD achieves better performance than
current drift de-tection methods. A comparison of the two last lines of Table
3 shows that the performance of Meta-ADD was improved by active learning.

###  4.3 Stream Learning on Real-world datasets

####  4.3.1 Experiment 4. Drift Detection on Real-word Datasets

This experiment investigates whether our proposed Meta-ADD continues to obtain
the best performance on real-world concept drift evaluation datasets. We
expect to see similar results to those of Experiment 3.

Experiment Settings. The basic settings are the same as Experiment 3. The main
difference is that we used a group of real-world datasets with unknown drift,
and these were most often used to evaluate the performance of drift detection
methods. These datasets were Bifet et al. (2010):

  * •

Elec: the Electricity Price Dataset has 45325 samples and each sample has 9
features

  * •

Weather: the NAOO Weather Dataset has 18712 samples and each sample has 9
features.

  * •

Spam: the Spam Filtering Dataset has 9829 samples and each sample has 501
features.

  * •

Air: the Airline Delay Dataset has 539395 samples and each sample has 8
features.

  * •

Poke: the Poker Hand Dataset has 923720 samples and each sample has 11
features.

In the Elec, Weather, Spam datasets, parameters $l$ and $n$ were set to 100
and 1, respectively. In the remaining datasets, parameters $l$ and $n$ were
set to 100 and 25, respectively.

Findings and Discussion. The learning accuracies of the different drift
detection methods appear in Table 4. From Table 4, we can see Meta-ADD
continues to obtain the best performance on all datasets. In addition, we
compared the number of drifts detected using different settings of parameters
$l$ and $n$. In general, with an increase in $l$ and $n$, the number of
detected drifts decreases. For example, in the Elec dataset, when parameter
$l=50$, but $n$ increases from 1 to 25, the number of detected drifts
decreases from 158 to 28.

##  5 Conclusion

In this paper, we propose a novel framework named Meta-ADD to learn a meta-
detector for detecting concept drift. Different to the current drift detection
methods, Meta-ADD does not rely on rules set by humans to judge whether
concept drift has occurred, rather it proves that machines can be offline
trained to classify concept drift, and thereby solve problems facing the
existing current drift detection methods, i.e., cold start and an inability to
classify concept drift. Hence, compared with current methods, using Meta-ADD
to detect concept drift can better understand them. Extensive experimental
results also show the effectiveness of Meta-ADD.

## References

  * Alippi and Roveri [2008] Cesare Alippi and Manuel Roveri.  Just-in-time adaptive classifiers—part i: Detecting nonstationary changes.  IEEE Transactions on Neural Networks, 19(7):1145–1153, 2008.
  * Alippi et al. [2017] C. Alippi, G. Boracchi, and M. Roveri.  Hierarchical change-detection tests.  IEEE Transactions on Neural Networks and Learning Systems, 28(2):246–258, 2017.
  * Baena-Garcıa et al. [2006] Manuel Baena-Garcıa, José del Campo-Ávila, Raúl Fidalgo, Albert Bifet, R Gavalda, and R Morales-Bueno.  Early drift detection method.  In Fourth international workshop on knowledge discovery from data streams, volume 6, pages 77–86, 2006.
  * Bifet and Gavalda [2007] Albert Bifet and Ricard Gavalda.  Learning from time-changing data with adaptive windowing.  In Proceedings of the 2007 SIAM international conference on data mining, pages 443–448. SIAM, 2007.
  * Bifet et al. [2010] Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Philipp Kranen, Hardy Kremer, Timm Jansen, and Thomas Seidl.  Moa: Massive online analysis, a framework for stream classification and clustering.  In Proceedings of the First Workshop on Applications of Pattern Analysis, pages 44–50. PMLR, 2010.
  * Dasu et al. [2006] Tamraparni Dasu, Shankar Krishnan, Suresh Venkatasubramanian, and Ke Yi.  An information-theoretic approach to detecting changes in multi-dimensional data streams.  In In Proc. Symp. on the Interface of Statistics, Computing Science, and Applications. Citeseer, 2006.
  * de Lima Cabral and de Barros [2018] Danilo Rafael de Lima Cabral and Roberto Souto Maior de Barros.  Concept drift detection based on fisher’s exact test.  Information Sciences, 442:220–234, 2018.
  * Finn et al. [2017] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 1126–1135, 2017.
  * Frías-Blanco et al. [2015] I. Frías-Blanco, J. d. Campo-Ávila, G. Ramos-Jiménez, R. Morales-Bueno, A. Ortiz-Díaz, and Y. Caballero-Mota.  Online and non-parametric drift detection methods based on hoeffding’s bounds.  IEEE Transactions on Knowledge and Data Engineering, 27(3):810–823, 2015.
  * Gama et al. [2004] Joao Gama, Pedro Medas, Gladys Castillo, and Pedro Rodrigues.  Learning with drift detection.  In Brazilian symposium on artificial intelligence, pages 286–295. Springer, 2004.
  * Gama et al. [2014] João Gama, Indrė Žliobaitė, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia.  A survey on concept drift adaptation.  ACM computing surveys (CSUR), 46(4):1–37, 2014.
  * He et al. [2019] Yi He, Baijun Wu, Di Wu, Ege Beyazit, Sheng Chen, Xindong Wu, et al.  Online learning from capricious data streams: A generative approach.  In IJCAI, pages 2491–2497, 2019.
  * Kifer et al. [2004] Daniel Kifer, Shai Ben-David, and Johannes Gehrke.  Detecting change in data streams.  In VLDB, volume 4, pages 180–191. Toronto, Canada, 2004.
  * Krawczyk and Cano [2019] Bartosz Krawczyk and Alberto Cano.  Adaptive ensemble active learning for drifting data stream mining.  In IJCAI, pages 2763–2771, 2019.
  * Liu et al. [2017] Anjin Liu, Yiliao Song, Guangquan Zhang, and Jie Lu.  Regional concept drift detection and density synchronized drift adaptation.  In IJCAI International Joint Conference on Artificial Intelligence, 2017.
  * Losing et al. [2018] Viktor Losing, Barbara Hammer, and Heiko Wersing.  Incremental on-line learning: A review and comparison of state of the art algorithms.  Neurocomputing, 275:1261–1274, 2018.
  * Lu et al. [2014] Ning Lu, Guangquan Zhang, and Jie Lu.  Concept drift detection via competence models.  Artificial Intelligence, 209:11–28, 2014.
  * Lu et al. [2017] Yang Lu, Yiu-ming Cheung, and Yuan Yan Tang.  Dynamic weighted majority for incremental learning of imbalanced data streams with concept drift.  In IJCAI, pages 2393–2399, 2017.
  * Lu et al. [2019] J. Lu, A. Liu, F. Dong, F. Gu, J. Gama, and G. Zhang.  Learning under concept drift: A review.  IEEE Transactions on Knowledge and Data Engineering, 31(12):2346–2363, 2019.
  * Montiel et al. [2018] Jacob Montiel, Jesse Read, Albert Bifet, and Talel Abdessalem.  Scikit-multiflow: A multi-output streaming framework.  The Journal of Machine Learning Research, 19(1):2915–2914, 2018\.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  the Journal of machine Learning research, 12:2825–2830, 2011.
  * Pratama and Wang [2019] Mahardhika Pratama and Dianhui Wang.  Deep stacked stochastic configuration networks for lifelong learning of non-stationary data streams.  Information Sciences, 495:150–174, 2019.
  * Shao et al. [2018] J. Shao, F. Huang, Q. Yang, and G. Luo.  Robust prototype-based learning on data streams.  IEEE Transactions on Knowledge and Data Engineering, 30(5):978–991, 2018.
  * Snell et al. [2017] Jake Snell, Kevin Swersky, and Richard Zemel.  Prototypical networks for few-shot learning.  In Advances in neural information processing systems, pages 4077–4087, 2017.
  * Yu et al. [2020] H. Yu, J. Lu, and G. Zhang.  Online topology learning by a gaussian membership-based self-organizing incremental neural network.  IEEE Transactions on Neural Networks and Learning Systems, 31(10):3947–3961, 2020.


# Connectedness of graphs arising from the dual Steenrod algebra

Donald M. Larson111The Catholic University of America, 620 Michigan Ave NE,
Washington DC 20064

###### Abstract

We establish connectedness criteria for graphs associated to monomials in
certain quotients of the mod 2 dual Steenrod algebra $\mathscr{A}^{*}$. We
also investigate questions about trees and Hamilton cycles in the context of
these graphs. Finally, we improve upon a known connection between the graph
theoretic interpretation of $\mathscr{A}^{*}$ and its structure as a Hopf
algebra.

Keywords. Steenrod algebra, Hopf algebras, graph theory.

Mathematics Subject Classification 2020. 55S10, 16T05, 05C90

##  1 Introduction

The mod 2 Steenrod algebra $\mathscr{A}_{*}$ and its dual $\mathscr{A}^{*}$
act on mod 2 cohomology and homology, respectively, making them indispensable
computational tools in homotopy theory at the prime 2. It is therefore
desirable to study these algebras from a variety of points of view (see, e.g.,
[5, 7, 8, 10] or the bibliography of [11]). The purpose of this paper is to
study the mod 2 dual Steenrod algebra $\mathscr{A}^{*}$ from the point of view
of graph theory, as first advocated by R. M. W. Wood in [11, §8] and
subsequently advanced by C. Yearwood in [12].

The algebra $\mathscr{A}^{*}$ has the structure of a graded polynomial
algebra. More precisely,
$\mathscr{A}^{*}=\mathbb{F}_{2}[\xi_{1},\xi_{2},\xi_{3},\ldots]$ where
$|\xi_{i}|=2^{i}-1$. Given an integer $n\geq 0$, we may form the truncated
polynomial algebra $\mathscr{A}^{*}(n)=\mathscr{A}^{*}/I(n)$, where

$I(n)=\left(\xi_{1}^{2^{n+1}},\xi_{2}^{2^{n}},\xi_{3}^{2^{n-1}},\ldots,\xi_{n+1}^{2},\xi_{n+2},\xi_{n+3},\ldots\right).$
(1)

Milnor [3] dualized these finite quotients over $\mathbb{F}_{2}$ to yield
finite subalgebras $\mathscr{A}_{*}(n)\subset\mathscr{A}_{*}$ that facilitate
computations of homotopy groups. For example, Adams spectral sequence
computations involving Ext for modules over $\mathscr{A}_{*}$ can sometimes be
done instead over $\mathscr{A}_{*}(n)$ for some $n$, via a change-of-rings
isomorphism [4, A1.3.12] (see also [1, §2] for concrete examples of this
phenomenon).

Wood gives a graph theoretic interpretation of the quotients
$\mathscr{A}^{*}(n)$ by associating to every monomial $x\in\mathscr{A}^{*}(n)$
a graph, which by abuse of notation we shall also denote $x$, on the vertex
set $\\{2^{0},2^{1},\ldots,2^{n+1}\\}$. We shall describe the construction of
these graphs in Section 2. Let us write
$x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}$, where $0\leq
r_{i}\leq 2^{n+2-i}-1$ and where each $r_{i}$ has the dyadic expansion

$r_{i}=\sum_{m=0}^{n+1-i}a_{n+1-m,n+1-i-m}2^{n+1-i-m}.$ (2)

Our first theorem gives connectedness criteria for $x$ using only the data of
its underlying monomial.

######  Theorem 1.1.

The graph $x$ is connected if and only if the integers

$C(p,q):=\sum_{t=1}^{n+1}\sum_{T}\prod_{k=1}^{t}a_{\min(p_{k-1},p_{k}),\max(p_{k-1},p_{k})}$
(3)

are positive for all $0\leq p<q\leq n+1$, where $T$ is the set of all
$(t+1)$-tuples $(p_{0},p_{1},\ldots,p_{t})\in\\{0,\ldots,n+1\\}^{t+1}$ such
that $p=p_{0}\neq p_{1}\neq\cdots\neq p_{t}=q$.

With Theorem 1.1 in hand, we may easily identify which graphs $x$ are trees.
Let $\alpha(m)$ denote the number of 1s in the dyadic expansion of an integer
$m$.

######  Theorem 1.2.

The graph $x$ is a tree if and only if the integers (3) are positive (that is
to say, $x$ is connected) and
$\displaystyle\sum_{i=1}^{n+1}\alpha(r_{i})=n+1$.

In [12], C. Yearwood sharpens the ideas in [11] by carefully interpreting the
Hopf algebra structure on $\mathscr{A}^{*}$ and its quotients
$\mathscr{A}^{*}(n)$ graph theoretically. We shall have more to say about this
in Section 5. One important implication of Yearwood’s work is that the graphs
$x$ are perhaps most naturally viewed as digraphs, with edges oriented in the
direction of the larger vertex (i.e., $2^{\alpha}\to 2^{\beta}$ if
$0\leq\alpha<\beta\leq n+1$). With this in mind, we offer a digraph version of
Theorem 1.1. Let $x^{\operatorname{dir}}$ denote the graph $x$ viewed as a
digraph. The appropriate connectedness property to study for
$x^{\operatorname{dir}}$ is that of being unilateral (see Section 2).

######  Theorem 1.3.

The digraph $x^{\operatorname{dir}}$ is unilateral if and only if the integers

$U(p,q):=\sum_{t=1}^{n+1}\sum_{T^{\prime}}\prod_{k=1}^{t}a_{p_{k-1},p_{k}}$
(4)

are positive for all $0\leq p<q\leq n+1$, where $T^{\prime}$ is the set of all
$(k+1)$-tuples $(p_{0},p_{1},\ldots,p_{t})\in\\{0,\ldots,n+1\\}^{t+1}$ such
that $p=p_{0}<p_{1}<\cdots<p_{t}=q$.

Among the questions posed by Wood in [11] regarding his graph theoretic
interpretation of $\mathscr{A}^{*}(n)$ is whether there are algebraic analogs
of classical questions about Hamilton cycles. In response, we offer the
following result.

######  Theorem 1.4.

The graph $x\in\mathscr{A}^{*}(n)$ has a Hamilton cycle if $n>0$ and for every
vertex $2^{j}$ of $x$,

$\\#\\{1\leq k\leq j\>:\>a_{j,j-k}=1\\}+\\#\\{1\leq k\leq
n+1-j\>:\>a_{j+k,j}=1\\}\geq\frac{n}{2}.$

Moreover, the digraph $x^{\operatorname{dir}}$ has a directed Hamilton path if
and only if $x$ is divisible by $\xi_{1}^{2^{n+1}-1}$.

The aforementioned Hopf algebra structure on $\mathscr{A}^{*}(n)$, to be
described in Section 5, includes a coproduct
$\Delta:\mathscr{A}^{*}(n)\otimes\mathscr{A}^{*}(n)\to\mathscr{A}^{*}(n)$ and
an antipode $c:\mathscr{A}^{*}(n)\to\mathscr{A}^{*}(n)$. Our last theorem is a
generalization of Lemmas 3.1.7 and 3.1.8 of [12].

######  Theorem 1.5.

Let $\xi_{i}^{2^{j}}\in\mathscr{A}^{*}(n)$ (whose underlying graph is the
single edge connecting $2^{j}$ and $2^{i+j}$; see Section 2). Then the
coproduct $\Delta(\xi_{i}^{2^{j}})\in\mathscr{A}^{*}(n)$ is the sum of tensors
of all pairs of edges that make length 2 directed paths from $2^{j}$ to
$2^{i+j}$, and the antipode $c(\xi_{i}^{2^{j}})\in\mathscr{A}^{*}(n)$ is the
sum of all directed paths from $2^{j}$ to $2^{i+j}$.

As a corollary, we obtain another characterization of the unilaterality of
$x^{\operatorname{dir}}$.

######  Corollary 1.6.

For $x\in\mathscr{A}^{*}(n)$, the graph $x^{\operatorname{dir}}$ is unilateral
if and only if for each $\xi_{i}^{2^{j}}\in\mathscr{A}^{*}(n)$, at least one
summand of $c(\xi_{i}^{2^{j}})$ is a factor of $x$.

The paper is structured as follows. Section 2 establishes the necessary
terminology from graph theory and describes Wood’s construction of the graphs
corresponding to monomials $x\in\mathscr{A}^{*}(n)$. In Section 3 we prove our
connectedness criteria, namely Theorems 1.1 and 1.3. Section 4 discusses trees
and Hamilton cycles and contains the proofs of Theorems 1.2 and 1.4. Finally,
in Section 5, we discuss the Hopf algebra structure of $\mathscr{A}^{*}(n)$ in
the context of graph theory, prove Theorem 1.5 and Corollary 1.6, and pose
some open questions.

### Acknowledgements

The author would like to thank Caroline Yearwood, whose thesis was a major
impetus for this work, and her advisor Kyle Ormsby, who kindly provided a copy
of Yearwood’s thesis. The author would also like to thank Kiran Bhutani and
Paul Kainen for many helpful comments and suggestions.

##  2 Graph theory background and Wood’s construction

The purposes of this section are to recall the necessary definitions from
graph theory and to describe Wood’s construction of graphs associated to
monomials in $\mathscr{A}^{*}(n)$. Our main graph theory references are [2]
and [9].

###  2.1 Definitions, conventions, and notation

A graph is an ordered pair $G=(V_{G},E_{G})$ where $V_{G}$ is the set of
vertices, and where $E_{G}$, the set of edges, is a subset of the set
$\binom{V_{G}}{2}$ of unordered pairs of vertices in $V_{G}$. If
$e=\\{v_{0},v_{1}\\}\in E_{G}$, we say $v_{0}$ and $v_{1}$ are the ends of
$e$. All graphs in this paper are finite, meaning $V_{G}$ and $E_{G}$ are
finite sets, and simple, meaning no edge has identical ends and no two edges
have the same pair of ends. A walk in $G$ is a finite non-empty sequence
$v_{0},v_{1},\ldots,v_{k}$ of vertices such that each consecutive pair
$v_{i},v_{i+1}$ comprises the ends of an edge in $E_{G}$. If the vertices of a
walk in $G$ are distinct, it is called a path in $G$. We say the walk or path
$v_{0},v_{1},\ldots,v_{k}$ has length $k$. We say $G$ is connected if there
exists a path connecting any two distinct vertices. If $S$ is a set of
vertices, a complete graph on $S$ is a graph whose vertex set is $S$ and whose
edge set contains one edge for every pair of distinct vertices in $S$.

A cycle in $G$ is a finite sequence $v_{0},v_{1},\ldots,v_{k},v_{0}$ of
vertices such that $v_{0},v_{1},\ldots,v_{k}$ is a path and the pair
$v_{k},v_{0}$ comprises the ends of an edge in $E_{G}$. We say $G$ is acyclic
if it contains no cycles. A tree is an acyclic connected graph. A Hamilton
cycle in $G$ is a cycle containing every vertex of $G$. The degree $\deg(v)$
of a vertex $v\in V_{G}$ is the number of edges in $E_{G}$ that have $v$ as an
end.

A directed graph (or digraph) is an ordered pair $D=(V_{D},E_{D})$ where
$V_{D}$ is the set of vertices, and where $E_{D}$, the set of edges, is a
subset of the set of ordered pairs of vertices in $V_{G}$. If
$e=(v_{0},v_{1})\in E_{D}$, we say $v_{0}$ is the tail of $e$ and $v_{1}$ is
the head of $e$. Any digraph has an underlying graph by replacing each ordered
pair $(v_{0},v_{1})\in E_{D}$ with the corresponding unordered pair
$\\{v_{0},v_{1}\\}$. All directed graphs in this paper have underlying graphs
that are finite and simple. A directed walk in $D$ is a finite non-empty
sequence $v_{0},v_{1},\ldots,v_{k}$ of vertices such that each for consecutive
pair $v_{i},v_{i+1}$, there is an edge in $E_{D}$ with tail $v_{i}$ and head
$v_{i+1}$. If the vertices of a directed walk in $D$ are distinct, it is
called a directed path in $D$. As with walks or paths, we say the directed
walk or directed path $v_{0},v_{1},\ldots,v_{k}$ has length $k$. A digraph $D$
is unilateral (see [2, Exercise 10.2.2]) if for every pair of distinct
vertices $v_{i},v_{j}\in V_{D}$, there is a directed path starting at $v_{i}$
and ending at $v_{j}$ or vice versa. A Hamilton directed path in $D$ is a
directed path containing every vertex of $D$. The out-degree
$\deg_{\operatorname{out}}(v)$ of a vertex $v\in V_{D}$ is the number of edges
in $D$ that have $v$ as a tail, and the in-degree
$\deg_{\operatorname{in}}(v)$ of $v$ is the number of edges in $D$ that have
$v$ as a head. Note that
$\deg(v)=\deg_{\operatorname{out}}(v)+\deg_{\operatorname{in}}(v)$, where we
interpret $\deg(v)$ as being the degree of $v$ in the graph underlying the
digraph $D$.

If $G$ is a graph with ordered vertex set $V_{G}=\\{v_{0},\ldots,v_{n-1}\\}$,
the adjacency matrix of $G$ is the $n\times n$ matrix $A_{G}$ with $(p,q)$th
entry equal to the number of edges with ends $v_{p}$ and $v_{q}$. (Here, we
use $p$ and $q$ as row and column indices, respectively, where $0\leq p\leq
n-1$ and $0\leq q\leq n-1$.) If $D$ is a digraph with vertex set
$V_{D}=\\{v_{0},\ldots,v_{n-1}\\}$, the adjacency matrix of $D$ is the
$n\times n$ matrix $A_{D}$ with $(p,q)$th entry equal to the number of edges
with tail $v_{p}$ and head $v_{q}$. As a result of our conventions, all
adjacency matrices $A_{G}$ associated to graphs $G$ in this paper will be
symmetric, binary (that is, all entries either 0 or 1), and will have zeros
along the main diagonal. Similarly, all adjacency matrices $A_{D}$ associated
to digraphs $D$ in this paper will be binary and strictly upper triangular.

###  2.2 Wood’s construction

We now explain how Wood encodes the algebras $\mathscr{A}^{*}(n)$ in terms of
graphs. Recall from Section 1 that the graph $x$ underlying a monomial
$x\in\mathscr{A}^{*}(n)$ will have vertex set
$V_{x}=\\{2^{0},2^{1},\ldots,2^{n+1}\\}$.

To begin, consider a monomial of the form
$\xi_{i}^{2^{j}}\in\mathscr{A}^{*}(n)$ where $1\leq i\leq n+1$ and $1\leq
j\leq 2^{n+2-i}-1$. Wood’s construction declares that the graph
$\xi_{i}^{2^{j}}$ has edge set consisting of a single edge with ends $2^{j}$
and $2^{i+j}$.

######  Example 2.1.

  1. (a)

$\xi_{2}\in\mathscr{A}^{*}(2)$

$\textstyle{8}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4}$$\textstyle{2}$

  2. (b)

$\xi_{3}^{2}\in\mathscr{A}^{*}(3)$

$\textstyle{16\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{8}$$\textstyle{1}$$\textstyle{4}$$\textstyle{2}$

If
$x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}\in\mathscr{A}^{*}(n)$,
then we may use the dyadic expansions given in (2) to write $x$ as a product
of monomials of the form $\xi_{i}^{2^{j}}$, and Wood’s construction declares
the graph $x$ to have edge set equal to the disjoint union of the
corresponding edges.

######  Example 2.2.

  1. (a)

$x=\xi_{1}^{6}\xi_{2}\xi_{3}=\xi_{1}^{2}\xi_{1}^{4}\xi_{2}\xi_{3}\in\mathscr{A}^{*}(2)$

$\textstyle{8}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

  2. (b)

$x=\xi_{1}^{15}\xi_{3}^{2}=\xi_{1}\xi_{1}^{2}\xi_{1}^{4}\xi_{1}^{8}\xi_{3}^{2}\in\mathscr{A}^{*}(3)$

$\textstyle{16\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{8\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Any graph on the vertices $\\{2^{0},2^{1},\ldots,2^{n+1}\\}$ has a
corresponding monomial in $\mathscr{A}^{*}(n)$. Following the notation in
[11], we shall denote the top degree class
$\xi_{1}^{2^{n+1}-1}\xi_{2}^{2^{n}-1}\cdots\xi_{n+1}\in\mathscr{A}^{*}(n)$ by
$\Delta$. The corresponding graph $\Delta$ is a complete graph on
$\\{2^{0},2^{1},\ldots,2^{n+1}\\}$. At the other extreme, the graph
corresponding to $1\in\mathscr{A}^{*}(n)$ is the graph on
$\\{2^{0},2^{1},\ldots,2^{n+1}\\}$ with empty edge set.

######  Example 2.3.

  1. (a)

$\Delta=\xi_{1}^{15}\xi_{2}^{7}\xi_{3}^{3}\xi_{4}\in\mathscr{A}^{*}(3)$

$\textstyle{16\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$------$\textstyle{8\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

  2. (b)

$1\in\mathscr{A}^{*}(3)$

$\textstyle{16}$$\textstyle{8}$$\textstyle{1}$$\textstyle{4}$$\textstyle{2}$

######  Remark 2.4.

If $x$ and $y$ are arbitrary monomials in $\mathscr{A}^{*}(n)$, we can obtain
the graph $xy$ from the individual graphs $x$ and $y$ via the following
procedure: (1) Overlay the graphs $x$ and $y$ on their common vertex set
$\\{2^{0},2^{1},\ldots,2^{n+1}\\}$; (2) For all pairs of edges between two
vertices $2^{i}$ and $2^{j}$, delete the pair and, if possible, perform a
“carry” by inserting an edge between $2^{i+1}$ and $2^{j+1}$; (3) Repeat until
no further deletions/carries are required. If
$x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}$ and
$y=\xi_{1}^{s_{1}}\xi_{2}^{s_{2}}\cdots\xi_{n+1}^{s_{n+1}}$, the carries of
edges one would perform correspond precisely to the carries required when
adding the dyadic expansions of $r_{i}$ and $s_{i}$ for $1\leq i\leq n+1$. In
fact, it is shown in [12] that if the set of all possible graphs on
$\\{2^{0},2^{1},\ldots,2^{n+1}\\}$ is endowed with this multiplication, and
with addition given by finite formal sums over $\mathbb{F}_{2}$, the result is
an $\mathbb{F}_{2}$-algebra (referred to as a truncated “graph algebra” in
[12]) that is isomorphic to $\mathscr{A}^{*}(n)$.

We noted in Section 1 that it is natural to view graphs
$x\in\mathscr{A}^{*}(n)$ as digraphs $x^{\operatorname{dir}}$ with edges
oriented in the direction of the larger vertex. To do this pictorially, one
can put an arrow on each edge pointing toward the head. Here is the graph
$\xi_{1}^{6}\xi_{2}\xi_{3}\in\mathscr{A}^{*}(2)$ from Example 2.2(a) viewed as
a digraph $(\xi_{1}^{6}\xi_{2}\xi_{3})^{\operatorname{dir}}$:

$\textstyle{8}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

######  Remark 2.5.

In the graph theory literature, a directed graph $D$ is said to be strongly
connected or diconnected ([2, §10.1]) if for any ordered pair of vertices
$(v_{0},v_{1})$, there is a directed path starting at $v_{0}$ and ending at
$v_{1}$ in $D$. The way we orient edges in graphs $x\in\mathscr{A}^{*}(n)$
makes it impossible for any corresponding $x^{\operatorname{dir}}$ to be
strongly connected. This is why we instead opt for characterizing the notion
of $x^{\operatorname{dir}}$ being unilateral as defined in the exercises of
[2].

##  3 Connectedness criteria

In this section, we prove the connectedness criteria in Theorems 1.1 and 1.3
using the basic theory of adjacency matrices.

###  3.1 Connectedness criterion for $x\in\mathscr{A}^{*}(n)$

We now prove Theorem 1.1, which asserts that the graph
$x\in\mathscr{A}^{*}(n)$ is connected if and only if the integers $C(p,q)$
defined in (3) are positive.

Let $G$ be a graph with ordered vertex set
$V_{G}=\\{v_{0},v_{1},\ldots,v_{n-1}\\}$ and corresponding adjacency matrix
$A_{G}$. Given a positive integer $t$, the $(p,q)$th entry of the matrix
$(A_{G})^{t}$ is equal to the number of distinct walks of length $t$ in $G$
between $v_{p}$ and $v_{q}$. We have the following well-known result from
graph theory as a consequence.

######  Proposition 3.1.

The graph $G$ is connected if and only if for all $0\leq p<q\leq n-1$, the
$(p,q)$th entry of the matrix

$A_{G}+(A_{G})^{2}+\cdots+(A_{G})^{n-1}$

is positive.

Let
$x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}\in\mathscr{A}^{*}(n)$
as in Section 1. Recall that the vertex set of the graph $x$ is
$V_{x}=\\{2^{0},2^{1},\ldots,2^{n+1}\\}$. Following the notation and
conventions from Subsection 2.1, let $A_{x}$ denote the $(n+2)\times(n+2)$
adjacency matrix of $x$, whose rows and columns we shall index by $p$ and $q$,
respectively, with $0\leq p\leq n+1$ and $0\leq q\leq n+1$. The key to our
proofs of Theorems 1.1 and 1.3 is the connection between the dyadic expansions
of the exponents $r_{i}$ given in (2) and the entries of $A_{x}$.

######  Lemma 3.2 ([11], or Lemma 3.2.4 of [12]).

For $0\leq p<q\leq n+1$, the $(p,q)$th entry of $A_{x}$ is $a_{p,q}$, where
$a_{p,q}$ is the coefficient on $2^{q}$ in the dyadic expansion of $r_{p-q}$,
as in (2).

###### Proof.

It follows from Wood’s construction (Subsection 2.2) and the observation
preceding Proposition 3.1 that the $i$th superdiagonal of $A_{x}$, read from
bottom to top, yields precisely the coefficients of the dyadic expansion of
$r_{i}$ in order from the largest power of 2 to the smallest. ∎

Let $t$ be a fixed positive integer such that $t\leq n+1$. Since $A_{x}$ is
symmetric, it follows from Lemma 3.2 and the definition of matrix
multiplication that the integer

$\sum_{T}\prod_{k=1}^{t}a_{\min(p_{k-1},p_{k}),\max(p_{k-1},p_{k})},$

where $T$ is the set of all $(t+1)$-tuples
$(p_{0},p_{1},\ldots,p_{t})\in\\{0,\ldots,n+1\\}^{t+1}$ such that $p=p_{0}\neq
p_{1}\neq\cdots\neq p_{t}=q$, is precisely the $(p,q)$th entry of
$(A_{x})^{t}$. Therefore, Proposition 3.1 implies that $x$ is connected if and
only if the integers $C(p,q)$ are positive for all $0\leq p<q\leq n+1$. This
proves Theorem 1.1.

###  3.2 Connectedness criterion for $x^{\operatorname{dir}}$

We now prove Theorem 1.3, the digraph analog of Theorem 1.1, which asserts
that the digraph $x^{\operatorname{dir}}$ is unilateral if and only if the
integers $U(p,q)$ defined in (4) are positive. The proof will be similar in
format to the proof of Theorem 1.1 given in Subsection 3.1 but with
adjustments made to accommodate the directed case as needed.

Let $D$ be a digraph with ordered vertex set
$V_{D}=\\{v_{0},v_{1},\ldots,v_{n-1}\\}$ and corresponding adjacency matrix
$A_{D}$. Given a positive integer $t$, the $(p,q)$th entry of the matrix
$(A_{D})^{t}$ is equal to the number of distinct directed walks of length $t$
in $D$ starting at $v_{p}$ and ending at $v_{q}$. We therefore have the
following digraph analog of Proposition 3.1.

######  Proposition 3.3.

The digraph $D$ is unilateral if and only if for all $0\leq p\neq q\leq n-1$,
either the $(p,q)$th entry or the $(q,p)$th entry of the matrix

$A_{D}+(A_{D})^{2}+\cdots+(A_{D})^{n-1}$

is positive.

Once again, let
$x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}\in\mathscr{A}^{*}(n)$
as in Section 1. Let $x^{\operatorname{dir}}$ be the underlying digraph, and
let $A_{x^{\operatorname{dir}}}$ denote its $(n+2)\times(n+2)$ adjacency
matrix. Because edges in $x^{\operatorname{dir}}$ are always oriented toward
the larger vertex, the $(p,q)$th entry of $A_{x^{\operatorname{dir}}}$ is
equal to the $(p,q)$th entry of $A_{x}$ if $p<q$, and is equal to zero
otherwise. This implies that Lemma 3.2 holds with $A_{x^{\operatorname{dir}}}$
in place of $A_{x}$. For a fixed positive integer $t\leq n+1$, it follows from
this altered version of Lemma 3.2 and the definition of matrix multiplication
for strictly upper triangular matrices that the integer

$\sum_{T^{\prime}}\prod_{k=1}^{t}a_{p_{k-1},p_{k}},$

where $T^{\prime}$ is the set of all $(k+1)$-tuples
$(p_{0},p_{1},\ldots,p_{t})\in\\{0,\ldots,n+1\\}^{t+1}$ such that
$p=p_{0}<p_{1}<\cdots<p_{t}=q$, is precisely the $(p,q)$th entry of
$(A_{x^{\operatorname{dir}}})^{t}$. Therefore, Proposition 3.3 implies
$x^{\operatorname{dir}}$ is unilateral if and only if the integers $U(p,q)$
are positive for all $0\leq p<q\leq n+1$. This proves Theorem 1.3.

###  3.3 Examples

We present two examples of Theorems 1.1 and 1.3 applied to graphs in
$\mathscr{A}^{*}(n)$. Consider first
$\xi_{1}^{6}\xi_{2}\xi_{3}\in\mathscr{A}^{*}(2)$ from Example 2.2(a). The
integers $C(p,q)$ associated to the underlying graph are

$C(0,1)=2,\quad C(0,2)=6,\quad C(0,3)=5,\quad C(1,2)=4,\quad C(1,3)=2,\quad
C(2,3)=6,$ (5)

while among the associated integers $U(p,q)$, one finds

$U(0,1)=0.$ (6)

Since the integers in (5) are all positive, Theorem 1.1 implies
$\xi_{1}^{6}\xi_{2}\xi_{3}$ is connected. On the other hand, (6) implies
$\xi_{1}^{6}\xi_{2}\xi_{3}$ is not unilateral by Theorem 1.3.

Next, consider $\xi_{1}^{15}\xi_{3}^{2}\in\mathscr{A}^{*}(3)$ from Example
2.2(b), for which the associated integers $C(p,q)$ are

$\displaystyle\begin{split}C(0,1)&=4,\quad C(0,2)=6,\quad C(0,3)=2,\quad
C(0,4)=6,\quad C(1,2)=6,\\\ C(1,3)&=12,\quad C(1,4)=6,\quad C(2,3)=5,\quad
C(2,4)=11,\quad C(3,4)=5.\end{split}$ (7)

and the associated integers $U(p,q)$ are

$\displaystyle\begin{split}U(0,1)&=1,\quad U(0,2)=1,\quad U(0,3)=1,\quad
U(0,4)=2,\quad U(1,2)=1,\\\ U(1,3)&=1,\quad U(1,4)=2,\quad U(2,3)=1,\quad
U(2,4)=1,\quad U(3,4)=1.\end{split}$ (8)

Since the integers in (7) are all positive, Theorem 1.1 implies
$\xi_{1}^{15}\xi_{3}^{2}$ is connected. Since the integers in (8) are all
positive, Theorem 1.3 implies $\xi_{1}^{15}\xi_{3}^{2}$ is also unilateral.

Note that whether a monomial $x$ is connected and/or unilateral depends in
part on which truncated polynomial algebra $\mathscr{A}^{*}(n)$ it lives in.
For example, we saw above that $\xi_{1}^{15}\xi_{3}^{2}\in\mathscr{A}^{*}(3)$
is both connected and unilateral, but if we were to regard
$\xi_{1}^{15}\xi_{3}^{2}$ as an element of $\mathscr{A}^{*}(n)$ for $n\geq 4$,
the monomial would have neither property because the vertex $2^{5}=32$ would
not be the end of any edge.

##  4 Trees and Hamilton cycles

The purpose of this section is to characterize trees and Hamilton cycles among
the graphs $x\in\mathscr{A}^{*}(n)$ by proving Theorems 1.2 and 1.4.

###  4.1 Trees in $\mathscr{A}^{*}(n)$

In this subsection we shall prove the criteria for trees in Theorem 1.2, which
asserts that $x\in\mathscr{A}^{*}(n)$ is a tree (that is, connected and
acyclic) if and only if the associated integers $C(p,q)$ from (3) are positive
and $\displaystyle\sum_{i=1}^{n+1}\alpha(r_{i})=n+1$. Our starting point is a
known characterization of trees given by the following result.

######  Proposition 4.1 (Theorem 2.1.4(B) of [9]).

A connected graph $G$ with $n$ vertices is a tree if and only if it has $n-1$
edges.

Using Proposition 4.1, Yearwood gives a criterion for when a connected graph
$x\in\mathscr{A}^{*}(n)$ is a tree.

######  Proposition 4.2 (Proposition 3.3.8 of [12]).

A connected graph
$x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}\in\mathscr{A}^{*}(n)$
is a tree if and only if $\displaystyle\sum_{i=1}^{n+1}\alpha(r_{i})=n+1$.

###### Proof.

It follows from Wood’s construction (Subsection 2.2) that the number of edges
of $x$ is the total number of 1s in the dyadic expansions of
$r_{1},\ldots,r_{n+1}$. Yearwood’s criterion then follows from Proposition
4.1. ∎

Theorem 1.2 follows immediately from Proposition 4.2 and Theorem 1.1.

###  4.2 Hamilton cycles

We now prove Theorem 1.4, starting with the sufficient condition for
$x\in\mathscr{A}^{*}(n)$ to have a Hamilton cycle. Recall from Section 1 that
we must show $x$ has a Hamilton cycle if $n>0$ and for every vertex $2^{j}$ of
$x$,

$\\#\\{1\leq k\leq j\>:\>a_{j,j-k}=1\\}+\\#\\{1\leq k\leq
n+1-j\>:\>a_{j+k,j}=1\\}\geq\frac{n}{2}$

where $x=\xi_{1}^{r_{1}}\xi_{2}^{r_{2}}\cdots\xi_{n+1}^{r_{n+1}}$ and the
integers $a_{p,q}$ are the dyadic coefficients of the exponents
$r_{1},\ldots,r_{n+1}$ as described in (2). We begin by establishing a lemma
that counts the computes the degree of a vertex in $x$.

######  Lemma 4.3.

The out-degree of a vertex $2^{j}$ in $x^{\operatorname{dir}}$ is

$\deg_{\operatorname{out}}(2^{j})=\\#\\{1\leq k\leq n+1-j\>:\>a_{j+k,j}=1\\}$

and its in-degree is

$\deg_{\operatorname{in}}(2^{j})=\\#\\{1\leq k\leq j\>:\>a_{j,j-k}=1\\}$

so that the degree of the vertex $2^{j}$ in $x$ is

$\deg(2^{j})=\\#\\{1\leq k\leq n+1-j\>:\>a_{j+k,j}=1\\}+\\#\\{1\leq k\leq
j\>:\>a_{j,j-k}=1\\}.$

###### Proof.

Using the dyadic expansions given in (2), we may factor $x$ as

$x=\prod_{i=1}^{n+1}\prod_{m=0}^{n+1-i}\xi_{i}^{a_{n+1-m,n+1-i-m}2^{n+1-i-m}}.$
(9)

By Wood’s construction (Subsection 2.2), the edges of the digraph
$x^{\operatorname{dir}}$ with tail $2^{j}$ correspond precisely to factors in
the product (9) of the form $\xi_{k}^{2^{j}}$ for $1\leq k\leq n+1-j$ (such an
edge has tail $2^{j}$ and head $2^{j+k}$). The factor $\xi_{k}^{2^{j}}$
appears in (9) if and only if the corresponding dyadic coefficient $a_{j+k,j}$
is equal to 1. Similarly, Wood’s construction implies the edges of
$x^{\operatorname{dir}}$ with head $2^{j}$ correspond precisely to factors in
the product (9) of the form $\xi_{k}^{2^{j-k}}$ for $1\leq k\leq j$ (such an
edge has tail $2^{j-k}$ and head $2^{j})$. The factor $\xi_{k}^{2^{j-k}}$
appears in (9) if and only if the corresponding dyadic coefficient $a_{j,j-k}$
is equal to 1. This yields the first two equations of the lemma, and the third
follows from the fact that
$\deg(v)=\deg_{\operatorname{out}}(v)+\deg_{\operatorname{in}}(v)$ for any
vertex $v$, as we noted in Subsection 2.1. ∎

Dirac’s Theorem from graph theory gives a sufficient condition for a graph $G$
to have a Hamilton cycle in terms of the degrees of the vertices of $G$.

######  Theorem 4.4 (Dirac’s Theorem).

A graph $G$ with at least 3 vertices has a Hamilton cycle if $\deg(v)\geq n/2$
for all vertices $v$ of $G$.

Lemma 4.3 and Theorem 4.4 together imply that a sufficient condition for
$x\in\mathscr{A}^{*}(n)$ to have a Hamilton cycle is to assume that $n>0$ (so
that $x$ has at least 3 vertices) and that for all vertices $2^{j}$ of $x$,

$\displaystyle\frac{n}{2}\leq\deg(2^{j})$
$\displaystyle=\deg_{\operatorname{out}}(2^{j})+\deg_{\operatorname{in}}(2^{j})$
$\displaystyle=\\#\\{1\leq k\leq n+1-j\>:\>a_{j+k,j}=1\\}+\\#\\{1\leq k\leq
j\>:\>a_{j,j-k}=1\\}.$

This completes the proof of the first statement of Theorem 1.4.

We now prove the second statement of Theorem 1.4, which asserts
$x^{\operatorname{dir}}$ has a directed Hamilton path if and only if $x$ is
divisible by $\xi_{1}^{2^{n+1}-1}$. The monomial $\xi_{i}^{2^{n+1}-1}$ is the
largest nonzero power of $\xi_{1}$ in the truncated polynomial algebra
$\mathscr{A}^{*}(n)$. Therefore, if $x$ is divisible by $\xi_{i}^{2^{n+1}-1}$,
we may write $x$ as

$\displaystyle x$
$\displaystyle=\xi_{1}^{2^{n+1}-1}\xi_{2}^{r_{2}}\xi_{3}^{r_{3}}\cdots\xi_{n+1}^{r_{n+1}}$
$\displaystyle=\xi_{1}^{1+2+4+\cdots+2^{n}}\xi_{2}^{r_{2}}\xi_{3}^{r_{3}}\cdots\xi_{n+1}^{r_{n+1}}$
$\displaystyle=\xi_{1}\xi_{1}^{2}\xi_{1}^{4}\cdots\xi_{1}^{2^{n}}\xi_{2}^{r_{2}}\xi_{3}^{r_{3}}\cdots\xi_{n+1}^{r_{n+1}}.$

The first $n+1$ factors (i.e., the powers of $\xi_{1}$) correspond precisely
to the edges in the directed path

$2^{0}\to 2^{1}\to 2^{2}\to\cdots\to 2^{n}\to 2^{n+1}$ (10)

which is a Hamilton directed path we have just shown is contained in
$x^{\operatorname{dir}}$. Conversely, suppose $x^{\operatorname{dir}}$
contains a Hamilton directed path. This Hamilton directed path must contain
all the vertices of $x^{\operatorname{dir}}$ by definition, in particular
$2^{0}$. Since no edge in $x^{\operatorname{dir}}$ has $2^{0}$ as its head,
the Hamilton directed path must in fact start at $2^{0}$. If the first edge of
the path went from $2^{0}$ to $2^{j}$ for $j>1$, the vertex $2^{1}$ could not
be contained in the path, which implies the first edge must be the edge from
$2^{0}$ to $2^{1}$, i.e., $\xi_{1}$. An analogous argument shows the next edge
in the path must be the edge $2^{1}$ to $2^{2}$, i.e., $\xi_{1}^{2}$.
Continuing in this manner shows that the Hamilton directed path in
$x^{\operatorname{dir}}$ must in fact be the directed path (10), and that $x$
is divisible by

$\xi_{1}\xi_{1}^{2}\xi_{1}^{4}\cdots\xi_{1}^{2^{n}}=\xi_{1}^{2^{n+1}-1}.$

This completes the proof of Theorem 1.4.

###  4.3 Examples

We present examples of Theorems 1.2 and 1.4 applied to graphs
$x\in\mathscr{A}^{*}(n)$. Consider first the monomial
$x=\xi_{1}\xi_{2}\xi_{3}\in\mathscr{A}^{*}(2)$. For this choice of $x$,
$r_{1}=r_{2}=r_{3}=1$, which implies

$\sum_{i=1}^{3}\alpha(r_{i})=3=2+1$

and so $\xi_{1}\xi_{2}\xi_{3}$ is a tree by Theorem 1.2. A picture of the
graph $\xi_{1}\xi_{2}\xi_{3}$ is given by

$\textstyle{8}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4}$$\textstyle{2}$

and verifies that $\xi_{1}\xi_{2}\xi_{3}$ is indeed a tree. On the other hand,
if we take $x$ to be $\xi_{1}^{6}\xi_{2}\xi_{3}\in\mathscr{A}^{*}(2)$ from
Example 2.2(a), then $r_{1}=6=4+2$ and $r_{2}=r_{3}=1$, which implies

$\sum_{i=1}^{3}\alpha(r_{i})=4\neq 2+1.$

We conclude the graph $\xi_{1}^{6}\xi_{2}\xi_{3}$ is not a tree by Theorem
1.2.

Next, let us take
$x=\xi_{1}^{6}\xi_{2}^{6}\xi_{3}\xi_{4}\in\mathscr{A}^{*}(3)$. The dyadic
coefficients $a_{p,q}$ for the exponents $r_{1}=r_{2}=6=4+2$ and
$r_{3}=r_{4}=1$ are given by

$\displaystyle a_{4,3}$ $\displaystyle=0,\quad a_{3,2}=1,\quad a_{2,1}=1,\quad
a_{1,0}=0,$ $\displaystyle a_{4,2}$ $\displaystyle=1,\quad a_{3,1}=1,\quad
a_{2,0}=0,$ $\displaystyle a_{4,1}$ $\displaystyle=0,\quad a_{3,0}=1,$
$\displaystyle a_{4,0}$ $\displaystyle=1.$

Using these values, we can verify directly that
$\xi_{1}^{6}\xi_{2}^{6}\xi_{3}\xi_{4}$ satisfies the sufficient condition for
having a Hamilton cycle given in Theorem 1.4 by checking the requisite
inequality at each vertex $v$:

$\displaystyle v$ $\displaystyle=1=2^{0}:\quad\\#\\{1\leq k\leq
0\>:\>a_{0,0-k}=1\\}+\\#\\{1\leq k\leq 4\>:\>a_{0+k,0}=1\\}=0+2\geq 3/2,$
$\displaystyle v$ $\displaystyle=2=2^{1}:\quad\\#\\{1\leq k\leq
1\>:\>a_{1,1-k}=1\\}+\\#\\{1\leq k\leq 3\>:\>a_{1+k,1}=1\\}=0+2\geq 3/2,$
$\displaystyle v$ $\displaystyle=4=2^{2}:\quad\\#\\{1\leq k\leq
2\>:\>a_{2,2-k}=1\\}+\\#\\{1\leq k\leq 2\>:\>a_{2+k,2}=1\\}=1+2\geq 3/2,$
$\displaystyle v$ $\displaystyle=8=2^{3}:\quad\\#\\{1\leq k\leq
3\>:\>a_{3,3-k}=1\\}+\\#\\{1\leq k\leq 1\>:\>a_{3+k,3}=1\\}=3+0\geq 3/2,$
$\displaystyle v$ $\displaystyle=16=2^{4}:\quad\\#\\{1\leq k\leq
4\>:\>a_{4,4-k}=1\\}+\\#\\{1\leq k\leq 0\>:\>a_{4+k,4}=1\\}=2+0\geq 3/2.$

A picture of the graph $\xi_{1}^{6}\xi_{2}^{6}\xi_{3}\xi_{4}$ is given by

$\textstyle{16\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$------$\textstyle{8\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

and corroborates the presence of a Hamilton cycle, e.g.,
$2^{1},2^{2},2^{4},2^{0},2^{3},2^{1}$.

Finally, consider $x=\xi_{1}^{15}\xi_{3}^{2}\in\mathscr{A}^{*}(3)$ from
Example 2.2(b). One can check that this choice of $x$ does not satisfy the
sufficient condition in Theorem 1.4 for containing a Hamilton cycle (and as it
turns out, it does not contain a Hamilton cycle). However, Theorem 1.4 does
guarantee that $\xi_{1}^{15}\xi_{3}^{2}$ contains a Hamilton directed path
since $\xi_{1}^{15}\xi_{3}^{2}$ is divisible by
$\xi_{1}^{15}=\xi_{1}^{2^{3+1}-1}$. The Hamilton directed path it contains is

$2^{0}\to 2^{1}\to 2^{2}\to 2^{3}\to 2^{4}$

which, as we observed in Subsection 4.2, is the only possible Hamilton
directed path that a digraph in $\mathscr{A}^{*}(3)$ could possibly contain.

##  5 The Hopf algebra structure of $\mathscr{A}^{*}(n)$

In this section, we review the basic theory of Hopf algebras and describe the
Hopf algebra structure of $\mathscr{A}^{*}(n)$. We then prove Theorem 1.5 and
Corollary 1.6 and pose some open questions. Our general reference for the
theory of Hopf algebras is [6].

###  5.1 Hopf algebras

Let $k$ be a field. Recall that a Hopf algebra over $k$ is a unital
associative $k$-algebra $A=(A,\mu,u)$ equipped with three additional
$k$-linear structure maps, namely $\Delta:A\to A\otimes A$ (the coproduct),
$\varepsilon:A\to k$ (the counit), and $c:A\to A$ (the antipode), such that
$\Delta$ is counital and coassociative, and such that the following diagram
commutes:

---
$\textstyle{A\otimes
A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{c\otimes
1}$$\textstyle{A\otimes
A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mu}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Delta}$$\scriptstyle{\varepsilon}$$\scriptstyle{\Delta}$$\textstyle{k\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{u}$$\textstyle{A}$$\textstyle{A\otimes
A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1\otimes
c}$$\textstyle{A\otimes
A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mu}$

This data amounts to saying that a Hopf algebra is a cogroup object in the
category of $k$-algebras, with $\Delta$ corresponding to the group operation,
$\varepsilon$ corresponding to the identity, and $c$ corresponding to
inversion.

Let $A$ be a Hopf algebra over $k$. An ideal $I\subset A$ is said to be a Hopf
ideal if $\Delta(I)\subset I\otimes A+A\otimes I$, $\varepsilon(I)=0$, and
$c(I)\subset I$. If $I\subset A$ is a Hopf ideal, then the structure maps of
$A$ descend to the quotient $A/I$, giving $A/I$ the structure of a Hopf
algebra.

###  5.2 The dual Steenrod algebra as a Hopf algebra

The dual Steenrod algebra
$\mathscr{A}^{*}=\mathbb{F}_{2}[\xi_{1},\xi_{2},\xi_{3},\ldots]$ has the
structure of a Hopf algebra [3], with coproduct $\Delta$ defined by

$\Delta(\xi_{i})=\sum_{k=0}^{i}\xi_{i-k}^{2^{k}}\otimes\xi_{k},$ (11)

counit $\varepsilon$ defined by $\varepsilon(\xi_{i})=0$, and antipode $c$
given recursively by

$\sum_{k=0}^{i}\xi_{i-k}^{2^{k}}c(\xi_{k})=0.$ (12)

These structure maps extend to all of $\mathscr{A}^{*}$ by declaring them to
be $\mathbb{F}_{2}$-algebra homomorphisms. Milnor solved the recursion in (12)
to obtain the formula

$c(\xi_{i})=\sum_{\pi}\prod_{k=1}^{\ell(\pi)}\xi_{\pi(k)}^{2^{\sigma(k)}}$
(13)

where the sum is over all all ordered partitions $\pi$ of $i$, $\ell(\pi)$ is
the length of $\pi$, $\pi(k)$ is the $k$th part of $\pi$, and $\sigma(k)$ is
the sum of the first $k-1$ parts of $\pi$.

One can check that the ideals $I(n)\subset\mathscr{A}^{*}$ defined in (1) are
Hopf ideals, so that the quotients $\mathscr{A}^{*}(n)=\mathscr{A}^{*}/I(n)$
inherit Hopf algebra structures under the maps $\Delta$, $\varepsilon$, and
$c$ defined in this Subsection.

###  5.3 Graph theoretic interpretation of the coproduct and antipode

We now prove Theorem 1.5, starting with the graph theoretic interpretation of
the coproduct. We must show that the image of
$\xi_{i}^{2^{j}}\in\mathscr{A}^{*}(n)$ under $\Delta$ is the sum of tensors of
all pairs of edges that make length 2 directed paths from $2^{j}$ to
$2^{i+j}$. The coproduct formula (14) implies

$\Delta(\xi_{i}^{2^{j}})=\Delta(\xi_{i})^{2^{j}}=\xi_{i}^{2^{j}}\otimes
1+1\otimes\xi_{i}^{2^{j}}+\sum_{k=1}^{i-1}\xi_{i-k}^{2^{j+k}}\otimes\xi_{k}^{2^{j}}.$
(14)

The first two summands of the right-hand side of (14) represent degenerate
length 2 directed paths from $2^{j}$ to $2^{i+j}$. A non-degenerate length 2
directed path from $2^{j}$ to $2^{i+j}$ corresponds to a choice of an
intermediate vertex, which in this case would be of the form $2^{j+k}$ for
some $k$, $1\leq k\leq i-1$. Given this choice of $k$, the edge from $2^{j}$
to $2^{j+k}$ is $\xi_{j+k-j}^{2^{j}}=\xi_{k}^{2^{j}}$ and the edge from
$2^{j+k}$ to $2^{i+j}$ is $\xi_{i+j-(j+k)}^{2^{j+k}}=\xi_{i-k}^{2^{j+k}}$. The
terms of the sum indexed by $k$ on the far-right of (14) correspond precisely
to the pairs of edges just described.

Next, we prove the portion of Theorem 1.5 concerning the graph theoretic
interpretation of the antipode. The claim here is that the image of
$\xi_{i}^{2^{j}}$ under $c$ is the sum of all directed paths from $2^{j}$ to
$2^{i+j}$. Our proof models that of [12, Lemma 3.1.8]. Milnor’s formula (13)
for the antipode implies

$c(\xi_{i}^{2^{j}})=c(\xi_{i})^{2^{j}}=\sum_{\pi}\prod_{k=1}^{\ell(\pi)}\xi_{\pi(k)}^{2^{\sigma(k)+j}}$
(15)

where $\pi$, $\ell(\pi)$, $\pi(k)$, and $\sigma(k)$ are defined as in
Subsection 5.2. A directed path from $2^{j}$ to $2^{i+j}$ corresponds to a
choice of intermediate vertices, say

$2^{j+a_{1}},2^{j+a_{2}},\ldots,2^{j+a_{m}}$

for $0=a_{0}<a_{1}<a_{2}<\cdots<a_{m}<a_{m+1}=i$. The successive differences
yield a unique ordered partition $\pi$ of $i$, namely

$i=(a_{1}-a_{0})+(a_{2}-a_{1})+\cdots+(a_{m}-a_{m-1})+(i-a_{m})$

for which $\ell(\pi)=m+1$, $\pi(k)=a_{k}-a_{k-1}$, and
$\sigma(k)=(a_{1}-0)+(a_{2}-a_{1})+\cdots+(a_{k-1}-a_{k-2})=a_{k-1}$. The
monomial corresponding to this directed path is therefore

$\displaystyle\xi_{j+a_{1}-j}^{2^{j}}\xi_{j+a_{2}-(j+a_{1})}^{2^{a_{1}+j}}\cdots\xi_{j+a_{m}-(j+a_{m-1})}^{2^{a_{m-1}+j}}\xi_{j+i-(j+a_{m})}^{2^{a_{m}+j}}$
$\displaystyle=\xi_{a_{1}-a_{0}}^{2^{a_{0}+j}}\xi_{a_{2}-a_{1}}^{2^{a_{1}+j}}\cdots\xi_{a_{m}-a_{m-1}}^{2^{a_{m-1}+j}}\xi_{a_{m+1}-a_{m}}^{2^{a_{m}+j}}$
$\displaystyle=\xi_{\pi(1)}^{2^{\sigma(1)+j}}\xi_{\pi(2)}^{2^{\sigma(2)+j}}\cdots\xi_{\pi(m)}^{2^{\sigma(m)+j}}\xi_{\pi(m+1)}^{2^{\sigma(m+1)+j}}$
$\displaystyle=\prod_{k=1}^{\ell(\pi)}\xi_{\pi(k)}^{2^{\sigma(k)+j}}$

which is precisely the general term of the summation in (13) indexed by $\pi$.
This completes the proof of Theorem 1.5.

Recall from Section 1 that Theorem 1.5 yields an alternate characterization of
unilaterality of a directed graph $x^{\operatorname{dir}}$ underlying
$x\in\mathscr{A}^{*}(n)$, namely Corollary 1.6. This corollary asserts
$x^{\operatorname{dir}}$ is unilateral if and only if for each
$\xi_{i}^{2^{j}}\in\mathscr{A}^{*}(n)$, at least one summand of
$c(\xi_{i}^{2^{j}})$ is a factor of $x$. To obtain the corollary, note that
the digraph $x^{\operatorname{dir}}$ underlying $x\in\mathscr{A}^{*}(n)$ is
unilateral if and only if there is a directed path connecting any two of its
vertices, say $2^{j}$ and $2^{j+i}$. Theorem 1.5 shows this is equivalent to
the demand that at least one summand of $c(\xi_{i}^{2^{j}})$ appears as a
factor of $x$.

###  5.4 Open questions

We record some outstanding questions related to Wood’s encoding of the
algebras $\mathscr{A}^{*}(n)$ in terms of graphs.

  1. 1.

What is the analog of Wood’s construction for the mod $p$ dual Steenrod
algebra for odd primes $p$? What characterizations of connectedness, trees,
etc., are there in these odd primary situations?

  2. 2.

In [11, §8], Wood points out that the mod 2 Steenrod algebra $\mathscr{A}_{*}$
(as opposed to its dual, which has been the sole focus of this paper) and some
of its subalgebras can be interpreted graph theoretically. What would the
results in [12] or in this paper look like in that setting?

  3. 3.

Given the Hopf algebra structure on $\mathscr{A}^{*}(n)$, including the
coproduct $\Delta$ and antipode $c$, what is the graph theoretic meaning of
$\Delta(x)$ and $c(x)$ for an arbitrary monomial $x\in\mathscr{A}^{*}(n)$?

  4. 4.

In [11, §5], Wood describes two procedures one can perform in the mod 2
Steenrod algebra $\mathscr{A}_{*}$, called stripping and strapping, that
together allow one to derive all of the Adem relations from the single
relation $Sq^{1}Sq^{1}=0$. A step in the process of recovering the Adem
relations involves assigning to each monomial
$\xi_{i}^{2^{j}}\in\mathscr{A}^{*}$ a “stripping operator” $\omega$ which is
analogous to how Wood’s construction discussed in this paper assigns an edge
of a graph to each $\xi_{i}^{2^{j}}$. How can this analogy be leveraged to
obtain further results about Wood’s graph theoretic interpretation of
$\mathscr{A}^{*}(n)$?

  5. 5.

How can Wood’s encoding of $\mathscr{A}^{*}(n)$ help with calculations in
homotopy theory, particularly with the Adams spectral sequence at the prime 2?

## References

  * [1] Scott M. Bailey.  On the spectrum $b{\rm o}\wedge{\rm tmf}$.  J. Pure Appl. Algebra, 214(4):392–401, 2010.
  * [2] J. A. Bondy and U. S. R. Murty.  Graph theory with applications.  North-Holland, 1982.
  * [3] John Milnor.  The Steenrod algebra and its dual.  Ann. of Math. (2), 67:150–171, 1958.
  * [4] Douglas C. Ravenel.  Complex cobordism and stable homotopy groups of spheres, volume 121 of Pure and Applied Mathematics.  Academic Press, Inc., Orlando, FL, 1986.
  * [5] Larry Smith.  An algebraic introduction to the Steenrod algebra.  In Proceedings of the School and Conference in Algebraic Topology, volume 11 of Geom. Topol. Monogr., pages 327–348. Geom. Topol. Publ., Coventry, 2007.
  * [6] M. E. Sweedler.  Hopf algebras.  Benjamin, 1969.
  * [7] Grant Walker and Reginald M. W. Wood.  Polynomials and the ${\rm mod}\,2$ Steenrod algebra. Vol. 1\. The Peterson hit problem, volume 441 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 2018.
  * [8] Grant Walker and Reginald M. W. Wood.  Polynomials and the ${\rm mod}\,2$ Steenrod algebra. Vol. 2\. Representations of ${\rm GL}(n,\mathbb{F}_{2})$, volume 442 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 2018.
  * [9] Douglas B. West.  Introduction to graph theory.  Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
  * [10] R. M. W. Wood.  Differential operators and the Steenrod algebra.  Proc. London Math. Soc. (3), 75(1):194–220, 1997.
  * [11] R. M. W. Wood.  Problems in the Steenrod algebra.  Bull. London Math. Soc., 30(5):449–517, 1998.
  * [12] C. Yearwood.  The Dual Steenrod Algebra and Graph Theory.  Senior thesis under the supervision of K. Ormsby, Reed College, May 2019.