# Predicting Music Hierarchies With a
Graph-Based Neural Decoder

###### Abstract

This paper describes a data-driven framework to parse musical sequences into
dependency trees, which are hierarchical structures used in music cognition
research and music analysis. The parsing involves two steps. First, the input
sequence is passed through a transformer encoder to enrich it with contextual
information. Then, a classifier filters the graph of all possible dependency
arcs to produce the dependency tree. One major benefit of this system is that
it can be easily integrated into modern deep-learning pipelines. Moreover,
since it does not rely on any particular symbolic grammar, it can consider
multiple musical features simultaneously, make use of sequential context
information, and produce partial results for noisy inputs. We test our
approach on two datasets of musical trees – time-span trees of monophonic note
sequences and harmonic trees of jazz chord sequences – and show that our
approach outperforms previous methods.111All our code and data are publicly
available at https://github.com/fosfrancesco/musicparser

##  1 Introduction

Tree-like representations are a powerful tool in many approaches to music
analysis, such as Schenkerian Theory and the Generative Theory of Tonal Music
(GTTM). In the Music Information Retrieval (MIR) literature, we find tree
models of melodies [1, 2, 3, 4], chord progressions [5, 6, 7, 8], and rhythm
[9, 10, 11, 12, 13]. Parallels between aspects of music and language are often
drawn, as these have similar hierarchical properties and their underlying
cognitive mechanisms could be closely related [14]. However, with a few
exceptions, such as instrument grouping and metrical information in scores,
music is generally encoded sequentially without explicit information about its
hierarchical organisation. The task of creating such hierarchies from a
sequential representation is called parsing and it is an active object of
study in the MIR community [15, 7, 11, 3].

Current parsing approaches are based on generative grammars, typically
context-free-grammars (CFG) or similar related mechanisms, which can be
fundamentally seen as a set of expansion rules generating a tree from the top
(the root) to the elements that compose the sequence (the leaves). Grammar
rules can be enriched with a probability model that permits the ranking of
different parses by plausibility. When a grammar is available, parsing can be
achieved with grammar-based parsing algorithms, typically variants of the
Cocke–Younger–Kasami (CYK) algorithm [16]. While the grammar rules are most
often built by hand, by relying on musicologists’ knowledge, the probabilities
can be learnt from data if sufficient amounts of musical sequences with
ground-truth tree annotations are available. The grammar approach has the
strong advantage of leveraging an interpretable and cognitively plausible
mechanism. Still, it has the following limitations: it is hard to achieve
robustness against noisy data, which can cause a complete failure with no
output in case the sequence cannot be produced by the grammar rules; it
requires a high degree of domain knowledge; it is challenging to account for
multiple musical dimensions in a single grammar rule; and parsing is usually
so slow for long sequences that heavy pruning is necessary (CYK-parsing
complexity is cubic in the length of the sequence, parallelisation does not
help much, and there is no active research in developing dedicated hardware).

Inspired by recent research in the field of natural language processing (NLP),
we propose a novel, _grammar-less_ approach that requires little domain
knowledge (only for the feature extraction phase), can easily consider
multiple musical features and sequential information, produces partial results
for noisy input, and is potentially scalable to longer sequences and larger
datasets (since its components are proven to succeed in such scenarios). Our
system works by predicting dependency trees which consist of dependency arcs
between the input sequence elements. Such a structure can be used as-is or
later be converted into constituent trees which are typically used to model
music hierarchies (see Figure 1). The probability of each dependency arc is
predicted in parallel (i.e., without considering other dependencies during
prediction) by leveraging the rich contextual information produced by a
transformer encoding of the input sequence. This set of probabilities is then
run through a post-processing algorithm to ensure a valid tree structure
(i.e., no cycles of dependency arcs).

We pair our Music Dependency Parser MuDeP with a procedure that enables its
usage from constituent trees, and test it on two tree datasets: the time-span
treebank from the GTTM database [17], which expresses subordinate relations
between notes in monophonic melodies; and the Jazz Harmony Treebank (JHT), a
set of harmonic analyses for chord sequences [18]. We compare the results of
our system with the best-performing available approaches and obtain new state-
of-the-art results.

Figure 1:  The tree harmonic analysis of the A Section of “Take the A Train”
in three different representations. Top: dependency tree, Left: GTTM-style
constituent tree. Right: CFG-style constituent tree.

##  2 Related Work

Music Trees and Music Parsing.  Trees of musical sequences have traditionally
been notated as constituent trees [5, 1, 2, 3, 6, 7, 8, 19, 9, 10, 11, 12,
13], with few exceptions, such as the usage of a dependency-based evaluation
metric [20], and the computation of pairwise voice dependencies [4, 21].

A system for parsing jazz chord sequences into harmonic analyses has been
proposed by Harasim et al. [7] and later evaluated on a larger dataset [20].
We compare our results to this approach below. Automatic grammar-based parsing
of time-span GTTM trees has been attempted by Hamanaka et al. [22, 23] and
Nakamura et al. [2]. The latter obtained comparable results with an approach
that doesn’t require manual parameter tuning, and we compare our system with
it. More recently, deep-learning-based approaches were also proposed [24, 25,
3] but the first two focus only on GTTM metrical and grouping information, and
the latter focus mainly on evaluating the usage of time-span trees for melodic
morphing and we could not reproduce their results.

Natural Language Parsing.  Our model architecture is inspired by the graph-
based dependency parser of Dozat and Manning [26, 27]. This model, extended
with second-order dependency predictions [28] and pretrained language models
[29], is still the state of the art for NLP sentence parsing [30]. Still, we
make some substantial changes: the embedding layer is adapted to work from
musical input, the encoder is a transformer instead of an LSTM, and, instead
of the bilinear layer for arc prediction, we use a linear layer. All these
choices are motivated by ablation studies.

##  3 Tree formats for music analyses

In this section, we detail the types of tree used in this paper, highlight
their differences, and propose algorithms to translate between them.

###  3.1 Constituent vs Dependency Trees

A tree can be defined recursively as a node with an arbitrary number
(including 0) of children that are also trees. The node that is not a child of
another node in the tree is called root, the nodes that do not have children
are called leaves, and the remaining nodes are called internal nodes. When a
tree is used to model some relations of the elements of a sequence there are
two possible configurations: dependency trees, where each node (leaf,
internal, and root) represents one and only one element of the sequence; and
constituent trees where all elements of the sequence are represented in the
leaves, and root and internal nodes represent nested groupings of such
elements.

Among the constituent trees there exist different representations. The bottom
part of Figure 1 shows the two kinds we consider in this paper: the one
introduced by Lerdahl and Jackendoff [31] in their Generative Theory of Tonal
Music (GTTM), and the one built from the Context-Free-Grammar (CFG) of jazz
harmony by Harasim et al. [7]. The two representations convey almost the same
information: they are both binary trees (i.e., every node has either 0 or 2
children), the internal nodes are denoted by line intersections on the first,
and by explicit labels on the second; they both specify an order of importance
among the children (i.e., the choice of a primary and secondary child) by the
straight line continuation, or by labelling the node with the label of the
primary child. However, this latter mechanism cannot differentiate between
primary and secondary when both children have the same label; therefore, the
GTTM representation is slightly more informative.

Our approach does not directly treat constituent trees but considers
dependency trees. Each child in such a tree is called dependent, and the node
of which it is a child is called the  head. Dependency trees can represent the
same information as the binary constituent trees described above. Indeed, a
dependent-head arc is equivalent to a head-labelled constituent node with two
children: the primary is again the head, and the secondary is the dependent.
There is only one ambiguity: the dependency tree does not encode a splitting
order in the case of double-sided dependencies, a configuration in which one
head has dependents on both sides. This makes the dependency-to-constituent
transformation not unique (see Figure 2). This configuration is never present
in our datasets (i.e., the root is always the left-most or right-most element
in the sequence) thus we don’t handle it. For more general datasets, one could
add a binary classifier that predicts the splitting order.

Figure 2: A dependency tree with double-sided dependencies (left). It
corresponds to two possible constituent trees (middle and right).

The dependency trees built from the constituent trees are projective, i.e.,
for all their arcs $x_{\textrm{dep}}\rightarrow{}x_{\textrm{head}}$, there is
a path from the head to every element $x$ that lies between the head and the
dependent in the sentence [32]. This means that there are no “crossing arcs”,
e.g., $x_{1}\xrightarrow{}x_{3},x_{2}\xrightarrow{}x_{4}$.

Before proceeding with the paper, we introduce some notation we will use in
the next sections. We denote the sequence that constitutes the input of our
system as $x=[x_{1},\dots,x_{\lambda}]$, where $\lambda$ is the sequence’s
length. We represent the dependency tree over $x$ as the set of dependent-
head222We indicate dependency arcs as arrows pointing in the direction of the
head. Note that in other (NLP) papers, the opposite convention is used.
indices that corresponds to each arc
$x_{\textrm{dep}}\rightarrow{}x_{\textrm{head}}$:

$y=\\{(\textrm{dep},\textrm{head})\mid\textrm{dep},\textrm{head}\in[1,\dots,\lambda]\\}$
(1)

###  3.2 Tree Conversion Algorithms

Since the ground-truth annotations in our datasets are constituent trees, we
translate them into dependency trees for training. We also translate tree
predictions back to constituent trees to run constituent-based evaluation
metrics, and when we are interested in using such a representation as input
for further applications. We assume our constituent trees to be binary trees
and not contain double-sided dependencies. For simplicity, we consider CFG-
style constituent trees with labels in their internal nodes.

####  3.2.1 Dependency to Constituent Tree

Existing NLP implementations of this transformation are unnecessarily
complicated for our scenario because they consider compound node labels and
double-sided dependencies [33]. Instead, we present a recursive top-down
algorithm which yields a unique constituent solution for every single-sided
dependency tree.

The algorithm takes a fully formed dependency tree and starts with the root of
the (to-be-built) constituent tree. At each step, it removes one dependency
and adds two new constituent nodes. The recursive function takes as input a
dependency tree node and a constituent tree node, both labelled with the same
sequence element. The constituent node gets assigned two children: the primary
is labelled with the element of the input nodes, and the secondary is labelled
with the dependent that is further away in the sequence. The choice of which
is the left and the right child respects their label position in the sequence.
The considered dependency is removed from the tree and the recursive function
is called two times, once for each constituent child (with the corresponding
dependency node). The process stops when the dependency tree node has no
dependents.

####  3.2.2 Constituent to Dependency Tree

This algorithm was used in the literature (e.g., [18]). It starts from a fully
formed constituent tree and a dependency tree without any dependency arcs,
consisting only of the nodes labelled with sequence elements. The algorithm
groups all internal tree nodes with their primary child (which all have the
same label) and uses all secondary child relations originating from each group
to create dependency arcs between the group label and the secondary child
label.

##  4 Parsing Technique

Our goal is to predict a dependency tree $y$ for a given musical sequence $x$.
Our pipeline consists of three steps: feature extraction from $x$; prediction
of dependency relations; and postprocessing to ensure that the output is a
valid tree structure. In the training phase, the output (before
postprocessing) is compared with the ground truth dependency tree and a loss
is computed to update the model parameters via backpropagation.

###  4.1 Feature Extraction

For each input element, $x_{i}\in x$, we produce three groups of features. The
first is a “static” description of the element (i.e., without any temporal
information), the second encodes the element’s duration, and the third encodes
the element’s metrical position, i.e., its position in the measure relative to
the hierarchy induced by the time signature. The static description is built
differently for chords and notes, while the other two are independent of the
input type. Note that, due to our model architecture (see next section), we
need categorical features and it is not primarily important to keep their
number small or to have them ordered.

For note sequences, the _static description_ of each element is a single
integer corresponding to either the MIDI pitch of the element in
$[0,\dots,127]$ if it is a note or with the value $128$ if the element is a
rest. For chord sequences, we use three integers. The first in $[0,\dots,11]$
encodes the pitch-class of the chord root. The second in $[0,\dots,5]$
specifies the basic form of the chord among major, minor, augmented, half-
diminished, diminished, and suspended (sus). The last in $[0,1,2]$ denotes a
chord extension among 6, minor 7, or major 7. The chord labels were simplified
by the author of the dataset to only include these extensions, but in a more
general scenario, a larger set of integers could be used. The chord sequences
do not contain rests.

