2023

[1]Pau Torras

[1]Computer Vision Center, Universitat Autònoma de Barcelona, Cerdanyola del
Vallès, 08193, Spain

# The Common Optical Music Recognition Evaluation Framework

<EMAIL_ADDRESS>Sanket Biswas<EMAIL_ADDRESS>Alicia Fornés
<EMAIL_ADDRESS>*

###### Abstract

The quality of Optical Music Recognition (OMR) systems is a rather difficult
magnitude to measure. There is no lingua franca shared among OMR datasets that
allows to compare systems’ performance on equal grounds, since most of them
are specialised on certain approaches. As a result, most state-of-the-art
works currently report metrics that cannot be compared directly. In this paper
we identify the need of a common music representation language and propose the
Music Tree Notation (MTN) format, thanks to which the definition of standard
metrics is possible. This format represents music as a set of primitives that
group together into higher-abstraction nodes, a compromise between the
expression of fully graph-based and sequential notation formats. We have also
developed a specific set of OMR metrics and a typeset score dataset as a proof
of concept of this idea.

###### keywords:

Optical Music Recognition, Evaluation, Datasets, Computer Vision

##  1 Introduction

Written music has been part of the cultural heritage of humankind for many
centuries. From neumes as old as a thousand of years to current-time western
notation scores, people have built methods to make this most ephemeral of arts
persistent through the passing of time. Rivers of ink have been imprinted on
libraries worth of paper in order to preserve music along the ages, and much
of it has indeed survived until today.

It is therefore unsurprising that, given the sheer volume of notably
interesting (and oftentimes, forgotten) pieces of music that have been endowed
to our current generations, scholars have turned their attention to computers
to aid them in the endeavour of preserving and analysing them. The task that
concerns us in this work is Optical Music Recognition (OMR), which is the
first and therefore fundamental step for the computational analysis of written
scores; converting images or scans of music into a defined format a computer
can process Calvo-Zaragoza et al (2021).

Modern-day OMR has been greatly enriched with the advent of the powerful Deep
Learning techniques developed during the last decade Calvo-Zaragoza et al
(2021); Rebelo et al (2012). Nevertheless, the field itself remains
fragmented, with few researchers fully devoted to it and each of them
developing their own unique point of view and methodology Pacha (2018); Calvo-
Zaragoza et al (2021). This is particularly evident when analysing the
available datasets Pacha (2017), as can be seen in Table 1; most of them are
restricted to specific steps or approaches Parada-Cabaleiro et al (2017);
Tuggener et al (2018); Calvo-Zaragoza and Rizo (2018a) and almost none of them
are compatible among each other (the most notable exception being the recent
Shatri and Fazekas (2021), which incorporates its ground truth in multiple
formats).

One of the main points of disagreement among OMR researchers is the matter of
the evaluation of models Hajič and Pecina (2017); Hajič jr. (2018); Mengarelli
et al (2019); Calvo-Zaragoza et al (2021), which is but the visible
consequence of many long-standing issues – some related to the inherent
difficulty of the field (for an example, see Figure 1), but others related to
the diversity of plausible approaches to music recognition.

Figure 1: Fragment of a scan of a 1910 edition of Claude Debussy’s La Danse de
Puck from the first volume of his Préludes. In this fragment, many of the
reasons why modelling OMR scores is difficult can be seen – a two-staff system
with voices that move along both of them, many small symbols concentrated in
limited areas of the score, many independent voices sounding in unison,
elements spanning multiple measures, chords, etc.

Evaluation of OMR models is currently performed on a per-methodology basis
Calvo-Zaragoza et al (2021); Rebelo et al (2012). If one considers the goal of
OMR to produce a computational representation of music – whichever that final
representation might be 111Byrd et al. Byrd and Isaacson (2003) collected a
very extensive and detailed set of requirements for a music notation system
that is suitable for both score engraving and OMR, but to the best of our
knowledge there is no recognition system that formally or explicitly applies
them. – one would expect the metrics to obey a criterion of either some aspect
of music understanding or quantifying the correctness of the final
representation. Instead, most metrics revolve around measuring the fidelity of
intermediate representations devoid of musical meaning, disregarding the full
reconstruction of music scores altogether. Moreover, the benchmarks this
evaluation metrics are computed upon are rarely widespread, with each
methodology using their own. Commercial OMR systems have also been very vague
about the specifics of their capacity.

With the aim of setting a step forward towards unifying the efforts of the
community, we propose a way to set a common framework for OMR. We believe the
first step is to set a target final representation that accommodates a
significant amount of use cases within Common Western Music Notation (CWMN).
We explicitly avoid trying to cover the entirety of OMR, as the nature of
notated music is diverse and heavily dependent on the time it was written and
the instrument it was written for. Once this target representation is chosen,
a way of easily working with it has to be developed. Currently used engraving
formats are quite exhaustive, verbose and option-filled, which allows
expressing the same score in a variety of ways – something that makes them
quite impractical for direct comparison. Thus, we propose an intermediate
representation that translates directly to the desired output but facilitates
OMR operations – including analysis, evaluation and composition of results –
regardless of the underlying approach. We propose doing so through a notation
based on the idea of building a tree structure; leaves are the objects in the
music score and intermediate nodes are their composition. The idea is
exploiting the expression advantages of graph-based approaches while
simplifying the kinds of relationships that such system can model.
Incorporating a common notation format is also a way of unifying all existing
datasets so that they can be both combined and compared on equal grounds,
regardless of the methodology they were originally designed to work with.

The contribution of this work can be summarised by the following claims:

  * •

We try to bridge the gap between the different benchmark suites in OMR
literature with a universal tree-based notation format designed to represent
musical scores at the graphical level.

  * •

We also present a common evaluation toolkit which aims towards unify existing
benchmark OMR tasks for fairer comparison.

  * •

We have produced a typeset dataset 222The data shall be published upon
acceptance alongside the conversion and evaluation code. using public domain
works with permissive licenses.

This paper is structured as follows. In section 2 some definitions for
recurrent topics in the article are presented. Then, section 3 justifies the
necessity for an OMR evaluation framework and debates about how that framework
should be structured. In section 4, our proposed notation format is presented
and described in detail, whereas in section 5 we describe the evaluation
metrics to be employed with it. In section 6 we introduce the proof-of-concept
dataset on typeset scores. Finally, section 7 closes the paper with some final
remarks and future work.

##  2 Terminology

In this section we shall address some specific recurrent terms for the sake of
clarity and cohesiveness of the text. Throughout this paper we shall adhere to
the nomenclature and definitions found in Calvo-Zaragoza et al.’s Calvo-
Zaragoza et al (2021).

By _structured output_ we refer to an output encoding format that allows the
replication of the input score holistically and unambiguously. This is in
contrast to partial outputs such as MIDI, which only encodes note pitch,
duration and velocity and omits any other indication present on the score.

Another relevant point is the definition of an _end-to-end_ OMR model. Modern
day literature employs this term frequently, but it must be noted that it is
used with a slightly different meaning than the term itself actually conveys.
The most widely recognised definition of the OMR pipeline is perhaps that of
the review penned by Rebelo et al. Rebelo et al (2012), which states four
distinct steps:

  1. 1.

Image preprocessing.

  2. 2.

Recognition of Musical Symbols.

  3. 3.

Reconstruction of Musical Information.

  4. 4.

Construction of a Musical Notation model.

Most end-to-end approaches do not actually perform all four steps; rather,
these models stop at step 3 with a notation that encodes most of the score’s
information directly or indirectly, but cannot be directly engraved (sometimes
requiring some additional interpretation before all music semantics can be
successfully produced). Whenever we address end-to-end approaches, we refer to
these. In this work we mostly address _offline_ use cases of OMR – that is,
recognition of raster images of scores. Nevertheless, we believe some of our
ideas are equally applicable in online use cases Calvo-Zaragoza and Oncina
(2014).

##  3 The Necessity for a Common OMR Evaluation Framework

In this section we provide thorough arguments as to why having a comprehensive
and common OMR evaluation system is necessary, while also providing some
insights into what we deem is the preferable approach given the current
circumstances of the field.

###  3.1 OMR Needs a Standardised Output

Most OMR research today does not tackle the problem of converting a model’s
output to a symbolic representation that can be engraved into a proper score.
In their review of the field in 2021, Calvo-Zaragoza et al. Calvo-Zaragoza et
al (2021) go as far as claiming that no research OMR system that they know of
is actually capable of performing such a conversion333There are however
commercial OMR systemsBitteur (2004) that can perform this step., and since
its publication we have only acknowledged one system that can Shishido et al
(2021). One of their main justifications for this is the fact that most
structured music engraving formats are either not mature enough to cover all
possible use cases or simply impractical for OMR tasks. In practice, what this
means is that very few OMR systems spawned in research contexts are employed
by final users. Furthermore, it hinders OMR systems’ evaluation potential, as
omitting music semantics inevitably reduces the level of interpretability of
the models’ outputs.

Going back to the matter of whether notation systems are practical or mature
enough for recognition, there are a few points that need to be made. If the
final goal of recognition is a structured encoding that attempts to replicate
the original score with the highest fidelity, there are currently two
realistic choices: MusicXML Good (2001) and MEI Roland (2002). A point can be
made about LilyPond’s The LilyPond Developement Team (2014) ability to engrave
scores from text written in a fairly succinct and descriptive fashion, but
since the specification of the format is subject to change and the fact that
it under-specifies some aspects of the score for the sake of usability, we do
not think it is realistic to use it as a comprehensive final output. Some
effort has also been devoted into extending Humdrum’s **kern notation to make
it capable of engraving scores uniquely Ríos-Vila et al (2023), but some of
the same limitations as those seen for Lilypond apply.

MusicXML and MEI are somewhat similar in their base design ideas, with the
former being more widely used within music score repository platforms and
engraving software and the latter in libraries and academic-oriented settings.
Perhaps the most obvious difference between the two is the fact that MusicXML
is designed with the idea of enabling MIDI playback out-of-the-box at the cost
of some redundancy, whereas MEI is more focused on musicological and archival
applications. At the end of the day, they both can model the most widely used
subset of CWMN music and they both have limitations derived from their use of
XML and CWMN’s inherent flexibility; it is difficult to express co-depending
symbols as a tree-like hierarchy. Therefore, both choices are probably equal
in value in terms of expressiveness.

Thus, we believe it to be a net positive to make all OMR applications
interoperable with these formats by design. The first advantage is making it
possible to export scores back and forth and therefore increasing the amount
of data available for recognition while making OMR more appealing for the end-
user. The second one is that the set of requirements of an OMR system is
grounded to those of the target application, making it simpler to cooperate
among the community as everybody is talking the same language. Finally, and
thanks to the fact that the targeted output is well defined, unambiguous
metrics for end-to-end score recognition can be defined.

The big question is then how to make it practical for OMR practitioners to
target these (rather complex) formats in a streamlined fashion. Our belief is
that it is best not to use them directly, but rather incorporating a
simplified intermediate format that makes it easy to convert to the structured
outputs and also sets a semantic frame that adjusts well to the necessities of
OMR.

###  3.2 On Computational Music Representations and their Tradeoffs

The most flexible – and perhaps the most logical – computational
representation of written music is most likely a graph, since it allows
expressing $n$-dimensional arbitrary relationships between primitives and
symbols. There exists a very widely known notation format based on this idea
called Music Notation Graph (MuNG) introduced for the MUSCIMA++ Hajič and
Pecina (2017). Some works have indeed succeeded in being able to reconstruct
music structure from these graphs, such as Baró et al.’s Musigraph Baró et al
(2022) or Garrido-Muñoz et al.’s Convolutional Recurrent Neural Networks
Garrido-Munoz et al (2022). Nevertheless, to the best of our knowledge, there
is no straightforward way of converting this graph output back into a
structured encoding. Moreover, the cost of evaluation on graphs is high due to
the complexity of matching graphs together.

At the other end of the spectrum lies the sequential music model, currently
employed in some form or another by most end-to-end OMR approaches Calvo-
Zaragoza et al (2017b); Calvo-Zaragoza and Rizo (2018b); Baró et al (2019);
Alfaro-Contreras and Valero-Mas (2021); Ríos-Vila et al (2022b); Baró et al
(2020); Torras et al (2021); Wen and Zhu (2022). These methods impose a
relationship between the horizontal axis of the image input and the playback
time of the score. However, this forces the insertion of music semantics in
order to properly model specific musical concepts such as unison, as the only
reliable way of aligning individual voices to their playback positions is by
providing their starting times. This is, in fact, how ubiquitous formats such
as MusicXML deal with this ambiguity – a “backup” token specifies that the
internal clock of the engraver must be brought back a number of time
partitions and start producing notes there. Current end-to-end OMR efforts are
mostly restricted to either monophonic or homophonic music scores as a result.

