# Elimination of Non-Novel Segments at Multi-Scale for Few-Shot Segmentation

Alper Kayabaşı1,2, Gülin Tüfekci1,2, İlkay Ulusoy2
1Research Center, Aselsan Inc
2Middle East Technical University, Ankara, Turkey
<EMAIL_ADDRESS>
###### Abstract

Few-shot segmentation aims to devise a generalizing model that segments query
images from unseen classes during training with the guidance of a few support
images whose class tally with the class of the query. There exist two domain-
specific problems mentioned in the previous works, namely spatial
inconsistency and bias towards seen classes. Taking the former problem into
account, our method compares the support feature map with the query feature
map at multi scales to become scale-agnostic. As a solution to the latter
problem, a supervised model, called as base learner, is trained on available
classes to accurately identify pixels belonging to seen classes. Hence,
subsequent meta learner has a chance to discard areas belonging to seen
classes with the help of an ensemble learning model that coordinates meta
learner with the base learner. We simultaneously address these two vital
problems for the first time and achieve state-of-the-art performances on both
PASCAL-5i and COCO-20i datasets.

##  1 Introduction

Semantic segmentation is a crucial task that classifies each pixel of an image
to make sense of the scene with application areas such as autonomous driving
[5] and medical imaging [19]. Deep learning pervades semantic segmentation
like other tasks of computer vision [2, 15]. Supervised segmentation models
are required to employ abundant annotated data belonging to each class in the
training set since the generalization capacity of supervised models decreases
with scarce labeled data. Therefore, adapting the model to work on unseen
classes requires dense annotation of myriad data from novel classes. Shaban
_et al_. [20] proposed few-shot segmentation to remove the labeling effort and
increase the generalization capacity of a model given few data for the first
time.

---
(a)
(b)
Figure 1: (a) Overview of BAM [10]. Support and query features are used by
meta learner to extract support feature map while base learner provides
guidance for the base classes and leads the meta learner to focus on novel
regions via ensembling. (b) Our proposed method. The decoder for meta learner
is improved such that query feature map is obtained at multi-scale. Support
feature map is compared with query feature maps at multi-scale to obtain
enriched query features. Query predictions obtained from enriched query
features at each scale are ensembled with the base map as well as the
prediction obtained from the fusion of them. Inner losses are computed at
different scale levels and the final prediction is obtained from the ensemble
of the base map with the predictions from the fused query feature maps. (Best
viewed in zoom)

Few-shot segmentation addresses the problem of making pixel-wise predictions
for a target image, called a query, from an unseen class with the guidance of
a support image from the same category. Inspired by the few-shot
classification task [23], most methods utilized the episodic training strategy
in which the gradients are averaged over tasks named as an episode. Each
episode is sampled from a dataset whose classes are disjoint from a test case
where only a few data are available. These episodes are used to imitate the
test case during training to prevent overfitting. Despite this intention, a
model trained with this strategy tends to mistake segments from seen training
classes, referred as base classes, as novel classes because of constantly
experiencing the same set of classes during training. Hence, the co-occurrence
of novel and base classes in the same scene causes entanglement between
features of pixels that are part of the novel and base categories.

To prevent this entanglement, prediction of the supervised model which is
trained on base classes guides the meta learner, which is responsible for
detecting novel areas. Meta learner is directed to areas not occupied by the
base classes so that contradiction between the base learner and the meta
learner is avoided via the ensemble model entailing both base and meta
predictions [10]. On the side of meta learner, candidate objects in query
image might not cover as same area as those in support images; so, the model
should compare support feature map with query feature map at different
resolutions to disentangle adjacent regions around novel segments [22]. As
shown in Fig. 1, the ensemble of base and meta learner without improved
decoder fails to distinguish background from foreground since naive decoder,
which is designed for the supervised scheme, lacks to combine features at
different resolutions in favor of complete query prediction. Hence, we
transform the naive decoder into an improved decoder such that not only does
it correlate the support image with the query image at multi-resolution but
also it benefits from merits of base learner at multi-resolution. In this
regard, we hypothesize that there are cases where it is not enough that base
learner discourages meta learner from base regions at single-scale. Our
experiments verify that the improved decoder and ensembling the predictions at
multi-scale outperform the decoder equipped with ensembling the prediction at
single-scale. Our contributions in this paper are two-fold:

  * •

We alleviate the spatial inconsistency and the bias problems together with the
assistance of our proposed decoder that seeks to remove bias at multi-
resolution.

  * •

Our proposed method achieves new state-of-the art performance on both
PASCAL-5i (mIoU @ 1-shot: 68.59%, mIoU @ 5-shot: 72.05%) and COCO-20i (mIoU @
1-shot: 47.16%, mIoU @ 5-shot: 52.50%) datasets for few-shot segmentation
task.

##  2 Related work

###  2.1 Semantic segmentation

Fully convolutional neural network (FCN), which is the pioneering work in
semantic segmentation field, formulates semantic segmentation as a pixel-wise
classification task [15]. In FCN, all fully connected layers at the end of a
model are transformed into convolution layers so that the network accepts
arbitrary input sizes. Success of FCN accelerates the field and results in
outstanding architectures such as UNet [19], PSPNet [30], and Deeplab [2, 3].
PSPNet combines average pooled feature maps at different scales to contain not
only global but also local context [30]. Deeplab introduces ASPP module [2]
equipped with dilated convolution that increases the receptive field of the
network without a decrease in resolution by inserting holes between filter
weights.

###  2.2 Few-shot segmentation

Few-shot segmentation studies can be categorized into four groups according to
their objectives: imbalance in details, inter-class gap, spatial
inconsistency, and correlation reliability.

The imbalance in details problem emphasizes that there might be details that
do not co-exist in both query and corresponding support image. Hence,
inconsistent regions between support and query should be detected and
eliminated on the support side to prevent redundant details or noise in an
adaptive manner. PGNet [28] proposes a network that associates each query
pixel to the relevant parts of the support image to remove noise, where
relevancy is generally quantified by a similarity metric such as cosine
similarity. PANet [24] adds regularization loss to ensure that the network
becomes successful if the roles of support and query are swapped. ASGNet [11]
aims to find an adaptive number of prototypes and their spatial extents based
on image content with a boundary-aware superpixel algorithm so that prototypes
represent parts of an object with similar characteristics. Each query pixel
utilizes support prototype giving maximum cosine similarity with itself as
reference.

Most approaches assume that transferable knowledge constantly exists in base
set and tries to segment image from unseen classes during training. This
strong assumption loses its validity in proportion to the discrepancy between
base and novel dataset, and this problem is referred as an inter-class gap.
RePRI [1] shows that the severity of overfitting is exaggerated in few-shot
segmentation and adapting novel classes by fine-tuning over support images
improves segmentation performance. CWT [16] episodically trains self-attention
block that adapts classifier weights of network updated over support image
during both training and test. BriNet [27] regards prediction for query as
pseudo-mask and switches the roles between query and support to update model
with ground truth support mask during test stage until determined mIoU
threshold is exceeded for support mask and its prediction.

Architectures designed for supervised cases fail to provide scale-invariance
in few-shot scenarios since contextual relationships are not figured out by a
handful of data. Methods design control mechanism that provides favorable
information exchange between different resolutions [25, 26, 22, 28].

Correlation map determines pixel-wise similarity between support and query
images. Problems such as background clutter and occlusion lead to noise in the
correlation map; hence, it results in erroneous comparisons and training
processes based on misinterpreted correspondences, which is called as a hyper
correlation reliability problem. Methods are proposed to check the validity of
correspondences based on learnable or engineered criteria so that filtered
correlation maps become interpretable. After the elimination of deceptive
correspondences, all similarities corresponding to each query pixel from the
support image are summed to obtain an activation score that determines the
level of association of that query pixel with the foreground of support [17,
8].

##  3 Preliminaries

In order to relate the specified challenges in few-shot segmentation with our
approach and guide the reader through steps, the task is formally defined in
Section 3.1, Feature Enrichment Module (FEM) [22] and Base and Meta Learner
(BAM) [10] are introduced in Sections 3.2 and 3.3, respectively.

###  3.1 Task description

Few-shot segmentation task utilizes base dataset containing adequate images
with their annotations whose classes, $\mathcal{C}_{base}$, are disjoint from
novel classes, $\mathcal{C}_{novel}$, in which dense predictions are fulfilled
with few data and their annotations. K number of available data and their
annotations belonging to the novel classes constitute a support set
$\mathcal{S}$ for testing which are expected to guide a model ${M}$ to make
predictions for query image $\mathcal{I}_{q}$, which is dubbed as K-shot
segmentation. The support set is formally represented as
$\mathcal{S}=\\{\mathcal{I}_{s_{i}},\mathcal{M}_{s_{i}}\\}_{i=1}^{K}$, where
$\mathcal{I}_{s_{i}}$, and $\mathcal{M}_{s_{i}}$ correspond to
i${}^{\text{th}}$ support image and its dense ground truth mask. On the side
of training, support set for training is sampled from base dataset along with
query set which consists of the query image and its ground truth, sharing its
class with the chosen support set. The aforementioned classes are treated as
novel class during training in order to perform episodic training, where
pixels belonging to chosen class are assigned as foreground while pixels from
all other classes are considered as background. Query set is formally
represented as $\mathcal{Q}=\\{\mathcal{I}_{q},\mathcal{M}_{q}\\}$, where
$\mathcal{I}_{q}$ and $\mathcal{M}_{q}$ correspond to the query image and its
dense ground truth mask. The model, ${M}$, is trained by backpropagating
binary cross entropy loss between $\mathcal{I}_{q}$ and $\mathcal{M}_{q}$ over
tasks, named as episodes involving the selected support set from base dataset
with the accompanying query set.

###  3.2 Revisit feature enrichment module

Multi-scale modules in supervised semantic segmentation generally do not
provide mechanism to form independent interaction between masked global
average pooled support feature map, called as support prototype, and average
pooled query feature map at different scales. For example, conventional multi-
scale architectures apply single filtering to combination of query feature
map, support prototype, and prior mask that describes likelihood of query
pixel being related with at least one pixel in foreground of support [22].
Different from these approaches, inter-source enrichment module of FEM
separately applies the filtering to the query feature map at each different
scale, which is combined with support prototype and prior mask. Furthermore,
inter-scale interaction module of FEM fulfills the information transfer
between two consecutive resolutions in top-down path, where top-down path
consists of outputs of inter-source enrichment module ordered from high
resolution to low resolution. During information transfer, preservation of
hierarchical structure allows gradual accumulation of information from higher
resolution to lower resolution. In this module, each resolution has direct
connection only to its neighbour in the top-down direction. Therefore, there
is no connection between any resolution pairs other than the consecutive ones.
Hence, the module has a chance to decide on the scale at which the obtained
information is sufficient to make a prediction and the following scales would
bring redundancy. Following this reasoning, feature maps at different
resolutions are fused via information concentration module in FEM.

###  3.3 Revisit base and meta learner

Typical few-shot segmentation approaches use meta-learning approach such that
the knowledge gained from training the model on the base classes is utilized
to predict the mask of the query image belonging to a novel class given a
support image belonging to the same novel class. This process is called as
meta-learning since learning tasks are sampled from the base classes during
training in order to simulate the few-shot settings in testing so that the
training and testing conditions are matched. However, as [10] states, training
on base classes introduce a bias towards them during testing, which prevents
the model to work on the novel classes properly. To tackle this bias BAM is
introduced, where a base learner, apart from the meta learner, explicitly
works on the known classes. When the information related to known classes is
used during testing, the recognition of novel classes would be enhanced.

Training BAM consists of two stages, namely base-training and meta-training.
Both learners share the same backbone as feature encoder. To leverage the
representations at different levels of abstraction, features are obtained from
different layers of the encoder. Base learner is trained in a supervised
manner so that the ability to make confident predictions regarding base
classes is gained. In meta-training stage, the parameters of the base learner
are fixed. The features of support and query images are extracted by the
shared encoder and the features obtained after block-2 and block-3 of
ResNet-50 [7] are concatenated and transformed with 1$\times$1 convolution
layer, which are denoted by $\textbf{f}_{m}^{s}$ and $\textbf{f}_{m}^{q}$
respectively. Query features after block-4 of ResNet-50, $\textbf{f}_{b}^{q}$,
are processed by base learner and decoded by Pyramid Scene Parsing Network
(PSPNet) [30], which is composed of Pyramid Pooling Module (PPM) and
classifier so that the probability map of base classes, $\textbf{p}_{b}^{f}$,
is obtained. This step is crucial since the base classes are the background
classes for the query image while the novel class is the foreground, which is
to be predicted by the meta learner. The support mask, $\textbf{m}^{s}$, is
used together with $\textbf{f}_{m}^{s}$ in order to obtain the support
prototype, $\textbf{v}_{s}$. The query features, support prototype and the
prior map are concatenated, which is inputted to the meta decoder. At the end
of the meta decoder, output background and foreground probability maps,
$\textbf{p}_{m}^{0}$ and $\textbf{p}_{m}^{1}$, are obtained.

Low level features for support and query images are obtained from the
intermediate levels of the encoder, denoted by $\textbf{f}_{low}^{s}$ and
$\textbf{f}_{low}^{q}$, and the Frobenius norm between their Gram matrices is
computed as adjustment factor, $\psi$. The adjustment factor is leveraged such
that the smaller $\psi$ is, the closer the representations of support and
query images become. In other words, as $\psi$ gets smaller, the reliability
of the prediction of the meta learner increases such that the query features
become representative of the support features. Moreover, $\textbf{p}_{m}^{0}$
is ensembled with $\textbf{p}_{b}^{f}$ in order to force the pixels belonging
to non-novel regions for the query image to be closer to the base classes.
This enhanced information is used such that the corresponding pixels are less
likely to be predicted as novel. Resultant ensembled information is
concatenated with $\textbf{p}_{m}^{1}$ in order to produce final prediction.

##  4 Method

As CANet implies [29], we use the middle level features by applying 1x1
convolution to concatenation of feature maps obtained from block-2 and
block-3. We represent middle level features belonging to support and querys
image respectively as in Eq. 1 and Eq. 2, where $Enc$ symbolizes the middle
level feature extractor.

$\textbf{f}_{m}^{s}=Enc(\mathcal{I}_{s})\;\in R^{H\times W\times C}$ (1)