We represent the _durations of the elements_ with discrete values normalised
by the duration of the measure. We pre-collect the list of all durations
occurring in the dataset and encode each element’s duration as an index on
that list. For the GTTM dataset, this would be an integer in $[0,\dots,44]$,
while for the JHB dataset, it is an integer in $[0,\dots,5]$. The number of
possibilities is very different, since the temporal position of chords follows
much simpler rules, mostly occurring only at the beginning or in the middle of
a bar for simple time signatures and at three bar positions for compound time
signatures. For tied notes, we consider a single note with the total duration,
and notes can last more than one measure. This is different from the
annotations in the JHT in which each measure opens a new chord symbol, even if
the same chord is repeated in consecutive measures.

To represent the _metrical position_ , we use an inverse measure of metrical
strength, encoded with a single integer in $[0,\dots,5]$. This integer is
computed as a function of the normalised temporal position in the measure
$t\in[0,1[$, and the time signature numerator. Each time-signature numerator
is associated with a template of metrical divisions $m$, as proposed by
Foscarin [10] and here extended to more time signatures. For example, a time
signature with a numerator $12$ (e.g., $12/8$ or $12/4$) will have metrical
divisions $m=[1,2,2,3,2]$, i.e., the whole measure at level $0$ is divided
into two parts at level $1$, each resulting part is divided in 2 at level $2$,
then 3 at level $3$, and 2 at level $4$. Table 3 reports metrical divisions
for all numerators we consider.

Each level $l$ in the metrical division defines a temporal grid with step
$\delta_{l}=1/\prod_{l=0}^{l}m_{l}$, and the _inverse metrical strength_ is
defined as the lowest level for which the note position falls on the temporal
grid, $\textrm{min}_{l}(l\mid t/\delta_{l}\in\mathbb{N})$. For example, a time
signature $6/8$ defines grids with steps
$[1,\frac{1}{2},\frac{1}{6},\frac{1}{12},\frac{1}{24}]$, and the notes of the
measure $|\musQuarter{}\musEighth{}\musQuarterDotted{}|$ will have normalised
temporal position $[0,\frac{2}{6},\frac{1}{2}]$ and inverse metrical strength
$[0,2,1]$. If the note doesn’t align with any temporal grid, then its inverse
metrical strength is the maximum, 5 in our settings. Using metrical strength
as input to our system may seem overly complicated. However, given the small
size of our datasets and the high variety of time signatures, we need a
mechanism to encode metrical information generalisable across different time
signatures. It is to be expected that with a larger dataset size, this feature
could be discarded, as the model could learn similar information from the list
of notes with duration.

Figure 3: Left: metrical divisions $m$ for different time signature
numerators. Right: visualisation of metrical divisions for a measure with time
signature 12/8.

The feature extraction process lets us build the input matrix
$\mathcal{X}\in\mathbb{N}^{\lambda\times\phi}$ where $\lambda$ is the sequence
length, and $\phi$ is the number of features for each element: 3 for the GTTM
dataset, and 5 for the JHT dataset. Before moving on, it has to be noted that
there exist other more general ways of transforming symbolic music into
convenient inputs for deep learning models, notably the tokenisation
techniques, e.g.,[34, 35] inspired by NLP research. However, given the small
dimension of our dataset and the fact that our melodies are strictly
monophonic, we prefer to use a more compact, ad-hoc input representation. Our
parsing framework remains general and usable with other techniques.

###  4.2 Model

Our model consists of two parts: an encoder and an arc predictor (see Figure
4). The goal of the encoder is to enrich the input features $\mathcal{X}$ with
contextual information. The arc predictor uses the enriched sequence features
to predict whether each possible pair of elements in the input sequence should
be connected by a dependency arc.

Figure 4: Architecture of our model. The input displayed is an example of a
chord sequence, but the same architecture is used for note sequences.

The first part of the encoder is an embedding layer, a learnable look-up table
which maps our collection of categorical features (each integer) to points in
a continuous multidimensional space. Specifically, we use $\phi$ embedding
layers (one for each input feature), which work independently, and map all
values that the feature can have to a vector of a fixed embedding dimension.
All vectors are then summed together to obtain a unique representation while
keeping the input size small (see [36] for an explanation of why summing is
better than concatenating). After the embedding layer, we have the encoder
part of a transformer [37] with relative position representations [38]. It
outputs a matrix with the same number of rows as the input matrix
$\mathcal{X}$ (one for each sequence element) but with a (possibly) different
number of hidden-feature columns $h$. Onto this, we concatenate a new
learnable single row that acts as the head of the root node. The result is a
new matrix $\mathcal{H}\in\mathbb{Q}^{(\lambda+1)\times h}$.

The arc predictor part of our model is a multilayer perceptron (MLP) that
performs the binary classification task of deciding whether each pair
$(x_{\textrm{head}},x_{\textrm{dep}})$ in the Cartesian product of the input
elements, i.e., $\\{(\textrm{head},\textrm{dep})\mid\forall\
\textrm{head},\textrm{dep}\in[1,\dots,\lambda]\\}$, should be connected by a
dependency arc. Depending on the input representation and the specific task we
are targeting, there may be some pairs that are not connectable by a
dependency arc, for example, pairs where $\textrm{head}=\textrm{dep}$. For the
GTTM input, pairs for which at least one element is a rest are also not
connectable. Therefore, the binary classification is performed only on a
subset of all pairs $\Lambda$ that we call potential arcs. For every potential
arc $(x_{\textrm{dep}},x_{\textrm{head}})$, we predict the probability
$\hat{y}_{\textrm{dep},\textrm{head}}$ of a dependency arc by concatenating
the two rows of $\mathcal{H}$ that correspond to the head’s and the
dependent’s index into a single vector of length $2h$ and giving it as input
to the MLP. We concatenate the two inputs instead of summing or multiplying
them because our arcs are directed, so we need to preserve the order when
aggregating the two embeddings. Moreover, despite the bilinear layer being a
major selling point of Dozat’s paper [26], we find that the concatenation
approach yields better results. We can collect the output for all potential
arcs into a weighted graph-adjacency matrix $\hat{Y}$, which is a
$\lambda\times\lambda$ matrix with entries
$\hat{y}_{\textrm{head},\textrm{dep}}$ at the corresponding indices. We assign
a probability 0 to the matrix entries that correspond to arcs $\notin\Lambda$.

###  4.3 Training Loss

In the training phase, we use the sum of the binary-cross-entropy (BCE) loss
and the (multiclass) cross-entropy (CE) loss. The BCE loss is computed
independently for each potential arc and measures the difference between the
ground-truth label (0 or 1) and the predicted probability. We also use the CE
loss because our problem can be framed as a multiclass classification problem
where for each element we predict his head among $\lambda+1$ possibilities
(each sequence element plus a dummy element for the root and rests elements).
The CE loss is therefore applied column-wise to the adjacency matrix $\hat{Y}$
predicted by our model.

In NLP, the BCE loss was used by [27] while the CE loss is used more
generally, for example, by [26, 39]. We experimentally found that the sum of
the two losses yields the best results.

###  4.4 Postprocessing

Since the prediction of our model is made independently for each potential
arc, simply taking the row-wise maximum of the weighted adjacency matrix to
select which head to assign to each element of the sequence could produce
dependency cycles and, therefore, not yield a tree structure. We use a
maximum-spanning-tree algorithm to find the tree over $\hat{Y}$ with the
highest weight. Since our dependency trees are projective, we use the Eisner
algorithm [40] which solves this problem using bottom–up dynamic programming
with a time complexity of $O(\lambda^{3})$. For applications involving non-
projective trees other post-processing approaches such as Chu-Liu/Edmonds [41,
42] ($O(\lambda^{2})$) are implemented in our framework.

##  5 Experiments

Below, we describe the datasets, evaluation metrics, and experimental settings
for the two kinds of trees we consider.

###  5.1 Datasets and preprocessing

We obtain the melodic time-span trees from the GTTM database [17], which
contains MusicXML encodings of monophonic scores and a dedicated XML-based
encoding of the constituent time-span trees (among other trees that we don’t
consider in this paper). We extract the note features with the Python library
Partitura [43]. Some pieces have two different trees, and we keep only the
first. We also discard 4 pieces that we could not import due to
inconsistencies in the XML file encoding. In total, we have 296 melodies of
lengths between 10 and 127 (notes + rests). For training, we augment the
dataset by considering all transpositions between one octave higher and one
octave lower.

We obtain the chord analyses from the Jazz Harmony Treebank (JHT) [9], which
encodes both chord labels and harmonic analyses as constituent trees, in JSON
format. As discussed in Section 3 this format does not distinguish between the
primary and the secondary child when both have the same chord label. In this
case, we assume by default that the right is the primary. The dataset contains
two kinds of trees: open and complete constituents. We use the former for
comparison reasons since the results are reported only for those [20]. In
total, we have 150 sequences of lengths between 11 and 38 chords. For
training, we augment the dataset by considering all 12 possible transpositions
of the chord roots.

###  5.2 Evaluation metrics

The papers we compare use different metrics, and we implement all of them. The
work of Harasim [20] uses two metrics, one more relevant for dependency trees
and the other for constituent trees. The first is the arc accuracy, i.e., the
normalised cardinality of the intersection between the set of predicted arcs
and the ground truth arcs. The second is the span accuracy, computed as the
normalised cardinality of the intersection between all the spans of the
predicted constituent tree (i.e., the pair of the leftmost and rightmost leaf
that is part of the subtree rooted at any non-leaf node) and the spans of the
ground truth tree (see [20] for a more detailed explanation). Nakamura et al.
[2] use the node accuracy metric, i.e., the normalised cardinality of the
intersection between nodes in the predicted and ground truth trees, where two
nodes are considered equal if the labels of the parent and children (or a
dummy label if the node have no parent or children) are equal.

We also report another metric, the head accuracy, computed as the multiclass
classification accuracy on the indices of the predicted heads, ordered by
their dependent. For example for the dependency tree of Figure 1, this would
correspond to the accuracy computed on the sequence $[4,2,3,4,-1]$, where $-1$
indicates the root (which has no head). This is similar to the arc accuracy
but enforces the presence of a dependency head for each sequence element
(which may not be the case for a generic system), and gives more weight to the
correct root prediction. It is also faster to compute and commonly used in
NLP, so we include it to set a metric for future research. Note that all
metrics presented above don’t consider the nodes corresponding to rests, since
they are only part of the input sequence, but not part of the tree.

###  5.3 Results

For our experiments, we set the hyperparameters of our encoder to an embedding
size of 96, and 2 transformer layers of hidden size 64. The arc predictor
(MLP) has 2 linear layers with the same hidden size. We use the GeLU
activation [44] and the AdamW optimiser [45], with a learning rate of 0.0004
and weight decay of 0.05. We train with learning rate warm-up [46] of 50 steps
and cosine annealing to limit the problem of high variance in the initial and
final stages of training. The latter was particularly important since we did
not use a validation set to perform early stopping due to the small size of
our datasets. We train for 60 and 20 epochs for the JHT and GTTM datasets,
respectively, since the latter is bigger and the data augmentation yields
twice as many pieces in total). The training time is roughly the same, around
1 hour on a GPU RTX 1080.

Figure 5:  Boxplots of three accuracy metrics (higher is better) computed with
leave-one-out cross-validation and their average. For Nakamura et al. [2], we
report the average from their paper, so there is no deviation information.

We compare the results of our MuDeP on the JHT with Harasim [20] and on the
GTTM with Nakamura et al. [2]. We use leave-one-out cross-validation, i.e.,
for a dataset with $N$ pieces, we run our system $N$ times, by training on
$N-1$ pieces and evaluating with the remaining one. As shown in Figure 5,
MuDeP outperforms previous methods.

By comparing the head accuracy between JHT and GTTM (79.2% vs 57.9%), it is
clear that time-span prediction is a much harder problem than the chord
analysis problem, despite the dataset being bigger. Another interesting result
is that the span accuracy is lower than head accuracy for the JHT dataset
(63.1%), but higher for the GTTM(64.8%). Apparently, the main problem for JHT
is to select which two chords to connect, but the arc direction (i.e., which
is the head and which is the dependent) is almost always correctly inferred;
conversely, for the GTTM dataset, the system often connects the correct notes,
but in the wrong direction. And this type of misprediction is punished in the
head accuracy, but not in the span accuracy.

The full piece-wise statistics on all metrics, a graphical rendering of all
our predicted trees, and the qualitative evaluation of some examples are
available in our repository.

###  5.4 Ablation study

We report the difference in head accuracy averaged over 10 runs with 90/10
random train/test split for the JHT dataset. Regarding the loss, sole usage of
the (multiclass) CE loss reduced the accuracy by 0.3%, and only using the
binary CE loss reduced the accuracy by 4.1%. The use of a bilinear layer in
the decoder reduced the accuracy by 1.2%. The absence of post-processing did
not reduce the accuracy (when the network is fully trained, otherwise the
reduction is very evident). This is promising but it does not automatically
implies that the network is producing correctly formed trees since dependency
loops could still be present in the output. There are also cases when the
postprocessing is reducing the accuracy, by incorrectly deciding which arc to
remove in a dependency loop.

##  6 Conclusion and Future Work

We presented MuDeP, a system for the dependency parsing of music sequences,
and a procedure to make it applicable to constituent trees. MuDeP improves
upon previous methods, by incorporating the ability to consider multiple
musical features simultaneously, taking advantage of sequential context, and
handling noisy inputs robustly. Moreover, since it is based on widely
researched deep learning components, it has the potential to scale to large
datasets and longer sequences. The bottleneck for such scalability is the
postprocessing algorithm with cubic complexity. Two solutions exist to this
problem: if one is interested in non-projective trees, algorithms with a
square complexity are available. Apart from that, our system is already having
good accuracy without the postprocessing phase, as highlighted in the ablation
study. Therefore, a faster heuristic may suffice to correct the few
problematic dependencies without decreasing the performance.

Since our deep learning model is a black box, it is notably complicated to
find a human-understandable explanation of its functioning. Although work in
this direction exists [47, 48], it is still very limited [49]. Therefore, our
model is mainly intended for scenarios in which one is only interested in
obtaining the parsing trees, for example, to use them as input for another MIR
task. Conversely, this paper might have limited utility if one’s goal is to
model music understanding and interpretation by humans. Grammar-based models
are much more suitable for this goal, although there is a (somewhat
speculative) possibility that the dependency-arc probabilities in our approach
relate to first-guess heuristics.

As research on the deep learning components we use is rapidly evolving, any
new discovery is likely to benefit our system. Self-supervised pretraining on
larger datasets of monophonic music or chord sequences, for example by
predicting next or masked tokens, could also improve the performance, as
already proved for language parsing. While the goal of this paper was to
present a general framework, we can also think about several domain-specific
improvements, for example, training the GTTM time-span parser with a multi-
target approach to predict at the same time the metrical, time-span, and
prolongation structure. We hope that this work will motivate the development
of more datasets of hierarchical music analyses, including datasets of
dependency trees, which may be a valid alternative to constituent structures,
and even open up more possibilities due to the missing projectivity
constraints. Finally, we intend to explore in future research how the
knowledge encoded in our model could be reused to guide other tasks, for
example, automatic chord recognition from audio files.

##  7 Acknowledgements

This work is supported by the European Research Council (ERC) under the EU’s
Horizon 2020 research & innovation programme, grant agreement No. 101019375
(“Whither Music?”), and the Federal State of Upper Austria (LIT AI Lab).

## References

  * [1] S. Abdallah, N. Gold, and A. Marsden, “Analysing symbolic music with probabilistic grammars,” _Computational music analysis_ , pp. 157–189, 2015\.
  * [2] E. Nakamura, M. Hamanaka, K. Hirata, and K. Yoshii, “Tree-structured probabilistic model of monophonic written music based on the generative theory of tonal music,” in _Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2016, pp. 276–280.
  * [3] M. Hamanaka, K. Hirata, and S. Tojo, “Time-span tree leveled by duration of time-span,” in _Proceedings of the International Symposium on Computer Music Multidisciplinary Research (CMMR)_ , 2021, pp. 155–164.
  * [4] C. Finkensiep and M. A. Rohrmeier, “Modeling and inferring proto-voice structure in free polyphony,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2021, pp. 189–196.
  * [5] M. Rohrmeier, “Towards a generative syntax of tonal harmony,” _Journal of Mathematics and Music_ , vol. 5, no. 1, pp. 35–53, 2011.
  * [6] M. Granroth-Wilding and M. Steedman, “A robust parser-interpreter for jazz chord sequences,” _Journal of New Music Research_ , vol. 43, no. 4, pp. 355–374, 2014.
  * [7] D. Harasim, M. Rohrmeier, and T. J. O’Donnell, “A generalized parsing framework for generative models of harmonic syntax.” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2018, pp. 152–159.
  * [8] O. Melkonian, “Music as language: putting probabilistic temporal graph grammars to good use,” in _Proceedings of the ACM SIGPLAN International Workshop on Functional Art, Music, Modeling, and Design_ , 2019, pp. 1–10.
  * [9] D. Harasim, T. J. O’Donnell, and M. A. Rohrmeier, “Harmonic syntax in time: rhythm improves grammatical models of harmony,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2019, pp. 335–342.
  * [10] F. Foscarin, F. Jacquemard, and P. Rigaux, “Modeling and learning rhythm structure,” in _Proceedings of the Sound and Music Computing Conference (SMC)_ , 2019.
  * [11] F. Foscarin, F. Jacquemard, P. Rigaux, and M. Sakai, “A parse-based framework for coupled rhythm quantization and score structuring,” in _Proceedings of the Mathematics and Computation in Music International Conference (MCM)_. Springer, 2019, pp. 248–260.
  * [12] F. Foscarin, R. Fournier-S’Niehotta, and F. Jacquemard, “A diff procedure for xml music score files,” in _Proceedings of the International Conference on Digital Libraries for Musicology (DLfM)_ , 2019.
  * [13] M. Rohrmeier, “Towards a formalization of musical rhythm.” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2020, pp. 621–629.
  * [14] W. T. Fitch and M. D. Martins, “Hierarchical processing in music, language, and action: Lashley revisited,” _Annals of the New York Academy of Sciences_ , vol. 1316, no. 1, pp. 87–104, 2014.
  * [15] M. Tsuchiya, K. Ochiai, H. Kameoka, and S. Sagayama, “Probabilistic model of two-dimensional rhythm tree structure representation for automatic transcription of polyphonic midi signals,” in _Proceedings of the Asia-Pacific Signal and Information Processing Association Annual Summit and Conference_. IEEE, 2013, pp. 1–6.
  * [16] I. Sakai, “Syntax in universal translation,” in _Proceedings of the International Conference on Machine Translation and Applied Language Analysis_ , 1961.
  * [17] M. Hamanaka, K. Hirata, and S. Tojo, “Musical structural analysis database based on gttm,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2014, pp. 325–330.
  * [18] D. Harasim, C. Finkensiep, P. Ericson, T. J. O’Donnell, and M. Rohrmeier, “The jazz harmony treebank,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2020, pp. 207–215.
  * [19] M. Rohrmeier, “The syntax of jazz harmony: diatonic tonality, phrase structure, and form,” _Music Theory and Analysis (MTA)_ , vol. 7, no. 1, pp. 1–63, 2020.
  * [20] D. Harasim, “The learnability of the grammar of jazz: Bayesian inference of hierarchical structures in harmony,” Ph.D. dissertation, EPFL, 2020.
  * [21] C. Finkensiep, “The structure of free polyphony,” Ph.D. dissertation, EPFL, 2023\.
  * [22] M. Hamanaka, K. Hirata, and S. Tojo, “Implementing “a generative theory of tonal music”,” _Journal of New Music Research_ , vol. 35, no. 4, pp. 249–277, 2006.
  * [23] ——, “FATTA: Full automatic time-span tree analyzer,” in _International Computer Music Conference (ICMC)_ , vol. 1, 2007, pp. 153–156.
  * [24] ——, “deepGTTM-III: Multi-task Learning with Grouping and Metrical Structures,” in _Proceedings of the International Symposium on Computer Music Multidisciplinary Research (CMMR)_ , 2018, pp. 238–251.
  * [25] Y.-R. Lai and A. W.-Y. Su, “Deep learning based detection of GPR6 GTTM global feature rule of music scores,” in _Proceedings of the International Conference on New Music Concepts_ , vol. 56, 2021.
  * [26] T. Dozat and C. D. Manning, “Deep biaffine attention for neural dependency parsing,” in _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2017.
  * [27] ——, “Simpler but more accurate semantic dependency parsing,” in _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , 2018.
  * [28] X. Wang, J. Huang, and K. Tu, “Second-order semantic dependency parsing with end-to-end neural networks,” 2019, pp. 4609––4618.
  * [29] H. He and J. D. Choi, “Establishing strong baselines for the new decade: Sequence tagging, syntactic and semantic parsing with bert,” in _Proceedings of the International Florida Artificial Intelligence Research Society Conference_ , 2019, pp. 228–233.
  * [30] M. Zhang, “A survey of syntactic-semantic parsing based on constituent and dependency structures,” _Science China Technological Sciences_ , vol. 63, no. 10, pp. 1898–1920, 2020.
  * [31] F. Lerdahl and R. S. Jackendoff, _A generative theory of tonal music_. MIT press, 1985.
  * [32] J. Daniel, M. James H _et al._ , _Speech and language processing: An introduction to natural language processing, computational linguistics, and speech recognition_. Prentice Hall series in artificial intelligence, 2007.
  * [33] L. Kong, A. M. Rush, and N. A. Smith, “Transforming dependencies into phrase structures,” in _Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , 2015, pp. 788–798.
  * [34] N. Fradet, J.-P. Briot, F. Chhel, A. El Fallah Seghrouchni, and N. Gutowski, “MidiTok: A python package for MIDI file tokenization,” in _Late-Breaking Demo Session of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2021.
  * [35] N. Fradet, J.-P. Briot, F. Chhel, A. E. F. Seghrouchni, and N. Gutowski, “Byte pair encoding for symbolic music,” _arXiv preprint arXiv:2301.11975_ , 2023\.
  * [36] EuroCC National Competence Center Sweden (ENCCS), “Graph neural networks and transformer workshop,” https://enccs.github.io/gnn_transformers/notebooks/session_1/1b_vector_sums_vs_concatenation/, 2022\.
  * [37] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [38] P. Shaw, J. Uszkoreit, and A. Vaswani, “Self-attention with relative position representations,” in _Proceedings of the North American Chapter of the Association for Computational Linguistics_ , 2018.
  * [39] D. Fernández-González and C. Gómez-Rodríguez, “Transition-based semantic dependency parsing with pointer networks,” _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , 2020.
  * [40] J. M. Eisner, “Three new probabilistic models for dependency parsing: An exploration,” in _Proceedings of the International Conference on Computational Linguistics (COLING)_ , 1996.
  * [41] J. Edmonds, “Optimum branchings,” _Journal of Research of the national Bureau of Standards_ , vol. 71, no. 4, pp. 233–240, 1967.
  * [42] Y.-J. Chu, “On the shortest arborescence of a directed graph,” _Scientia Sinica_ , vol. 14, pp. 1396–1400, 1965.
  * [43] C. E. Cancino-Chacón, S. D. Peter, E. Karystinaios, F. Foscarin, M. Grachten, and G. Widmer, “Partitura: A Python Package for Symbolic Music Processing,” in _Proceedings of the Music Encoding Conference (MEC)_ , Halifax, Canada, 2022.
  * [44] D. Hendrycks and K. Gimpel, “Gaussian error linear units (GELUs),” _arXiv preprint arXiv:1606.08415_ , 2016.
  * [45] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,” in _International Conference on Learning Representations (ICLR)_ , 2019.
  * [46] X. S. Huang, F. Perez, J. Ba, and M. Volkovs, “Improving transformer optimization through better initialization,” in _Proceedings of the International Conference on Machine Learning (ICML)_ , 2020, pp. 4475–4483.
  * [47] S. Mishra, B. L. Sturm, and S. Dixon, “Local Interpretable Model-agnostic Explanations for Music Content Analysis,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2017, pp. 537–543.
  * [48] F. Foscarin, K. Hoedt, V. Praher, A. Flexer, and G. Widmer, “Concept-based techniques for "musicologist-friendly" explanations in a deep music classifier,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2022.
  * [49] V. Praher, K. Prinz, A. Flexer, and G. Widmer, “On the veracity of local, model-agnostic explanations in audio classification: targeted investigations with adversarial examples,” in _Proceedings of the International Society for Music Information Retrieval Conference (ISMIR)_ , 2021.


# Tight bounds on adjacency labels for monotone graph classes

Édouard Bonnet Univ. Lyon, ENS de Lyon, UCBL, CNRS, LIP, France,
<EMAIL_ADDRESS>0000-0002-1653-5822 Julien Duron Univ. Lyon, ENS
de Lyon, UCBL, CNRS, LIP, France<EMAIL_ADDRESS>John Sylvester
Department of Computer Science, University of Liverpool, UK,
<EMAIL_ADDRESS>0000-0002-6543-2934 Viktor Zamaraev Department
of Computer Science, University of Liverpool, UK,
<EMAIL_ADDRESS>0000-0001-5755-4141 Maksim Zhukovskii
Department of Computer Science, University of Sheffield, UK,
<EMAIL_ADDRESS>0000-0001-8763-9533

###### Abstract

A class of graphs admits an adjacency labeling scheme of size $f(n)$, if the
vertices of any $n$-vertex graph $G$ in the class can be assigned binary
strings (aka labels) of length $f(n)$ so that the adjacency between each pair
of vertices in $G$ can be determined only from their labels. The Implicit
Graph Conjecture (IGC) claimed that any graph class which is _hereditary_
(i.e. closed under taking induced subgraphs) and _factorial_ (i.e. containing
$2^{\Theta(n\log n)}$ graphs on $n$ vertices) admits an adjacency labeling
scheme of order optimal size $\mathcal{O}(\log n)$. After thirty years open,
the IGC was recently disproved [Hatami and Hatami, FOCS 2022].

In this work we show that the IGC does not hold even for _monotone_ graph
classes, i.e. classes closed under taking subgraphs. More specifically, we
show that there are monotone factorial graph classes for which the size of any
adjacency labeling scheme is $\Omega(\log^{2}n)$. Moreover, this is best
possible, as any monotone factorial class admits an adjacency labeling scheme
of size $\mathcal{O}(\log^{2}n)$.

This is a consequence of our general result that establishes tight bounds on
the size of adjacency labeling schemes for monotone graph classes: for any
function $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ with
$\log x\leqslant f(x)\leqslant x^{1-\delta}$ for some constant $\delta>0$,
that satisfies some natural conditions, there exist monotone graph classes, in
which the number of $n$-vertex graphs grows as $2^{\mathcal{O}(nf(n))}$ and
that do not admit adjacency labels of size at most $f(n)\log n$. On the other
hand any such class admits adjacency labels of size $\mathcal{O}(f(n)\log n)$,
which is a factor of $\log n$ away from the order optimal bound
$\mathcal{O}(f(n))$. This is the first example of tight bounds on adjacency
labels for graph classes that do not admit order optimal adjacency labeling
schemes.

##  1 Introduction

A _class_ of graphs is a set of graphs which is closed under isomorphism. For
a class of graphs $\mathcal{X}$ we denote by $\mathcal{X}_{n}$ the set of
graphs in $\mathcal{X}$ with vertex set $[n]$. A _coding_ of graphs is
representation of graphs by words in a finite alphabet. In this paper we will
always assume the binary alphabet $\\{0,1\\}$. One of the main considerations
with graph representations is their succinctness; clearly, any representation
of $n$-vertex graphs in a class $\mathcal{X}$ would require at least
$\lceil\log|\mathcal{X}_{n}|\rceil$ bits for some graphs in $\mathcal{X}_{n}$.
Another consideration is whether the representation is global or local.

Standard graph representations, such as adjacency matrix or adjacency lists,
are examples of _global_ representations, where a graph is stored in a single
data structure that needs to be accessed in order to query some information
about the graph, e.g., adjacency between a pair of vertices. By contrast, in
_local_ graph representations, the encoding of a graph is distributed over its
vertices in such a way that the queries can be answered by looking only into
the local information associated with the vertices involved in the query. In
this work we are concerned with local graph representations for adjacency
queries, i.e., queries that given two vertices answer whether they are
adjacent or not.

Let $\mathcal{X}$ be a class of graphs and $f:\mathbb{N}\rightarrow\mathbb{N}$
be a function. An _$f(n)$ -bit adjacency labeling scheme_ (or simply _$f(n)$
-bit labeling scheme_) for $\mathcal{X}$ is a pair (encoder, decoder) of
algorithms where for any $n$-vertex graph $G\in\mathcal{X}_{n}$ the encoder
assigns to the vertices of $G$ binary strings of length $f(n)$, called
_labels_ , such that the adjacency between any pair of vertices can be
inferred by the decoder only from their labels. We note that the decoder
depends on the class $\mathcal{X}$, but not on the graph $G$. The function $f$
is the _size_ of the labeling scheme. Adjacency labeling schemes were
introduced by Kannan, Naor, and Rudich [KNR88, KNR92], and independently by
Muller [Mul88] in the late 1980’s and have been actively studied since then.

Adjacency labeling schemes are closely related to induced universal graphs,
which we will refer to simply as universal graphs, as this is the only type of
universal graph that we will see in this paper. For a function
$u:\mathbb{N}\rightarrow\mathbb{N}$, a  _universal graph sequence_ or simply
_universal graph_ of size $u(n)$ is a sequence of graphs
$(U_{n})_{n\in\mathbb{N}}$ such that for every $n\in\mathbb{N}$ the graph
$U_{n}$ has at most $u(n)$ vertices and every $n$-vertex graph in
$\mathcal{X}$ is an induced subgraph of $U_{n}$. It was observed in [KNR92]
that for a class of graphs the existence an $f(n)$-bit labeling scheme is
equivalent to the existence of a universal graph of size $2^{f(n)}$.

The binary word, obtained by concatenating labels of the vertices of a graph
$G\in\mathcal{X}_{n}$ assigned by an adjacency labeling scheme, uniquely
determines graph $G$. Thus, an $f(n)$-bit labeling scheme cannot represent
more than $2^{nf(n)}$ graphs on $n$ vertices, and therefore, if $\mathcal{X}$
admits an $f(n)$-bit labeling scheme, then $|\mathcal{X}_{n}|\leqslant
2^{nf(n)}$. This implies a lower bound of $\log|\mathcal{X}_{n}|/n$ on the
size $f(n)$ of any adjacency labeling scheme for $\mathcal{X}$. A natural and
important question is: which classes admit an adjacency labeling scheme of
size that matches this information-theoretic lower bound?

We say that a graph class $\mathcal{X}$ admits an _implicit representation_ ,
if it admits an _order optimal_ adjacency labeling scheme, i.e., if
$\mathcal{X}$ has an $f(n)$-bit labeling scheme, where
$f(n)=\mathcal{O}(\log|\mathcal{X}_{n}|/n)$. Equivalently, $\mathcal{X}$
admits an implicit representation if $\mathcal{X}$ has a universal graph of
size $2^{\mathcal{O}(\log|\mathcal{X}_{n}|/n)}$. For example, the class
$\mathcal{A}$ of all graphs admits an implicit representation, because
$|\mathcal{A}_{n}|=2^{\binom{n}{2}}=2^{\Theta(n^{2})}$ and
$f(n)=\mathcal{O}(\log|\mathcal{A}_{n}|/n)=\mathcal{O}(n)$, and one can easily
design an $\mathcal{O}(n)$-bit labeling scheme for $\mathcal{A}$, e.g., by
assigning to each vertex of a graph an $n$-bit label which is the
corresponding row in an adjacency matrix of the graph.

However, not every class admits an implicit representation. The following
example is due to Muller [Mul88] (see also [Spi03]). Let $\mathcal{Y}$ be the
class of graphs in which the number of edges does not exceed the number of
vertices. It is easy to estimate that $|\mathcal{Y}_{n}|=2^{\mathcal{O}(n\log
n)}$. To show that this class does not admit an implicit representation,
consider an arbitrary $n$-vertex graph $G$. Obviously, $G$ does not
necessarily belong to $\mathcal{Y}$, but after adding $n^{2}-n$ isolated
vertices to $G$, we obtain a graph $H$ on $n^{2}$ vertices that belongs to
$\mathcal{Y}$. Now, if an $\mathcal{O}(\log n)$-bit labeling scheme for
$\mathcal{Y}$ existed, then the $\mathcal{O}(\log n^{2})$-bit adjacency labels
for $H$ could be used as $\mathcal{O}(\log n)$-bit adjacency labels for $G$.
Since, $G$ was chosen arbitrarily, this is in contradiction with the lower
bound of $\log|\mathcal{A}_{n}|/n=\Omega(n)$ on the size of any labeling
scheme for the class $\mathcal{A}$ of all graphs.

The crucial property used in the above example is that by adding isolated
vertices to a graph not in $\mathcal{Y}$ one can obtain a graph in
$\mathcal{Y}$. Using more familiar terminology, one would say that class
$\mathcal{Y}$ is not _hereditary_ , i.e., it is not closed under vertex
removal or, equivalently, under taking induced subgraphs. Many natural graph
classes (e.g., forests, planar graphs, disk graphs) are hereditary. It turns
out that finding a hereditary graph class that does not admit an implicit
representation is a non-trivial question. For factorial graph classes, this
question was asked by Kannan, Naor, and Rudich [KNR88], which was later stated
by Spinrad [Spi03] in the form of a conjecture, that became known as the
_Implicit Graph Conjecture_.

######  Conjecture 1.1 (Implicit Graph Conjecture [KNR88, Spi03]).

Any hereditary class of at most factorial speed admits an implicit
representation, i.e., an $\mathcal{O}(\log n)$-bit labeling scheme.

This question remained open for over 30 years until a recent breakthrough by
Hatami and Hatami [HH22]. They showed that, for any $\delta>0$, there exists a
hereditary factorial class that does not admit a labeling scheme of size
$n^{1/2-\delta}$, which is very far from the information-theoretic lower bound
of $\Omega(\log n)$. This result leaves wide open the question of
characterizing factorial hereditary graph classes that admit an implicit
representation (see [HWZ22] for more discussion).

Factorial classes form an important family of hereditary classes, as many
classes of theoretical or practical interest are factorial. However, as was
noted by Spinrad [Spi03], there is nothing that prevents one from considering
implicit representability of other hereditary graph classes. Reformulating the
question of Spinrad [Spi03], which he dubbed the Generalized Implicit Graph
Question, we state the following

######  Question 1 ([Spi03]).

Which hereditary graph classes admit implicit representations?

The answer to this question is known for classes with
$|\mathcal{X}_{n}|=2^{\Omega(n^{2})}$, and for _subfactorial_ graph classes,
i.e., classes $\mathcal{X}$ with $|\mathcal{X}_{n}|=2^{o(n\log n)}$. Indeed,
for the latter classes, it is known that they have at most exponential speed,
i.e., $|\mathcal{X}_{n}|=2^{\mathcal{O}(n)}$ [Ale97, SZ94], and also admit
$\mathcal{O}(1)$-bit labeling schemes [Sch99]. For the former classes, the
$\mathcal{O}(n)$-bit labeling scheme mentioned above for the class
$\mathcal{A}$ of all graphs is an order optimal labeling scheme. In fact, in
this regime, _asymptotically optimal_ (up to the second-order term) labelling
schemes are available. For the class of all graphs, such results (in the
language of universal graphs) were available since 1965 [Moo65, AKTZ15,
Alo17]. For proper hereditary graph classes $\mathcal{X}$ with the speed
$2^{\Omega(n^{2})}$, by the Alekseev–Bollobás–Thomason theorem [Ale92, BT95],
their speed is $|\mathcal{X}_{n}|=2^{(1-1/k(\mathcal{X}))n^{2}/2+o(n^{2})}$,
where $k(\mathcal{X})$ is an integer greater than 1. Recently, Bonamy,
Esperet, Groenland, and Scott showed [BEGS21] that all such classes have
asymptotically optimal adjacency labeling schemes of size
$(1-1/k(\mathcal{X}))n/2+o(n)$.

For the classes in the intermediate range, i.e., the classes with the speed
between $2^{\Omega(n\log n)}$ and $2^{o(n^{2})}$ the picture is much less
understood (see Figure 1). Most known information is concentrated around the
lower extreme of the range, i.e., around factorial speed, which was promoted
by the Implicit Graph Conjecture. Factorial graph classes from certain
families are known to admit implicit representations: proper minor-closed
graph classes [GL07], graph classes of bounded degeneracy (equivalently, of
bounded arboricity) [KNR88], clique-width [CV03, Spi03] (see also [Ban22]),
and twin-width [BGK+22] all admit implicit representations. The only lower
bound witnessing (non-constructively) factorial classes that do not admit an
implicit representation is the above-mentioned result by Hatami and Hatami
[HH22]. A notable family of hereditary graph classes where 1 remains open is
the _small_ graph classes, i.e., classes $\mathcal{X}$ with
$|\mathcal{X}_{n}|\leqslant c^{n}n!$ for some constant $c$. These classes
encompass only the bottom part of the factorial layer and include proper
minor-closed classes [NSTW06], and more generally, classes of bounded twin-
width [BGK+22]. However, it is still unknown if all such classes admit an
implicit representation (see [BDS+23] for more details on implicit
representation of small classes). Alon showed [Alo23] that every hereditary
graph class $\mathcal{X}$ with $|\mathcal{X}_{n}|=2^{o(n^{2})}$ admits an
$n^{1-\delta}$-bit labeling scheme for some $\delta>0$.

Hereditary ClassesSpeed $|\mathcal{X}_{n}|$Sub-Factorial$2^{o(n\log
n)}$$\checkmark$[Sch99]Small-Factorial$c^{n}\cdot n!$?Bdd
Twinwidth$\checkmark$ [BGK+22]Factorial$2^{\mathcal{O}(n\log n)}$LB:
$n^{1/2-\delta}$ [HH22]Super-Factorial$2^{o(n^{2})}$UB: $n^{1-\delta}$
[Alo23]Dense$2^{\Theta(n^{2})}$$\checkmark$[BEGS21]Monotone✗LB/UB:
$\frac{\log|\mathcal{X}_{n}|}{n}\cdot\log n$[Theorem 1.3 & Proposition
1.2]✗LB/UB: $\log^{2}n$[Corollary 1.4]?Bdd Degeneracy$\checkmark$
[KNR92]Minor-Closed[GL07] Figure 1: The status of implicit representability
and best known upper and lower bounds on the size of adjacency labelling
schemes for some well-known hereditary classes. The presence of a $\checkmark$
denotes the existence of an implicit representation for any class of that
type, likewise ✗ indicates that there is a class of the given type that does
not admit an implicit representation, and ? shows this question is open. A
$\checkmark$ is inherited by every sub-region, a ✗ is inherited to the left of
the marked region, and a ? only holds in that region. The upper and lower
bounds (denoted UB and LB respectively) are stated up to constants which may
depend on the class.

###  1.1 Our contribution

In this paper, we study 1 for _monotone_ graph classes, i.e., graph classes
that are closed under taking subgraphs. Monotone graph classes form a
subfamily of hereditary graph classes. The following result shows that any
monotone class with non-decreasing speed admits a labeling scheme of size at
most $\mathcal{O}(\log n)$ away from the information-theoretic lower bound.

######  Proposition 1.2.

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be a non-
decreasing function. Then, any monotone class of graphs $\mathcal{X}$ with the
speed $|\mathcal{X}_{n}|=2^{\mathcal{O}(nf(n))}$ admits an adjacency labeling
scheme of size $\mathcal{O}(f(n)\log n)$.

This upper bound is an easy consequence of an estimation of the number of
edges in graphs from monotone classes combined with a standard labeling scheme
for $c$-degenerate graphs [KNR88], i.e., graphs in which every induced
subgraph contains a vertex of degree at most $c$.

Our main result shows that this upper bound is attained by some monotone
classes. Before stating the result formally we must briefly introduce a family
of non-decreasing functions we call “decent”. Roughly speaking, on some domain
$[s,\infty)$, decent functions are sub-multiplicative, i.e., $f(xy)\leqslant
f(x)f(y)$, and slow-growing, that is $\log x\leqslant f(x)\leqslant
x^{1-\delta}$ for some constant $\delta\in(0,1)$.

######  Theorem 1.3.

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be a
decent function. Then, there exists a monotone graph class $\mathcal{X}$ with
speed $|\mathcal{X}_{n}|=2^{\mathcal{O}(nf(n))}$ that does not admit a
universal graph of size at most $2^{f(n)\log n}$. Equivalently, $\mathcal{X}$
admits no adjacency labeling scheme of size at most $f(n)\log n$.

Theorem 1.3 is the main contribution of the paper, and it gives the existence
of monotone classes requiring labels whose size is a $\log n$-factor above the
information-theoretic lower bound. In particular this shows that Proposition
1.2 is tight.

A special case of Theorem 1.3 (when $f(x)=\log x$) implies that the Implicit
Graph Conjecture (1.1) does not hold even for monotone graph classes.
Combining this observation with Proposition 1.2 gives the following result.

######  Corollary 1.4.

For any constant $c>0$, there are factorial monotone classes that do not admit
a $(c\log^{2}n)$-bit labeling scheme, while any factorial monotone class
admits an $\mathcal{O}(\log^{2}n)$-bit labeling scheme.

###  1.2 Outline

The rest of the paper is organized as follows. In Sections 2.1 and 2.2, we
cover some common notation, definitions and lemmas. In Section 2.3 we
introduce two key concepts used in our proofs. Firstly, we give the notion of
_$f$ -good_ graphs, which are the building blocks for the monotone classes
used to prove our main result. Secondly, we formally define _decent_ functions
which describe the speeds of these monotone graph classes, before concluding
Section 2.3 with some natural examples of decent functions. In Section 3, we
prove a result about random graphs which is the main technical ingredient of
our lower bound. In Section 4, we establish the lower and upper bounds on
labeling schemes for monotone classes. We conclude the paper in Section 5 with
a discussion and some open problems.

##  2 Preliminaries

###  2.1 Standard definitions and notation

For two real numbers $i,j$, we let $[i,j]:=\\{\lceil i\rceil,\lceil
i\rceil+1,\ldots,\lfloor j\rfloor-1,\lfloor j\rfloor\\}$. Note that if $j<i$,
then $[i,j]$ is the empty set. We may use $[i]$ as a short-hand for
$[1,\lfloor i\rfloor]$, and $\ln^{c}x$ as a short-hand for $(\ln x)^{c}$. We
use $\mathbb{R}_{\geqslant 0}$ to denote the set of non-negative real numbers.

We use $X\sim\mathcal{D}$ to denote that the random variable $X$ has
distribution $\mathcal{D}$. We say that a sequence of events $(A_{n})$ holds
_with high probability (w.h.p.)_ if
$\mathbb{P}\left[\,A_{n}\,\right]\rightarrow 1$ as $n\rightarrow\infty$..

#### Graphs.

We consider finite undirected graphs, without loops or multiple edges. Given a
graph $G$, we write $V(G)$ for its vertex set, and $E(G)$ for its edge set. A
graph $H$ is a  _subgraph_ of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq
E(G)$. Thus, $H$ can be obtained from $G$ by vertex and edge deletions. The
graph $H$ is an _induced subgraph_ of $G$ if $V(H)\subseteq V(G)$, and $E(H)$
consists exactly of the edges in $E(G)$ with both endpoints in $V(H)$. In that
case, $H$ can be obtained from $G$ by vertex deletions only. In the usual way,
for a set of vertices $U\subseteq V(G)$, we denote by $G[U]$ the induced
subgraph of $G$ with the set of vertices $U$. We denote by $e(G)$ the number
of edges in $G$

When we refer to an $n$-vertex graph $G$ as _labeled_ , we mean that the
vertex set of $G$ is $[n]$ and we distinguish two different labeled graphs
even if they are isomorphic. In contrast, if we refer to $G$ as _unlabeled_
graph, its vertices are indistinguishable and two isomorphic graphs correspond
to the same unlabeled graph.

#### Graph classes.

A graph class is _hereditary_ if it is closed under taking induced subgraphs,
and it is _monotone_ if it closed under taking subgraphs. For a set
$\mathcal{X}$ of graphs we let $\mathrm{Her}(\mathcal{X})$ denote the
hereditary closure of $\mathcal{X}$, i.e., the inclusion-wise minimal
hereditary class that contains $\mathcal{X}$; and $\mathrm{Mon}(\mathcal{X})$
denote the monotone closure of $\mathcal{X}$, i.e., the minimal monotone class
that contains $\mathcal{X}$.

###  2.2 Useful lemmas

We use standard notation $G(n,p)$ to denote the distribution on $n$-vertex
graphs where each edge is included independently with probability $p$, and
$G(n,m)$ to denote the uniform distribution on $n$-vertex graphs with $m$
edges, see (for example) [FK23]. The following lemma allows us to transfer
results from one graph model to another.

######  Lemma 2.1.

Let $\mathcal{P}$ be any graph property (i.e., graph class) and $0\leqslant
p\leqslant 1$ satisfy $p\binom{n}{2}\rightarrow\infty$ and
$\binom{n}{2}-p\binom{n}{2}\rightarrow\infty$ and $m=\left\lceil
p\binom{n}{2}\right\rceil$. Then, for $G_{n}\sim G(n,m)$ and
$G_{n}^{\prime}\sim G(n,p)$, we have

$\mathbb{P}\left[\,G_{n}\in\mathcal{P}\,\right]\leqslant
10\sqrt{m}\cdot\mathbb{P}\left[\,G_{n}^{\prime}\in\mathcal{P}\,\right].$

Lemma 2.1 follows by a very minor adaption of [FK23, Lemma 3.2], the only
difference is a ceiling in the number of edges, which makes no difference in
the proof.

We will make use of the following version of the Chernoff bound (see [AS08,
Theorem A.1.15]), where $\mathrm{Bin}(N,p)$ denotes the binomial distribution
with parameters $N$ and $p$.

######  Lemma 2.2 (Chernoff bound).

Let $\xi\sim\mathrm{Bin}(N,p)$, $\mu=Np$, and $a,t>0$. Then,

$\mathbb{P}(\xi>(1+a)\mu)\leqslant\left(\frac{e^{a}}{(1+a)^{1+a}}\right)^{\mu}\leqslant\exp\left(-(1+a)\mu\cdot\ln\frac{1+a}{e}\right).$

###  2.3 Good graphs and decent functions

######  Definition 2.3 ($f$-good).

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be a
function. An $n$-vertex graph $G$ is _$f$ -good_ if the number of edges in any
subgraph on $k$ vertices is bounded from above by

$\begin{cases}\frac{k\cdot f(k)}{\log k}&\text{ if }2\leqslant
k\leqslant\sqrt{n}\\\ k\cdot f(k)&\text{ if }\sqrt{n}<k\leqslant
n\end{cases}.$

We observe that $f$-goodness is a monotone property, i.e., if a graph $G$ is
$f$-good, then so is any of its subgraphs. Indeed moving the threshold
(between the first and the second, more relaxed, upper bound) from $\sqrt{n}$
down to a smaller value may only help in satisfying these bounds.

######  Definition 2.4 ($(\delta,C,s)$-_decent_).

For constants $\delta\in(0,1)$, $C\geqslant 1$ and $s\geqslant 2$, we say that
a non-decreasing function $f:\mathbb{R}_{\geqslant
0}\rightarrow\mathbb{R}_{\geqslant 0}$ is $(\delta,C,s)$-_decent_ if the
following properties hold

(Moderate-growth):

$\log x\leqslant f(x)\leqslant C\cdot x^{1-\delta}$ holds for every
$x\in[s,\infty)$,

(Sub-multiplicativity):

$f(xy)\leqslant C\cdot f(x)\cdot f(y)$ holds for any $x,y\in[s,\infty)$.

We say that a function $f$ is decent if there exist some constants
$\delta\in(0,1)$, $C\geqslant 1$, and $s\geqslant 2$ such that $f$ is
$(\delta,C,s)$-decent. We now give some natural examples of decent functions.

######  Lemma 2.5.

For any constants $\alpha>0,\beta\geqslant 1$ and $d\in(0,1)$, the following
functions are decent:

  1. (i)

$f(x)=\alpha x^{d}$,

  2. (ii)

$f(x)=\exp\left(\alpha(\ln x)^{d}\right)$,

  3. (iii)

$f(x)=\exp\left((\alpha+1)\cdot\ln^{\beta}(\log x)\right)$,

  4. (iv)

$f(x)=(\log x)^{\beta}$

  5. (v)

$f(x)=\beta\cdot g(x)$, where $g(x)$ is decent.

  6. (vi)

$f(x)=g(x)\cdot h(x)$, where $g(x),h(x)$ are decent and $g(x)\cdot h(x)$ is
moderately-growing.

###### Proof.

For $(i)$, if we set $s_{1}:=\left(\frac{2}{d\max\\{\alpha,1\\}}\right)^{2/d}$
then we have

$f(s)=\alpha\cdot\left(\frac{2}{d\max\\{\alpha,1\\}}\right)^{2}\geqslant\frac{2}{d}\cdot\frac{2}{d\max\\{\alpha,1\\}}\geqslant\frac{2}{d}\cdot\log\frac{2}{d\max\\{\alpha,1\\}}=\log
s.$

Furthermore, there exists some constant $s_{2}:=s_{2}(\alpha,d)$ such that
$\frac{\alpha x^{d}}{\log x}$ is increasing for all $x\geqslant s_{2}$,
establishing moderate-growth on $[\max\\{s_{1},s_{2}\\},\infty)$ with
$C=\alpha$ and $\delta=1-d$. Observe also that $f(xy)=\frac{1}{\alpha}\cdot
f(x)f(y)$, and thus $f(x)=\alpha x^{d}$ is
$\Big{(}1-d,\max\left\\{\alpha,\frac{1}{\alpha}\right\\},\max\\{s_{1},s_{2}\\}\Big{)}$-decent.

For $(ii)$, moderate-growth holds for $C=1$, any fixed $\delta\in(0,1)$, and
sufficiently large $s\geqslant 2$. For $x,y\geqslant 0$ let
$g_{x}(y)=(x+y)^{d}-x^{d}-y^{d}$ and observe that $g_{x}(0)=0$ and
$g_{x}^{\prime}(y)=d(x+y)^{d-1}-dy^{d-1}\leqslant 0$. Consequently,
$g_{x}(y)\leqslant 0$ for all $x,y\geqslant 0$, or equivalently
$(x+y)^{d}\leqslant x^{d}+y^{d}$. This implies that $f$ is sub-multiplicative
as

$f(xy)=\exp\left(\alpha(\ln x+\ln y)^{d}\right)\leqslant\exp\left(\alpha((\ln
x)^{d}+(\ln y)^{d})\right)=f(x)\cdot f(y).$

For $(iii)$, it will be useful to show that

$\ln^{\beta}(x+y)\leqslant\ln^{\beta}x+\ln^{\beta}y,\qquad\text{for all
}x,y\in[e^{\beta},\infty).$ (1)

To prove (1), we first observe that the function $g(x)=\frac{\ln^{\beta}x}{x}$
is non-increasing for $x\in[e^{\beta},\infty)$. This follows since $g$ is
differentiable when $x\neq 0$ and $g^{\prime}(x)=\frac{(\beta-\ln
x)\ln^{\beta-1}x}{x^{2}}<0$ for all $x>e^{\beta}>1$. Thus (1) follows from
this observation, since for any $x,y\in[e^{\beta},\infty)$ we have

$\ln^{\beta}(x+y)=x\cdot\frac{\ln^{\beta}(x+y)}{x+y}+y\cdot\frac{\ln^{\beta}(x+y)}{x+y}\leqslant
x\cdot\frac{\ln^{\beta}x}{x}+y\cdot\frac{\ln^{\beta}y}{y}=\ln^{\beta}x+\ln^{\beta}y.$

We now see that $f$ is sub-multiplicative for any
$x,y\in[2^{e^{\beta}},\infty)$ as by (1) we have

$f(xy)=\exp\left((\alpha+1)\cdot\ln^{\beta}(\log x+\log
y)\right)\leqslant\exp\left((\alpha+1)\cdot(\ln^{\beta}(\log
x)+\ln^{\beta}(\log y))\right)=f(x)\cdot f(y).$

Since $\beta\geqslant 1$ and $\alpha>0$, $f$ is also moderately-growing for a
sufficiently large $s$.

For $(iv)$, we see that $f(x)=\log^{\beta}x$ is moderately-growing for large
$s\geqslant 2$ as $\beta\geqslant 1$. For sub-multiplicativity, for any
$x,y\in[s,\infty)$

$f(x)=\log^{\beta}(xy)=(\log x+\log
y)^{\beta}\leqslant(2\log(x)\log(y))^{\beta}\leqslant 2^{\beta}f(x)f(y).$

For $(v)$, if $g$ is $(\delta_{g},C_{g},s_{g})$-decent, then it is easy to
check that $\beta g$ is $(\delta_{g},\beta C_{g},s_{g})$-decent.

For $(vi)$, let $g$ be $(\delta_{g},C_{g},s_{g})$-decent and $h$ be
$(\delta_{h},C_{h},s_{h})$-decent, and $f(x):=g(x)\cdot h(x)$. As $\log
x\leqslant f(x)\leqslant C^{\prime}x^{1-\delta^{\prime}}$ for some
$\delta^{\prime}\in(0,1),C^{\prime}>0$, and $s^{\prime}\geqslant 2$, by
assumption, it remains to show sub-multiplicativity. For any
$x,y\in[s,\infty)$, where $s=\max\\{s^{\prime},s_{g},s_{h}\\}$, we have

$f(xy)=g(xy)\cdot h(xy)\leqslant C_{g}g(x)g(y)\cdot C_{h}h(x)h(y)\leqslant
C_{g}\cdot C_{h}\cdot f(x)f(y),$

and thus $f$ is $(\delta^{\prime},\max\\{C^{\prime},C_{g}\cdot
C_{h}\\},s)$-decent. ∎

##  3 Growth of the number of edges in subgraphs of $G(n,p)$

######  Theorem 3.1.

For any constants $\delta\in(0,1)$, $C\geqslant 1$, and $s\geqslant 2$, let
$f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be
$(\delta,C,s)$-decent. Then, for any fixed $\gamma>1$, there exists
$c:=c(\delta,C,s,\gamma)>0$ such that, for large $n$,

$\mathbb{P}\left[\,G(n,\gamma f(n)/n)\text{ is not }(cf)\text{-good
}\right]\leqslant n^{-2}.$

###### Proof.

Let $p:=p(n)=\gamma f(n)/n$, and let $c_{1},c_{2}$ be sufficiently large
constants (depending on $\gamma$) fixed later. Let $\mathcal{E}_{1,k}$
(respectively $\mathcal{E}_{2,k}$) be the event that there are no subgraphs of
size $k$ with more than $c_{1}kf(k)/\log k$ edges (respectively $c_{2}kf(k)$
edges). Observe that if $c=\max\\{c_{1},c_{2},\binom{s}{2}\\}$, then

$\left\\{G(n,p)\text{ is not
}(cf)\text{-good}\right\\}\subseteq\left(\bigcup_{k=s}^{\lfloor\sqrt{n}\rfloor}\neg\mathcal{E}_{1,k}\right)\cup\left(\bigcup_{k=\lfloor\sqrt{n}\rfloor+1}^{n}\neg\mathcal{E}_{2,k}\right).$
(2)

Let $k$ denote the number of vertices in a subgraph, and thus
$\xi\sim\mathrm{Bin}\left({k\choose 2},p\right)$ denotes the number of edges
in a given $k$-vertex subgraph. The expectation of $\xi$ is

$\mu:={k\choose 2}p=\frac{\gamma}{2}\cdot\frac{k(k-1)f(n)}{n}.$

On the other hand, the number of ways to choose a $k$-vertex subgraph is

${n\choose
k}\leqslant\left(\frac{en}{k}\right)^{k}=\exp\left(k\ln\frac{n}{k}+k\right)\leqslant\exp\left(2k\ln
n\right).$ (3)

Our strategy will be to bound the probability of the events on the right hand
side of (2) using the union and Chernoff bounds.

We begin by considering events of the form $\mathcal{E}_{2,k}$ and thus can
assume that $\lfloor\sqrt{n}\rfloor+1\leqslant k\leqslant n$. Observe that
since $f$ is sub-multiplicative, non-decreasing, and moderately-growing, we
have

$\frac{f(k)}{f(n)}=\frac{f(k)}{f\left(\frac{n}{k}\cdot
k\right)}\geqslant\frac{f(k)}{C\cdot f(\frac{n}{k})\cdot
f(k)}\geqslant\frac{f(k)}{C\cdot f(\frac{sn}{k})\cdot
f(k)}\geqslant\frac{f(k)}{C^{2}\cdot(\frac{sn}{k})^{1-\delta}\cdot
f(k)}\geqslant\frac{k}{C^{2}s\cdot n}.$ (4)

If we now fix

$c_{2}=C^{2}s\cdot e^{2}\cdot\gamma>6,$ (5)

then by (4) we have

$\frac{2c_{2}nf(k)}{e\gamma(k-1)f(n)}=\frac{2C^{2}se\cdot
nf(k)}{(k-1)f(n)}\geqslant\frac{2ek}{k-1}>e.$ (6)

So, applying Chernoff bound (Lemma 2.2) with
$1+a=\frac{c_{2}kf(k)}{\mu}=\frac{2c_{2}nf(k)}{\gamma(k-1)f(n)}$ gives

$\displaystyle\mathbb{P}(\xi>c_{2}kf(k))$
$\displaystyle\leqslant\exp\left(-(1+a)\mu\cdot\ln\frac{1+a}{e}\right)$
$\displaystyle=\exp\left(-c_{2}kf(k)\cdot\ln\frac{2c_{2}nf(k)}{e\gamma(k-1)f(n)}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:keyGnp}}}{{\leqslant}}\exp\left(-c_{2}kf(k)\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:consstc2}}}{{\leqslant}}\exp\left(-6kf(k)\right).$
(7)