This dichotomy of approaches defines a search space that is still being
explored Alfaro-Contreras and Valero-Mas (2021); Alfaro-Contreras et al
(2022); Baró et al (2019); Hajič and Pecina (2017). Our proposal is to try and
exploit the advantages of both ends: the structural expresiveness of graphs
and the ease of use of sequences. We propose modelling music as a tree
structure, in which small semantic units (primitives) can be composed into
complex high-level constructs (note groups, measures). The tree restriction
makes it simpler to operate with, as the number of relationships is
drastically reduced, relationship semantics are strictly hierarchical (and
thus simpler to model) and its resemblance to the targeted formats makes
conversion a simpler task. Also, imposing an ordering restriction within the
tree as in a sequence makes matching computationally less demanding and allows
modelling the idea of time and position somewhat implicitly.

###  3.3 The Complicated Endeavour of Music and Data

Table 1: Description of annotation formats available for OMR datasets designed for final output production (i.e. they are designed to reconstruct a full score in some form). Columns from left to right: the publication that spawned the dataset, the name it is usually referred to as, what type of music samples it contains and whether it contains bounding box annotations, pixel-mask annotations, notation graph (MuNG) among symbols, string-based output annotations and a final structured output (MusicXML or MEI). Publication |  Dataset Name |  Dataset Type |  Boxes? |  Masks? |  Graph? |  String? |  Struct?
---|---|---|---|---|---|---|---
Hajič and Pecina (2017) |  MUSCIMA++ |  Handwritten Contemporary |  ✓ |  |  ✓ |  |
Tuggener et al (2018, 2020) |  DeepScores |  Typeset |  ✓ |  ✓ |  |  |
Tuggener et al (2023) |  RealScores |  Scanned |  ✓ |  ✓ |  |  |
Shatri and Fazekas (2021) |  DoReMi |  Typeset |  ✓ |  ✓ |  ✓ |  ✓ |  ✓
Parada-Cabaleiro et al (2017) |  SEILS |  Typeset Scanned Mensural |  |  |  |  ✓ |  ✓
Baró et al (2020) |  Baró Synthetic |  Typeset |  |  |  |  ✓ |
Baró et al (2020) |  Pau Llinás |  Handwritten Historical |  |  |  |  ✓ |
Calvo-Zaragoza and Rizo (2018b) |  PRIMuS |  Typeset |  |  |  |  ✓ |  ✓
Calvo-Zaragoza and Rizo (2018a) |  Camera PRIMuS |  Typeset |  |  |  |  ✓ |  ✓

One of the longest-standing and most crippling problems OMR has faced in the
recent years is the lack of reliably annotated data for contexts other than
recognition of typeset scores. Even in that case, the datasets are heavily
opinionated and rarely incorporate structured music sources (see Table 1 for
more detail).

In particular, there is a very noticeable lack of annotated data in CWMN set
within historical contexts – that is, scores written from the 16th century up
to the 20th. As can be seen in Table 1, only Baró et al.’s Baró et al (2020)
Pau Llinás dataset is dedicated to music from this period. Ironically, some of
the composers within it are among the most extensively studied musicians of
all time: Bach, Beethoven, Mozart, Händel or Haydn, to name a few.

Given their importance to the art and craft of music, many efforts have been
made to preserve their work. Some libraries have extensive repositories of
historical music documents from a very broad period of time, some of which
have devoted efforts specifically aimed at democratising access to big names
in music noa (2023, 2008). Some of these original manuscripts are currently
part of the public domain, which also enables them for use within OMR
research.

The main question however is how to best incorporate this data into the field,
as most of the original manuscripts do not have an associated ground truth
that is useful for OMR. The most direct approach would be to collect a
significant corpus of works and manually annotate it comprehensively (per-
pixel symbol annotation, music score transcription, etc.). Nevertheless, this
annotation is both extremely costly and time-consuming, and it entails an
implicit choice of domain; scores that do not abide to the statistical
properties of the collected corpus will still be intractable, and thus the
manual annotation cycle would begin anew.

Therefore, our belief is that the way forward is not just about producing new
hand-annotated datasets, but rather trying to exploit every single bit of data
already publicly available. More specifically, we propose the creation of new
OMR datasets based on existing transcriptions of public domain works. The
goals are twofold: 1) to build a corpus of real scores soft-aligned (that is,
a dataset where the position of measures within the page is known but the
position of each individual object need not be) with existing transcriptions
and 2) to enable the generation of old-looking synthetic scores, an avenue
that is already being explored by Mayer et al. Mayer and Pecina (2021); Mayer
(2022).

The downside of this approach is that producing symbol-level masks becomes
considerably more complicated, which in practical terms shuts down the use of
object detection-based methods in the short term. We nevertheless believe that
this is probably going to be a temporary situation, as enabling recognition of
these scores might potentially open the door for robust implicit segmentation
or alignment systems with which an object-level dataset can be bootstrapped.

When it comes to the problem of alignment of scores, some issues do arise in
the form of conflicting transcriptions and notation adaptations by editors or
scholars. Nevertheless, heuristics can be set in place to detect consistent
mistakes or usual deliberate changes – e.g. changes in the time signature,
changes in the way voices are arranged on the staff, changes in clef and so on
– and then apply the appropriate modifications back on the ground truth
transcription. Those cases where the transcription is wrong are assumed to be
minimal but possible nonetheless, as with any other human-produced ground
truth.

Other roads for the use of non-annotated data currently exist to improve
recognition efforts. In line with recent trends in the literature about
building very large language models, many methods employ unlabelled input
samples as some form of proxy task target. Examples of such techniques in
Computer Vision related tasks include SimCLR Chen et al (2020) or Masked
Autoencoders He et al (2022), which to the best of our knowledge have never
been used in the context of OMR.

###  3.4 Evaluation of OMR Models

Having discussed the benefits of having a common notation format and the
importance of producing a structured output, we now delve into the specifics
of evaluation of OMR systems.

Unfortunately, most metrics used by the OMR community in modern day are fairly
domain-specific and rarely take into account music semantics, a direct
consequence of not targeting a musically-meaningful output format Mengarelli
et al (2019). Authors that address OMR as an object detection problem report
object detection metrics, whereas authors that address OMR as an image-to-
sequence task rely on sequence edit distances. Consequently, there is no
realistic way of comparing them since the semantics of the mistakes of the
system are lost and the underlying notations are different. The few authors
that do report musically-aware metrics restrict themselves to per-note pitch
and/or time accuracy Baró et al (2019); Huang et al (2019).

Moreover, end users for OMR systems are not concerned so much about the
absolute number of mistakes, but rather how costly or realistic it is to fix
them, something that is hard to convey with metrics that treat all errors
equally. A simple example of why this distinction is relevant is the
following: imagine there are two available OMR systems, one that is unreliable
providing correct note pitches but is otherwise very robust and another one
which is very good at determining music semantics but tends to miss structural
primitives. Instead of devoting efforts improving both systems independently,
the outputs of both models can be combined and weighted according to their
strengths to produce better results at essentially zero additional cost. This
is something that has already been done for other similar tasks such as
Handwritten Text Recognition Bertolami and Bunke (2008).

In this direction, there is also debate regarding the specific aspects of
music that should be measured. Hajić jr. Hajič jr. (2018) argues that the best
metric is one that summarises the entire notation system as one single value,
reminiscent of the Symbol Error Rate (SER) metric for strings. We believe
that, while such a metric is a good indicator of overall performance (and is
definitely useful for benchmarking), it must not be considered on its own, as
definite conclusions about the underlying models are very hard to make. Our
belief is that there should be an array of metrics that are oriented at
different aspects of the score that should be logged together, increasing the
coverage of the system.

###  3.5 The Ideal Scope for Recognition

In this final section we discuss the effect of tackling OMR at different
levels of detail.

At the current day there is no pre-defined scope to tackle the problem of OMR.
Therefore researchers can choose whether to implement recognition at measure
Baró et al (2020, 2022), line Calvo-Zaragoza and Rizo (2018a); Baró et al
(2019); Wen and Zhu (2022) or page level Pacha et al (2018); Ríos-Vila et al
(2022a); Zhang et al (2023). While there are practical advantages on each
perspective, there is an arguing point that should be brought to discussion
given the current situation of OMR and Computer Vision as a whole.

Current state-of-the-art object detection and recognition models struggle with
both small Yu et al (2020); Pacha (2021); Baró et al (2022) and scale-variant
symbols Zhang et al (2018). Music scores are quintessential examples of both
phenomena: large symbols (slurs, ties, staves) coexist with very small ones
(dots, fingering numbers), and writers draw symbols at their preferred
relative scale without affecting their meaning – something that is
particularly true for noteheads and stems – while also writing semantically-
distinct symbols that change based on their size – grace notes. Moreover, the
number of objects present in the input image also affects the recognition
performance, a recurrent matter for a significant amount of pieces.

Since addressing visual recognition tasks at smaller scopes helps to obtain
better results, we believe that OMR should first be approached at measure
level, since this is the smallest semantic unit of music. The first immediate
consequence is that layout analysis of music scores becomes a lot more
important, as all successive recognition steps depend on finding the measures
reliably on the page. Nevertheless, we argue that it is objectively a simpler
problem than fully-fledged recognition: staves and bar lines are very
prominent, very ubiquitous and can easily be identified heuristically Fujinaga
(2004); Cardoso et al (2009); Fornés et al (2013); Bui et al (2014); Calvo-
Zaragoza et al (2017a); Egozy and Clester (2022), as opposed to many of the
other musical symbols. Therefore, by composing small semantic units and
propagating shared semantics (key, time signature, clef) whenever needed, a
full notation reconstruction can be obtained quite simply, as measures are
mostly independent.

Tangentially, this idea also helps in the recognition by providing higher dpi
images which are more informative, as there is a substantial part of the score
that is usually plain white space. Some tricks have been developed to try to
minimise these gaps, such as removing all horizontal space between primitives
Zhang et al (2023). This is not something particularly useful with scores with
noisy backgrounds (e.g. scans from old documents with signs of paper
degradation, a recurrent matter within old music scores), but it has been
proven to improve results substantially.

In this section we have provided the core ideas for a common OMR notation
format and evaluation procedure. This shall be the logical foundation upon
which our proposed solution, described in the following section, is built.

##  4 The Music Tree Notation Format

As stated in Introduction and in concordance to the necessities discussed in
Section 3, we have designed a notation format that

  * •

enables comparison of diverse OMR methods on equal grounds,

  * •

normalises the set of music primitives to be recognised,

  * •

simplifies conversion to a final structured format and

  * •

facilitates the usage of non-OMR-specific data.

The base logic for the notation system is introduced in 4.1. The notation
system is described in detail in 4.2.

Figure 2: Example showing a fragment of a measure in which the annotation
format for attributes and staff-modifying elements is shown. Rectangular nodes
represent primitives as tokens and rounded nodes are abstract elements.

###  4.1 Rationale

The basis for our approach to OMR evaluation and (optionally) end-to-end
inference is the Music Tree Notation format (MTN). We believe the final goal
of structured OMR is the reconstruction of the score at the visual domain. The
core idea of this format is therefore to build a notation that exclusively
models relationships between graphical symbols and defers inference of music
semantics until a later stage. Only those high-level music concepts that are
strictly required to reconstruct the score unambiguously are kept if and only
if there is a direct graphical cue that allows straightforward inference.

Evaluation should be possible regardless of the scope of recognition of the
evaluated system – page, line or measure. Nevertheless, a minimal semantic
unit is still required in order to reconstruct music semantics afterwards and
facilitate alignment of predictions and their groundtruth. Exploiting the
assumption evaluation is performed on the visual domain and therefore
application of semantic-altering objects is irrelevant, we propose using the
measure as the minimal unit of music on which to evaluate.

MTN should act as a final target for OMR, through which to convert the score
into any other high-level notation system. This is in order to facilitate OMR
systems from research being deployed into real use-cases as well as enabling
any source of structured data to be used in OMR applications easily.
Therefore, MTN draws heavy inspiration from both MEI and MusicXML, but
“normalises” their structure in such a way that every score can only be
expressed in one way. This also allows implementation many of the already-
studied evaluation requirement ideas from other authors, particularly Hajič
jr. Hajič jr. et al (2016) and Byrd Byrd and Simonsen (2015).