$\textbf{f}_{m}^{q}=Enc(\mathcal{I}_{q})\;\in R^{H\times W\times C}$ (2)

To obtain the prior map in a similar manner to PFENet [22], high level query
and support features are reshaped from RH×W×C to RHW×C at first. After that,
row wise norms for high level query and support pixel features are computed
respectively as in Eq. 3 and Eq. 4, where ∘ corresponds to Hadamard root while
$diag$ outputs diagonal elements of a matrix as a column vector.

$\lVert\tilde{\textbf{f}_{b}^{q}}\rVert=(diag(\tilde{\textbf{f}_{b}^{q}}\times\tilde{\textbf{f}_{b}^{q}}^{\intercal}))^{\circ{1/2}}\in
R^{HW\times 1}$ (3)
$\lVert\tilde{\textbf{f}_{b}^{s}}\rVert=(diag(\tilde{\textbf{f}_{b}^{s}}\times\tilde{\textbf{f}_{b}^{s}}^{\intercal}))^{\circ{1/2}}\in
R^{HW\times 1}$ (4)

Prior map is calculated by max pooling the cosine similarity matrix between
the high level query and support pixels along row wise direction as shown in
Eq. 5, where $\oslash$ is Hadamard divison.

$\textbf{C}_{q}=\text{pool}((\tilde{\textbf{f}_{b}^{q}}\times\tilde{\textbf{f}_{b}^{s}}^{\intercal})\oslash(\lVert\tilde{\textbf{f}_{b}^{q}}\rVert\times\lVert\tilde{\textbf{f}_{b}^{s}}\rVert^{\intercal}))\;\in
R^{H\times W\times 1}$ (5)

Masked global average pooling is applied to $\textbf{f}_{m}^{s}$ to extract
support prototype, $\textbf{v}_{s}$, in Eq. 6, where $\mathcal{R}$ downsamples
$\mathcal{M}_{s}$ to the size of $\textbf{f}_{m}^{s}$.

$\textbf{v}_{s}=\text{masked\\_avg\\_pool}(\textbf{f}_{m}^{s},\mathcal{R}\left(\mathcal{M}_{s}\right))\;\in
R^{1\times 1\times C}$ (6)

$FEM$ takes $\textbf{v}_{s},\textbf{C}_{q}$, and $\textbf{f}_{m}^{q}$ as input
and outputs N+1 enriched query feature maps where N of them correspond to
enriched auxiliary feature maps at N different scales and the last one is the
fusion of them as shown in Eq. 7.

$\textbf{X}_{q}^{s_{1}},\textbf{X}_{q}^{s_{2}},...,\textbf{X}_{q}^{s_{N}},\textbf{X}_{q}^{fused}=FEM(\textbf{C}_{q},\textbf{f}_{m}^{q},\textbf{v}_{s})$
(7)

$\textbf{C}^{AUX}=\\{\textbf{C}^{aux,1},\textbf{C}^{aux,2},...,\textbf{C}^{aux,N},\textbf{C}^{aux,fused}\\}$
(8)

$\textbf{C}^{AUX}$ in Eq. 8 represents set of classifiers, where first N
classifiers correspond to auxiliary classifiers, which make predictions for
the multi-scale features, while the last classifier is responsible for the
prediction deduced from the fused feature. By using these classifiers, we
obtain background and foreground logit values for enriched query feature maps
at each scale and the fused feature map respectively in Eq. 9 and Eq. 11,
where $\oplus$ performs concatenation operation.

$\textbf{p}_{m,s_{i}}^{0},\textbf{p}_{m,s_{i}}^{1}=\textbf{C}^{aux,i}(\textbf{X}_{q}^{s_{i}})$
(9)

$\textbf{p}_{m,s_{i}}=\textbf{p}_{m,s_{i}}^{0}\oplus\textbf{p}_{m,s_{i}}^{1}$
(10)

$\textbf{p}_{m,fused}^{0},\textbf{p}_{m,fused}^{1}=\textbf{C}^{aux,fused}(\textbf{X}_{q}^{fused})$
(11)

$\textbf{p}_{m,fused}=\textbf{p}_{m,fused}^{0}\oplus\textbf{p}_{m,fused}^{1}$
(12)

Figure 2: Detailed architecture of the multi-scale ensemble module. Features
at multi-scale and the fusion of them are obtained at the end of the improved
decoder as $\textbf{X}_{q}^{s_{i}}$ and $\textbf{X}_{q}^{fused}$ respectively,
which are used by the corresponding auxiliary classifiers. The resultant
enriched query feature maps are ensembled with the base map to obtain query
predictions at multi-scale, which are denoted by $\textbf{p}_{f,s_{i}}$ and
$\textbf{p}_{f,fused}$ respectively. Inner losses are computed from
probability maps at intermediate scales $\left(\textbf{p}_{m,s_{i}}\right)$
and predictions at intermediate scales $\left(\textbf{p}_{f,s_{i}}\right)$
while fused losses are computed from fused probability maps
$\left(\textbf{p}_{m,fused}\right)$ and fused predictions
$\left(\textbf{p}_{f,fused}\right)$. (Best viewed in color)

$BaseLearner$ in Eq. 13 takes $\textbf{f}_{q}^{m}$ as input and outputs
summation of predicted probabilities for all classes except background.

$\textbf{p}_{b}^{f}=BaseLearner(\textbf{f}_{m}^{q})$ (13)

While Eq. 14, Eq. 15, and Eq. 16 are the same as in BAM [10], we employ
separate ensemble models for each auxiliary predictions to render meta-model
aware of non-novel regions at each scale, as inspired by BAM, as shown in Eq.
17, Eq. 18, and Eq. 19 as well as in Fig. 2 with pink rectangular boxes
covered by dashed lines.

$\textbf{p}_{f,fused}^{0}=Ens_{\phi}(\textbf{p}_{b}^{f},Ens_{\psi}(\textbf{p}_{m,fused}^{0},\psi))$
(14)

$\textbf{p}_{f,fused}^{1}=Ens_{\psi}(\textbf{p}_{m,fused}^{1},\psi)$ (15)

$\textbf{p}_{f,fused}=\textbf{p}_{f,fused}^{0}\oplus\textbf{p}_{f,fused}^{1}$
(16)

$\textbf{p}_{f,s_{i}}^{0}=Ens_{\phi,s_{i}}(\textbf{p}_{b}^{f},Ens_{\psi}(\textbf{p}_{m,s_{i}}^{0},\psi))$
(17)

$\textbf{p}_{f,s_{i}}^{1}=Ens_{\psi}(\textbf{p}_{m,s_{i}}^{1},\psi)$ (18)

$\textbf{p}_{f,s_{i}}=\textbf{p}_{f,s_{i}}^{0}\oplus\textbf{p}_{f,s_{i}}^{1}$
(19)

$\mathcal{L}_{meta}^{inner}=\sum_{i=1}^{N}CE(\textbf{p}_{m,s_{i}},\mathcal{M}_{q})$
(20)

$\mathcal{L}_{meta}^{fused}=CE(\textbf{p}_{m,fused},\mathcal{M}_{q})$ (21)

$\mathcal{L}_{final}^{inner}=\sum_{i=1}^{N}CE(\textbf{p}_{f,s_{i}},\mathcal{M}_{q})$
(22)

$\mathcal{L}_{final}^{fused}=CE(\textbf{p}_{f,fused},\mathcal{M}_{q})$ (23)

Eq. 20 and Eq. 21 compute cross entropy losses for the auxiliary predictions
and the fused prediction before ensemble respectively while Eq. 22 and Eq. 23
compute cross entropy losses for the auxiliary predictions and the fused
prediction after ensemble accordingly.

$\mathcal{L}_{final}^{total}=\mathcal{L}_{meta}^{inner}+\mathcal{L}_{meta}^{fused}+\mathcal{L}_{final}^{inner}+\mathcal{L}_{final}^{fused}$
(24)

All individuals losses are accumulated to update the network eventually as in
Eq. 24.

Backbone | Method | 1-shot (%) | 5-shot (%)
---|---|---|---
Fold-0 | Fold-1 | Fold-2 | Fold-3 | Average | Fold-0 | Fold-1 | Fold-2 | Fold-3 | Average
VGG-16 | PFENet (TPAMI’20) [22] | 56.90 | 68.20 | 54.40 | 52.40 | 58.00 | 59.00 | 69.10 | 54.80 | 52.90 | 59.00
NTRENet (CVPR’22) [14] | 57.70 | 67.60 | 57.10 | 53.70 | 59.00 | 60.30 | 68.00 | 55.20 | 57.10 | 60.20
DPCN (CVPR’22) [13] | 58.90 | 69.10 | 63.20 | 55.70 | 61.70 | 63.40 | 70.70 | 68.10 | 59.00 | 65.30
BAM (CVPR’22) [10] | 63.18 | 70.77 | 66.14 | 57.53 | 64.41 | 67.36 | 73.05 | 70.61 | 64.00 | 68.76
BAM++ (ours) | 64.67 | 72.11 | 67.83 | 59.47 | 66.02 | 69.40 | 74.35 | 72.77 | 67.19 | 70.93
ResNet-50 | PGNet (ICCV’19) [28] | 56.00 | 66.90 | 50.60 | 50.40 | 56.00 | 57.70 | 68.70 | 52.90 | 54.60 | 58.50
PFENet (TPAMI’20) [22] | 61.70 | 69.50 | 55.40 | 56.30 | 60.80 | 63.10 | 70.70 | 55.80 | 57.90 | 61.90
NTRENet (CVPR’22) [14] | 65.40 | 72.30 | 59.40 | 59.80 | 64.20 | 66.20 | 72.80 | 61.70 | 62.20 | 65.70
ASNet (CVPR’22) [9] | 68.90 | 71.70 | 61.10 | 62.70 | 66.10 | 72.60 | 74.30 | 65.30 | 67.10 | 70.80
DPCN (CVPR’22) [13] | 65.70 | 71.60 | 69.10 | 60.60 | 66.70 | 70.00 | 73.20 | 70.90 | 65.50 | 69.90
BAM (CVPR’22) [10] | 68.97 | 73.59 | 67.55 | 61.13 | 67.81 | 70.59 | 75.05 | 70.79 | 67.20 | 70.91
BAM++ (ours) | 69.46 | 74.16 | 69.20 | 61.54 | 68.59 | 70.81 | 75.34 | 73.04 | 68.99 | 72.05

Table 1: 1-shot and 5-shot class mIoU results on PASCAL-5i dataset for VGG-16
and ResNet-50 as backbone, provided for 4 folds and the average. The best
results are given in boldface. The underlined results show the best
performance excluding our method.

Backbone | Method | 1-shot (%) | 5-shot (%)
---|---|---|---
Fold-0 | Fold-1 | Fold-2 | Fold-3 | Average | Fold-0 | Fold-1 | Fold-2 | Fold-3 | Average
ResNet-50 | NTRENet (CVPR’22) [14] | 36.80 | 42.60 | 39.90 | 37.90 | 39.30 | 38.20 | 44.10 | 40.40 | 38.40 | 40.30
ASNet (CVPR’22) [9] | - | - | - | - | 42.20 | - | - | - | - | 68.80
DPCN (CVPR’22) [13] | 42.00 | 47.00 | 43.20 | 39.70 | 43.00 | 46.00 | 54.90 | 50.80 | 47.40 | 49.80
BAM (CVPR’22) [10] | 43.41 | 50.59 | 47.49 | 43.42 | 46.23 | 49.26 | 54.20 | 51.63 | 49.55 | 51.16
BAM++ (ours) | 44.43 | 51.98 | 47.01 | 45.22 | 47.16 | 52.53 | 57.02 | 50.97 | 49.49 | 52.50

Table 2: 1-shot and 5-shot class mIoU results on COCO-20i dataset for
ResNet-50 as backbone, provided for 4 folds and the average. The best results
are given in boldface. The underlined results show the best performance
excluding our method.

##  5 Experiments

###  5.1 Details

Datasets. The model is evaluated on two datasets which are commonly used in
few-shot segmentation tasks. PASCAL-5i [20] is the first dataset, containing
20 classes and it is a combination of PASCAL VOC 2012 [4] and the extended
annotations obtained from [6]. The second dataset is COCO-20i [18], which is
generated from MSCOCO [12]. COCO-20i is more challenging when compared to
PASCAL-5i as it consists of images belonging to 80 classes. The datasets are
split into 4 folds containing equal number of classes in order to perform
cross-validation while 1000 support and query pairs are randomly sampled for
each fold. One of the folds is selected for evaluating the performance of the
model on unseen classes while the rest of them are used as base classes for
training the model. This procedure is repeated for all folds.

Evaluation metrics. In order to compare with previous studies on few-shot
segmentation [28, 22, 14, 9, 13, 10], class mean intersection-over-union is
used as the evaluation metric, which is calculated as in 25, where $C$ is the
number of classes in each fold.

$mIoU=\frac{1}{C}\sum_{i=1}^{C}IoU_{i}$ (25)

The foreground-background IoU (FB-IoU) is also calculated as an additional
metric.

Implementation details. All experiments are conducted on PyTorch framework
with NVIDIA RTX 2080Ti GPUs. As suggested in BAM [10], there are two training
stages, namely pre-training and meta-training. Pre-training stage is utilized
for learning the base classes while ResNet-50 [7] and VGG-16 [21] are used as
backbone for PASCAL-5i and only ResNet-50 [7] is used as backbone for
COCO-20i. For PASCAL-5i, PSPNet [30] is trained for 100 epochs as base learner
with an initial learning rate of 2.5e-3. For the base learner on COCO-20i, the
model shared by the authors of [10] is used. In meta-training stage, PASCAL-5i
and COCO-20i are trained for 200 and 50 epochs respectively while the learning
rate is set to 5e-2. For both stages, SGD is utilized as optimizer. Random
scaling, rotation, horizontal flip, cropping and Gaussian Blur is applied to
images. The sizes of the enriched query features at the output of the improved
decoder are set to 60, 30, 15, and 8, which makes N = 4 as suggested by [22].

Figure 3: Qualitative 1-shot results on PASCAL-5i dataset for ResNet-50
backbone. Results for one novel class from each fold are provided in rows.
First two columns contain image and mask for support while the following two
columns contain image and ground truth for query. Fifth column shows the
probability map for query obtained from base learner. Predictions are provided
for BAM [10] and our method for comparison in the last two columns. (Best
viewed in color)