Thus, by (3), (3), the union bound, and as $f(k)\geqslant\log k>\ln k$, we
have

$\mathbb{P}\left(\bigcup_{k=\lfloor\sqrt{n}\rfloor+1}^{n}\neg\mathcal{E}_{2,k}\right)\leqslant\sum_{k=\lfloor\sqrt{n}\rfloor+1}^{n}\exp\left(2k\ln
n\right)\cdot\exp\left(-6kf(k)\right)\leqslant\sum_{k=\lfloor\sqrt{n}\rfloor+1}^{n}k^{-k}\leqslant\exp(-\sqrt{n}).$
(8)

We now treat events of the from $\mathcal{E}_{1,k}$ and thus we can assume
that $s\leqslant k\leqslant\lfloor\sqrt{n}\rfloor$. Observe that for any fixed
constant $d>0$ and sufficiently large $n$ we have $\frac{n^{2/3}}{k(\log
k)^{d}}\geqslant s$ as $k\leqslant\sqrt{n}$. Thus, by sub-multiplicativity,
and moderate-growth we have

$\displaystyle f\left(\frac{n^{2/3}}{(\log k)^{d}}\right)$
$\displaystyle=f\left(\frac{n^{2/3}}{k(\log k)^{d}}\cdot k\right)$
$\displaystyle\leqslant C\cdot f\left(\frac{n^{2/3}}{k(\log
k)^{d}}\right)\cdot f\left(k\right)$ $\displaystyle\leqslant
C^{2}\cdot\left(\frac{n^{2/3}}{k(\log k)^{d}}\right)^{1-\delta}\cdot f(k)$
$\displaystyle\leqslant C^{2}\cdot\frac{n^{2/3}}{k(\log k)^{d}}\cdot f(k).$