Finally, music notation is very rich and tends to bend its own rules quite
heavily. The goal for this notation and evaluation system is to accommodate a
most significant subset of CWMN, but covering every single exception proves to
be a daunting task. Byrd Byrd and Simonsen (2015) presents some specific cases
such as a spanning slur with seven inflection points that is rather
complicated to model in the logical domain. Therefore, our rationale is that
support for these should not be prioritary. We believe it is better to have
some solid tools on a core subset of music rather than trying to cover every
possible case with highly complex and fragile ones as this makes adoption of
the format much more difficult.

###  4.2 Description of the Format

A graphical representation of a simple measure engraved in MTN can be seen in
Figure 2. The core element of this format is the Musical Primitive, a concept
that is quite widespread in the OMR literature Baró et al (2016, 2020); Calvo-
Zaragoza and Rizo (2018a); Tuggener et al (2018) and can be defined as any of
the independent structural elements that may or may not be combined together
to form a semantic unit in the music score. The set of musical primitives
includes all graphical elements in a score that are self-contained and require
no other symbols to convey meaning (this includes rests, clefs or time
signatures), the set of graphical elements that compose notes (noteheads,
stems, flags, dots, etc.) and other miscellaneous elements such as numbers for
compound time signatures. Every primitive is given a unique work-level
identifier.

These primitives associate together to form more abstract constructs. This is
modelled in MTN using a tree-like structure of higher-order elements
resembling an Abstract Syntax Tree (AST), which defines the set of
dependencies among objects in the score. This idea emulates parsing the
contents of the score using a grammar, enabling the bulk of tools and research
on parsers, parser generators and AST analysis and processing to be used in
the context of music. Furthermore, it is a structure that can be modelled very
easily using widespread exchange formats such as XML or JSON. The structure of
the format may be found in Table 2.

Table 2: Definition of elements within MTN and the overall structure of the format. Each of the lowest levels of the notation contain the various final tokens. For more information, refer to the implementation of the format. Top Level |  Level 1 |  Level 2 |  Definition
---|---|---|---
Attributes |  |  |  Any semantic change the score goes through.
|  Staff |  |  Group of changes occuring on the same staff.
|  |  Clef |  A change of clef in the score.
|  |  TimeSig |  A change of time signature in the score.
|  |  Key |  A change of key in the score.
Barline |  |  |  A measure separator and its attached modifiers.
Direction |  |  |  A single playback directive.
Note Group |  |  |  Group of notes tied together by at leas one beam.
|  Chord |  |  Set of notes in unison attached to the same stem.
|  |  Stem |  Stem direction information and beams or flags attached to it.
|  |  Note |  A notehead and its attached modifiers.
Rest |  |  |  Rest token and its attached modifiers.

There are, however, some elements in music that break the tree-like structure
assumption. These are elements that connect multiple notes together outside
their local note group structure: slurs, ties, parentheses and tuplets, among
others. Both MEI and MusicXML acknowledge this limitation and circumvent it
through the use of identifiers. MTN is no different: it provides a unique
starting and ending token for each side of the object and gives both ends the
same identifier.

In order to emplace musical elements in their corresponding positions, MTN
uses two magnitudes. Firstly, for every token a tuple of two integers denotes
the staff the element belongs to and its position within the staff. The
position is denoted counting the number of steps from the first ledger line
below a staff. For those elements without a specific position (such as rests
or stems), a null value is used. Secondly, for any object immediately below
the class measure, an exact timing value is provided. It is measured in
fractions of a quarter note from the start of the measure itself. This
information is also provided for every chord in a note group even if this
information can be inferred for the sake of simplifying evaluation procedures.

Figure 3: The first few measures on Claude Debussy’s first Arabesque. The
single voice moves along both staves and is played using both hands on a
piano. If one was to separate both staves, it would be impossible to extract
the exact timing where each group of notes is to be played. Another
interesting aspect of this piece is that many editions use implicit triplets,
something that only can be inferred contextually by the fact that eighth notes
are on groups of three.

This musical information is necessary for two reasons. The only visual cue for
aligning elements in a polyphonic setup is that, at some point, addicional
voices have at least one object that is perfectly aligned with one in the main
voice. This is very hard to model cleanly with anything other than a graph.
Moreover, the main voice of a measure may arbitrarily jump from staff to staff
in a system, making timing generally impossible to resolve on a per-staff
basis, as can be seen in Figure 3. A small trick to optimise sequence-based
notation systems is that one only needs timing information for the first
element in a group, as all successive chords’ timings can be inferred from the
note types and tuplets attached to them (or their surrounding elements).

Doubly stemmed notes (such as in the last measure of the Arabesques example in
Figure 3) can be interpreted like two notes playing at the same time.
Therefore, they can be modelled using two distinct groups without needing to
break the tree-like structure.

Finally, to enable unambiguous comparison, a reading order of sorts must be
established. We propose the following ordering criterion:

  * •

By starting time counting from the beginning of the measure.

  * •

By top level class:

    1. 1.

Attributes

    2. 2.

Directions

    3. 3.

Rests

    4. 4.

Note Groups

    5. 5.

Barlines

  * •

By staff position: first objects on upper staves and lower positions within
them.

  * •

In case of Note Groups, by direction of the first stem: first stems looking
upwards.

  * •

For anything else, token alphabetical order. This also guarantees stability of
the notation if new token types are added.

###  4.3 Extensions

The main goal for the notation is to address symbolic-level OMR. Nevertheless,
many practitioners use pipelined architectures where some partial results need
to be annotated (most notably, object bounding boxes). Providing these
annotations with MTN is straightforward: it is a matter of adding an
“annotations” field with each token identifier linked to the desired
information. This also includes some other relevant semantic cues such as
voices, which we deem unnecessary for the task of score reconstruction but
might be useful for some other music information retrieval tasks. A concern
surrounding voice information is that its definition around music engraving
software is more akin to a layer in a graphic design suite; it is used more as
a hacky way of circumventing engraving limitations, making voice information
in files like MusicXML rather arbitrary.

The presence of text in scores can also be treated separately from the rest of
music semantics. Since its interaction with the score is very situational and
depends a lot on the contents of the text itself, it is very difficult to
devise a set of relationships that might be useful for most scores. Therefore,
the only text that is to be represented in MTN are dynamic directives, which
are common and well-defined. For the rest of the text such as tempo
indications or other textual remarks, we believe it is best to append a set of
text boxes in a similar way as bounding boxes are provided.

The format itself is still maturing phase and open to feedback from the
community. We are open to extending it to accommodate the needs of OMR
practitioners as they put it into test.

##  5 Evaluation Metrics

We propose a set of evaluation metrics that both acknowledge the existence of
multiple paradigms for OMR while also setting ways to compare any structured
output equally. These metrics draw inspiration from the currently used Symbol
Error Rate and ideas from Hajič jr. Hajič jr. et al (2016). We have divided
our proposed metrics as tiers depending on the abstraction level they address.

###  5.1 Tier 0: Methodology-Specific Metrics

The first tier is that devoted to specific pipeline metrics before performing
any kind of reconstruction into the MTN format. The idea behind this tier is
that comparison of methodology-specific metrics is still useful, since it
might help identify strengths or shortcomings on certain applications and help
quantify the effectiveness of methods converting into MTN format (which
depending on the OMR methodology might be more or less nuanced).

Since the approaches to OMR are both diverse and unique, it does not make much
sense to overly specify what metrics to employ under this tier, but rather use
those metrics that are already being employed. Some examples of the kinds of
metrics that should be reported here include (but are not restricted to):

  * •

For object detection methods, metrics such as mean average precision, F1
score, average intersection over union and so on.

  * •

For end-to-end string-based methods, metrics such as symbol error rate or
string parseability (whether or not the output string can be interpreted
correctly with whichever grammar describes its underlying language).

###  5.2 Tier 1: Primitive Level

The first set of metrics addresses the presence or absence of terminals within
the MTN string. The main goal is determining the capacity of models of
detecting objects and analysing token co-ocurrence phenomena. These metrics do
not take into account structural matters, making them quick to compute. Given
a set of unique terminals $T$, which is a subset of the full MTN vocabulary
$V$, the multiset of predicted terminals within a sample $P=\left\\{p_{1}\dots
p_{n}:p_{i}\in T\right\\}$ as the multiset of all terminals produced by a
model and the multiset of ground truth terminals within a sample
$G=\left\\{g_{1}\dots g_{m}:g_{i}\in T\right\\}$ as the multiset of all
terminals existing in the groundtruth (both in no particular order), we define
the following metrics:

  * •

Primitive-level precision

$precision=\frac{\|P\cap G\|}{\|P\|}$ (1)

  * •

Primitive-level recall

$recall=\frac{\|P\cap G\|}{\|G\|}$ (2)

Since the underlying datasets are quite unbalanced due to the presence of many
dominating tokens (e.g. noteheads), these metrics are computed per-class for
the entire dataset. In order to produce a single precision and recall measure,
results are aggregated per-class using a weighted average, where the weights
are the relative frequency of each token in the ground truth.

###  5.3 Tier 2: Structural Level

This level takes into account the structure of the produced MTN and compares
it directly with that of the ground truth. A matching from ground truth
elements to those present in the prediction is performed using a tree edit
distance algorithm. In particular, since there is a restriction on the
ordering of sibling labels, the $O\left(n^{3}\right)$ solution from Zhang and
Sasha can be employed Zhang and Shasha (1989).

Given the following operations:

  * •

Substitution: Changing the label of a single node within the tree.

  * •

Deletion: Removing a single node of the tree and setting its children as
siblings.

  * •

Insertion: Adding a new node under a parent one and setting a consecutive
subsequence of its siblings as children.

Given a predicted tree and a ground truth tree whose set of vertices is $G$
and assuming an equal edit cost of 1 for all operations, the Tree Error Rate
(TER) is defined as

$TER=\frac{S+D+I}{\|G\|}$ (3)

where $S$, $D$ and $I$ are the number of substitution, deletion and insertion
operations required to produce the ground truth tree from the predicted tree.
This metric is designed mostly for benchmarking and is defined by analogy to
the ubiquitous Symbol Error Rate (SER).

###  5.4 Tier 3: Semantic Level

This level considers some aspects of music semantics, particularly those
concerned with pitch and time. This tier depends on the matching extracted
from the structural level in order to identify the association between objects
and their ground truth correspondences. Since evaluation has to be possible at
the measure level, we use a graphical definition of pitch, which is the
position of the notehead within the system.

A note $n$ is defined as a 3-tuple
$(p,t,d)\in\mathbb{Z}^{2}\times\mathbb{Q}\times\mathbb{Q}$, where $p$ is a
tuple of the staff the note belongs to and its position within the staff, $t$
is the number of beats from the start of the measure and $d$ is the duration
of the note in number of beats. Rests are considered notes whose pitch is
irrelevant (in practical terms, they can be thought of having a unique shared
number for pitch). Given the set of predicted notes $P$ and the set of ground
truth notes $G$, the matching between $P$ and $G$ is defined as a set of
tuples $M=(n_{p},n_{g})\in P\times G$ such that at most one tuple with either
a specific $n_{p}$ or $n_{g}$ exists.

The Missing Note Rate (MNR) is defined as the ratio of ground truth notes that
do not have a corresponding prediction. More formally,

$MNR=\frac{\|\left\\{n_{g}\in G:(n_{p},n_{g})\notin M,\forall n_{p}\in
P\right\\}\|}{\|G\|}.$ (4)

Similarly, the False Positive Rate (FPR) is defined as the ratio of predicted
notes that do not have a corresponding ground truth note. It is defined by
analogy to MNR.

Pitch Precision (PP) is defined as the number of correctly predicted pitches
w.r.t. the ground truth as defined by the matching $M$. Therefore,

$PP=\frac{\|\left\\{(n_{p},n_{g})\in
M:p_{n_{p}}=p_{n_{g}}\right\\}\|}{\|M\|}.$ (5)

Time Precision (TP) and Duration Precision (DP) are defined analogously.

The Average Pitch Shift (APS) is defined as the average offset in pitch from
the predicted note w.r.t. its corresponding ground truth note as defined by
the matching $M$. Therefore,

$APS=\frac{1}{\|M\|}\sum_{\forall(n_{p},n_{g})\in M}p_{n_{p}}-p_{n_{g}}.$ (6)