Generalized few-shot segmentation setting. Our method is also evaluated in
generalized few-shot segmentation setting, which is defined by [10], where
both pixels belonging to novel and base classes are detected. For this
setting, novel pixels are predicted as novel if their final foreground
probabilities exceed a predefined threshold while the pixels predicted as base
should be assigned to one of the base classes. By this way, the pixels
belonging to different base classes are distinguished while the rest of the
pixels are classified as novel or background. This setting requires the
calculation of mIoU on base and novel classes and also the combination of
them, which are denoted by mIoUn, mIoUb and mIoUa respectively.

###  5.2 Results

####  5.2.1 Quantitative results

Table 1 shows the performance comparison between BAM++ and other methods
proposed for few-shot segmentation task using ResNet-50 and VGG-16. The mIoU
results include 1-shot and 5-shot cases for PASCAL-5i dataset. BAM++
outperforms the existing methods for both settings. When VGG-16 is utilized as
backbone, our method surpasses the state-of-the-art results by 1.61% and 2.17%
for 1-shot and 5-shot settings, respectively. When it comes to the model with
ResNet-50 as backbone, 0.78% and 1.14% performance gains are achieved for
1-shot and 5-shot settings. The results on COCO-5i dataset are provided in
Table 2 for ResNet-50 as backbone only. BAM++ outperforms the best results by
0.93% and 1.34% under 1-shot and 5-shot settings, respectively. Comparison
with state-of-the-art models regarding the FB-IoU scores is provided in Table
3 for both backbones on PASCAL-5i dataset. The results show that our method
performs well in 1-shot setting while exceeds the best result by 0.66% in
5-shot setting for ResNet-50. On the other hand, model with VGG-16 outperforms
the previous state-of-the-art by 1.43% and 1.42% for 1-shot and 5-shot
settings respectively.

####  5.2.2 Qualitative results

Qualitative results for PASCAL-5i dataset under 1-shot setting with ResNet-50
backbone are provided in Fig. 3. The differences between our proposed
architecture and BAM can be seen when the predicted masks are analyzed. The
main advantage of our model is revealed in cases where there is another object
adjacent to the novel target object. In such cases, models generally tend to
entangle the objects. In Fig. 3, it is seen that BAM predicts both the monitor
and the computer as novel objects although there is only monitor in the
support image. Since our model analyzes the features at different scales, it
distinguishes the neighboring objects from each other well. Moreover, another
faulty case is given in the third row, which is consistent with our
hypothesis. Even though base learner discourages meta learner from non-novel
regions, i.e. sofa, meta learner of BAM predicts these regions as novel. When
ensembling the query predictions at different scales is introduced, such
incorrect predictions are eliminated. As it can be seen in the predicted map
of our method, only the regions belonging to the dog are considered as
foreground. We deduce that ensembling at multi-scale ensures the model to
focus on non-novel regions rather than the areas belonging to base classes.

Backbone | Method | 1-shot (%) | 5-shot (%)
---|---|---|---
VGG-16 | PFENet (TPAMI’20) [22] | 72.00 | 72.30
NTRENet (CVPR’22) [14] | 73.10 | 74.20
DPCN (CVPR’22) [13] | 73.70 | 77.20
BAM (CVPR’22) [10] | 77.26 | 81.10
BAM++ (ours) | 78.69 | 82.52
ResNet-50 | PFENet (TPAMI’20) [22] | 73.30 | 73.90
NTRENet (CVPR’22) [14] | 77.00 | 78.40
ASNet (CVPR’22) [9] | 77.70 | 80.40
DPCN (CVPR’22) [13] | 78.00 | 80.70
BAM (CVPR’22) [10] | 79.71 | 82.18
BAM++ (ours) | 79.65 | 82.84

Table 3: 1-shot and 5-shot FB-IoU results on PASCAL-5i dataset for VGG-16 and
ResNet-50 as backbone, provided as the average. The best results are given in
boldface. The underlined results show the best performance excluding our
method.

####  5.2.3 Generalized few-shot segmentation results

Our method surpasses BAM [10] in generalized few-shot segmentation setting for
both backbones on PASCAL-5i dataset as shown in Table 4. The mIoU results
validate the superiority of ensembling at multi-scale for both novel and base
predictions.

###  5.3 Ablation study

Ablation study regarding the decision on how to include the inner losses for
the multi-scale predictions are performed by considering the following cases:
calculation of inner losses before and after the ensembling, without the
ensembling, and after the ensembling only. The contributions of
$\mathcal{L}_{meta}^{inner}$ in Eq. 20 and $\mathcal{L}_{final}^{inner}$ in
Eq. 22 on the final mIoU performance are investigated. Thus, we experimented
with the cases where either $\mathcal{L}_{meta}^{inner}$ is inactive,
$\mathcal{L}_{final}^{inner}$ is inactive, or both
$\mathcal{L}_{meta}^{inner}$ and $\mathcal{L}_{final}^{inner}$ are active for
the $\mathcal{L}_{final}^{total}$ calculation in Eq. 24. The results are
obtained for PASCAL-5i dataset under 1-shot setting and provided in Table 5.
Activating only $\mathcal{L}_{meta}^{inner}$ reaches an mIoU performance of
68.37% while including $\mathcal{L}_{final}^{inner}$ alone obtains the
performance of 68.45%. The last row in Table 5 indicates that when both
$\mathcal{L}_{meta}^{inner}$ and $\mathcal{L}_{final}^{inner}$ are used, the
highest performance is achieved, which is 68.59%. As consequence, this
ablation experiment validates our hypothesis, which emphasizes the weakness of
the model implementing ensembling at single scale and the merits of the co-
existence of $\mathcal{L}_{meta}^{inner}$ and $\mathcal{L}_{final}^{inner}$.

Backbone | Method | 1-shot (%) | 5-shot (%)
---|---|---|---
mIoUn | mIoUb | mIoUa | mIoUn | mIoUb | mIoUa
VGG-16 | BAM [10] | 43.19 | 67.03 | 61.07 | 46.15 | 67.02 | 61.80
BAM++ | 43.94 | 67.80 | 61.83 | 47.20 | 67.80 | 62.64
ResNet-50 | BAM [10] | 47.93 | 72.72 | 66.52 | 49.17 | 72.72 | 66.83
BAM++ | 49.98 | 72.87 | 67.15 | 52.41 | 72.87 | 67.76

Table 4: Generalized few-shot segmentation results on PASCAL-5i dataset for
VGG-16 and ResNet-50 as backbone. The best results are given in boldface.

Method | $\mathcal{L}_{inner}^{meta}$ | $\mathcal{L}_{inner}^{final}$ | mIoU (%)
---|---|---|---
BAM++ | ✓ | - | 68.37
BAM++ | - | ✓ | 68.45
BAM++ | ✓ | ✓ | 68.59

Table 5: Ablation studies on inner losses for the multi-scale predictions
regarding the ensembling with the base map under 1-shot setting for PASCAL-5i.
Results show the averaged mIoU over 4 folds.

##  6 Conclusion

We observed that although ensembling meta prediction with base prediction
guides the model by making the meta learner cautious in the regions where
objects from base classes exist, meta learner misclassifies non-novel regions
by neglecting base learner. This situation arises as a consequence of
ensembling the predictions at single-scale. Therefore, we proposed to perform
ensembling for predictions at multi-scale as well as the final prediction. By
this way, bias existing at non-novel regions is diminished. The experiments on
PASCAL-5i and COCO-20i verifies our hypothesis and our model achieves new
state-of-the-art on few-shot segmentation benchmark.

## References

  * [1] Malik Boudiaf, Hoel Kervadec, Ziko Imtiaz Masud, Pablo Piantanida, Ismail Ben Ayed, and Jose Dolz.  Few-shot segmentation without meta-learning: A good transductive inference is all you need?  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13979–13988, 2021.
  * [2] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):834–848, 2017.
  * [3] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 801–818, 2018.
  * [4] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  International Journal of Computer Vision, 88(2):303–338, 2010.
  * [5] Jiaqi Fan, Fei Wang, Hongqing Chu, Xiao Hu, Yifan Cheng, and Bingzhao Gao.  Mlfnet: Multi-level fusion network for real-time semantic segmentation of autonomous driving.  IEEE Transactions on Intelligent Vehicles, 2022.
  * [6] Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik.  Semantic contours from inverse detectors.  In 2011 International Conference on Computer Vision, pages 991–998. IEEE, 2011.
  * [7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.
  * [8] Sunghwan Hong, Seokju Cho, Jisu Nam, and Seungryong Kim.  Cost aggregation is all you need for few-shot segmentation.  arXiv preprint arXiv:2112.11685, 2021.
  * [9] Dahyun Kang and Minsu Cho.  Integrative few-shot learning for classification and segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9979–9990, 2022.
  * [10] Chunbo Lang, Gong Cheng, Binfei Tu, and Junwei Han.  Learning what not to segment: A new perspective on few-shot segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8057–8067, 2022.
  * [11] Gen Li, Varun Jampani, Laura Sevilla-Lara, Deqing Sun, Jonghyun Kim, and Joongkyu Kim.  Adaptive prototype learning and allocation for few-shot segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8334–8343, 2021.
  * [12] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European Conference on Computer Vision, pages 740–755. Springer, 2014.
  * [13] Jie Liu, Yanqi Bao, Guo-Sen Xie, Huan Xiong, Jan-Jakob Sonke, and Efstratios Gavves.  Dynamic prototype convolution network for few-shot semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11553–11562, 2022.
  * [14] Yuanwei Liu, Nian Liu, Qinglong Cao, Xiwen Yao, Junwei Han, and Ling Shao.  Learning non-target knowledge for few-shot semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11573–11582, 2022.
  * [15] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3431–3440, 2015.
  * [16] Zhihe Lu, Sen He, Xiatian Zhu, Li Zhang, Yi-Zhe Song, and Tao Xiang.  Simpler is better: Few-shot semantic segmentation with classifier weight transformer.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8741–8750, 2021.
  * [17] Juhong Min, Dahyun Kang, and Minsu Cho.  Hypercorrelation squeeze for few-shot segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6941–6952, 2021.
  * [18] Khoi Nguyen and Sinisa Todorovic.  Feature weighting and boosting for few-shot segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 622–631, 2019.
  * [19] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 234–241. Springer, 2015.
  * [20] Amirreza Shaban, Shray Bansal, Zhen Liu, Irfan Essa, and Byron Boots.  One-shot learning for semantic segmentation.  arXiv preprint arXiv:1709.03410, 2017.
  * [21] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [22] Zhuotao Tian, Hengshuang Zhao, Michelle Shu, Zhicheng Yang, Ruiyu Li, and Jiaya Jia.  Prior guided feature enrichment network for few-shot segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020\.
  * [23] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al.  Matching networks for one shot learning.  Advances in Neural Information Processing Systems, 29, 2016.
  * [24] Kaixin Wang, Jun Hao Liew, Yingtian Zou, Daquan Zhou, and Jiashi Feng.  Panet: Few-shot image semantic segmentation with prototype alignment.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9197–9206, 2019.
  * [25] Guo-Sen Xie, Jie Liu, Huan Xiong, and Ling Shao.  Scale-aware graph neural network for few-shot semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5475–5484, 2021.
  * [26] Guo-Sen Xie, Huan Xiong, Jie Liu, Yazhou Yao, and Ling Shao.  Few-shot semantic segmentation with cyclic memory network.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7293–7302, 2021.
  * [27] Xianghui Yang, Bairun Wang, Kaige Chen, Xinchi Zhou, Shuai Yi, Wanli Ouyang, and Luping Zhou.  Brinet: Towards bridging the intra-class and inter-class gaps in one-shot segmentation.  arXiv preprint arXiv:2008.06226, 2020.
  * [28] Chi Zhang, Guosheng Lin, Fayao Liu, Jiushuang Guo, Qingyao Wu, and Rui Yao.  Pyramid graph networks with connection attentions for region-based one-shot semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9587–9595, 2019.
  * [29] Chi Zhang, Guosheng Lin, Fayao Liu, Rui Yao, and Chunhua Shen.  Canet: Class-agnostic segmentation networks with iterative refinement and attentive few-shot learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5217–5226, 2019.
  * [30] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2881–2890, 2017.


# Hopf algebra of digraphs

Vladimir Grujić
Faculty of Mathematics
Belgrade University
Serbia
<EMAIL_ADDRESS>
Tanja Stojadinović
Faculty of Mathematics
Belgrade University
Serbia
<EMAIL_ADDRESS>
###### Abstract

In a series of recent talks Richard Stanley introduced a symmetric function
associated to digraphs. This symmetric function enumerates descent sets of
permutations corresponding to digraphs. We show that such constructed
symmetric function of digraphs arises from a suitable structure of
combinatorial Hopf algebra on digraphs. We use Hopf algebra methods to reprove
Berge’s classical result on the number of Hamiltonian paths in digraphs.

Keywords: digraph, permutation, combinatorial Hopf algebra, symmetric function

MSC2020: 05C20, 16T30, 05E05

##  1 Introduction

A digraph $X$ is a triple $X=(V,E,<)$, where $(V,<)$ is a finite linearly
ordered set and $E$ is a collection $E\subset\\{(u,v)\in V\times V|u\neq
v\\}$. Elements $u\in V$ are vertices and elements $(u,v)\in E$ are directed
edges of the digraph $X$. For a permutation of vertices $\sigma\in\Sigma_{V}$,
denoted as a list $\sigma=(\sigma_{1},\ldots,\sigma_{n})$, define the
$X$-descent set as

$X\mathrm{Des}(\sigma)=\\{1\leq i\leq n-1|(\sigma_{i},\sigma_{i+1})\in X\\}.$

If $V$ is the set $[n]=\\{1,\ldots,n\\}$ and $X=\\{(i,j)|1\leq j<i\leq n\\}$
then $X$-descent sets are standard descent sets of permutations
$\sigma\in\Sigma_{[n]}$.

Grinberg and Stanley associated to a digraph $X$ a generating function for
$X$-descent sets and named it the Redei-Berge symmetric function, see [4], [7]

$U_{X}=\sum_{\sigma\in\Sigma_{V}}F_{XDes(\sigma)}.$ (1)

It is expanded in the basis of fundamental quasisymmetric functions

$F_{I}=\sum_{\begin{subarray}{c}1\leq i_{1}\leq i_{2}\leq\cdots\leq i_{n}\\\
i_{j}<i_{j+1}\ \mathrm{for\ each}\ j\in
I\end{subarray}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}},I\subset[n-1].$ (2)