Similarly, by sub-multiplicativity and moderate-growth, we have

$\displaystyle f(n)$ $\displaystyle=f\left(\frac{n^{2/3}}{(\log k)^{d}}\cdot
n^{1/3}(\log k)^{d}\right)$ $\displaystyle\leqslant C\cdot
f\left(\frac{n^{2/3}}{(\log k)^{d}}\right)\cdot f\left(n^{1/3}(\log
k)^{d}\right)$ $\displaystyle\leqslant C^{2}\cdot f\left(\frac{n^{2/3}}{(\log
k)^{d}}\right)\cdot n^{(1-\delta)/3}(\log k)^{(1-\delta)\cdot d}.$

If we set $d=1/\delta>0$ then the two bounds above give

$\frac{f(k)}{f(n)}\geqslant\frac{f\left(\frac{n^{2/3}}{(\log
k)^{d}}\right)\cdot\frac{k(\log k)^{d}}{2C^{2}n^{2/3}}}{C^{2}\cdot
f\left(\frac{n^{2/3}}{(\log k)^{d}}\right)\cdot n^{(1-\delta)/3}(\log
k)^{(1-\delta)\cdot d}}=\frac{k(\log k)^{\delta
d}}{2C^{4}n^{1-\delta/3}}=\frac{k\log k}{2C^{4}n}\cdot n^{\delta/3}.$ (9)