Time Average Shift (TAS) and Duration Average Shift (DAS) are defined
analogously. Signedness is kept in order to identify the direction in which
the underlying OMR system tends to move the notes. These should be accompanied
by the corresponding standard deviation.

In order for all of these metrics to be independent of the sequence length,
they should be computed and accumulated for the entire dataset and not
averaged on a by-prediction basis.

There is also the possibility of extending the TER metric with some semantics
in order to ensure better matching and more fine-grained information from it.
Instead of matching the predicted and ground truth trees with their structure
alone, it would be interesting to incorporate pitch into the notehead
elements. Thus, a pitch change can be though of a partial substitution of the
node at a reduced cost of $0.5$ for either the staff, the position on the
staff or the notehead type. If more than one of this properties change, it
should be considered a full substitution.

##  6 The COMREF Dataset

We have developed a dataset using our notation built on transcriptions of
public domain works as a proof of concept of the notation format. In
particular, we have used the OpenScore project’s transcriptions of widely
known works such as The Art of the Fugue by J.S. Bach or the Planets by Gustav
Holst, among others. We have also incorporated the Lieder Corpus Gotham and
Jonas (2022) and the String Quartet corpus str (2023). All these scores are
engraved in MusicXML, but we plan on supporting MEI as a conversion source at
some point in the future.

###  6.1 Images

In summary, the dataset is produced by processing of 896 individual works into
images at the measure level (including all staves that belong to it), to
produce a total of $439.972$ images. After verification, $3.260$ images are
removed due to noise in the annotations, totalling $436.752$ images after
cleanup.

Figure 4: The pipeline through which the COMREF dataset has been generated.

The process through which the dataset was produced is summarised in Figure 4.
Scores are engraved through Verovio into page-level SVG files. Using the
hierarchical structure within the SVG and exploiting the optional identifier
information Verovio can be instructed to attach, we employ a splitter script
that finds bounding boxes for every measure and engraves them individually. It
also finds what measures lie at the beginning of a line in order to properly
add this information on the notation. The bounding boxes for all measures are
cropped at the next staff vertically and a fixed amount of pixels
horizontally.

Once the images are produced, the converter uses the MusicXML file and
produces the MTN notation. In order to ensure all images have their
corresponding ground truth, we use a cleaning script that finds matching
identifiers for images in the MTN files. It also checks for outliers in case
there are blatant mistakes in the notation. Although we have taken precautions
to minimise the number of errors, there are a few images with objects far from
the staff, either temporally or graphically. We remove these outliers
heuristically to ensure the quality of the data.

###  6.2 Ground Truth

The dataset incorporates 91 different classes, which are shown alongside their
frequencies in Table 3. A relevant aspect of this dataset is that it is quite
unbalanced, with roughly 70% of the elements pertaining to the 4 first
classes.

Table 3: Tokens and their frequencies in the COMREF dataset. Token | Count | Token | Count | Token | Count
---|---|---|---|---|---
notehead_black | 1986948 | rest_breve | 18103 | notehead_white_cue | 738
beam | 1517194 | clef_C | 17664 | rest_whole | 681
stem_down | 1018045 | notehead_black_grace | 13086 | regular | 529
stem_up | 803884 | tenuto | 11444 | sfz | 462
flag | 244232 | strong_accent | 9414 | rf | 173
accidental_sharp | 226428 | pp | 8484 | mordent | 136
accidental_flat | 211192 | rest_32nd | 8381 | ffff | 130
notehead_white | 197408 | ff | 7449 | sfp | 129
staccato | 171070 | sf | 7282 | notehead_breve | 125
slur_stop | 168855 | light_light | 7230 | sffz | 105
slur_start | 168853 | notehead_black_cue | 6889 | clef_G_oct1 | 102
dot | 153128 | rest_maxima | 6171 | turn | 83
rest_eighth | 126179 | mf | 5748 | caesura | 75
tied_start | 101092 | fermata | 5330 | slide_start | 72
tied_stop | 101029 | light_heavy | 3294 | slide_stop | 71
accidental_natural | 99920 | rest_64th | 3248 | accidental_natural_sharp | 51
rest_quarter | 94522 | trill_mark | 2589 | rfz | 43
clef_G | 75140 | timesig_common | 2366 | segno | 31
clef_F | 46386 | accidental_double_sharp | 1990 | pppp | 15
tuplet_stop | 43781 | fz | 1700 | glissando_stop | 14
tuplet_start | 43650 | clef_G_oct-1 | 1295 | glissando_start | 10
rest_long | 43610 | staccatissimo | 1268 | clef_F_oct1 | 9
wedge_stop | 38286 | mp | 1245 | notehead_black_grace_cue | 8
accent | 27450 | wavy_line | 1107 | coda | 7
arpeggiate | 22102 | fff | 987 | schleifer | 4
rest_half | 21554 | accidental_flat_flat | 969 | sfpp | 3
rest_16th | 21452 | fp | 913 | accidental_natural_flat | 2
p | 21103 | timesig_cut | 890 | pppppp | 1
wedge_crescendo | 20115 | ppp | 862 | ppppp | 1
f | 19771 | clef_percussion | 774 |  |
wedge_diminuendo | 18233 | clef_F_oct-1 | 760 | Total | 8015354

##  7 Conclusions

In this paper we have argued for the implementation of a Common Optical Music
Recognition Evaluation Framework through the instauration of a notation format
in which score reconstruction can be evaluated fairly an unambiguously. Our
proposed reification of this idea is the MTN format, which draws heavy
inspiration from existing formats and adapts many ideas already present in the
field while also being quite expressive and general. Its main idea is
exploiting the expresiveness of graphs while keeping the ordering properties
of sequences, thanks to which evaluation and inference are better-defined and
less computationally demanding. Of course, CWMN is a tremendously complex
notation system which has been optimised and streamlined for hundreds of
years. It is highly likely that MTN (or any other computational representation
of music for that matter) cannot model every possible music score that has
been written. Nevertheless, we believe the subset of music that can be
expressed in this format is large enough to be useful for the community of
OMR.

In this work we have also presented a concrete implementation of a set of
metrics for OMR practitioners with the hopes of bringing together the
community to finally speak the same language; a lingua franca thanks to which
research can be shared and compared fairly and easily. We also hope this might
lower the barrier of entry and bring some new interest on the field.

The work that lies ahead now is bulding a corpus of music that can be employed
with this format into a benchmark for CWMN recognition, both in typeset and
handwritten domains. For typeset scores, building a corpus in MTN should be as
straightforward as compiling a comprehensive set of scores in MusicXML and
engraving them. For handwritten music, the million dollar question now lies in
how to reliably align MTN to the source material and where to find good
transcriptions, which shall be the focus of our next efforts.

Supplementary information LINKS TO THE DATA AND CODE UPON ACCEPTANCE.
Acknowledgments This work has been partially supported by the Spanish projects
PID2021-126808OB-I00 (GRAIL) and CNS2022-135947 (DOLORES), as well as the
AGAUR Joan Oró FI grant 2023 FI-1-00324. The authors acknowledge the support
of the Generalitat de Catalunya CERCA Program to CVC’s general activities.

## Declarations

The authors have no conflicts of interest to declare that are relevant to the
content of this article.