The symmetic function $U_{X}$ is related to two classical results in graph
theory. The first of them originates in 1933 paper of the famous Hungarian
mathematician Laszlo Redei [6] and states that every finite tournament
contains an odd number of Hamiltonian paths. The other one was found by Claude
Berge [2] and it claims that the numbers of Hamiltonian paths of a digraph and
its complement are of the same oddity.

We introduce the combinatorial Hopf algebra on digraphs $(\mathcal{D},\zeta)$
and obtain the expansion of the enumerator $U_{X}$ in the basis of monomial
quasisymmetric functions. The character $\zeta$ enumerates Hamiltonian paths
in the complementary digraph $\overline{X}$. The principal specialization

$u_{X}(m)=\mathrm{ps}^{1}(U_{X})(m)$

of the symmetric function $U_{X}$ is a polynomial in $m$ which enumerates
$(f,X)$-friendly permutations for colorings of vertices with at most $m$
colors. The Berge result follows from the reciprocity formula for the
polynomial $u_{X}(m)$.

##  2 Basics from combinatorial Hopf algebras

The theory of combinatorial Hopf algebras is founded in [1]. We review some
basic notions and facts. A partition $\\{V_{1},\ldots,V_{k}\\}\vdash V$ of the
length $k$ of a finite set $V$ is a family of disjoint nonempty subsets with
$V_{1}\cup\ldots\cup V_{k}=V$. A composition $(V_{1},\ldots,V_{k})\models V$
is an ordered partition. Let $n=|V|$ be the number of elements of $V$. A
composition $\alpha\models n$ is a sequence $\alpha=(a_{1},\ldots,a_{k})$ of
positive integers with $a_{1}+\cdots+a_{k}=n$. The type of a composition
$(V_{1},\ldots,V_{k})\models V$ is the composition
$\mathrm{type}(V_{1},\ldots,V_{k})=(|V_{1}|,\ldots,|V_{k}|)\models n$. A
partition $\lambda\vdash n$ is a composition $\lambda\models n$ with
$a_{1}\geq a_{2}\geq\cdots\geq a_{k}$. There is a bijection between the set of
compositions $\mathrm{Comp}(n)$ and the power set $2^{[n-1]}$ given by
$(a_{1},\ldots,a_{k})\mapsto\\{a_{1},a_{1}+a_{2},\ldots,a_{1}+\cdots+a_{k-1}\\}$.
We denote the inverse of this bijection by $I\mapsto\mathrm{comp}(I)$.

A combinatorial Hopf algebra $(\mathcal{H},\zeta)$ (CHA for short) over a
field $\mathbf{k}$ is a graded, connected Hopf algebra
$\mathcal{H}=\oplus_{n\geq 0}\mathcal{H}_{n}$ over $\mathbf{k}$ together with
a multiplicative functional $\zeta:\mathcal{H}\rightarrow\mathbf{k}$ called
the character.

The terminal object in the category of CHA’s is the CHA of quasisymmetric
functions $(QSym,\zeta_{Q})$. For basics of quasisymmetric functions see [8]
and for the Hopf algebra structure on $QSym$ see [3]. A composition
$\alpha=(a_{1},\ldots,a_{k})\models n$ defines the monomial quasisymmetric
function

$M_{\alpha}=\sum_{i_{1}<\cdots<i_{k}}x_{i_{1}}^{a_{1}}\cdots
x_{i_{k}}^{a_{k}}.$

Alternatively we write $M_{I}=M_{\mathrm{comp}(I)},\ I\subset[n-1]$. Another
basis consists of fundamental quasisymmetric functions $(\ref{fundamental})$
which are expressed in the monomial basis by

$F_{I}=\sum_{I\subset J}M_{J},\ I\subset[n-1].$ (3)

The antipode $S$ on $QSym$ is determined by its values on fundamental
quasisymmetric functions

$S(F_{I})=(-1)^{|V|}F_{(I^{\text{op}})^{c}},I\subset[n-1],$ (4)

where $I^{\text{op}}=\\{n-i|i\in I\\}$ and $(I^{\text{op}})^{c}$ is its
complement in $[n-1]$.

The principal specialization $\mathrm{ps}^{1}:QSym\rightarrow\mathbf{k}[m]$ is
an algebra homomorphism to the polynomial algebra defined by

$\mathrm{ps}^{1}(\Phi)(m)=\Phi(\underbrace{1,\ldots,1}_{\text{$m$
ones}},0,0,\ldots).$