Foreseeing the need for the constant $15$ later on, we now set

$c_{1}=e\cdot 15\cdot C^{4}\gamma/\delta.$ (10)

We now set $1+a:=\frac{c_{1}kf(k)}{\mu\cdot\log k}$, which by (9) satisfies

$1+a=\frac{c_{1}kf(k)}{\mu\cdot\log k}=\frac{2c_{1}nf(k)}{\gamma(k-1)f(n)\log
k}\geqslant\frac{c_{1}k}{\gamma(k-1)C^{4}}\cdot n^{\delta/3}>e\cdot
n^{\delta/3}.$ (11)

As before, Chernoff bound (Lemma 2.2) with this $1+a$ gives

$\displaystyle\mathbb{P}\left(\xi>\frac{c_{1}kf(k)}{\log k}\right)$
$\displaystyle\leqslant\exp\left(-\frac{c_{1}kf(k)}{\log
k}\cdot\ln\frac{1+a}{e}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:secondabdd}}}{{\leqslant}}\exp\left(-\frac{c_{1}kf(k)}{\log
k}\cdot\frac{\delta}{3}\ln n\right)$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leqslant}}\exp\left(-c_{1}k\cdot\frac{\delta}{3}\ln
n\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:constc1}}}{{\leqslant}}\exp\left(-5k\ln
n\right),$ (12)