## References

  *   * noa (2008) (2008) Bach Digital. URL https://www.bach-digital.de/content/index.xed, accessed: 2023-03-01
  * noa (2023) (2023) Beethoven-Haus Bonn. URL https://www.beethoven.de/en/archive/list, accessed: 2023-03-01
  * str (2023) (2023) String quartet corpus. URL https://github.com/OpenScore/StringQuartets, accessed: 2023-10-10
  * Alfaro-Contreras and Valero-Mas (2021) Alfaro-Contreras M, Valero-Mas JJ (2021) Exploiting the two-dimensional nature of agnostic music notation for neural optical music recognition. Applied Sciences 11(8):3621. Publisher: MDPI
  * Alfaro-Contreras et al (2022) Alfaro-Contreras M, Ríos-Vila A, Valero-Mas JJ, et al (2022) Decoupling music notation to improve end-to-end Optical Music Recognition. Pattern Recognition Letters 158:157–163. 10.1016/j.patrec.2022.04.032, URL https://www.sciencedirect.com/science/article/pii/S0167865522001428
  * Baró et al (2016) Baró A, Riba P, Fornés A (2016) Towards the Recognition of Compound Music Notes in Handwritten Music Scores. In: 2016 15th International Conference on Frontiers in Handwriting Recognition (ICFHR), pp 465–470, 10.1109/ICFHR.2016.0092, iSSN: 2167-6445
  * Baró et al (2019) Baró A, Riba P, Calvo-Zaragoza J, et al (2019) From Optical Music Recognition to Handwritten Music Recognition: A baseline. Pattern Recognition Letters 123:1–8. 10.1016/j.patrec.2019.02.029, URL https://linkinghub.elsevier.com/retrieve/pii/S0167865518303386
  * Baró et al (2020) Baró A, Badal C, Fornés A (2020) Handwritten Historical Music Recognition by Sequence-to-Sequence with Attention Mechanism. In: 2020 17th International Conference on Frontiers in Handwriting Recognition (ICFHR), pp 205–210, 10.1109/ICFHR2020.2020.00046
  * Baró et al (2022) Baró A, Riba P, Fornés A (2022) Musigraph: Optical Music Recognition Through Object Detection and Graph Neural Network. In: Porwal U, Fornés A, Shafait F (eds) Frontiers in Handwriting Recognition. Springer International Publishing, Cham, Lecture Notes in Computer Science, pp 171–184, 10.1007/978-3-031-21648-0_12
  * Bertolami and Bunke (2008) Bertolami R, Bunke H (2008) Hidden Markov model-based ensemble methods for offline handwritten text line recognition. Pattern Recognition 41(11):3452–3460. 10.1016/j.patcog.2008.04.003, URL https://www.sciencedirect.com/science/article/pii/S0031320308001349
  * Bitteur (2004) Bitteur H (2004) Audiveris. URL https://github.com/audiveris
  * Bui et al (2014) Bui HN, Na IS, Kim SH (2014) Staff Line Removal Using Line Adjacency Graph and Staff Line Skeleton for Camera-Based Printed Music Scores. In: 22nd International Conference on Pattern Recognition, pp 2787–2789, 10.1109/ICPR.2014.480, iSSN: 1051-4651
  * Byrd and Simonsen (2015) Byrd D, Simonsen JG (2015) Towards a Standard Testbed for Optical Music Recognition: Definitions, Metrics, and Page Images. Journal of New Music Research 44(3):169–195. 10.1080/09298215.2015.1045424, URL http://www.tandfonline.com/doi/full/10.1080/09298215.2015.1045424
  * Byrd and Isaacson (2003) Byrd DA, Isaacson EJ (2003) A Music Representation Requirement Specification for Academia. Computer Music Journal 27(4):43–57. URL https://muse.jhu.edu/pub/6/article/49604, publisher: The MIT Press
  * Calvo-Zaragoza and Oncina (2014) Calvo-Zaragoza J, Oncina J (2014) Recognition of Pen-Based Music Notation: The HOMUS Dataset. In: 22nd International Conference on Pattern Recognition. Institute of Electrical & Electronics Engineers (IEEE), pp 3038–3043, 10.1109/ICPR.2014.524, iSSN: 1051-4651
  * Calvo-Zaragoza and Rizo (2018a) Calvo-Zaragoza J, Rizo D (2018a) Camera-PrIMuS: Neural End-to-End Optical Music Recognition on Realistic Monophonic Scores. In: 19th International Society for Music Information Retrieval Conference, Paris, France, pp 248–255, URL http://ismir2018.ircam.fr/doc/pdfs/33_Paper.pdf
  * Calvo-Zaragoza and Rizo (2018b) Calvo-Zaragoza J, Rizo D (2018b) End-to-End Neural Optical Music Recognition of Monophonic Scores. Applied Sciences 8(4):606. 10.3390/app8040606, URL https://www.mdpi.com/2076-3417/8/4/606, number: 4 Publisher: Multidisciplinary Digital Publishing Institute
  * Calvo-Zaragoza et al (2017a) Calvo-Zaragoza J, Pertusa A, Oncina J (2017a) Staff-line detection and removal using a convolutional neural network. Machine Vision and Applications pp 1–10. 10.1007/s00138-017-0844-4
  * Calvo-Zaragoza et al (2017b) Calvo-Zaragoza J, Valero-Mas JJ, Pertusa A (2017b) End-to-End Optical Music Recognition Using Neural Networks. Suzhou, China, 10.5281/zenodo.1418333, URL https://zenodo.org/record/1418333, iSBN: 9789811151798 Pages: 472-477 Publisher: ISMIR Publication Title: Proceedings of the 18th International Society for Music Information Retrieval Conference
  * Calvo-Zaragoza et al (2021) Calvo-Zaragoza J, Hajič Jr. J, Pacha A (2021) Understanding Optical Music Recognition. ACM Comput Surv 53(4):1–35. 10.1145/3397499, URL https://dl.acm.org/doi/10.1145/3397499
  * Cardoso et al (2009) Cardoso JdS, Capela A, Rebelo A, et al (2009) Staff Detection with Stable Paths. IEEE Transactions on Pattern Analysis and Machine Intelligence 31(6):1134–1139. 10.1109/TPAMI.2009.34, publisher: Institute of Electrical & Electronics Engineers (IEEE)
  * Chen et al (2020) Chen T, Kornblith S, Norouzi M, et al (2020) A Simple Framework for Contrastive Learning of Visual Representations. In: Proceedings of the 37th International Conference on Machine Learning. PMLR, pp 1597–1607, URL https://proceedings.mlr.press/v119/chen20j.html, iSSN: 2640-3498
  * Egozy and Clester (2022) Egozy E, Clester I (2022) Computer-Assisted Measure Detection in a Music Score-Following Application. In: Calvo-Zaragoza J, Pacha A, Shatri E (eds) Proceedings of the 4th International Workshop on Reading Music Systems, Online, pp 33–36, 10.48550/arXiv.2211.13285, URL https://sites.google.com/view/worms2022/proceedings
  * Fornés et al (2013) Fornés A, Dutta A, Gordo A, et al (2013) The 2012 Music Scores Competitions: Staff Removal and Writer Identification. In: Kwon YB, Ogier JM (eds) Graphics Recognition. New Trends and Challenges. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 173–186, 10.1007/978-3-642-36824-0_17
  * Fujinaga (2004) Fujinaga I (2004) Staff detection and removal. In: Visual Perception of Music Notation: On-Line and Off Line Recognition. IGI Global, p 1–39, 10.4018/978-1-59140-298-5.ch001
  * Garrido-Munoz et al (2022) Garrido-Munoz C, Rios-Vila A, Calvo-Zaragoza J (2022) A holistic approach for image-to-graph: application to optical music recognition. IJDAR 10.1007/s10032-022-00417-4, URL https://doi.org/10.1007/s10032-022-00417-4
  * Good (2001) Good M (2001) MusicXML: An Internet-Friendly Format for Sheet Music. Tech. rep., Recordare LLC, URL https://pdfs.semanticscholar.org/5617/972667ff794da79a4cbb6b985e85f8487ddd.pdf
  * Gotham and Jonas (2022) Gotham MRH, Jonas P (2022) The OpenScore Lieder Corpus. In: Münnich S, Rizo D (eds) Music Encoding Conference Proceedings 2021. Humanities Commons, pp 131–136, 10.17613/1my2-dm23
  * Hajič and Pecina (2017) Hajič J, Pecina P (2017) The MUSCIMA++ Dataset for Handwritten Optical Music Recognition. In: 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR), pp 39–46, 10.1109/ICDAR.2017.16, iSSN: 2379-2140
  * Hajič jr. (2018) Hajič jr. J (2018) A Case for Intrinsic Evaluation of Optical Music Recognition. In: Calvo-Zaragoza J, Hajič jr. J, Pacha A (eds) 1st International Workshop on Reading Music Systems, Paris, France, pp 15–16, URL https://sites.google.com/view/worms2018/proceedings
  * Hajič jr. et al (2016) Hajič jr. J, Novotný J, Pecina P, et al (2016) Further Steps towards a Standard Testbed for Optical Music Recognition. In: Mandel M, Devaney J, Turnbull D, et al (eds) 17th International Society for Music Information Retrieval Conference. New York University, New York, USA, pp 157–163, URL https://wp.nyu.edu/ismir2016/event/proceedings/, backup Publisher: New York University
  * He et al (2022) He K, Chen X, Xie S, et al (2022) Masked Autoencoders Are Scalable Vision Learners. pp 16,000–16,009, URL https://openaccess.thecvf.com/content/CVPR2022/html/He_Masked_Autoencoders_Are_Scalable_Vision_Learners_CVPR_2022_paper.html
  * Huang et al (2019) Huang Z, Jia X, Guo Y (2019) State-of-the-Art Model for Music Object Recognition with Deep Learning. Applied Sciences 9(13):2645–2665. 10.3390/app9132645, URL https://www.mdpi.com/2076-3417/9/13/2645
  * Mayer (2022) Mayer J (2022) Semi-supervised learning in Optical Music Recognition. Master’s thesis, URL https://dspace.cuni.cz/handle/20.500.11956/173547, accepted: 2022-06-28T10:48:03Z Publisher: Univerzita Karlova, Matematicko-fyzikální fakulta
  * Mayer and Pecina (2021) Mayer J, Pecina P (2021) Synthesizing Training Data for Handwritten Music Recognition. In: Lladós J, Lopresti D, Uchida S (eds) Document Analysis and Recognition – ICDAR 2021, vol 12823. Springer International Publishing, Cham, pp 626–641, 10.1007/978-3-030-86334-0_41, URL https://link.springer.com/10.1007/978-3-030-86334-0_41, series Title: Lecture Notes in Computer Science
  * Mengarelli et al (2019) Mengarelli L, Kostiuk B, Vitório JG, et al (2019) OMR metrics and evaluation: a systematic review. Multimedia Tools and Applications 10.1007/s11042-019-08200-0
  * Pacha (2017) Pacha A (2017) The OMR Datasets Project. URL https://apacha.github.io/OMR-Datasets
  * Pacha (2018) Pacha A (2018) Advancing OMR as a Community: Best Practices for Reproducible Research. In: Calvo-Zaragoza J, Hajič jr. J, Pacha A (eds) 1st International Workshop on Reading Music Systems, Paris, France, pp 19–20, URL https://sites.google.com/view/worms2018/proceedings
  * Pacha (2021) Pacha A (2021) The Challenge of Reconstructing Digits in Music Scores. In: Calvo-Zaragoza J, Pacha A (eds) Proceedings of the 3rd International Workshop on Reading Music Systems, Alicante, Spain, pp 4–7, URL https://sites.google.com/view/worms2021/proceedings
  * Pacha et al (2018) Pacha A, Hajič jr. J, Calvo-Zaragoza J (2018) A Baseline for General Music Object Detection with Deep Learning. Applied Sciences 8(9):1488–1508. 10.3390/app8091488, URL http://www.mdpi.com/2076-3417/8/9/1488
  * Parada-Cabaleiro et al (2017) Parada-Cabaleiro E, Batliner A, Baird A, et al (2017) The SEILS Dataset: Symbolically Encoded Scores in Modern-Early Notation for Computational Musicology. In: 18th International Society for Music Information Retrieval Conference, Suzhou, China, URL https://ismir2017.smcnus.org/wp-content/uploads/2017/10/14_Paper.pdf
  * Rebelo et al (2012) Rebelo A, Fujinaga I, Paszkiewicz F, et al (2012) Optical music recognition: state-of-the-art and open issues. Int J Multimed Info Retr 1(3):173–190. 10.1007/s13735-012-0004-6, URL http://link.springer.com/10.1007/s13735-012-0004-6
  * Roland (2002) Roland P (2002) The music encoding initiative (MEI). In: 1st International Conference on Musical Applications Using XML, pp 55–59, URL https://pdfs.semanticscholar.org/7fc4/16754b0508837dde8b505b3fd4dc517c7292.pdf
  * Ríos-Vila et al (2022a) Ríos-Vila A, Iñesta JM, Calvo-Zaragoza J (2022a) End-To-End Full-Page Optical Music Recognition of Monophonic Documents via Score Unfolding. In: Calvo-Zaragoza J, Pacha A, Shatri E (eds) Proceedings of the 4th International Workshop on Reading Music Systems, Online, pp 20–24, 10.48550/arXiv.2211.13285, URL https://sites.google.com/view/worms2022/proceedings
  * Ríos-Vila et al (2022b) Ríos-Vila A, Iñesta JM, Calvo-Zaragoza J (2022b) On the Use of Transformers for End-to-End Optical Music Recognition. In: Pinho AJ, Georgieva P, Teixeira LF, et al (eds) Pattern Recognition and Image Analysis. Springer International Publishing, Cham, Lecture Notes in Computer Science, pp 470–481, 10.1007/978-3-031-04881-4_37
  * Ríos-Vila et al (2023) Ríos-Vila A, Rizo D, Iñesta JM, et al (2023) End-to-end optical music recognition for pianoform sheet music. International Journal on Document Analysis and Recognition (IJDAR) 26(3):347–362. 10.1007/s10032-023-00432-z, URL https://doi.org/10.1007/s10032-023-00432-z
  * Shatri and Fazekas (2021) Shatri E, Fazekas G (2021) DoReMi: First glance at a universal OMR dataset. In: Calvo-Zaragoza J, Pacha A (eds) Proceedings of the 3rd International Workshop on Reading Music Systems, Alicante, Spain, pp 43–49, URL https://sites.google.com/view/worms2021/proceedings
  * Shishido et al (2021) Shishido T, Fati F, Tokushige D, et al (2021) Listen to Your Favorite Melodies with img2Mxml, Producing MusicXML from Sheet Music Image by Measure-based Multimodal Deep Learning-driven Assembly. URL http://arxiv.org/abs/2106.12037, arXiv:2106.12037 [cs]
  * The LilyPond Developement Team (2014) The LilyPond Developement Team (2014) LilyPond - Essay on automated music engraving. URL http://www.lilypond.org/
  * Torras et al (2021) Torras P, Baró A, Kang L, et al (2021) On the Integration of Language Models into Sequence to Sequence Architectures for Handwritten Music Recognition. Online, 10.5281/zenodo.5624451, URL https://zenodo.org/record/5624451, pages: 690-696 Publication Title: Proceedings of the 22nd International Society for Music Information Retrieval Conference Publisher: ISMIR
  * Tuggener et al (2018) Tuggener L, Elezi I, Schmidhuber J, et al (2018) DeepScores - A Dataset for Segmentation, Detection and Classification of Tiny Objects. In: 24th International Conference on Pattern Recognition. ZHAW, Beijing, China, 10.21256/zhaw-4255, URL https://arxiv.org/abs/1804.00525
  * Tuggener et al (2020) Tuggener L, Satyawan YP, Pacha A, et al (2020) The DeepScoresV2 Dataset and Benchmark for Music Object Detection. In: Proceedings of the 25th International Conference on Pattern Recognition, Milan, Italy, 10.21256/zhaw-20647
  * Tuggener et al (2023) Tuggener L, Emberger R, Ghosh A, et al (2023) Real world music object recognition. Transactions of the International Society for Music Information Retrieval 10.21256/zhaw-28644, URL https://digitalcollection.zhaw.ch/handle/11475/28644, accepted: 2023-09-08T13:52:37Z Publisher: Ubiquity Press
  * Wen and Zhu (2022) Wen C, Zhu L (2022) A Sequence-to-Sequence Framework Based on Transformer With Masked Language Model for Optical Music Recognition. IEEE Access 10:118,243–118,252. 10.1109/ACCESS.2022.3220878, conference Name: IEEE Access
  * Yu et al (2020) Yu X, Han Z, Gong Y, et al (2020) The 1st Tiny Object Detection Challenge: Methods and Results. In: Bartoli A, Fusiello A (eds) Computer Vision – ECCV 2020 Workshops. Springer International Publishing, Cham, Lecture Notes in Computer Science, pp 315–323, 10.1007/978-3-030-68238-5_23
  * Zhang et al (2018) Zhang J, Du J, Dai L (2018) Multi-Scale Attention with Dense Encoder for Handwritten Mathematical Expression Recognition. In: 2018 24th International Conference on Pattern Recognition (ICPR), pp 2245–2250, 10.1109/ICPR.2018.8546031, iSSN: 1051-4651
  * Zhang and Shasha (1989) Zhang K, Shasha D (1989) Simple Fast Algorithms for the Editing Distance between Trees and Related Problems. SIAM J Comput 18(6):1245–1262. 10.1137/0218082, URL https://epubs.siam.org/doi/abs/10.1137/0218082, publisher: Society for Industrial and Applied Mathematics
  * Zhang et al (2023) Zhang Y, Huang Z, Zhang Y, et al (2023) A detector for page-level handwritten music object recognition based on deep learning. Neural Comput & Applic 10.1007/s00521-023-08216-6, URL https://doi.org/10.1007/s00521-023-08216-6