On the monomial basis it takes values
$\mathrm{ps}^{1}(M_{I})(m)={m\choose|I|+1},I\subset[n-1]$ and determines the
character
$\zeta_{Q}(M_{I})=\mathrm{ps}^{1}(M_{I})(1)=\left\\{\begin{array}[]{cc}1,&I=\emptyset,\\\
0,&\text{otherwise}\end{array}\right.$. The reciprocity formula expresses
values of the principal specialization at negative integers

$\text{ps}^{1}(\Phi)(-m)=\text{ps}^{1}(S(\Phi))(m).$ (5)

The unique canonical morphism
$\Psi:(\mathcal{H},\zeta)\rightarrow(QSym,\zeta_{Q})$ is given on homogeneous
elements with

$\Psi(h)=\sum_{\alpha\models n}\zeta_{\alpha}(h)M_{\alpha},\
h\in\mathcal{H}_{n},$ (6)

where $\zeta_{\alpha}$ is the convolution product

$\zeta_{\alpha}=\zeta_{a_{1}}\cdots\zeta_{a_{k}}:\mathcal{H}\stackrel{{\scriptstyle\Delta^{(k-1)}}}{{\longrightarrow}}\mathcal{H}^{\otimes
k}\stackrel{{\scriptstyle
proj}}{{\longrightarrow}}\mathcal{H}_{a_{1}}\otimes\cdots\otimes\mathcal{H}_{a_{k}}\stackrel{{\scriptstyle\zeta^{\otimes
k}}}{{\longrightarrow}}\mathbf{k}.$ (7)

The algebra of symmetric functions $Sym$ is the subalgebra of $QSym$ and it is
the terminal object in the category of cocommutative combinatorial Hopf
algebras.

##  3 Hopf algebra of digraphs

We say that two digraphs $X=(V,E,<)$ and
$Y=(V^{\prime},E^{\prime},<^{\prime})$ are isomorphic if there is an order
preserving bijection $f:(V,<)\rightarrow(V^{\prime},<^{\prime})$ such that
$(u,v)\in E$ if and only if $(f(u),f(v))\in E^{\prime}$. Any isomorphism class
of digraphs $[X]$ has the canonical representative on the vertex set
$[n]=\\{1<2<\cdots<n\\}$ for some integer $n\geq 0$.

The restriction of a digraph $X=(V,E,<)$ on a subposet $S\subset V$ is the
digraph $X|_{S}=(S,E|_{S},<)$, where $E|_{S}=\\{(u,v)\in E|u,v\in S\\}$. For
digraphs $X=(V,E,<)$ and $Y=(V^{\prime},E^{\prime},<^{\prime})$ we define the
product $X\cdot Y$ as the digraph on the linear sum $V\oplus
V^{\prime}=(V\sqcup V^{\prime},\prec)$ with the set of directed edges

$E\cup E^{\prime}\cup\\{(u,v)|u\in V,v\in V^{\prime}\\}.$

The order $\prec$ on the disjoint union $V\sqcup V^{\prime}$ is defined by
$u\prec v$ if and only if either $u<v$ in $V$, $u<^{\prime}v$ in $V^{\prime}$
or $u\in V,v\in V^{\prime}$. The product of digraphs is obviously an
associative, but not a commutative operation.

Let $\mathcal{D}=\oplus_{n\geq 0}\mathcal{D}_{n}$ be the graded vector space
over the field of rational numbers $\mathbb{Q}$, which is linearly spanned by
the set of all isomorphism classes of digraphs, where the grading is given by
the number of vertices. The linear extension of the product on digraphs
determines the multiplication
$\mu:\mathcal{D}\otimes\mathcal{D}\rightarrow\mathcal{D}$, which turns the
space $\mathcal{D}$ into a noncommutative algebra. The restrictions of
digraphs may be used to define a comultiplication
$\Delta:\mathcal{D}\rightarrow\mathcal{D}\otimes\mathcal{D}$ by

$\Delta([X])=\sum_{S\subset V}[X|_{S}]\otimes[X|_{V\setminus S}],$

where $V$ is the vertex set of a digraph $X$. Evidently, this is a
coassociative and a cocommutative operation. It is easy to check that $\Delta$
is an algebra morphism, meaning that

$\Delta([X\cdot Y])=\Delta([X])\cdot\Delta([Y])$

for any isomorphism classes $[X]$ and $[Y]$ of digraphs. With these operations
the space of digraphs $\mathcal{D}$ is endowed with a structure of a graded,
connected, noncommutative and cocommutative Hopf algebra. The unit element is
the digraph $\emptyset$ on the empty set of vertices and the counit is given
by $\epsilon(\emptyset)=1$ and $\epsilon([X])=0$ otherwise.

The antipode of $\mathcal{D}$, determined recursively by the Takeuchi formula
for graded bialgebras, is given by

$S([X])=\sum_{k\geq 1}(-1)^{k}\sum_{(V_{1},\ldots,V_{k})\models
V}[X|_{V_{1}}\cdots X|_{V_{k}}],$

where the inner sum goes over all compositions of the length $k$ of the vertex
set $V$ of a digraph $X$.

We define some natural operations on digraphs and examine their obvious
properties.

######  Definition 3.1.

For a digraph $X=(V,E,<)$, let $\overline{X}=(V,E^{c},<)$ and
$X^{\text{op}}=(V,E^{\text{op}},<)$ be its complementary and opposite digraph
respectively, whose directed edges are determined by

$(u,v)\in E^{c}\ \text{if and only if}\ (u,v)\notin E,$ $(u,v)\in
E^{\text{op}}\ \text{if and only if}\ (v,u)\in E.$

######  Lemma 3.2.

The operations of taking the conjugate and the opposite digraphs are mutually
conjugate idempotent antihomomorphisms of the algebra $\mathcal{D}$, i.e.

$\overline{X\cdot Y}=\overline{Y}\cdot\overline{X},(X\cdot
Y)^{\text{op}}=Y^{\text{op}}\cdot X^{\text{op}},$
$(X^{\text{op}})^{\text{op}}=X,\overline{(\overline{X})}=X,$
$\overline{X^{\text{op}}}=(\overline{X})^{\text{op}}.$

Define reversion of a permutation
$\sigma=(\sigma_{1},\ldots,\sigma_{n})\in\Sigma_{V}$ by
$\text{rev}\sigma=(\sigma_{n},\ldots,\sigma_{1})$.

######  Lemma 3.3.

For a digraph $X$ on the vertex set $V$ and a permutation
$\sigma\in\Sigma_{V}$ it holds

$X^{\text{op}}\mathrm{Des}(\text{rev}\sigma)=(X\mathrm{Des}(\sigma))^{\text{op}},$
$\overline{X}\mathrm{Des}(\sigma)=(X\mathrm{Des}(\sigma))^{c}.$

To obtain a structure of a combinatorial Hopf algebra on digraphs we need a
character.

######  Definition 3.4.

A permutation $\sigma=(\sigma_{1},\ldots,\sigma_{n})\in\Sigma_{V}$ is a
Hamiltonian path of a digraph $X$ on the vertex set $V$ if
$X\mathrm{Des}(\sigma)=[n-1]$. This means that $(\sigma_{j},\sigma_{j+1})\in
X$ for all $j=1,\ldots,n-1$.

Let $\zeta:\mathcal{D}\rightarrow\mathbb{Q}$ be a linear functional that
counts Hamiltonian paths of the complementary digraph

$\zeta([X])=\\#\\{\sigma\in\Sigma_{V}|X\mathrm{Des}(\sigma)=\emptyset\\}.$ (8)

######  Proposition 3.5.

The linear functional $\zeta$ is multiplicative on the Hopf algebra of
digraphs $\mathcal{D}$.

###### Proof.

Let $X$ and $Y$ be digraphs. Each Hamiltonian path of $\overline{X\cdot
Y}=\overline{Y}\cdot\overline{X}$ is uniquely broken into Hamiltonian paths of
$\overline{Y}$ and $\overline{X}$. On the other hand any pair of Hamiltonian
paths of $\overline{Y}$ and $\overline{X}$ produces by concatenation the
Hamiltonian path of $\overline{X\cdot Y}$. ∎

We have constructed a combinatorial Hopf algebra of digraphs
$(\mathcal{D},\zeta)$. The universal morphism $\Psi:\mathcal{D}\rightarrow
QSym$ assigns to each digraph $X$ a quasisymmetric function $\Psi([X])$
determined by $(\ref{canonical})$. If $X$ is a digraph on the vertex set $V$
the coefficients of this quasisymmetric function in the monomial basis are
determined by $(\ref{generalcoeff})$ with

$\zeta_{\alpha}([X])=\sum_{\begin{subarray}{c}(V_{1},\ldots,V_{k})\models V\\\
\mathrm{type}(V_{1}\ldots,V_{k})=\alpha\end{subarray}}\zeta([X|_{V_{1}}])\cdots\zeta([X|_{V_{k}}]).$
(9)

Since $\mathcal{D}$ is a cocommutative combinatorial Hopf algebra we actually
have that $\Psi([X])$ is a symmetric function. This implies that values of the
coefficients $\zeta_{\alpha}$ depend only on set partitions of the vertex set
$V$.

##  4 A generating function for X-descent sets

From the definition $(\ref{descents})$ of the Redei-Berge symmetric function
we have

$U_{X}=\sum_{\sigma\in\Sigma_{V}}F_{X\mathrm{Des}(\sigma)}=\sum_{\sigma\in\Sigma_{V}}\sum_{X\mathrm{Des}(\sigma)=I}F_{I}=\sum_{I\subset[n-1]}\lambda_{I}(X)F_{I},$
(10)

where the coefficients are given by

$\lambda_{I}(X)=\\#\\{\sigma\in\Sigma_{V}|X\mathrm{Des}(\sigma)=I\\}.$

In the basis of monomial quasisymmetric functions we obtain using
$(\ref{montofund})$

$U_{X}=\sum_{\sigma\in\Sigma_{V}}\sum_{XDes(\sigma)\subset
I}M_{I}=\sum_{I\subset[n-1]}\mu_{I}(X)M_{I},$ (11)

where

$\mu_{I}(X)=\\#\\{\sigma\in\Sigma_{V}|XDes(\sigma)\subset I\\}.$

Grinberg and Stanley in [4, Theorem 1.31] expanded the function $U_{X}$ in the
power sum basis of the algebra of symmetric functions. As a part of this
expansion they obtained an interpretation of $U_{X}$ as a certain enumerator
of colorings of vertices with positive integers. We emphasize this
interpretation in the following proposition.

######  Definition 4.1.

Let $X$ be a digraph on the vertex set $V$. For a coloring of vertices with
positive integers $f:V\rightarrow\mathbb{P}$, a permutation
$\sigma=(\sigma_{1},\ldots,\sigma_{n})\in\Sigma_{V}$ is called
$(f,X)$-friendly if

$f(\sigma_{1})\leq f(\sigma_{2})\leq\cdots\leq f(\sigma_{n})\ \text{and}$
$f(\sigma_{j})<f(\sigma_{j+1})\ \mathrm{for\ each}\ j\in[n-1]\
\mathrm{satisfying}\ (\sigma_{j},\sigma_{j+1})\in X.$

Denote by $\Sigma_{V}(f,X)$ the set of all $(f,X)$-friendly permutations and
by $\delta_{f}:\Sigma_{V}\rightarrow\\{0,1\\}$ its indicator function. For a
coloring $f:V\rightarrow\mathbb{P}$ we write $\mathbf{x}_{f}=\prod_{v\in
V}x_{f(v)}$.

######  Proposition 4.2 ([4, section 2.11]).

The generating function $U_{X}$ of a digraph $X$ on the vertex set $V$ is
given by

$U_{X}=\sum_{f:V\rightarrow\mathbb{P}}\sum_{\sigma\in\Sigma_{V}}\delta_{f}(\sigma)\mathbf{x}_{f}.$

###### Proof.

Let $V=\\{v_{1}<\cdots<v_{n}\\}$ be the linear order of vertices. For a
coloring $g:V\rightarrow\mathbb{P}$ we have that a permutation $\sigma$ is
$(g\circ\sigma^{-1},X)$-friendly if and only if $g$ is monotonly
nondecreasing, $g(v_{1})\leq\cdots\leq g(v_{n})$, and $g(v_{j})<g(v_{j+1})$
for each $j\in X\mathrm{Des}(\sigma)$. Therefore the fundamental
quasisymmetric function $F_{X\mathrm{Des}(\sigma)}$ defined by
$(\ref{fundamental})$ can be described as

$F_{X\mathrm{Des}\sigma}=\sum_{g:V\rightarrow\mathbb{P}}\delta_{g\circ\sigma^{-1}}(\sigma)\mathbf{x}_{g}.$

Since the correspondence $f=g\circ\sigma^{-1}$ is a bijection of colorings we
have

$F_{X\mathrm{Des}(\sigma)}=\sum_{f:V\rightarrow\mathbb{P}}\sigma_{f}(\sigma)\mathbf{x}_{f\circ\sigma}=\sum_{f:V\rightarrow\mathbb{P}}\sigma_{f}(\sigma)\mathbf{x}_{f}.$

The latter equality is obtained by taking into account commutativity of
variables, $\mathbf{x}_{f\circ\sigma}=\mathbf{x}_{f}$. Summing over all
$\sigma\in\Sigma_{V}$ we obtain

$U_{X}=\sum_{\sigma\in\Sigma_{V}}\sum_{f:V\rightarrow\mathbb{P}}\sigma_{f}(\sigma)\mathbf{x}_{f}=\sum_{f:V\rightarrow\mathbb{P}}\sum_{\sigma\in\Sigma_{V}}\delta_{f}(\sigma)\mathbf{x}_{f}.$

∎

By proposition 4.2 the symmetric function $U_{X}$ is described as an integer
points enumerator. This was immanent in the theory of generalized
permutohedra, see [5] for details. The colorings $f:V\rightarrow\mathbb{P}$
are positive integer points in the Euclidian space $\mathbb{R}^{V}$. The
hyperplanes $t_{v_{i}}=t_{v_{j}},1\leq i<j\leq n$ form the braid arrangement
which divides the space into cones $c_{\mathcal{F}}$ described by flags of
vertices

$\mathcal{F}:\emptyset=F_{0}\subset F_{1}\subset\cdots\subset F_{k-1}\subset
F_{k}=V$

with $t_{v_{p}}=t_{v_{q}}$ if $v_{p},v_{q}\in F_{i+1}\setminus F_{i}$ for some
$i=0,1,\ldots,k-1$ and $t_{v_{p}}\leq t_{v_{q}}$ if $v_{p}\in F_{i}\setminus
F_{i-1}$ and $v_{q}\in F_{i+1}\setminus F_{i}$ for some $i=1,\ldots,k-1$.
Flags are in bijective correspondence with compositions by the assignment
$\text{comp}(\mathcal{F})=(V_{1},\ldots,V_{k})\models V$, where
$V_{i}=F_{i}\setminus F_{i-1},i=1,\ldots,k$. We say that $\mathcal{F}$ is of
the length $|\mathcal{F}|=k$ and of the type
$(\mathcal{F})=(|V_{1}|,\ldots,|V_{k}|)$. A coloring
$f:V\rightarrow\mathbb{P}$ is an $\mathcal{F}$-coloring if and only if it
belongs, as the point in $\mathbb{R}^{V}$, to the relative interior $f\in
c_{\mathcal{F}}^{\circ}$ of the cone $c_{\mathcal{F}}$. Let $M_{\mathcal{F}}$
be the enumerator of $\mathcal{F}$-colorings

$M_{\mathcal{F}}=\sum_{f\in c_{\mathcal{F}}^{\circ}}\mathbf{x}_{f}.$

It depends only on the type of a flag, i.e.
$M_{\mathcal{F}}=M_{(\mathcal{F})}$. The following obvious lemma shows that
the indicator $\delta_{f}$ depends only on the braid cone containing the
coloring $f$.

######  Lemma 4.3.

Let $f,g\in\mathbb{P}^{V}$ be colorings of vertices of a digraph $X$. Suppose
there is a braid cone $c_{\mathcal{F}}\subset\mathbb{R}^{V}$ containing them
in its relative interior $f,g\in c_{\mathcal{F}}^{\circ}$. Then
$\Sigma(f,X)=\Sigma(g,X)$.

According to the previous lemma the following definition is correct.

######  Definition 4.4.

A permutation $\sigma\in\Sigma_{V}$ is $(\mathcal{F},X)$-friendly if it is
$(f,X)$-friendly for some coloring $f\in c_{\mathcal{F}}^{\circ}$.

We give another characterization for $(\mathcal{F},X)$-friendly permutations
which leads to their total number.

######  Lemma 4.5.

Let $\mathcal{F}$ be a flag of vertices corresponded to the set composition
$\text{comp}(\mathcal{F})=(V_{1},\ldots,V_{k})\models V$ and
$X_{i}=X|_{V_{i}},i=1,\ldots,k$ be the restrictions of $X$. A permutation
$\sigma\in\Sigma_{V}$ is $(\mathcal{F},X)$-friendly if and only if it can be
written as the concatenation $\sigma=\sigma^{1}\cdots\sigma^{k}$ of
Hamiltonian paths $\sigma^{i}\in\Sigma_{V_{i}}$ of complementary digraphs
$\overline{X}_{i}$. The total number of $(\mathcal{F},X)$-friendly
permutations is given by

$|\Sigma_{V}(\mathcal{F},X)|=\zeta([X_{1}])\cdots\zeta([X_{k}]).$

######  Proposition 4.6.

The symmetric function $U_{X}$ of a digraph $X$ on the vertex set $V$ has the
following expansion

$U_{X}=\sum_{\mathcal{F}}|\Sigma(\mathcal{F},X)|M_{\mathcal{F}}.$

###### Proof.

The identity follows from proposition 4.2

$U_{X}=\sum_{f:V\rightarrow\mathbb{P}}\sum_{\sigma\in\Sigma_{V}}\delta_{f}(\sigma)\mathbf{x}_{f}=\sum_{\mathcal{F}}\sum_{f\in
c_{\mathcal{F}}^{\circ}}\big{(}\sum_{\sigma\in\Sigma_{V}}\delta_{f}(\sigma)\big{)}\mathbf{x}_{f}=\sum_{\mathcal{F}}|\Sigma(\mathcal{F},X)|\sum_{f\in
c_{\mathcal{F}}^{\circ}}\mathbf{x}_{f}.$

∎

######  Theorem 4.7.

Let $\Psi:\mathcal{D}\rightarrow QSym$ be a universal morphism from the
combinatorial Hopf algebra of digraphs to quasisymmetric functions. Then for a
digraph $X$

$\Psi([X])=U_{X}.$

###### Proof.

According to the expansion of proposition 4.6 we have

$U_{X}=\sum_{\alpha\models|V|}\Big{(}\sum_{(\mathcal{F})=\alpha}|\Sigma_{V}(\mathcal{F},X)|\Big{)}M_{\alpha},$

which shows that

$\mu_{I}(X)=\sum_{(\mathcal{F})=\text{comp}(I)}|\Sigma_{V}(\mathcal{F},X)|.$

By the characterization 4.5 we have further

$\mu_{I}(X)=\sum_{\text{type}(V_{1},\ldots,V_{k})=\text{comp}(I)}\zeta([X|_{V_{1}}])\cdots\zeta([X|_{V_{k}}]).$

This is exactly the coefficient $(\ref{zeta})$

$\mu_{I}(X)=\zeta_{\text{comp}(I)}([X]).$

∎

We are interested in relations between symmetric functions
$U_{X},U_{X^{\text{op}}}$ and $U_{\overline{X}}$.

######  Proposition 4.8.

The Redei-Berge symmetric functions of a digraph $X$ and its opposite digraph
$X^{\text{op}}$ are equal

$U_{X^{\text{op}}}=U_{X}.$

###### Proof.

For a permutation $\sigma\in\Sigma_{V}$ of vertices $V$ it follows from 3.3
that $XDes(\sigma)\subset I$ if and only if
$X^{\text{op}}Des(\mathrm{rev}\sigma)\subset I^{\text{op}}$ for any subset
$I\subset[n-1]$. Therefore
$\mu_{I}(X)=\mu_{I^{\text{op}}}(X^{\text{op}}),I\subset[n-1]$. The operation
of reversion can be defined on the monomial bases by
$\mathrm{rev}M_{I}=M_{I^{\text{op}}}$ and linearly extended to all
quasisymmetric functions. Using expansion $(\ref{monomial})$ we obtain

$U_{X}=\mathrm{rev}U_{X^{\text{op}}}.$

The statement follows since the reversion on symmetric functions is an
identity.

∎

The operation of taking the complementary digraph leads to the Grinberg and
Stanley antipode formula [4, Theorem 8.1]. We reprove this formula avoiding
the power sum expansion.

######  Theorem 4.9.

The antipode $S$ acts on the Redei-Berge symmetric function $U_{X}$ of a
digraph $X$ on the vertex set $V$ by

$S(U_{X})=(-1)^{|V|}U_{\overline{X}}.$

###### Proof.

By the expansion $(\ref{fundamentalexp})$ of $U_{X}$ and the action of $S$ on
fundamental quasisymmetric functions $(\ref{fundantipod})$ we have

$S(U_{X})=\sum_{I}\lambda_{I}(X)S(F_{I})=(-1)^{|V|}\sum_{I}\lambda_{I}(X)F_{(I^{\text{op}})^{c}}.$

Changing the summing variable $J=(I^{\text{op}})^{c}$ gives

$S(U_{X})=(-1)^{|V|}\sum_{J}\lambda_{(J^{c})^{\text{op}}}(X)F_{J}.$

It follows from lemma 3.3 that

$\lambda_{(J^{c})^{\text{op}}}(X)=\lambda_{J^{c}}(X^{\text{op}})=\lambda_{J}(\overline{X^{\text{op}}})=\lambda_{J}((\overline{X})^{\text{op}}).$

The last identity is a consequence of lemma 3.2. Finally, proposition 4.8
implies $\lambda_{J}((\overline{X})^{\text{op}})=\lambda_{J}(\overline{X})$
which finishes the proof. ∎

##  5 The Redei-Berge polynomial

We call the principal specialization $u_{X}(m)=\mathrm{ps}^{1}(U_{X})(m)$ the
Redei-Berge polynomial. It is an immediate consequence of proposition 4.2 that

$u_{X}(m)=\sum_{f:V\rightarrow[m]}|\Sigma_{V}(f,X)|,$

which reveals the combinatorial nature of this polynomial.

######  Proposition 5.1.

The Redei-Berge polynomial $u_{X}(m)$ counts $(f,X)$-friendly permutations for
colorings $f:V\rightarrow[m]$ with at most $m$ colors.

The reciprocity formula $(\ref{reciprocity})$ and the antipode formula of
theorem 4.9 give the following identity.

######  Proposition 5.2.

The Redei-Berge polynomial satisfies

$u_{X}(-m)=(-1)^{|V|}u_{\overline{X}}(m).$

The Berge theorem about Hamiltonian paths of a digraph is a consequence of the
reciprocity theorem for the Redei-Berge polynomial $u_{X}(m)$.

######  Theorem 5.3.

The numbers of Hamiltonian paths of a digraph $X$ and its complementary
digraph $\overline{X}$ are of the same parity.

###### Proof.

It follows from the definition $(\ref{character})$ of the character $\zeta$
that

$\mu_{\emptyset}(\overline{X})=\zeta([{\overline{X}}])$

detects the number of Hamiltonian paths of $X$. We have

$u_{X}(1)=\mathrm{ps}^{1}(U_{X})(1)=\mu_{\emptyset}(X).$

On the other hand, from proposition 5.2 we obtain

$u_{X}(-1)=(-1)^{|V|}u_{\overline{X}}(1)=(-1)^{|V|}\mu_{\emptyset}(\overline{X}).$

Since $u_{X}(1)$ and $u_{X}(-1)$ are of the same parity the statement follows.
∎

##  6 Tournaments

A tournament is a digraph $X=(V,E,<)$ such that either $(u,v)\in E$ or
$(v,u)\in E$ for all vertices $u,v\in V$. Tournaments are obviously closed
under operations of taking restrictions and products, so their isomorphism
classes generate a Hopf subalgebra $\mathcal{T}\subset\mathcal{D}$ of the Hopf
algebra of digraphs. We call $\mathcal{T}$ the Hopf algebra of tournaments.
The complementary digraph $\overline{X}$ of a tournament $X$ is a tournament
itself and is equal to its opposite digraph $\overline{X}=X^{\text{op}}$. The
proposition 4.8 and the theorem 4.9 imply

######  Corollary 6.1.

For each tournament we have $U_{X}=U_{\overline{X}}$. The antipode acts on
$U_{X}$ by $S(U_{X})=(-1)^{|V|}U_{X}$.

## References

  * [1] M. Aguiar, N. Bergeron, F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compositio Mathematica 142 (2006) 1-30.
  * [2] C. Berge, Graphs and Hypergraphs, North-Holland Mathematical Library 6, 2nd edition, North-Holland 1976.
  * [3] D. Grinberg, V. Reiner, Hopf algebras in combinatorics, arXiv::1409.8356v7
  * [4] D. Grinberg, R. Stanley, The Redei-Berge symmetric function of a directed graph, arXiv::2307.05569v1
  * [5] V. Grujić, M. Pešović, T. Stojadinović, Weighted quasisymmetric enumerator for generalized permutohedra, J Algebr Comb 51 (2020), 247-272.
  * [6] L. Redei, Ein kombinatorischer Satz, Acta Litteraria Szeged 7 (1934), 39-43.
  * [7] R. Stanley, The X-Descent set of a permutation, Combinatorial and Algebraic Enumeration, Waterloo, Ontario, 2022. available at: https://math.mit.edu/~rstan/transparencies/gj.pdf
  * [8] R. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Univ. Press, Cambridge, 1999\.


# Hypercyclic and mixing composition operators on $H^{p}$

Zhen Rong  Z.R., College of statistics and mathematics, Inner Mongolia
University of Finance and Economics, Hohhot 010000, China.
<EMAIL_ADDRESS>
(Date: June 30, 2022)

###### Abstract.

Extending previous results of Bourdon and Shapiro we characterize the
hypercyclic and mixing composition operators $C_{\varphi}$ for the
automorphisms of $\mathbb{D}$ on any of the spaces $H^{p}$ with $1\leqslant
p<+\infty$.

###### Key words and phrases:

Hypercyclic operators, mixing operators, composition operators

###### 2010 Mathematics Subject Classification:

47A16, 47B38

##  1\. Introduction

Throughout this article, let $\mathbb{N}$ denote the set of nonnegative
integers. Let $\mathbb{C}$ denote the complex number field. Let
$\mathbb{T}=\\{z\in\mathbb{C}:|z|=1\\}$ and
$\mathbb{D}=\\{z\in\mathbb{C}:|z|<1\\}$.

An automorphism of $\mathbb{D}$ is a bijective analytic function
$\varphi:\mathbb{D}\rightarrow\mathbb{D}$. The set of all automorphisms of
$\mathbb{D}$ is denoted by $Aut(\mathbb{D})$. It is well known that the
automorphisms of $\mathbb{D}$ are the linear fractional transformations

$\varphi(z)=b\frac{z-a}{1-\overline{a}z},|a|<1,|b|=1.$

Moreover, every $\varphi\in Aut(\mathbb{D})$ maps $\mathbb{T}$ bijectively
onto itself (see [8, pages 131-132]).

For $1\leqslant p<+\infty$, let $H^{p}$ denote the space of all analytic
functions on $\mathbb{D}$ for which

$\sup\limits_{0\leqslant
r<1}(\frac{1}{2\pi}\int_{0}^{2\pi}|f(re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}<+\infty.$

For any $f\in H^{p}$, let

$\|f\|_{p}=\sup\limits_{0\leqslant
r<1}(\frac{1}{2\pi}\int_{0}^{2\pi}|f(re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}.$

Then $(H^{p},\|\cdot\|_{p})$ is a Banach space.

Let $\varphi\in Aut(\mathbb{D})$ and let $C_{\varphi}(f)=f\circ\varphi(f\in
H^{p})$ be the corresponding composition operator on $H^{p}$. It is well known
that for any $1\leqslant p<+\infty$ and $\varphi\in Aut(\mathbb{D})$,
$C_{\varphi}$ defines a continuous linear operator on $H^{p}$ (see [25, pages
220-221]).

A continuous linear operator $T$ on a Banach space $X$ is called hypercyclic
if there is an element $x$ in $X$ whose orbit $\\{T^{n}x:n\in\mathbb{N}\\}$
under $T$ is dense in $X$; topologically transitive if for any pair $U,V$ of
nonempty open subsets of $X$, there exists some nonnegative integer $n$ such
that $T^{n}(U)\cap V\neq\emptyset$; and mixing if for any pair $U,V$ of
nonempty open subsets of $X$, there exists some nonnegative integer $N$ such
that $T^{n}(U)\cap V\neq\emptyset$ for all $n\geqslant N$.

The historical interest in hypercyclicity is related to the invariant subset
problem. The invariant subset problem, which is open to this day, asks whether
every continuous linear operator on any infinite dimensional separable Hilbert
space possesses an invariant closed subset other than the trivial ones given
by $\\{0\\}$ and the whole space. Counterexamples do exist for continuous
linear operators on non-reflexive spaces like $l^{1}$. After a simple
observation, a continuous linear operator $T$ on a Banach space $X$ has no
nontrival invariant closed subsets if and only if every nonzero vector $x$ is
hypercyclic (i.e. the orbit $\\{T^{n}x:n\in\mathbb{N}\\}$ under $T$ is dense
in $X$).

The best known examples of hypercyclic operators are due to Birkhoff [4],
MacLane [18] and Rolewicz [21]. Each of these papers had a profound influence
on the literature on hypercyclicity. Birkhoff’s result on the hypercyclicity
of the translation operator $T_{a}(f)(z)=f(z+a),a\neq 0,$ on the space
$H(\mathbb{C})$ of entire functions has led to an extensive study of
hypercyclic composition operators (see [15, pages 110-118]), while MacLane’s
result on the hypercyclicity of the differentiation operator $Df=f^{\prime}$
on $H(\mathbb{C})$ initiated the study of hypercyclic differential operators
(see [15, pages 104-110]). Shift operators on Banach sequence spaces were
first studied by Rolewicz [21] who showed that for any $\lambda>1$ the
multiple $\lambda B$ of the unilateral unweighted backward shift $B$ on the
Banach sequence spaces $l^{p}(1\leqslant p<+\infty)$ or $c_{0}$ is
hypercyclic. Since then the hypercyclic, mixing, weakly mixing and chaotic
properties of shift operators have been studied by several authors (see [1, 2,
3, 4, 7, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]).

Recently Bourdon and Shapiro [5, 6] have done an extensive study of cyclic and
hypercyclic linear fractional composition operators on $H^{2}$. Zorboska [26]
has determined hypercyclic and cyclic composition operators induced by a
linear fractional self map of $\mathbb{D}$, acting on a special class of
smooth weighted Hardy spaces $H^{2}(\beta)$. Gallardo and Montes [11] have
obtained a complete characterization of the cyclic, supercyclic and
hypercyclic composition operators $C_{\varphi}$ for linear fractional self-
maps $\varphi$ of $\mathbb{D}$ on any of the spaces
$\mathcal{S}_{\nu},\nu\in\mathbb{R}$. In particular, $\mathcal{S}_{0}$ is the
Hardy space $H^{2}$, $\mathcal{S}_{-1/2}$ is the Bergman space $A^{2}$, and
$\mathcal{S}_{1/2}$ is the Dirichlet space $\mathcal{D}$ under an equivalent
norm. Since the Hardy space $H^{2}$ is a particular case of the spaces $H^{p}$
with $1\leqslant p<+\infty$, it is therefore very natural to try to
characterize the cyclic, supercyclic and hypercyclic composition operators
$C_{\varphi}$ for linear fractional self-maps $\varphi$ of $\mathbb{D}$ on any
of the spaces $H^{p}$ with $1\leqslant p<+\infty$. In this paper we will
characterize the hypercyclic and mixing composition operators $C_{\varphi}$
for the automorphisms of $\mathbb{D}$ on any of the spaces $H^{p}$ with
$1\leqslant p<+\infty$, generalizing the corresponding results in [5, 6].

######  Theorem 1.1.

Let $1\leqslant p<+\infty$. Let $\varphi\in Aut(\mathbb{D})$ and $C_{\varphi}$
be the corresponding composition operator on $H^{p}$. Then the following
assertions are equivalent:

(1) $C_{\varphi}$ is hypercyclic;

(2) $C_{\varphi}$ is mixing;

(3) $\varphi$ has no fixed point in $\mathbb{D}$.

Bourdon and Shapiro [5, 6] proved the above result in the case $p=2$. Hence
the above result generalizes the corresponding results in [5, 6].

This paper is organized as follows. In Section 2 we characterize the
hypercyclic and mixing composition operators $C_{\varphi}$ for the
automorphisms of $\mathbb{D}$ on any of the spaces $H^{p}$ with $1\leqslant
p<+\infty$.

Acknowledgments. Z. R. was supported by Research Program of Science at
Universities of Inner Mongolia Autonomous Region (Grant No. NJZY22328).

##  2\. Hypercyclic and mixing composition operators on $H^{p}$

In this section we characterize the hypercyclic and mixing composition
operators $C_{\varphi}$ for the automorphisms of $\mathbb{D}$ on any of the
spaces $H^{p}$ with $1\leqslant p<+\infty$, generalizing the corresponding
results in [5, 6].

Recall the notion of annihilator introduced in [24, page 163].

######  Definition 2.1.

Let $X$ be a normed linear space. If $A\subseteq X$, the annihilator
$A^{\bot}$ of $A$ is the set

$A^{\bot}=\\{x^{\prime}\in X^{\ast}:x^{\prime}(x)=0\text{ for all }x\in A\\},$

where $X^{\ast}$ is the set of continuous linear functionals on $X$.

If $F\subseteq X^{\ast}$, the annihilator $F^{\bot}$ of $F$ is the set

$F^{\bot}=\\{x\in X:x^{\prime}(x)=0\text{ for all }x^{\prime}\in F\\}.$

The following technical results will help us characterize hypercyclic and
mixing composition operators on $H^{p}$ for $1\leqslant p<+\infty$.

The following proposition is well known (see [24, page 164]).

######  Proposition 2.2.

A normed linear space $X$ is a reflexive Banach space if and only if every
norm-closed linear subspace in $X^{\ast}$ is $\sigma(X^{\ast},X)$-closed,
where $\sigma(X^{\ast},X)$ is the weak∗ topology on $X^{\ast}$.

We need the following proposition (see [24, pages 163-164]).

######  Proposition 2.3.

Let $X$ be a normed linear space. If $F$ is a nonempty subset of $X^{\ast}$,
then $F^{\bot\bot}$ is the $\sigma(X^{\ast},X)$-closed linear subspace
generated by $F$, where $F^{\bot\bot}=(F^{\bot})^{\bot}$.

We need the following Kitai criterion (see [15, page 71]).

######  Proposition 2.4.

Let $T$ be a continuous linear operator on a Banach space $X$. If there are
dense subsets $X_{0},Y_{0}\subseteq X$ and a map $S:Y_{0}\rightarrow Y_{0}$
such that, for any $x\in X_{0},y\in Y_{0}$,

(i) $T^{n}x\rightarrow 0$,

(ii) $S^{n}y\rightarrow 0$,

(iii) $TSy=y$,

then $T$ is mixing.

The following propositions are the major techniques we need.

######  Proposition 2.5.

For any $1\leqslant p<+\infty$, each point evaluation
$k_{\lambda}:H^{p}\rightarrow\mathbb{C}(\lambda\in\mathbb{D})$ is continuous
on $H^{p}$, where $k_{\lambda}(f)=f(\lambda)(f\in H^{p})$.

###### Proof.

Let $\lambda\in\mathbb{D}$, $\\{f_{n}\\}_{n=1}^{\infty}$ be a sequence in
$H^{p}$, $f\in H^{p}$ and $\lim\limits_{n\rightarrow\infty}\|f_{n}-f\|_{p}=0$.
We will show that $\lim\limits_{n\rightarrow\infty}f_{n}(\lambda)=f(\lambda)$.
Since $\lambda\in\mathbb{D}$, we may choose $r,R\in(0,1)$ with
$|\lambda|<r<R<1$. Notice that

$\displaystyle\|f_{n}-f\|_{p}\geqslant$
$\displaystyle(\frac{1}{2\pi}\int_{0}^{2\pi}|f_{n}(Re^{i\theta})-f(Re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$
$\displaystyle\geqslant$
$\displaystyle\frac{1}{(2\pi)^{\frac{1}{p}}}(\int_{0}^{2\pi}|f_{n}(Re^{i\theta})-f(Re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$
$\displaystyle\geqslant$
$\displaystyle\frac{1}{(2\pi)^{\frac{1}{p}}}\frac{1}{(2\pi)^{\frac{1}{q}}}\int_{0}^{2\pi}|f_{n}(Re^{i\theta})-f(Re^{i\theta})|d\theta(\text{
where }\frac{1}{p}+\frac{1}{q}=1)$ $\displaystyle=$
$\displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}|f_{n}(Re^{i\theta})-f(Re^{i\theta})|d\theta.$

By Cauchy’s integral formula, we have

$\displaystyle(f_{n}-f)(\lambda)=$ $\displaystyle\frac{1}{2\pi
i}\int_{\gamma}\frac{(f_{n}-f)(\omega)}{\omega-\lambda}d\omega(\text{ where
}\gamma(t)=Re^{i\theta},0\leqslant\theta\leqslant 2\pi)$ $\displaystyle=$
$\displaystyle\frac{1}{2\pi
i}\int_{0}^{2\pi}\frac{f_{n}(Re^{i\theta})-f(Re^{i\theta})}{Re^{i\theta}-\lambda}d(Re^{i\theta})$
$\displaystyle=$
$\displaystyle\frac{R}{2\pi}\int_{0}^{2\pi}\frac{f_{n}(Re^{i\theta})-f(Re^{i\theta})}{Re^{i\theta}-\lambda}e^{i\theta}d\theta.$

Therefore

$\displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}|f_{n}(Re^{i\theta})-f(Re^{i\theta})|d\theta$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}|\frac{f_{n}(Re^{i\theta})-f(Re^{i\theta})}{Re^{i\theta}-\lambda}e^{i\theta}|\cdot|Re^{i\theta}-\lambda|d\theta$
$\displaystyle\geqslant\frac{R-r}{2\pi}\int_{0}^{2\pi}|\frac{f_{n}(Re^{i\theta})-f(Re^{i\theta})}{Re^{i\theta}-\lambda}e^{i\theta}|d\theta$
$\displaystyle\geqslant\frac{R-r}{2\pi}|\int_{0}^{2\pi}\frac{f_{n}(Re^{i\theta})-f(Re^{i\theta})}{Re^{i\theta}-\lambda}e^{i\theta}d\theta|$
$\displaystyle=\frac{R-r}{2\pi}|\frac{2\pi}{R}(f_{n}(\lambda)-f(\lambda))|$
$\displaystyle=\frac{R-r}{R}|f_{n}(\lambda)-f(\lambda)|.$

Hence $\|f_{n}-f\|_{p}\geqslant\frac{R-r}{R}|f_{n}(\lambda)-f(\lambda)|$.
Since $\lim\limits_{n\rightarrow\infty}\|f_{n}-f\|_{p}=0$,
$\lim\limits_{n\rightarrow\infty}f_{n}(\lambda)=f(\lambda)$. ∎

$\Box$

If $f\in H^{p}(1\leqslant p<+\infty)$, then $\lim\limits_{r\rightarrow
1^{-}}f(re^{i\theta})$ exists for almost all values of $\theta$ (see [10, page
17]), thus defining a function which we denote by $f(e^{i\theta})$.

######  Proposition 2.6.

For any $1<p<+\infty$, $H^{p}$ is reflexive.

###### Proof.

Since $1<p<+\infty$, each $\phi\in(H^{p})^{\ast}$ is representable in the
following form

$\phi(f)=\frac{1}{2\pi}\int_{0}^{2\pi}f(e^{i\theta})g(e^{-i\theta})d\theta(f\in
H^{p})$

by a unique function $g\in H^{q}$, where $\frac{1}{p}+\frac{1}{q}=1$.
Furthermore, the linear operator $T:(H^{p})^{\ast}\rightarrow H^{q}$ defined
by $T(\phi)=g(\phi\in(H^{p})^{\ast})$ is a topological isomorphism (see [10,
pages 112-113]). Let $x^{\prime\prime}\in(H^{p})^{\ast\ast}$. We will show
that there exists a $g\in H^{p}$ such that
$x^{\prime\prime}(x^{\prime})=x^{\prime}(g)$ for all
$x^{\prime}\in(H^{p})^{\ast}$. Let $y^{\prime\prime}=x^{\prime\prime}\circ
T^{-1}$. Then $y^{\prime\prime}\in(H^{q})^{\ast}$ and
$y^{\prime\prime}(Tx^{\prime})=x^{\prime\prime}(x^{\prime})$ for
$x^{\prime}\in(H^{p})^{\ast}$. Hence there exists a unique function $g\in
H^{p}$ such that

$y^{\prime\prime}(f)=\frac{1}{2\pi}\int_{0}^{2\pi}f(e^{i\theta})g(e^{-i\theta})d\theta(f\in
H^{q}).$

Therefore, if $x^{\prime}\in(H^{p})^{\ast}$,

$\displaystyle x^{\prime\prime}(x^{\prime})=$ $\displaystyle
y^{\prime\prime}(Tx^{\prime})$ $\displaystyle=$
$\displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}(Tx^{\prime})(e^{i\theta})g(e^{-i\theta})d\theta$
$\displaystyle=$
$\displaystyle-\frac{1}{2\pi}\int_{0}^{-2\pi}g(e^{i\theta})(Tx^{\prime})(e^{-i\theta})d\theta$
$\displaystyle=$
$\displaystyle\frac{1}{2\pi}\int_{-2\pi}^{0}g(e^{i\theta})(Tx^{\prime})(e^{-i\theta})d\theta$
$\displaystyle=$
$\displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}g(e^{i\theta})(Tx^{\prime})(e^{-i\theta})d\theta$
$\displaystyle=$ $\displaystyle x^{\prime}(g).$

This implies that $x^{\prime\prime}(x^{\prime})=x^{\prime}(g)$ for all
$x^{\prime}\in(H^{p})^{\ast}$ and $H^{p}$ is reflexive. ∎

$\Box$

We need the following important properties of the $H^{p}$-spaces (see [10,
pages 9, 12, 21]).

######  Proposition 2.7.

Let $f\in H^{p},1\leqslant p<+\infty$. Then

(1) $\|f\|_{p}=\lim\limits_{r\rightarrow
1^{-}}(\frac{1}{2\pi}\int_{0}^{2\pi}|f(re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$;

(2) $\lim\limits_{r\rightarrow
1^{-}}\int_{0}^{2\pi}|f(re^{i\theta})|^{p}d\theta=\int_{0}^{2\pi}|f(e^{i\theta})|^{p}d\theta$;

(3) $\lim\limits_{r\rightarrow
1^{-}}\int_{0}^{2\pi}|f(re^{i\theta})-f(e^{i\theta})|^{p}d\theta=0$.

######  Proposition 2.8.

Let $1\leqslant p<+\infty$. Then the polynomials form a dense set in $H^{p}$.
Hence $H^{p}$ is separable.

###### Proof.

It is obvious that every polynomial belongs to $H^{p}$. Next we will show that
the polynomials form a dense set in $H^{p}$.

Given $f\in H^{p}$ and $\varepsilon>0$. By Proposition 2.7 we have

$\lim_{r\rightarrow
1^{-}}\int_{0}^{2\pi}|f(re^{i\theta})-f(e^{i\theta})|^{p}d\theta=0.$

Hence we may choose $0<\rho<1$ such that

$\int_{0}^{2\pi}|f(\rho
e^{i\theta})-f(e^{i\theta})|^{p}d\theta<2\pi(\frac{\varepsilon}{2})^{p}.$

Now let $S_{n}(z)$ denote the $n$th partial sum of the Taylor series of $f$ at
the origin. Since $S_{n}(z)\rightarrow f(z)$ uniformly on
$\\{z\in\mathbb{C}:|z|=\rho\\}$, we may choose a positive integer $n_{0}$ such
that

$\int_{0}^{2\pi}|S_{n_{0}}(\rho e^{i\theta})-f(\rho
e^{i\theta})|^{p}d\theta<2\pi(\frac{\varepsilon}{2})^{p}.$

Thus, using Minkowski’s inequality in the case $1\leqslant p<+\infty$, we find

$\displaystyle(\int_{0}^{2\pi}|S_{n_{0}}(\rho
e^{i\theta})-f(e^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$
$\displaystyle\leqslant(\int_{0}^{2\pi}|S_{n_{0}}(\rho e^{i\theta})-f(\rho
e^{i\theta})|^{p}d\theta)^{\frac{1}{p}}+(\int_{0}^{2\pi}|f(\rho
e^{i\theta})-f(e^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$
$\displaystyle<(2\pi)^{\frac{1}{p}}\frac{\varepsilon}{2}+(2\pi)^{\frac{1}{p}}\frac{\varepsilon}{2}$
$\displaystyle=(2\pi)^{\frac{1}{p}}\varepsilon.$

Let $(S_{n_{0}})_{\rho}(z)=S_{n_{0}}(\rho z)(z\in\mathbb{C})$. Next we will
show that $\|(S_{n_{0}})_{\rho}-f\|_{p}<\varepsilon$.

$\displaystyle\|(S_{n_{0}})_{\rho}-f\|_{p}=$
$\displaystyle\sup\limits_{0\leqslant
r<1}(\frac{1}{2\pi}\int_{0}^{2\pi}|S_{n_{0}}(r\rho
e^{i\theta})-f(re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$ $\displaystyle=$
$\displaystyle\lim_{r\rightarrow
1^{-}}(\frac{1}{2\pi}\int_{0}^{2\pi}|S_{n_{0}}(r\rho
e^{i\theta})-f(re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}(\text{ By Proposition
2.7})$ $\displaystyle=$
$\displaystyle\frac{1}{(2\pi)^{\frac{1}{p}}}\lim_{r\rightarrow
1^{-}}(\int_{0}^{2\pi}|S_{n_{0}}(r\rho
e^{i\theta})-f(re^{i\theta})|^{p}d\theta)^{\frac{1}{p}}$ $\displaystyle=$
$\displaystyle\frac{1}{(2\pi)^{\frac{1}{p}}}(\int_{0}^{2\pi}|S_{n_{0}}(\rho
e^{i\theta})-f(e^{i\theta})|^{p}d\theta)^{\frac{1}{p}}(\text{ By Proposition
2.7})$ $\displaystyle<$
$\displaystyle\frac{1}{(2\pi)^{\frac{1}{p}}}(2\pi)^{\frac{1}{p}}\varepsilon$
$\displaystyle=$ $\displaystyle\varepsilon.$

Notice that $(S_{n_{0}})_{\rho}$ is also a polynomial. Hence the polynomials
form a dense set in $H^{p}$. ∎

$\Box$

We need the following property of the Taylor coefficients of $H^{p}$ functions
(see [10, page 94]).

######  Proposition 2.9.

Let $1\leqslant p\leqslant 2$ and $f\in H^{p}$. Let
$\sum\limits_{n=0}^{\infty}a_{n}z^{n}$ be the Taylor series of $f$ at the
origin. Then $\\{a_{n}\\}_{n=0}^{\infty}\in l^{q}$, where
$\frac{1}{p}+\frac{1}{q}=1$.

Our aim now is to characterize when $C_{\varphi}$ is hypercyclic on $H^{p}$.
To this end we need some important dynamical properties of automorphisms
$\varphi$ of $\mathbb{D}$.

Let

$\varphi(z)=\frac{az+b}{cz+d},ad-bc\neq 0$

be an arbitrary linear fractional transformation, which we consider as a map
on the extended complex plane $\widehat{\mathbb{C}}$. Then $\varphi$ has
either one or two fixed points in $\widehat{\mathbb{C}}$, or it is the
identity.

Suppose that $\varphi$ has two distinct fixed points $z_{0}$ and $z_{1}$, and
let $\sigma$ be a linear fractional transformation that maps $z_{0}$ to 0 and
$z_{1}$ to $\infty$. Then $\psi:=\sigma\circ\varphi\circ\sigma^{-1}$ has fixed
points 0 and $\infty$, which easily implies that $\psi(z)=\lambda z$ for some
$\lambda\neq 0$. The constant $\lambda$ is called the _multiplier_ of
$\varphi$. Replacing $\sigma$ by $1/\sigma$ one sees that also $1/\lambda$ is
a multiplier, which, however, causes no problem in the following.

######  Definition 2.10.

Let $\varphi$ be a linear fractional transformation that is not the identity.

(a) If $\varphi$ has a single fixed point then it is called _parabolic_.

(b) Suppose that $\varphi$ has two distinct fixed points, and let $\lambda$ be
its multiplier. If $|\lambda|=1$ then $\varphi$ is called _elliptic_ ; if
$\lambda>0$ then $\varphi$ is called _hyperbolic_ ; in all other cases,
$\varphi$ is called _loxodromic_.

We need the following dynamical properties of automorphisms $\varphi$ of
$\mathbb{D}$ (see [15, pages 125-126]).

######  Proposition 2.11.

Let $\varphi\in Aut(\mathbb{D})$, not the identity. Then we have the
following:

(i) if $\varphi$ is parabolic then its fixed point $z_{0}$ lies in
$\mathbb{T}$, and $\varphi^{n}(z)\rightarrow z_{0},\varphi^{-n}(z)\rightarrow
z_{0}$ for all $z\in\widehat{\mathbb{C}}$;

(ii) if $\varphi$ is elliptic then it has a fixed point in $\mathbb{D}$;

(iii) if $\varphi$ is hyperbolic then it has distinct fixed points $z_{0}$ and
$z_{1}$ in $\mathbb{T}$ such that $\varphi^{n}(z)\rightarrow z_{0}$ for all
$z\in\widehat{\mathbb{C}},z\neq z_{1}$, and $\varphi^{-n}(z)\rightarrow z_{1}$
for all $z\in\widehat{\mathbb{C}},z\neq z_{0}$;

(iv) $\varphi$ cannot be loxodromic.

The dynamical properties of $\varphi\in Aut(\mathbb{D})$ imply the dynamical
properties of $C_{\varphi}$.

Finally we prove Theorem 1.1.

$\mathbf{Proof~{}of~{}Theorem~{}1.1.}$

(2)$\Rightarrow$(1) Assume that $C_{\varphi}$ is mixing. Then $C_{\varphi}$ is
topologically transitive. Since a continuous linear operator on a separable
Banach space is topologically transitive if and only if it is hypercyclic (see
[15, page 10]), by Proposition 2.8 we have $C_{\varphi}$ is hypercyclic.

(1)$\Rightarrow$(3) Assume that $C_{\varphi}$ is hypercyclic. We will show
that $\varphi$ has no fixed point in $\mathbb{D}$. Suppose $\varphi$ has a
fixed point $z_{0}\in\mathbb{D}$. Since $C_{\varphi}$ is hypercyclic, there
exists a $f\in H^{p}$ such that $\\{(C_{\varphi})^{n}f:n\geqslant 0\\}$ is
dense in $H^{p}$. We may choose a $g\in H^{p}$ with $g(z_{0})\neq f(z_{0})$.
Since $\overline{\\{(C_{\varphi})^{n}f:n\geqslant 0\\}}=H^{p}$, we may choose
a sequence $\\{n_{k}\\}_{k=1}^{\infty}$ of positive integers with
$n_{1}<n_{2}<\cdots<n_{k}<n_{k+1}<\cdots$ such that
$\lim\limits_{k\rightarrow\infty}(C_{\varphi})^{n_{k}}f=g$. By Proposition 2.5
we have
$\lim\limits_{k\rightarrow\infty}((C_{\varphi})^{n_{k}}f)(z_{0})=g(z_{0})$.
Notice that

$((C_{\varphi})^{n_{k}}f)(z_{0})=(f\circ\varphi^{n_{k}})(z_{0})=f(\varphi^{n_{k}}(z_{0}))=f(z_{0}).$

Hence $f(z_{0})=g(z_{0})$, this is a contradiction with $f(z_{0})\neq
g(z_{0})$. Therefore $\varphi$ has no fixed point in $\mathbb{D}$.

(3)$\Rightarrow$(2) Suppose that $\varphi$ has no fixed point in $\mathbb{D}$.
It suffices to show that $C_{\varphi}$ satisfies Kitai’s criterion. By
Proposition 2.11, $\varphi$ is either parabolic or hyperbolic, and in both
cases $\varphi$ has fixed points $z_{0}$ and $z_{1}$ in $\mathbb{T}$ (possibly
with $z_{0}=z_{1}$) such that $\varphi^{n}(z)\rightarrow z_{0}$ for all
$z\in\mathbb{T}\backslash\\{z_{1}\\}$ and $\varphi^{-n}(z)\rightarrow z_{1}$
for all $z\in\mathbb{T}\backslash\\{z_{0}\\}$.

Now, for $X_{0}$ we will take the subspace of $H^{p}$ of all functions that
are analytic on a neighbourhood of $\overline{\mathbb{D}}$ and that vanish at
$z_{0}$. Since $z_{0}$ is a fixed point of $\varphi$, $C_{\varphi}$ maps
$X_{0}$ into itself.

$\mathbf{Claim~{}1.}$ For any $1\leqslant p<+\infty$ we have
$\overline{X_{0}}=H^{p}$.

We divide it into two cases.

Case i. If $1<p<+\infty$. First we will show that $X_{0}^{\bot}=\\{0\\}$. Let
$1<p<+\infty$ and $x^{\ast}\in X_{0}^{\bot}$. We will show that $x^{\ast}=0$.
Since $1<p<+\infty$ and $x^{\ast}\in(H^{p})^{\ast}$, there exists a unique
function $g\in H^{q}$ such that

$x^{\ast}(f)=\frac{1}{2\pi}\int_{0}^{2\pi}f(e^{i\theta})g(e^{-i\theta})d\theta(f\in
H^{p}),$

where $\frac{1}{p}+\frac{1}{q}=1$ (see [10, pages 112-113]). By Proposition
2.7 we have

$\lim_{r\rightarrow
1^{-}}\int_{0}^{2\pi}|g(re^{i\theta})-g(e^{i\theta})|^{q}d\theta=0.$

Hence for each $f\in H^{p}$ we have

$\lim_{r\rightarrow
1^{-}}\frac{1}{2\pi}\int_{0}^{2\pi}f(e^{i\theta})g(re^{-i\theta})d\theta=\frac{1}{2\pi}\int_{0}^{2\pi}f(e^{i\theta})g(e^{-i\theta})d\theta.$

Since, for any $n\geqslant 0$, the functions
$g_{n}:\mathbb{C}\rightarrow\mathbb{C}$ defined by
$g_{n}(z)=z_{0}z^{n}-z^{n+1}$ belong to $X_{0}$ we have that
$x^{\ast}(g_{n})=0(n\geqslant 0)$. Notice that

$\displaystyle x^{\ast}(g_{n})=$
$\displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}g_{n}(e^{i\theta})g(e^{-i\theta})d\theta$
$\displaystyle=$ $\displaystyle\lim_{r\rightarrow
1^{-}}\frac{1}{2\pi}\int_{0}^{2\pi}g_{n}(e^{i\theta})g(re^{-i\theta})d\theta.$

Hence for any $n\geqslant 0$ we have

$\lim_{r\rightarrow
1^{-}}\frac{1}{2\pi}\int_{0}^{2\pi}g_{n}(e^{i\theta})g(re^{-i\theta})d\theta=0.$

Let $g(z)=\sum\limits_{n=0}^{\infty}a_{n}z^{n}(z\in\mathbb{D})$, $0<r<1$ and
$n\geqslant 0$. Then

$\displaystyle\frac{1}{2\pi}\int_{0}^{2\pi}g_{n}(e^{i\theta})g(re^{-i\theta})d\theta$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}(z_{0}e^{in\theta}-e^{i(n+1)\theta})g(re^{-i\theta})d\theta$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}z_{0}e^{in\theta}g(re^{-i\theta})d\theta-\frac{1}{2\pi}\int_{0}^{2\pi}e^{i(n+1)\theta}g(re^{-i\theta})d\theta$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}z_{0}e^{in\theta}(\sum_{k=0}^{\infty}a_{k}r^{k}e^{-ik\theta})d\theta-\frac{1}{2\pi}\int_{0}^{2\pi}e^{i(n+1)\theta}(\sum_{k=0}^{\infty}a_{k}r^{k}e^{-ik\theta})d\theta$
$\displaystyle=\sum_{k=0}^{\infty}\frac{1}{2\pi}\int_{0}^{2\pi}z_{0}e^{in\theta}a_{k}r^{k}e^{-ik\theta}d\theta-\sum_{k=0}^{\infty}\frac{1}{2\pi}\int_{0}^{2\pi}e^{i(n+1)\theta}a_{k}r^{k}e^{-ik\theta}d\theta$
$\displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}z_{0}a_{n}r^{n}d\theta-\frac{1}{2\pi}\int_{0}^{2\pi}a_{n+1}r^{n+1}d\theta$
$\displaystyle=z_{0}a_{n}r^{n}-a_{n+1}r^{n+1}.$

Since $\lim\limits_{r\rightarrow
1^{-}}\frac{1}{2\pi}\int_{0}^{2\pi}g_{n}(e^{i\theta})g(re^{-i\theta})d\theta=0$,
we have

$\lim\limits_{r\rightarrow
1^{-}}(z_{0}a_{n}r^{n}-a_{n+1}r^{n+1})=z_{0}a_{n}-a_{n+1}=0.$

Hence $a_{n}=a_{0}z_{0}^{n}(n\geqslant 0)$. Since $q=\frac{p}{p-1}>1$, we may
choose $1<q_{1}\leqslant 2$ with $q_{1}<q$. It is evident that $H^{q}\subseteq
H^{q_{1}}$. Since $g\in H^{q}$, $g\in H^{q_{1}}$. By Proposition 2.9 we have
$\\{a_{n}\\}_{n=0}^{\infty}\in l^{p_{1}}$, where
$\frac{1}{p_{1}}+\frac{1}{q_{1}}=1$. Notice that

$\sum\limits_{n=0}^{\infty}|a_{n}|^{p_{1}}=\sum\limits_{n=0}^{\infty}|a_{0}z_{0}^{n}|^{p_{1}}=\sum\limits_{n=0}^{\infty}|a_{0}|^{p_{1}}<+\infty.$

Hence $a_{0}=0$ and $a_{n}=0$ for $n\geqslant 0$. Therefore $g(z)=0$ for all
$|z|<1$ and $x^{\ast}=0$.

Second we will show that $\overline{X_{0}}=H^{p}$. Since
$\overline{X_{0}}^{\bot}=X_{0}^{\bot}$ and $X_{0}^{\bot}=\\{0\\}$, we have
$\overline{X_{0}}^{\bot}=\\{0\\}$. Hence
$\overline{X_{0}}^{\bot\bot}=\\{0\\}^{\bot}=H^{p}$. Since $1<p<+\infty$, by
Proposition 2.6 we have $H^{p}$ is reflexive. Since $\overline{X_{0}}$ is
norm-closed, by Proposition 2.2 we have $\overline{X_{0}}$ is
$\sigma(X^{\ast},X)$-closed. Finally by Proposition 2.3 we have
$\overline{X_{0}}^{\bot\bot}=\overline{X_{0}}$. Hence
$\overline{X_{0}}=H^{p}$. This proves the case $1<p<+\infty$.

Case ii. If $p=1$. We will show that $\overline{X_{0}}=H^{1}$. Let $f\in
H^{1}$ and $\varepsilon>0$. We will show that there exists a $g\in X_{0}$ such
that $\|f-g\|_{1}<\varepsilon$. By Proposition 2.8, there exists a polynomial
$h$ such that $\|f-h\|_{1}<\frac{\varepsilon}{2}$. By the case $p=2$, $X_{0}$
is dense in $H^{2}$. Hence there exists a $g\in X_{0}$ such that
$\|g-h\|_{2}<\frac{\varepsilon}{2}$. Notice that
$\|g-h\|_{1}\leqslant\|g-h\|_{2}$. Then $\|g-h\|_{1}<\frac{\varepsilon}{2}$.
Hence $\|f-g\|_{1}\leqslant\|f-h\|_{1}+\|h-g\|_{1}<\varepsilon$. This proves
the case $p=1$.

$\mathbf{Claim~{}2.}$ $(C_{\varphi})^{n}f\rightarrow 0$ for all $f\in X_{0}$.

Let $f\in X_{0}$. Since $f\circ\varphi^{n}$ is continuous on
$\overline{\mathbb{D}}$, by Proposition 2.7 we have

$\|(C_{\varphi})^{n}f\|_{p}^{p}=\frac{1}{2\pi}\int_{0}^{2\pi}|f(\varphi^{n}(e^{i\theta}))|^{p}d\theta.$

Since the integrands are uniformly bounded and convergent to
$|f(z_{0}|^{p}=0$, for every $t$ with possibly one exception, the dominated
convergence theorem implies that $(C_{\varphi})^{n}f\rightarrow 0$. This
proves Claim 2.

Next, for $Y_{0}$ we will take the subspace of $H^{p}$ of all functions that
are analytic on a neighbourhood of $\overline{\mathbb{D}}$ and that vanish at
$z_{1}$, and for $S$ we take the map $S=C_{\varphi^{-1}}$. Since $z_{1}$ is a
fixed point of $\varphi^{-1}$, $S$ maps $Y_{0}$ into itself, and clearly
$C_{\varphi}S=I$. It follows as above that $Y_{0}$ is dense in $H^{p}$ and
that $S^{n}f\rightarrow 0$ for all $f\in Y_{0}$. Therefore the conditions of
Kitai’s criterion are satisfied, so that $C_{\varphi}$ is mixing.

$\Box$

Bourdon and Shapiro [5, 6] proved Theorem 1.1 in the case $p=2$. Hence Theorem
1.1 generalizes the corresponding results in [5, 6].

## References

  * [1] Beauzamy, B.: Introduction to Operator Theory and Invariant Subspaces, North-Holland Publishing Co., Amsterdam, 1988
  * [2] Bernal-González, L.: Derivative and antiderivative operators and the size of complex domains. _Ann. Polon. Math._ , 59, 267–274 (1994)
  * [3] Bès, J., Peris, A.: Hereditarily hypercyclic operators. _J. Funct. Anal._ , 167, 94–112 (1999)
  * [4] Birkhoff, G. D.: Démonstration d’un théorème élémentaire sur les fonctions entières. _C. R. Acad. Sci. Paris._ , 189, 473–475 (1929)
  * [5] Bourdon, P. S., Shapiro, J. H.: Cyclic composition operators on $H^{2}$, American Mathematical Society, Providence, RI, 1990
  * [6] Bourdon, P. S., Shapiro, J. H.: Cyclic phenomena for composition operators, Mem. Amer. Math. Soc., no. 596, 125 (1997)
  * [7] Chan, K. C., Sanders, R.: A weakly hypercyclic operator that is not norm hypercyclic. _J. Operator Theory._ , 52, 39–59 (2004)
  * [8] Conway, J. B.: Functions of One Complex Variable, Graduate Texts in Mathematics, 11, Springer-Verlag, New York, 1978
  * [9] Costakis, G., Sambarino, M.: Topologically mixing hypercyclic operators. _Proc. Amer. Math. Soc._ , 132, 385–389 (2004)
  * [10] Duren, P. L.: Theory of $H^{p}$ Spaces, Academic Press, New York, 1970
  * [11] Gallardo-Gutiérrez, E. A., Montes-Rodríguez, A: The role of the spectrum in the cyclic behavior of composition operators, Mem. Amer. Math. Soc., no. 791, 167 (2004)
  * [12] Gethner, R. M., Shapiro, J. H.: Universal vectors for operators on spaces of holomorphic functions. _Proc. Amer. Math. Soc._ , 100, 281–288 (1987)
  * [13] Godefroy, G., Shapiro, J. H.: Operators with dense, invariant, cyclic vector manifolds. _J. Funct. Anal._ , 98, 229–269 (1991)
  * [14] Grosse-Erdmann, K.-G.: Hypercyclic and chaotic weighted shifts. _Studia Math._ , 139, 47–68 (2000)
  * [15] Grosse-Erdmann, K.-G., Peris, A.: Linear Chaos, Universitext, 223, Springer-Verlag, London, 2011
  * [16] Gulisashvili, A., MacCluer, C. R.: Linear chaos in the unforced quantum harmonic oscillator. _J. Dynam. Systems Measurement Control._ , 118, 337–338 (1996)
  * [17] Kitai, C.: Invariant closed sets for linear operators, Thesis, University of Toronto, Toronto, 1982
  * [18] MacLane, G. R.: Sequences of derivatives and normal families. _J. Anal. Math._ , 2, 72–87 (1952/53)
  * [19] Martínez-Giménez, F., Peris, A.: Chaos for backward shift operators. _Internat. J. Bifur. Chaos Appl. Sci. Engrg._ , 12, 1703–1715 (2002)
  * [20] Mathew, V.: A note on hypercyclic operators on the space of entire sequences. _Indian J. Pure Appl. Math._ , 25, 1181–1184 (1994)
  * [21] Rolewicz, S.: On orbits of elements. _Studia Math._ , 32, 17–22 (1969)
  * [22] Salas, H.: A hypercyclic operator whose adjoint is also hypercyclic. _Proc. Amer. Math. Soc._ , 112, 765–770 (1991)
  * [23] Salas, H.: Hypercyclic weighted shifts. _Trans. Amer. Math. Soc._ , 347, 993–1004 (1995)
  * [24] Taylor, A. E., Lay, D. C.: Introduction to Functional Analysis, second edition, John Wiley-Sons, New York, 1980
  * [25] Zhu, K.: Operator Theory in Function Spaces, second edition, American Mathematical Society, Providence, RI, 2007
  * [26] Zorboska, N.: Cyclic composition operators on smooth weighted Hardy spaces. _Rocky Mountain J. Math._ , 29, 725–740 (1999)