where $(*)$ follows as $f(k)\geqslant\log k$ by moderate-growth. Thus, by (3),
(3), and the union bound,

$\mathbb{P}\left(\bigcup_{k=s}^{\lfloor\sqrt{n}\rfloor}\neg\mathcal{E}_{1,k}\right)\leqslant\sum_{k=s}^{\lfloor\sqrt{n}\rfloor}\exp\left(2k\ln
n\right)\cdot\exp\left(-5k\ln n\right)\leqslant\sqrt{n}\cdot n^{-3s}\leqslant
n^{-5}.$ (13)

The result follows by taking $c=\max\\{c_{1},c_{2},\binom{s}{2}\\}$, (2), and
the union bound over (8) and (13). ∎

We can now use this result to bound the number of $cf$-good graphs from below.

######  Lemma 3.2.

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be
$(\delta,C,s)$-decent for some constants $\delta\in(0,1)$, $C\geqslant 1$, and
$s\geqslant 2$. Then, for any fixed $\gamma>1$, there exists some
$c:=c(\gamma,\delta,C,s)>0$ such that for every $n\in\mathbb{N}$ there are at
least $2^{(\gamma\delta/2-o(1))\cdot nf(n)\log n}$ many unlabeled $(cf)$-good
graphs.

###### Proof.