# Whitney Numbers of Partial Dowling Lattices

Thomas Zaslavsky  Department of Mathematics and Statistics, Binghamton
University (SUNY), Binghamton, NY 13902-6000, U.S.A.
<EMAIL_ADDRESS>
###### Abstract.

A weight-2 Dowling lattice $Q_{n}(\mathfrak{G})$ is the geometric lattice of
partial $\mathfrak{G}$-partitions of a finite set, where $\mathfrak{G}$ is a
finite group; alternatively, it is the lattice of flats of the frame matroid
of a full $\mathfrak{G}$-expansion of a complete graph,
$\mathfrak{G}K_{n}^{(V)}$. A higher-weight Dowling lattice of weight $k$ is
the geometric lattice of all vectors of weight $\leq k$ in the vector space
$\mathbb{F}_{q}^{n}$ of a finite field of order $q$. Ravagnani suggested and
partially proved that the Whitney numbers of the first kind of
$Q_{n}(\mathfrak{G})$ and higher-weight Dowling lattices are polynomial
functions of $|\mathfrak{G}|$. We give a simple proof for weight-2 Dowling
lattices and their generalization to the lattice of flats of the frame matroid
of a $\mathfrak{G}$-expansion of an arbitrary graph and its combinatorial
analog the full biased expansion. We determine the degree and coefficients of
the polynomials.

###### Key words and phrases:

Matroid, Whitney number, gain graph, Dowling lattice, group expansion gain
graph

###### 2010 Mathematics Subject Classification:

Primary 05B35; Secondary 05C22, 05C31

The famous Dowling lattices of a group, or more precisely their matroids, are
one of the two fundamental types of matroid in the classification of Kahn and
Kung [2]. We show that their Whitney numbers of the first kind, which are the
coefficients of their characteristic polynomials, are themselves polynomials
in the order of the group. This is obvious from Dowling’s own formulas, but we
notice that this property generalizes considerably, to what we might call
partial Dowling lattices.

My attention was drawn to this property by Ravagani’s study [3] of the same
property of the higher-weight Dowling lattices, which he calls
$\mathcal{H}(n,q,d)$. Such a lattice is the lattice of flats of the matroid of
all vectors in $\mathbb{F}_{q}^{n}$ with at most $d$ nonzero coordinates. The
case of weight $d=1$ gives a free matroid but weight $d=2$ is more complicated
(and as Dowling showed it generalizes to arbitrary groups [1]) and higher-
weight Dowling lattices have resisted analysis, in particular of their
important characteristic polynomials which have implications for linear coding
theory. Ravagnani suggested that the coefficients of these polynomials, which
were dubbed Whitney numbers of the first kind by G.-C. Rota, are polynomial
functions of $q$ and obtained partial results. Stimulated by this work I
looked at a different generalization, still in the realm of weight 2, and
obtained conclusions that are fundamentally simple but with some complicated
details.

##  1\. Gains and Dowlings

We begin by introducing Dowling’s lattices $Q_{n}(\mathfrak{G})$ of a group
[1] by way of their matroids.

A _gain graph_ $\Phi=(\Gamma_{\Phi},\phi)$ consists of a graph
$\Gamma_{\Phi}=(V,E)$ and a _gain mapping_ $\phi$ from oriented edges to a
group $\mathfrak{G}$. That is, the gain $\phi(e)$ depends on the orientation
of the edge so that reversing the orientation inverts the gain, which we
express in a formula as $\phi(e^{-1})=\phi(e)^{-1}$, where $e$ is an oriented
edge and $e^{-1}$ denotes the opposite orientation. A particular kind of gain
graph is the $\mathfrak{G}$-expansion of a graph $\Gamma$, written
$\mathfrak{G}{\cdot}\Gamma$, whose vertex set is $V=V(\Gamma)$ and which has
an edge $ge$ with every possible gain $g\in\mathfrak{G}$ for each edge $e\in
E(\Gamma)$. A _half edge_ is an edge with only one endpoint; we may add to the
$\mathfrak{G}$-expansion a half edge at each vertex of a subset $X\subseteq
V$, giving the _partially filled_ $\mathfrak{G}$-expansion
$\mathfrak{G}{\cdot}\Gamma^{(X)}$. In particular, when $X=V$ we call the
result the _full_ $\mathfrak{G}$-expansion of $\Gamma$.

The associated _frame matroid_ $\mathbf{F}(\Phi)$ of a gain graph $\Phi$ (see
[6, Section 2]) is defined on the edge set $E(\Phi)$ with circuits of the
following three kinds C1–C3. The gain of a circle (i.e., a “cycle” or
“polygon”) $C=e_{1}\cdots e_{l}$ is $\phi(C)=\phi(e_{1})\cdots\phi(e_{l})$;
this is sufficiently well defined because we only care whether the gain is the
neutral element or not. If the gain is the neutral element, $C$ is called
_neutral_.

  1. C1.

A neutral circle.

  2. C2.

Two disjoint non-neutral circles together with a minimal connecting path, or
two distinct non-neutral circles with exactly one common vertex. Either or
both circles may be replaced by a half edge in this type of circuit.

  3. C3.

A theta subgraph whose three circles are not neutral.

A subgraph or edge set is _balanced_ if every circle is neutral and there are
no half edges. The rank of an edge set $S$ is

$\operatorname{rk}(S)=|V|-b(S),$

where $b(S)$ denotes the number of balanced components of the spanning
subgraph $(V,S)$. An edge set is _closed_ , or a _flat_ of $\mathbf{F}(\Phi)$,
if it is maximal with its rank, i.e., adding any edge increases the rank.

The usual cycle matroid of $\Gamma$ is the frame matroid of the gain graph
consisting of the graph $\Gamma$ with identity gains from the trivial group.
We write $\mathbf{F}(\Gamma)$ for this matroid.

The _Dowling matroid_ of rank $n$ of a group $\mathfrak{G}$ is
$\mathbf{F}(\mathfrak{G}K_{n}^{(V)})$ and the _Dowling lattice_
$Q_{n}(\mathfrak{G})$ is the lattice of flats of this matroid [7, Examples
3.6, 5.6]. Dowling originally considered $Q_{n}(\mathfrak{G})$ as the lattice
of the matroid formed by the weight 1 and 2 vectors in $\mathbb{F}_{q}^{n}$,
that is, $\mathcal{H}(n,q,2)$, in which context the group $\mathfrak{G}$ is
the multiplicative group $\mathbb{F}_{q}^{\times}$ of order $q-1$. (Both $q$
and $q-1$ appear naturally in Ravagnani’s formulas for Whitney numbers of
higher-weight Dowling lattices. Does this suggest that both the additive and
multiplicative groups of the field play a role in determining the matroid?)

##  2\. Chromatics and characteristics

A gain graph has a chromatic polynomial $\chi_{\Phi}(\lambda)$ (see [7,
Section 3]), one of whose definitions is

$\chi_{\Phi}(\lambda):=\sum_{S\subseteq E}(-1)^{|S|}\lambda^{b(S)}.$

We state the essential formulas. We assume $\Phi$ has order $n$ and write
$\gamma=|\mathfrak{G}|$. The chromatic polynomial is monic of degree $n$. If
$b(\Phi)=0$ (as is the case for group expansions when $\gamma>1$ or $X=V$),
the chromatic polynomial equals the characteristic polynomial
$p_{\mathbf{F}(\Phi)}(\lambda)$ of the matroid; in general,

$\chi_{\Phi}(\lambda)=\lambda^{b(\Phi)}p_{\mathbf{F}(\Phi)}(\lambda)$

by [7, Theorem 5.1]. Thus, the two polynomials have the same coefficients
aside from a possible displacement. From the definition, obviously

(1) $\chi_{\Phi}(\lambda)=\lambda^{n}\text{ if }E(\Phi)=\varnothing.$

A useful chromatic formula is the product rule,

(2)
$\chi_{\Phi_{1}\cup\Phi_{2}}(\lambda)=\chi_{\Phi_{1}}(\lambda)\chi_{\Phi_{2}}(\lambda)$

if $\Phi_{1}$ and $\Phi_{2}$ are disjoint gain graphs. The usual chromatic
polynomial of a graph is the chromatic polynomial of the trivial group
expansion: $\chi_{\Gamma}(\lambda)=\chi_{\mathbf{1}{\cdot}\Gamma}(\lambda)$,
where $\mathbf{1}$ denotes the trivial group.

We need the basic formula for chromatic polynomials of full group expansions,
which is a reduction to ordinary graphs [7, Examples 3.6 and 6.6]:

(3)
$\chi_{\mathfrak{G}{\cdot}\Gamma^{(V)}}(\lambda)=\gamma^{n}\chi_{\Gamma}\Big{(}\frac{\lambda-1}{\gamma}\Big{)}.$

We note that this polynomial is independent of the group structure. One of
Dowling’s main discoveries was (in slightly different language) this simple
formula for $\Gamma=K_{n}$, in contrast to the generally hard problem of
computing characteristic polynomials of matroids.

Formula (3) and the fact that
$\chi_{\mathfrak{G}{\cdot}\Gamma^{(V)}}(\lambda)$ is a polynomial of degree
$n$ clearly imply that the coefficients are polynomials in $\gamma$. We want
more detailed information.

##  3\. Whitneys

The characteristic polynomial of a matroid $M$ has the form

$p_{M}(\lambda)=\sum_{i=0}^{\operatorname{rk}M}w_{i}(M)\lambda^{\operatorname{rk}M-i},$

the coefficients $w_{i}(M)$ being the _Whitney numbers of $M$ of the first
kind_. The chromatic polynomial of $\Phi$ therefore has the form

$\chi_{\Phi}(\lambda)=\sum_{i=0}^{n}w_{i}(\Phi)\lambda^{n-i},$

where $w_{i}(\Phi)$ is defined as $w_{i}(\mathbf{F}(\Phi))$; similarly,
$w_{i}(\Gamma)$ is defined as $w_{i}(\mathbf{F}(\Gamma))$. The Whitney numbers
of a matroid are nonzero, alternate in sign, and begin with $w_{0}=1$ and
$-w_{1}=|E(M)|$ (the number of atoms of $M$) [4], so the same is true for
those of a gain graph; but note that $w_{i}(\Phi)=0$ for
$i>\operatorname{rk}\mathbf{F}(\Phi)=n-b(\Phi)$. Similarly, the Whitney
numbers $w_{i}(\Gamma)$ are nonzero for $0\leq i\leq n-c$ and 0 otherwise,
where $c$ denotes the number of components of $\Gamma$ and
$n-c=\operatorname{rk}\mathbf{F}(\Gamma)$.

We simplify our work by changing to the _signless chromatic polynomial_ ,
$\bar{\chi}_{\Phi}(\lambda):=(-1)^{n}\chi_{\Phi}(-\lambda)$, and the _signless
Whitney numbers_ , which are $\bar{w}_{i}=(-1)^{i}w_{i}=|w_{i}|$ by the
alternating sign property. Thus,

$\bar{\chi}_{\Phi}(\lambda)=\sum_{i=0}^{n-b(\Phi)}\bar{w}_{i}(\Phi)\lambda^{n-i}.$

Equation (3) becomes

(4)
$\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(V)}}(\lambda)=\gamma^{n}\bar{\chi}_{\Gamma}\Big{(}\frac{\lambda+1}{\gamma}\Big{)}.$

For brevity we say “Whitney number” for both signed and signless Whitney
numbers; the notation will show which is meant.

In group expansions we have, for example,
$\bar{w}_{0}(\mathfrak{G}{\cdot}\Gamma^{(X)})=1$ and
$\bar{w}_{1}(\mathfrak{G}{\cdot}\Gamma^{(X)})=|E(\Gamma)|\gamma+|X|,$ which
obviously are polynomial functions of $\gamma$. An exercise for the reader is
to compute $\bar{w}_{2}$ before reading Formula (5).

######  Theorem 1.

Given a simple graph $\Gamma$ of order $n>0$, a finite group $\mathfrak{G}$ of
order $\gamma>0$, and an integer $i=0,1,\dots,n$, the signless Whitney number
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(V)})$ is a polynomial function of
$\gamma$ of degree $\min(i,n-c)$, with positive coefficients, i.e.,