Let $m:=\big{\lceil}\tfrac{\gamma(n-1)f(n)}{2}\big{\rceil}$ and $G_{n}\sim
G\big{(}n,m\big{)}$. Observe that by Theorem 3.1 and Lemma 2.1, there exists
some fixed $c>0$ such that for sufficiently large $n$

$\mathbb{P}\left[\,G_{n}\text{ is $(cf)$-good}\,\right]\geqslant
1-10\sqrt{\big{\lceil}\tfrac{\gamma(n-1)f(n)}{2}\big{\rceil}}\cdot
n^{-2}=1-o(1).$ (14)

The number of labeled graphs in the support of $G\big{(}n,m\big{)}$ is

$\binom{\binom{n}{2}}{m}=\binom{\binom{n}{2}}{\left\lceil\tfrac{\gamma(n-1)f(n)}{2}\right\rceil}\geqslant\left(\frac{n}{\gamma
f(n)}\right)^{\tfrac{\gamma(n-1)f(n)}{2}}=2^{\frac{\gamma}{2}\cdot(n-1)f(n)\cdot(\log
n-\log(\gamma f(n)))}.$

By (14), a $1-o(1)$ fraction of these labeled graphs are $(cf)$-good.
Furthermore, there are at most $n!\leqslant n^{n}$ labelings of a given
unlabeled graph. Thus, the number of unlabeled $n$-vertex $(cf)$-good graphs
is bounded from below by

$\displaystyle(1-o(1))\cdot\frac{1}{n^{n}}\cdot
2^{\frac{\gamma}{2}\cdot(n-1)f(n)\cdot(\log n-\log(\gamma f(n)))}$
$\displaystyle=2^{\frac{\gamma}{2}\cdot nf(n)\cdot(\log
n-\log(f(n))-\mathcal{O}(1))}$ $\displaystyle\geqslant
2^{\frac{\gamma}{2}\cdot nf(n)\cdot(\log n-(1-\delta)\log(n)-\mathcal{O}(1))}$
$\displaystyle=2^{(\delta\gamma/2-o(1))\cdot nf(n)\log n},$

as claimed, since $\log n\leqslant f(n)\leqslant Cn^{1-\delta}$ by moderate-
growth. ∎

##  4 Tight bounds on labeling schemes for monotone factorial classes

We begin in Section 4.1 with a lemma which is useful for bounding the speed
when constructing monotone classes with no implicit representation. This is
then used to prove our lower bound in Section 4.2. Finally, in Section 4.3 we
give a matching upper bound on labeling schemes for monotone classes, this
follows from [KNR92] and included mainly for completeness.

###  4.1 Construction of monotone tiny classes

We begin with a lemma showing, for a decent function $f$, we can create
monotone classes from the union of many $f$-good graphs and still maintain
control over the speed. The proof follows the broad idea of [HH22, Claim 3.1].

######  Lemma 4.1.

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be
$(\delta,C,s)$-decent for some constants $\delta\in(0,1)$, $C\geqslant 1$, and
$s\geqslant 2$. Let $c>0$ be a constant, and, for every $n\in\mathbb{N}$, let
$M_{n}$ be any set of $(cf)$-good unlabeled $n$-vertex graphs satisfying
$|M_{n}|\leqslant\big{\lceil}2^{\sqrt{nf(n)}}\big{\rceil}$. Then the speed of
$\mathcal{X}:=\mathrm{Mon}(\cup_{n\in\mathbb{N}}M_{n})$ is
$2^{\mathcal{O}(nf(n))}$.

###### Proof.

Let $\mathcal{Y}:=\mathrm{Her}(\cup_{n\in\mathbb{N}}M_{n})$. Note that
$\mathcal{X}=\mathrm{Mon}(\mathcal{Y})$. We first estimate the speed of
$\mathcal{Y}$. For an $n$-vertex graph $G\in\mathcal{Y}$, let $N$ be the
smallest integer such that $G$ is an induced subgraph of a graph $H\in M_{N}$.
We split the proof over two cases: $(i)$: $N\geqslant n^{2}$, and $(ii)$:
$N<n^{2}$. Case (ii):

Since $H$ is a $(cf)$-good $N$-vertex graph and $G$ is its $n$-vertex induced
subgraph, where $n\leqslant\sqrt{N}$, it follows from Definition 2.3 that $G$
must have at most $g(n):=cnf(n)/\log n$ many edges. The number of such graphs
is at most

$\binom{\binom{n}{2}}{g(n)}\leqslant\left(\frac{n^{2}e}{g(n)}\right)^{g(n)}=2^{g(n)\cdot\log\frac{n^{2}e}{g(n)}}=2^{c\frac{nf(n)}{\log
n}\cdot\log\frac{n^{2}e}{g(n)}}=2^{\mathcal{O}(nf(n))},$

and so $\mathcal{Y}$ contains $2^{\mathcal{O}(nf(n))}$ many $n$-vertex labeled
graphs each of which is an induced subgraph of a graph in $M_{N}$ for some $N$
with $n\leqslant\sqrt{N}$.

For this case, we simply use the fact that any $H\in M_{N}$ has at most
$N^{n}$ many $n$-vertex induced subgraphs.

Thus, the number of $n$-vertex labeled graphs in $\mathcal{Y}$ each of which
is an induced subgraph of a graph in $M_{N}$ for some $N$ with $N<n^{2}$ is
bounded from above by

$\displaystyle n!\cdot\sum_{N=n}^{n^{2}}N^{n}\cdot|M_{N}|$
$\displaystyle\leqslant n!\cdot\sum_{N=n}^{n^{2}}N^{n}\cdot\left\lceil
2^{\sqrt{Nf(N)}}\right\rceil$ $\displaystyle\leqslant n!\cdot
n^{2}\cdot(n^{2})^{n}\cdot\left\lceil 2^{\sqrt{n^{2}f(n^{2})}}\right\rceil$
$\displaystyle\leqslant 2^{\mathcal{O}(n\log n)}\cdot\left\lceil
2^{\sqrt{C}nf(n)}\right\rceil$ $\displaystyle=2^{\mathcal{O}(nf(n))},$

where in the last inequality we used sub-multiplicativity of $f$, and in the
final equality we used the fact that $f(x)\geqslant\log x$. Thus,
$|\mathcal{Y}_{n}|=2^{\mathcal{O}(nf(n))}$. Now, since every $n$-vertex
labeled graph in $\mathcal{X}$ is a subgraph of an $n$-vertex labeled graph in
$\mathcal{Y}$, and, due to $(cf)$-goodness, every graph in $\mathcal{Y}_{n}$
has at most $2^{cnf(n)}$ $n$-vertex subgraphs, we conclude that
$|\mathcal{X}_{n}|\leqslant|\mathcal{Y}_{n}|\cdot
2^{cnf(n)}=2^{\mathcal{O}(nf(n))}$. ∎

###  4.2 Lower bound

We can now show the main result of the paper, which we recall for convenience.

######  Theorem 1.3.

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be a
decent function. Then, there exists a monotone graph class $\mathcal{X}$ with
speed $|\mathcal{X}_{n}|=2^{\mathcal{O}(nf(n))}$ that does not admit a
universal graph of size at most $2^{f(n)\log n}$. Equivalently, $\mathcal{X}$
admits no adjacency labeling scheme of size at most $f(n)\log n$.

###### Proof.

By assumption $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$
is $(\delta,C,s)$-decent for some constants $\delta\in(0,1)$, $C\geqslant 1$,
and $s\geqslant 2$. We will construct a monotone class (via the probabilistic
method) with the speed $2^{\mathcal{O}(nf(n))}$ that does not admit a
universal graph of size $u_{n}:=2^{f(n)\log n}$. Fix $\gamma:=4/\delta>1$ and
let $c:=c(\gamma,\delta,C,s)>0$ be the satisfying constant from Lemma 3.2
corresponding to this choice of $\gamma$. Let $k_{n}:=\left\lceil
2^{\sqrt{nf(n)}}\right\rceil$.