(5) $\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(V)})=\sum_{0\leq j\leq
i}\bar{w}_{j}(\Gamma)\binom{n-j}{i-j}\gamma^{j}.$

###### Proof.

The proof from Equation (4) is easy.

$\displaystyle\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(V)}}(\lambda)$
$\displaystyle=\gamma^{n}\bar{\chi}_{\Gamma}\Big{(}\frac{\lambda+1}{\gamma}\Big{)}=\sum_{j}\bar{w}_{j}(\Gamma)\gamma^{j}(\lambda+1)^{n-j}$
$\displaystyle=\sum_{j}\bar{w}_{j}(\Gamma)\gamma^{j}\sum_{k}\binom{n-j}{k}\lambda^{k}$
$\displaystyle={\sum\sum}_{0\leq k\leq n-j\leq
n}\lambda^{k}\bar{w}_{j}(\Gamma)\gamma^{j}\sum_{k}\binom{n-j}{k}$

and substituting $k=n-i$,

(6) $\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(V)}}(\lambda)=\sum_{0\leq i\leq
n}\lambda^{n-i}\sum_{0\leq j\leq
i}\bar{w}_{j}(\Gamma)\gamma^{j}\binom{n-j}{i-j},$

which implies (5). Thus, the Whitney numbers are polynomials in $\gamma$ and,
as promised, all coefficients of powers $\gamma^{j}$ are positive when $j\leq
i$ and $\bar{w}_{j}(\Gamma)\neq 0$, i.e., $j\leq n-c$. Thus, the degree is
$\min(i,n-c)$. ∎

When $i\leq n-c$, the leading coefficient in (5) is $\bar{w}_{i}(\Gamma)$,
which is the number of no-broken-circuit sets of $i$ edges in $\Gamma$ [5].
When $i>n-c$, the leading coefficient is that of $\gamma^{n-c}$, which is
$\bar{w}_{n-c}(\Gamma)\binom{c}{n-i}$. The first factor is the number of
maximal forests that contain no broken circuit. The second factor is the
number of ways to choose $n-i$ of the $c$ components of the forest. As a
combinatorial interpretation of the product this seems arbitrary. Are there
meaningful combinatorial interpretations of the coefficients of powers of
$\gamma$?

##  4\. More expansions

We generalize to group expansions $\mathfrak{G}{\cdot}\Gamma^{(X)}$ with
$X\subseteq V$, i.e., for any set of half edges. (These were studied in [7,
Examples 3.7 and 6.7].) We say a vertex set is _stable_ if it contains no
edges in $\Gamma$. The number of stable sets of order $k$ is
$\alpha_{k}(\Gamma)$. The complement of $X\subseteq V$ is $X^{c}$. The number
of isolated vertices of $\Gamma$ that are not in $X$ is $\zeta$.

######  Theorem 2.

For any set $X\subseteq V(\Gamma)$, the Whitney number
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})$ is a polynomial function of
$\gamma$ of degree $\min(i,n-c)$ for each $i=0,1,\ldots,n-\zeta$.
Specifically,

(7)
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})=\sum_{j=0}^{i}\gamma^{j}\sum_{k=0}^{i-j}(-1)^{k}\binom{n-j-k}{n-i}\sum_{\begin{subarray}{c}Y\subseteq
X^{c}:\,\text{stable}\\\ |Y|=k\end{subarray}}\bar{w}_{j}(\Gamma\smallsetminus
Y)$

if $i\leq n-\zeta$ and $\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})=0$ if
$i>n-\zeta$. The leading term is $\bar{w}_{i}(\Gamma)\gamma^{i}$ if $i\leq
n-c$ and $\bar{w}_{n-c}(\Gamma)\binom{c-\zeta}{i-(n-c)}\gamma^{n-c}$ if
$n-c\leq i\leq n-\zeta$.

###### Proof.

The crucial formula is

$\displaystyle\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(X)}}(\lambda)=\sum_{Y\subseteq
X^{c}:\text{
stable}}(-1)^{|Y|}\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(V)}\smallsetminus
Y}(\lambda),$

from [7, Theorem 6.1]. We extract the Whitney numbers via Equation (6):

$\displaystyle\sum_{\begin{subarray}{c}Y\subseteq X^{c}\\\
\text{stable}\end{subarray}}(-1)^{|Y|}\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(V)}\smallsetminus
Y}(\lambda)$ $\displaystyle=\sum_{\begin{subarray}{c}Y\subseteq X^{c}\\\
\text{stable}\end{subarray}}(-1)^{|Y|}\sum_{k=0}^{n-|Y|}\bar{w}_{k}(\mathfrak{G}{\cdot}\Gamma^{(V)}\smallsetminus
Y)\lambda^{n-|Y|-k}$ $\displaystyle=\sum_{\begin{subarray}{c}Y\subseteq
X^{c}\\\
\text{stable}\end{subarray}}(-1)^{|Y|}\sum_{k=0}^{n-|Y|}\sum_{j=0}^{k}\bar{w}_{j}(\Gamma\smallsetminus
Y)\binom{n-|Y|-j}{k-j}\gamma^{j}\lambda^{n-|Y|-k}$ and now substituting
$i=|Y|+k$,
$\displaystyle=\sum_{i=0}^{n}\lambda^{n-i}\sum_{\begin{subarray}{c}Y\subseteq
X^{c}\\\ \text{stable}\\\ |Y|\leq
i\end{subarray}}(-1)^{|Y|}\sum_{j=0}^{i-|Y|}\bar{w}_{j}(\Gamma\smallsetminus
Y)\binom{n-j-|Y|}{n-i}\gamma^{j}.$

The chromatic polynomial is therefore

(8)
$\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(X)}}(\lambda)=\sum_{i=0}^{n}\lambda^{n-i}\sum_{j=0}^{i}\gamma^{j}\sum_{\begin{subarray}{c}Y\subseteq
X^{c}:\,\text{stable}\\\ |Y|\leq
i-j\end{subarray}}(-1)^{|Y|}\binom{n-j-|Y|}{n-i}\bar{w}_{j}(\Gamma\smallsetminus
Y).$

As the coefficient of $\lambda^{n-i}$ is
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})$, we obtain (7) by introducing
$k:=|Y|\leq i-j$. This quantity is a polynomial in $\gamma$ of degree at most
$i$. The term of degree $i$ arises only from $Y=\varnothing$ and its
coefficient is $\bar{w}_{i}(\Gamma)$, which is nonzero as long as $i\leq n-c$.
It remains to find the degree when $i>n-c$.

Let $Z$ be the set of isolated vertices that are not in $X$, so $\zeta:=|Z|$.
From the product formula (2) along with (1) we find that
$\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(X)}}(\lambda)=\lambda^{\zeta}\bar{\chi}_{\mathfrak{G}{\cdot}\Gamma^{(X)}\smallsetminus
Z}(\lambda)\text{ and
}\bar{\chi}_{\Gamma}(\lambda)=\lambda^{\zeta}\bar{\chi}_{\Gamma\smallsetminus
Z}(\lambda);$ we conclude that
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})=0$ if $i>n-\zeta$. (This
corresponds to the fact that
$\operatorname{rk}\mathbf{F}(\mathfrak{G}{\cdot}\Gamma^{(X)})=n-\zeta$ if
$\gamma>1$ and is at most that if $\gamma=1$; see [6, Section 2].)

Thus, now we assume $n-c\leq i\leq n-\zeta$. The highest-degree term in
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})$ has degree at most $n-c$
because $\bar{w}_{j}(\Gamma\smallsetminus Y)=0$ when $j>n-c$. We examine the
coefficient of $\gamma^{n-c}$, i.e.,

(9) $\sum_{\begin{subarray}{c}Y\subseteq X^{c},\text{ stable}\\\ |Y|\leq
i-(n-c)\end{subarray}}(-1)^{|Y|}\bar{w}_{n-c}(\Gamma\smallsetminus
Y)\binom{c-|Y|}{n-i}.$

Let $c_{Y}$ denote the number of components of $\Gamma\smallsetminus Y$. The
rank of $\mathbf{F}(\Gamma\smallsetminus Y)$ is $n-|Y|-c_{Y}$, so if
$n-|Y|-c_{Y}<n-c$, then $\bar{w}_{n-c}(\Gamma\smallsetminus Y)=0$ and the term
of $Y$ in (11) drops out. We may therefore restrict $Y$ to satisfy
$|Y|+c_{Y}\leq c$. Restating this as $c(\Gamma\smallsetminus Y)\leq c-|Y|$
shows that deleting $Y$ destroys at least $|Y|$ components, which is possible
only if $Y$ consists of isolated vertices in $\Gamma$. As $Y\subseteq X^{c}$,
this means $Y\subseteq Z$; indeed, $Y$ is any subset of $Z$ of the right size.
It also means that $\bar{w}_{j}(\Gamma\smallsetminus Y)=\bar{w}_{j}(\Gamma)$
since the Whitney numbers do not take account of isolated vertices.

We digress to prove an identity using Vandermonde convolution, assuming $c\geq
m\geq 0$:

(10) $\displaystyle\sum_{k=0}^{m}(-1)^{k}\binom{\zeta}{k}\binom{c-k}{c-m}$
$\displaystyle=\sum_{k=0}^{m}(-1)^{k}\binom{\zeta}{k}\binom{c-k}{m-k}=(-1)^{m}\sum_{k=0}^{m}\binom{\zeta}{k}\binom{-(c-m+1)}{m-k}$
$\displaystyle=(-1)^{m}\binom{\zeta-c+m-1}{m-k}=\binom{c-\zeta}{m}.$

Formula (9) becomes

(11) $\displaystyle\bar{w}_{n-c}(\Gamma)\sum_{\begin{subarray}{c}Y\subseteq
Z:|Y|\leq i-(n-c)\end{subarray}}(-1)^{|Y|}\binom{c-|Y|}{n-i}$
$\displaystyle=\bar{w}_{n-c}(\Gamma)\sum_{k=0}^{i-(n-c)}(-1)^{k}\binom{\zeta}{k}\binom{c-k}{n-i}.$
$\displaystyle=\bar{w}_{n-c}(\Gamma)\binom{c-\zeta}{i-(n-c)}$

by (10) with $m=i-(n-c)$ (so $n-i=c-m$). Note that $c-\zeta\geq i-(n-c)$
because we assumed $i\leq n-\zeta$; therefore this coefficient is positive.
Thus, $\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})$ is a polynomial in
$\gamma$ of degree exactly $n-c$ when $n-c<i\leq n-\zeta$. ∎

##  5\. Examples

###  5.1. Lower Whitney numbers

Here are formulas for the lower Whitney numbers in terms of the structure of
$\Gamma$, from (7). The complement of the simple graph $\Gamma$ is
$\Gamma^{c}$. The degree in $\Gamma$ of a vertex $v$ is $d_{\Gamma}(v)$. The
number of triangles in $\Gamma$ is $t(\Gamma)$; note that
$\bar{w}_{2}(\Gamma)=\binom{|E(\Gamma)|}{2}-t(\Gamma)$.

(12) $\displaystyle\bar{w}_{0}(\mathfrak{G}{\cdot}\Gamma^{(V)})$
$\displaystyle=1,$ $\displaystyle\bar{w}_{1}(\mathfrak{G}{\cdot}\Gamma^{(V)})$
$\displaystyle=|E(\Gamma)|\gamma+|X|,$
$\displaystyle\bar{w}_{2}(\mathfrak{G}{\cdot}\Gamma^{(V)})$
$\displaystyle=\bigg{[}\binom{|E(\Gamma)|}{2}-t(\Gamma)\bigg{]}\gamma^{2}+\bigg{[}(|X|-1)|E(\Gamma)|+\sum_{y\in
X^{c}}d_{\Gamma}(y)\bigg{]}\gamma$
$\displaystyle\qquad+\bigg{[}(n-1)\Big{(}|X|-\frac{n}{2}\Big{)}+|E(\Gamma^{c}\smallsetminus
X)|\bigg{]}$

###  5.2. Special coefficients

The constant term of $\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})$, which is
the value of the Whitney number when $\gamma=0$, is

$\sum_{k=0}^{i}(-1)^{k}\binom{n-k}{i-k}\alpha_{k}(\Gamma\smallsetminus X).$

Suppose $\Gamma=K_{n}$, $n>1$. Then $\zeta=0$. There are no stable sets larger
than a single vertex. The constant term is