The number of distinct $u_{n}$-vertex graphs is at most $2^{u_{n}^{2}}$ and
the number of $n$-vertex induced subgraphs of a fixed $u_{n}$-vertex graph is
at most $\binom{u_{n}}{n}$. Hence the number of collections of $k_{n}$ graphs
on $n$ vertices that are induced subgraphs of a $u_{n}$-vertex (universal)
graph is at most

$2^{u_{n}^{2}}\cdot\binom{\binom{u_{n}}{n}}{k_{n}}\leqslant 2^{u_{n}^{2}}\cdot
u_{n}^{k_{n}\cdot n}.$ (15)

On the other hand, from Lemma 3.2, the number of different collections of
$n$-vertex $(cf)$-good graphs of cardinality $k_{n}$ is at least

$\binom{2^{(\gamma\delta/2-o(1))\cdot nf(n)\log
n}}{k_{n}}\geqslant\left(\frac{2^{(\gamma\delta/2-o(1))\cdot nf(n)\log
n}}{k_{n}}\right)^{k_{n}}=2^{k_{n}\cdot(\gamma\delta/2-o(1))\cdot nf(n)\log
n},$ (16)

as $\log k_{n}=\mathcal{O}(\sqrt{nf(n)})=o(nf(n)\log n)$. By taking
logarithms, we can see that for sufficiently large $n$ the upper bound (15) is
smaller than the lower bound (16). In particular, taking the logarithm of (15)
gives

$\displaystyle\log\left(2^{u_{n}^{2}}\cdot u_{n}^{k_{n}\cdot n}\right)$
$\displaystyle=u_{n}^{2}+k_{n}\cdot n\log u_{n}$ $\displaystyle=2^{2f(n)\log
n}+k_{n}\cdot nf(n)\log n$ $\displaystyle=(1+o(1))\cdot k_{n}\cdot nf(n)\log
n,$ as $k_{n}:=\left\lceil 2^{\sqrt{nf(n)}}\right\rceil=\omega(2^{2f(n)\log
n})$. However, since $\gamma=4/\delta$, the logarithm of (16) is
$\displaystyle\log\left(2^{k_{n}\cdot(\gamma\delta/2-o(1))\cdot nf(n)\log
n}\right)$ $\displaystyle=k_{n}\cdot(\gamma\delta/2-o(1))\cdot nf(n)\log n$
$\displaystyle=(2-o(1))\cdot k_{n}\cdot nf(n)\log n.$

Thus, for any sufficiently large $n$, there exists a collection $M_{n}$ of
$k_{n}$ $(cf)$-good $n$-vertex graphs that are not representable by any
universal graph of size at most $u_{n}=2^{f(n)\log n}$. Consequently, by Lemma
4.1, the speed of $\mathcal{X}:=\mathrm{Mon}(\cup_{n}M_{n})$ is
$|\mathcal{X}_{n}|=2^{\mathcal{O}(nf(n))}$ and $\mathcal{X}$ does not admit a
universal graph of size at most $2^{f(n)\log n}$. ∎

###  4.3 Upper bound

######  Proposition 1.2.

Let $f:\mathbb{R}_{\geqslant 0}\rightarrow\mathbb{R}_{\geqslant 0}$ be a non-
decreasing function. Then, any monotone class of graphs $\mathcal{X}$ with the
speed $|\mathcal{X}_{n}|=2^{\mathcal{O}(nf(n))}$ admits an adjacency labeling
scheme of size $\mathcal{O}(f(n)\log n)$.

###### Proof.

Let $\mathcal{X}$ be a monotone class with at most $2^{Cnf(n)}$ labeled
$n$-vertex graphs for every $n$. If an $n$-vertex graph $G\in\mathcal{X}$ has
$m$ edges, then $\mathcal{X}$ contains at least $2^{m}$ labeled $n$-vertex
graphs, as every subgraph of $G$ also belongs to $\mathcal{X}$ due to
monotonicity.

This implies that every $n$-vertex graph $G$ in $\mathcal{X}$ contains at most
$Cnf(n)$ edges, and hence, has a vertex of degree at most $2Cf(n)$. Due to
monotonicity of $f$, the same is true for every subgraph of $G$. Indeed, if
$H$ is a $k$-vertex subgraph of $G$, then, since $H$ belongs to $\mathcal{X}$,
the number of edges in $H$ is at most $Ckf(k)\leqslant Ckf(n)$, and therefore
$H$ has a vertex of degree at most $2Cf(n)$.

Thus, every $n$-vertex graph in $\mathcal{X}$ is $2Cf(n)$-degenerate, and the
standard adjacency labeling scheme for $c$-degenerate graphs [KNR92] implies
that $\mathcal{X}$ admits a $2Cf(n)\log n$-bit labeling scheme. ∎

##  5 Conclusions

Our main result shows that for any ‘decent’ function $f$ we can find a
monotone class of graphs $\mathcal{X}$ with speed
$|\mathcal{X}_{n}|=2^{\mathcal{O}(nf(n))}$ for which any labeling scheme
requires a multiplicative factor $\log n$ more bits than the information-
theoretic lower bound. Furthermore, we gave an upper bound on the size of
labeling schemes for any monotone class with non-decreasing speed which
matches our lower bound, up-to a constant.

A natural question arising from our work is to characterize monotone classes
that admit an implicit representation, i.e., an adjacency labeling scheme of
order optimal size. Motivated by the Implicit Graph Conjecture, of particular
interest is the case of factorial classes.

######  Question 2.

Which _monotone_ factorial graph classes admit an $\mathcal{O}(\log n)$-bit
labeling scheme?

An analogous question is completely understood for constant-size _adjacency
sketches_ (a probabilistic version of adjacency labeling schemes) that were
studied in [FK09, Har20, HWZ22]. The importance of constant-size adjacency
sketches is that they can be derandomized to $\mathcal{O}(\log n)$-bit
adjacency labels [Har20, HWZ22]. Thus, if a class admits constant-size
adjacency sketches, then it admits an $\mathcal{O}(\log n)$-bit labeling
scheme. Though, the converse is not always true. Esperet, Harms, and Kupavskii
showed [EHK22] that a monotone class admits constant-size adjacency sketches
if and only if it has bounded degeneracy. This result may suggest that bounded
degeneracy also characterises monotone classes that admit $\mathcal{O}(\log
n)$-bit labeling schemes. This, however, is not the case, as the class of
subgraphs of hypercubes is monotone, has unbounded degeneracy, and admits an
$\mathcal{O}(\log n)$-bit labeling scheme [EHZ23].

Recall that 1 (first raised in [Spi03]), asks which hereditary graph classes
admit implicit representations. A prominent instance of 1 is whether every
small class (i.e., class $\mathcal{X}$ with $|\mathcal{X}_{n}|\leqslant
c^{n}\cdot n!$ for some constant $c>0$), or even every monotone small class,
admits an implicit representation. It is known that for any $\kappa>0$ there
is a small monotone class which does not admit a ($\kappa\log n$)-bit labeling
scheme [BDS+23]. In particular, some small classes admit no asymptotically
optimal labeling scheme. However, this result does not rule out the existence
of an order optimal labeling scheme for each small class of graphs.

Finally, a more technical (yet natural) question is whether the conditions
(moderate-growth and sub-multiplicativity) of ‘decent’ can be relaxed. Due to
the discussion in the introduction, the moderate-growth condition is
essentially necessary. It is not so clear to what extent the sub-
multiplicativity condition is necessary, however, if one is to follow our
method, some notion of global “smoothness” is required to prove Theorem 3.1.
To see this, consider a function $f:\mathbb{N}\rightarrow\mathbb{R}_{\geqslant
0}$ such that $f(n)=\log n$, if $n$ is odd, and $f(n)=\sqrt{n}$, if $n$ is
even. Then, for any $c>0$, and large enough even $n$, $G(n,f(n)/n)$ will not
be $cf$-good as the restriction on the subgraphs with odd number of vertices
is far too stringent.

## References

  * [AKTZ15] Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick.  Adjacency labeling schemes and induced-universal graphs.  In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 625–634, 2015.
  * [Ale92] Vladimir E. Alekseev.  Range of values of entropy of hereditary classes of graphs.  Diskretnaya Matematika, 4(2):148–157, 1992.
  * [Ale97] Vladimir E. Alekseev.  On lower layers of a lattice of hereditary classes of graphs.  Diskretnyi Analiz i Issledovanie Operatsii, 4(1):3–12, 1997.
  * [Alo17] Noga Alon.  Asymptotically optimal induced universal graphs.  Geom. Funct. Anal., 27(1):1–32, 2017.
  * [Alo23] Noga Alon.  Implicit representation of sparse hereditary families.  Discret. Comput. Geom., to appear, 2023.
  * [AS08] Noga Alon and Joel H. Spencer.  The Probabilistic Method, Third Edition.  Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2008.
  * [Ban22] Avah Banerjee.  An adjacency labeling scheme based on a decomposition of trees into caterpillars.  In International Workshop on Combinatorial Algorithms, pages 114–127. Springer, 2022.
  * [BDS+23] Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii.  Small but unwieldy: A lower bound on adjacency labels for small classes.  CoRR, abs/2307.11225, 2023.
  * [BEGS21] Marthe Bonamy, Louis Esperet, Carla Groenland, and Alex Scott.  Optimal labelling schemes for adjacency, comparability, and reachability.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1109–1117, 2021.
  * [BGK+22] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width II: small classes.  Combinatorial Theory, 2 (2), 2022.
  * [BT95] Béla Bollobás and Andrew Thomason.  Projections of bodies and hereditary properties of hypergraphs.  Bulletin of the London Mathematical Society, 27(5):417–424, 1995\.
  * [CV03] Bruno Courcelle and Rémi Vanicat.  Query efficient implementation of graphs of bounded clique-width.  Discrete Applied Mathematics, 131(1):129–150, 2003.
  * [EHK22] Louis Esperet, Nathaniel Harms, and Andrey Kupavskii.  Sketching distances in monotone graph classes.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [EHZ23] Louis Esperet, Nathaniel Harms, and Viktor Zamaraev.  Optimal adjacency labels for subgraphs of cartesian products.  In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, volume 261 of LIPIcs, pages 57:1–57:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [FK09] Pierre Fraigniaud and Amos Korman.  On randomized representations of graphs using short labels.  In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, pages 131–137, 2009.
  * [FK23] Alan Frieze and Michał Karoński.  Random Graphs and Networks: A First Course.  Cambridge University Press, 2023.
  * [GL07] Cyril Gavoille and Arnaud Labourel.  Shorter implicit representation for planar graphs and bounded treewidth graphs.  In Algorithms–ESA 2007: 15th Annual European Symposium (ESA 2007). Proceedings 15, pages 582–593. Springer, 2007.
  * [Har20] Nathaniel Harms.  Universal communication, universal graphs, and graph labeling.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [HH22] Hamed Hatami and Pooya Hatami.  The implicit graph conjecture is false.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 1134–1137. IEEE, 2022.
  * [HWZ22] Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev.  Randomized communication and implicit graph representations.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), pages 1220–1233, 2022.
  * [KNR88] Sampath Kannan, Moni Naor, and Steven Rudich.  Implicit representation of graphs.  In Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988), pages 334–343, 1988.
  * [KNR92] Sampath Kannan, Moni Naor, and Steven Rudich.  Implicit representation of graphs.  SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992.
  * [Moo65] John W Moon.  On minimal $n$-universal graphs.  Glasgow Mathematical Journal, 7(1):32–33, 1965.
  * [Mul88] John H. Muller.  Local Structure in Graph Classes.  PhD thesis, 1988.
  * [NSTW06] Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan.  Proper minor-closed families are small.  Journal of Combinatorial Theory, Series B, 96(5):754–757, 2006\.
  * [Sch99] Edward R Scheinerman.  Local representations using very short labels.  Discrete mathematics, 203(1-3):287–290, 1999.
  * [Spi03] Jeremy P Spinrad.  Efficient Graph Representations, volume 19.  Fields Institute monographs. American Mathematical Soc., 2003.
  * [SZ94] Edward R Scheinerman and Jennifer Zito.  On the size of hereditary classes of graphs.  Journal of Combinatorial Theory, Series B, 61(1):16–39, 1994.