$\sum_{k=0}^{1}(-1)^{k}\binom{n-k}{i-k}\alpha_{k}(K_{n}\smallsetminus
X)=\binom{n-1}{n-i}|X|-(i-1)\binom{n}{i}.$

Note that $\binom{n-1}{-1}=0$ and that by setting $\gamma=0$ we do not get the
chromatic polynomial of a partially filled edgeless graph,
$(K_{n}^{c})^{(X)}$.

We state the two highest terms in $\gamma$ of
$\bar{w}_{i}(\mathfrak{G}{\cdot}\Gamma^{(X)})$, assuming $i\leq n-c$. The
highest power, $\gamma^{i}$, has coefficient $\bar{w}_{j}(\Gamma)$. The next
lower coefficient is more interesting: it is

$(n+1-i)\bar{w}_{i-1}(\Gamma)-\sum_{y\notin
X}\bar{w}_{i-1}(\Gamma\smallsetminus y).$

###  5.3. A short path

As a thorough example we develop the formulas for
$\Gamma=P_{2}=v_{1}v_{2}v_{3}$, the path of length 2. We deduce the Whitney
numbers from Equation (7). The stable sets are $\varnothing$, $\\{v_{p}\\}$
for $p=1,2,3$, and $\\{v_{1},v_{3}\\}$. The Whitney numbers of $P_{2}$ are
$\bar{w}_{0}(P_{2})=1$, $\bar{w}_{1}(P_{2})=2$, $\bar{w}_{2}(P_{2})=1$,
$\bar{w}_{3}(P_{2})=0$.

$\displaystyle\bar{w}_{i}(\mathfrak{G}{\cdot}P_{2}^{(X)})$
$\displaystyle=\sum_{j=0}^{i}\gamma^{j}\sum_{k=0}^{i-j}(-1)^{k}\binom{3-j-k}{3-i}\sum_{\begin{subarray}{c}Y\subseteq
X^{c}:\,\text{stable}\\\ |Y|=k\end{subarray}}\bar{w}_{j}(P_{2}\smallsetminus
Y).$

We conclude that

(13) $\displaystyle\bar{w}_{i}(\mathfrak{G}{\cdot}P_{2}^{(X)})$
$\displaystyle=\sum_{k=0}^{2}(-1)^{k}\binom{3-k}{3-i}\alpha_{k}(P_{2}\smallsetminus
X)$
$\displaystyle\quad+\gamma\sum_{k=0}^{2}(-1)^{k}\binom{3-1-k}{3-i}\sum_{\begin{subarray}{c}Y\subseteq
X^{c}:\,\text{stable}\\\ |Y|=k\end{subarray}}\bar{w}_{1}(P_{2}\smallsetminus
Y)$
$\displaystyle\quad+\gamma^{2}\sum_{k=0}^{2}(-1)^{k}\binom{3-2-k}{3-i}\sum_{\begin{subarray}{c}Y\subseteq
X^{c}:\,\text{stable}\\\ |Y|=k\end{subarray}}\bar{w}_{2}(P_{2}\smallsetminus
Y).$

There are six different possible sets $X$ up to isomorphism:

$X=\varnothing,\\{v_{1}\\},\\{v_{2}\\},\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},V.$

We present the Whitney numbers in Table 1 and abbreviated calculations for two
of the six cases.

$X$ | $\bar{w}_{0}$ | $\bar{w}_{1}$ | $\bar{w}_{2}$ | $\bar{w}_{3}$ | $\gamma=1$ | $\mathbf{F}(\mathbf{1}{\cdot}P_{2}^{(X)})$
---|---|---|---|---|---|---
$\varnothing$ | $1$ | $2\gamma$ | $-2+2\gamma+\gamma^{2}$ | $-1+\gamma^{2}$ | 1, 2, 1, 0 | $\mathbf{F}(C_{4})$
$\\{v_{1}\\}$ | $1$ | $1+2\gamma$ | $-1+3\gamma+\gamma^{2}$ | $-1+\gamma+\gamma^{2}$ | 1, 3, 3, 1 | $F_{3}$
$\\{v_{2}\\}$ | $1$ | $1+2\gamma$ | $2\gamma+\gamma^{2}$ | $\gamma^{2}$ | 1, 3, 3, 1 | $F_{3}$
$\\{v_{1},v_{2}\\}$ | $1$ | $2+2\gamma$ | $1+3\gamma+\gamma^{2}$ | $\gamma+\gamma^{2}$ | 1, 4, 5, 2 | $\mathbf{F}(C_{3})\oplus\mathbf{F}(K_{2})$
$\\{v_{1},v_{3}\\}$ | $1$ | $2+2\gamma$ | $1+4\gamma+\gamma^{2}$ | $2\gamma+\gamma^{2}$ | 1, 4, 6, 3 | $\mathbf{F}(C_{4})$
$V$ | $1$ | $3+2\gamma$ | $3+4\gamma+\gamma^{2}$ | $1+2\gamma+\gamma^{2}$ | 1, 5, 8, 4 | $\mathbf{F}(K_{4}\smallsetminus e)$
Table 1. The Whitney numbers of the six expansions
$\mathfrak{G}{\cdot}P_{2}^{(X)}$. $F_{3}$ is the free matroid. The fact that
the formulas with $\gamma=1$ give the right Whitney numbers for the matroid of
$\mathbf{1}{\cdot}P_{2}^{(X)}$ in all six cases gives confidence that the
formulas are correct.

Case 2\. Consider $X=\\{v_{1}\\}$, so $X^{c}=\\{v_{2},v_{3}\\}$ and
$P_{2}\smallsetminus X=K_{2}$.

$\displaystyle\bar{w}_{i}(\mathfrak{G}{\cdot}P_{2}^{(v_{1})})$
$\displaystyle=\sum_{k=0}^{2}(-1)^{k}\binom{3-k}{3-i}\alpha_{k}(P_{2}\smallsetminus
v_{1})$
$\displaystyle\quad+\gamma\sum_{k=0}^{2}(-1)^{k}\binom{3-1-k}{3-i}\sum_{\begin{subarray}{c}Y\subseteq\\{v_{2},v_{3}\\}:\,\text{stable}\\\
|Y|=k\end{subarray}}\bar{w}_{1}(P_{2}\smallsetminus Y)$
$\displaystyle\quad+\gamma^{2}\sum_{k=0}^{2}(-1)^{k}\binom{3-2-k}{3-i}\sum_{\begin{subarray}{c}Y\subseteq\\{v_{2},v_{3}\\}:\,\text{stable}\\\
|Y|=k\end{subarray}}\bar{w}_{2}(P_{2}\smallsetminus Y)$
$\displaystyle=\bigg{[}\binom{3}{3-i}-\binom{2}{3-i}2\bigg{]}+\gamma\bigg{[}\binom{2}{3-i}2-\binom{1}{3-i}\bigg{]}+\gamma^{2}\bigg{[}\binom{1}{3-i}\bigg{]}.$

Case 6\. Here $X=V$ so $X^{c}=\varnothing$. We know the chromatic polynomial
from (3). This enables us to check the formula (13) for arbitrary values of
$\gamma$.

$\displaystyle\bar{w}_{i}(\mathfrak{G}{\cdot}P_{2}^{(V)})$
$\displaystyle=\bigg{[}\binom{3}{3-i}\bigg{]}+\gamma\bigg{[}\binom{2}{3-i}2\bigg{]}+\gamma^{2}\bigg{[}\binom{1}{3-i}\bigg{]}.$

The Whitney numbers (Table 1) should agree with

$\displaystyle\chi_{\mathfrak{G}{\cdot}K_{3}^{(V)}}(\lambda)$
$\displaystyle=\gamma^{3}\frac{\lambda-1}{\gamma}\Big{(}\frac{\lambda-1}{\gamma}-1\Big{)}^{2}=(\lambda-1)(\lambda-[1+\gamma])^{2}$
$\displaystyle=\lambda^{3}-\lambda^{2}\Big{[}3+2\gamma\Big{]}+\lambda\Big{[}1+2\gamma+\gamma^{2}+2(1+\gamma)\Big{]}-\Big{[}1+2\gamma+\gamma^{2}\Big{]}.$

from (3), and they do.

###  5.4. Dowling Examples

######  Example 1 (Dowlings).

Equation (4) immediately gives the Whitney numbers of the Dowling lattices.
The base graph chromatic polynomial is
$\chi_{K_{n}}(\lambda)=\sum_{j=0}^{n}s(n,n-j)\lambda^{n-j}$, where $s(n,n-j)$
is the Stirling number of the first kind. Its sign is $(-1)^{n-j}$ if $j<n$;
$s(n,0)$ is 0 if $n>0$. Write $\bar{s}(n,n-j)=(-1)^{n-j}s(n,n-j)$ for the
signless Stirling number. Thus, $\bar{w}_{j}(K_{n})=\bar{s}(n,n-j)$ and for
the Dowling lattice we have the polynomial formula

$\bar{w}_{i}(Q_{n}(\mathfrak{G}))=\bar{w}_{i}(\mathfrak{G}{\cdot}K_{n}^{(V)})=\sum_{0\leq
j\leq i}\bar{s}(n,n-j)\binom{n-j}{i-j}\gamma^{j}.$

######  Example 2 (More or Less Jointless Dowlings).

These are the lattices of $\mathbf{F}(\mathfrak{G}{\cdot}K_{n}^{(X)})$ for any
vertex set $X$, or in Kung’s terminology any set of joints. Kung introduced
the term _joint_ for the half edges in a group expansion, when viewed as
elements of a standard basis for the matroid [2]. If all joints are missing,
he calls the lattice _jointless_.

For $K_{n}$ with $n>0$, we have $c=1$ and the only stable sets $Y$ are
$\varnothing$ and $\\{y\\}$ for $y\in X^{c}$. Equation (7) becomes

$\displaystyle\bar{w}_{i}(\mathfrak{G}{\cdot}K_{n}^{(X)})=$
$\displaystyle\sum_{j=0}^{i}\left[\bar{s}(n,n-j)\binom{n-j}{i-j}-|X^{c}|\bar{s}(n-1,n-j-1)\binom{n-j-1}{i-j-1}\right]\gamma^{j}.$

In particular, for $\gamma=1$ this should give
$\bar{s}(n,n-i)=\bar{w}_{i}(K_{n})$. Thus, we have an identity involving
Stirling numbers:

$\displaystyle\sum_{j=0}^{i}\left[\bar{s}(n,n-j)\binom{n-j}{i-j}-n\bar{s}(n-1,n-j-1)\binom{n-j-1}{i-j-1}\right]=\bar{s}(n,n-i).$

##  6\. Biased expansions

An $\gamma$-fold biased expansion of $\Gamma$ [7, Example 3.8], where $\gamma$
is a positive integer, is a combinatorial abstraction and generalization of a
group expansion. It has the same numerical properties as a group expansion [7,
Example 6.8] but does not require a group (although it is true that if
$\Gamma$ is 3-connected, every biased expansion is a group expansion [8]).
That is, all the preceding results apply equally to biased expansions.

## References

  * [1] T.A. Dowling, A class of geometric lattices based on finite groups. _J. Combin. Theory Ser. B_ 14 (1973), 61–86. Erratum. _ibid_. 15 (1973), 211.
  * [2] Jeff Kahn and Joseph P.S. Kung, Varieties of combinatorial geometries. _Trans. Amer. Math. Soc._ 271 (1982), 485–499.
  * [3] Alberto Ravagnani, Whitney numbers of combinatorial geometries and higher-weight Dowling lattices. _SIAM J. Appl. Algebra Geom._ 6 (2022), no. 2, 156–189.
  * [4] Gian-Carlo Rota, On the foundations of combinatorial theory: I. Theory of Möbius functions. _Z. Wahrsch. verw. Gebiete_ 2 (1964), 340–368.
  * [5] H. Whitney, A logical expansion in mathematics. _Bull. Amer. Math. Soc._ 38 (1932), 572–579.
  * [6] Thomas Zaslavsky, Biased graphs. II. The three matroids. _J. Combin. Theory Ser. B_ 51 (1991), 46–72.
  * [7] Thomas Zaslavsky, Biased graphs. III. Chromatic and dichromatic invariants. _J. Combin. Theory Ser. B_ 64 (1995), 17–88.
  * [8] Thomas Zaslavsky, Associativity in multary quasigroups: The way of biased expansions. _Aequat. Math._ 83 (2012), no. 1, 1–66.