# Neural Language Models for Nineteenth-Century English

Kasra Hosseinia∗, Kaspar Beelena,b, Giovanni Colavizzac, Mariona Coll
Ardanuya,b
aThe Alan Turing Institute, London, UK
bQueen Mary University of London, London, UK
cInstitute for Logic, Language and Computation, University of Amsterdam, NL

∗Corresponding author: Kasra Hosseini<EMAIL_ADDRESS>

###### Abstract

We present four types of neural language models trained on a large historical
dataset of books in English, published between 1760-1900 and comprised of
$\approx$5.1 billion tokens. The language model architectures include static
(word2vec and fastText) and contextualized models (BERT and Flair). For each
architecture, we trained a model instance using the whole dataset.
Additionally, we trained separate instances on text published before 1850 for
the two static models, and four instances considering different time slices
for BERT. Our models have already been used in various downstream tasks where
they consistently improved performance. In this paper, we describe how the
models have been created and outline their reuse potential.

Keywords: language model; BERT; word2vec; fastText; nineteenth-century
English; digital heritage.

##  1 Overview

As language is subject to continuous change, the computational analysis of
digital (textual) heritage should attune models and methods to the specific
historical contexts in which these texts emerged. This paper aims to
facilitate the “historicization” of Natural Language Processing (NLP) methods
by releasing various language models trained on a 19th-century book
collection. These models can support research in digital and computational
humanities, history, computational linguistics and the cultural heritage or
GLAM sector (galleries, libraries, archives, and museums). To accommodate
different research needs, we release a wide variety of models, from “static”
embeddings (word2vec and fastText) to more recent language models that produce
context-dependent word or string embeddings (BERT and Flair, respectively).
Here, we consider a model “static” when it generates only one embedding for a
given token at inference time, regardless of the textual context in which the
token appears. On the other hand, “contextual” models generate a distinct
embedding according to the textual context at inference time.

#### Repository location

The dataset is available on Zenodo at http://doi.org/10.5281/zenodo.4782245.

#### Context

This work was produced as part of Living with Machines (LwM),11endnote:
1https://livingwithmachines.ac.uk (last access: 2021-05-24). an
interdisciplinary project focused on the lived experience of Britain’s
industrialization during the long 19th century. The language models presented
here have been used in several research projects, to assess the impact of
optical character recognition (OCR) on NLP tasks (van Strien et al., 2020), to
detect atypical animacy (Coll Ardanuy et al., 2020), and for targeted sense
disambiguation (Beelen et al., 2021).

##  2 Method

###  2.1 Original corpus

Figure 1: Number of books by publication date. The preprocessed dataset has
47,685 books in English consisting of $\approx$5.1 billion tokens. The red
vertical dashed lines mark the boundaries between the time periods we used to
slice the dataset. See Section 2.2 for details.

The original collection consists of $\approx$48K digitized books in English,
made openly available by the British Library in partnership with Microsoft,
henceforth Microsoft British Library Corpus (MBL). The digitized books are
available as JSON files from the British Library web page.22endnote:
2https://data.bl.uk/digbks/db14.html (last access: 2021-05-24). Figure 1 gives
an overview of the number of books by year. The bulk of the material is dated
somewhere between 1800 and 1900, with the number of documents steeply rising
at the end of the 19th century. Because all copyrights are cleared and the
data are in the public domain, they have already become a popular resource for
(digital) historians and literary scholars.33endnote: 3See for example the
Contagion Project https://cca.ucd.ie/contagion-project-british-library-corpus/
(last access: 2021-05-24). However, one notable issue with this collection
(when used for historical research) is the somewhat opaque selection process
of books: while the data provide decent coverage over the nineteenth century,
the exact criteria for inclusion remain unclear and future work might
profitably consider assessing the characteristics of this collection in more
detail.

###  2.2 Steps

#### Preprocessing

Each book was minimally normalized: we converted the text to ASCII, fixed
common punctuation errors, dehyphenated broken tokens, removed most
punctuation and separated the remaining punctuation marks from tokens. While
the large majority of books in the MBL corpus are written in English, the
collection still contains a substantial amount of documents in other
languages. Therefore, we filtered by English language, using spaCy’s language
detector (Honnibal et al., 2020). Finally, we used syntok44endnote:
4https://pypi.org/project/syntok (last access: 2021-05-24). to split the book
into sentences and tokenize the text. This process resulted in one file per
book where each line corresponded to a sentence with space-separated tokens.

#### Data selection

For each of the selected models, we trained an instance using the whole
dataset (i.e., books from all over the 19th century; see Figure 1). For the
word2vec and fastText models, we have also trained instances on text published
before 1850. Moreover, for BERT, we have fine-tuned four model instances on
different time slices, with data from before 1850, between 1850 and 1875,
between 1875 and 1890, and between 1890 and 1900, each slice containing
$\approx$1.3B tokens per period, except for 1890-1900, which included
$\approx$1.1B tokens. While this periodization was largely motivated by the
number of tokens, the different models (that resulted from the data
partitioning) may enable historians to track cultural changes over the long
19th century.55endnote: 5For example, the pre-1850 dataset sets apart the
first industrial revolution from later developments in Britain. Likewise,
1890-1900 is set off, especially in literary terms, by the emergence of
‘modernist’ sensibilities and the questioning of class and gender hierarchies
associated with the term ‘fin de siècle’.

#### Word2vec and fastText

We trained the word2vec (Mikolov et al., 2013) and fastText (Bojanowski et
al., 2016) models as implemented in the Gensim library (Rehurek and Sojka,
2011). In addition to the preprocessing steps described above, we lowercased
all tokens before training. For word2vec, we used the skip-gram architecture,
which we trained for one epoch. We set the dimension of the word embedding
vectors to 300 and removed tokens appearing less than 20 times. The same
hyperparameters were used for training fastText models.

#### Flair

Flair is a character language model based on the Long short-term memory (LSTM)
variant of recurrent neural networks (Hochreiter and Schmidhuber, 1997; Akbik
et al., 2019). Even though less popular than the Transformers, it has been
shown to obtain state-of-the-art results in Named Entity Recognition (NER). We
trained a character-level, forward-pass Flair language model on all the books
in the MBL corpus for one epoch and sequence length of 250 characters (during
training). We used the default character dictionary in Flair. The LSTM
component had one layer and a hidden dimension of 2048.

#### BERT

To fine-tune BERT model instances, we started with a contemporary model: ‘BERT
base uncased’,66endnote: 6https://github.com/google-research/bert (last
access: 2021-05-24). hereinafter referred to as BERT-base (Devlin et al.,
2019; Wolf et al., 2019). This instance was then fine-tuned on the earliest
time period (i.e., books predating 1850). For the consecutive period
(1850-1875), we used the pre-1850 language model instance as a starting point
and continued fine-tuning with texts from the following period. This procedure
of consecutive incremental fine-tuning was repeated for the other two time
periods.

We used the original BERT-base tokenizer as implemented by
HuggingFace77endnote: 7https://github.com/huggingface/transformers (last
access: 2021-05-24). (Wolf et al., 2019). We did not train new tokenizers for
each time period. This way, the resulting language model instances can be
compared easily with no further processing or adjustments. The tokenized and
lowercased sentences were fed to the language model fine-tuning tool in which
only the masked language model (MLM) objective was optimized. We used a batch
size of 5 per GPU and fine-tuned for 1 epoch over the books in each time-
period. The choice of batch size was dictated by the available GPU memory (we
used 4$\times$ NVIDIA Tesla K80 GPUs in parallel). Similar to the original
BERT pre-training procedure, we used the Adam optimizer (Kingma and Ba, 2014)
with a learning rate of 0.0001, $\beta_{1}=0.9$, $\beta_{2}=0.999$ and $L_{2}$
weight decay of 0.01. In our fine-tuning procedure, we used a linear learning-
rate warm-up over the first 2,000 steps. A dropout probability of 0.1 was
applied in all layers.

#### Quality control

The quality of our language models was mainly evaluated on multiple downstream
tasks. In van Strien et al. (2020), we investigated the impact of OCR quality
on the 19th-century word2vec model and showed how language models trained on
large OCR’d corpora still yield robust word embedding vectors. The BERT models
have been used in Coll Ardanuy et al. (2020) and Beelen et al. (2021), where
they generally improved the performance of various downstream tasks when the
data of the experiments was contemporaneous to that of the language models,
thereby confirming their quality via extrinsic evaluation.

##  3 Language model zoo

#### Object name

histLM.

#### Format names and versions

The models are shared as ZIP files (one per model architecture). The directory
structure is described in the README.md file.

#### Creation dates

2020-01-31 to 2020-10-07.

#### Dataset creators

Kasra Hosseini, Kaspar Beelen and Mariona Coll Ardanuy (The Alan Turing
Institute) preprocessed the text, created a database, trained and fine-tuned
language models as described in this paper. Giovanni Colavizza (University of
Amsterdam) initiated this work on historical language models. All authors
contributed to planning and designing the experiments.

#### Language

The language models have been trained on 19th-century texts in English.

#### License

The models are released under open license CC BY 4.0, available at
https://creativecommons.org/licenses/by/4.0/legalcode.

#### Repository name

All the language models are published in Zenodo at
http://doi.org/10.5281/zenodo.4782245. We have also provided scripts to work
with the language models, available on GitHub at https://github.com/Living-
with-machines/histLM.

#### Publication date

2021-05-23.

##  4 Reuse Potential

Even though word2vec has been around almost a decade—an eternity in the fast-
moving NLP ecosystem—the static word embeddings it produces persist as popular
instruments, especially for interdisciplinary research (Azarbonyad et al.,
2017; Hengchen et al., 2019). The more recent fastText model extends on
word2vec by using subword information. Contextualized language models have
meant a breakthrough in NLP research (see e.g., Smith (2019) for an overview),
as they represent words in the contexts in which they appear, instead of
conflating all senses, one of the main criticisms of static word embeddings.
The potential of using such models for historical research is immense as they
allow a more accurate context-dependent representation of meaning.

Given that existing libraries such as Gensim, Flair, or Hugging Face provide
convenient interfaces to work with these embeddings, we are confident that our
historical models will serve the needs of a wide-variety of scholars, from NLP
and data science to the humanities, for different tasks and research purposes,
such as measuring how words change meaning over time, automatic OCR correction
(Hämäläinen and Hengchen, 2019), interactive query expansion88endnote: 8See
for example the search tools provided by the Impresso interface
https://impresso-project.ch (last access: 2021-05-24). or, more generally, any
research that involves diachronic language change (Shoemark et al., 2019).

## Acknowledgements

We are grateful to David Beavan (The Alan Turing Institute) and James
Hetherington (University College London) for helping with the data access and
research infrastructure. We thank the British Library for supplying digitised
books.

## Funding Statement

This work was supported by Living with Machines (AHRC grant AH/S01179X/1) and
The Alan Turing Institute (EPSRC grant EP/N510129/1).

## Competing interests

The authors have no competing interests to declare.

###### Notes

  1. 1 https://livingwithmachines.ac.uk (last access: 2021-05-24).
  2. 2 https://data.bl.uk/digbks/db14.html (last access: 2021-05-24).
  3. 3 See for example the Contagion Project https://cca.ucd.ie/contagion-project-british-library-corpus/ (last access: 2021-05-24).
  4. 4 https://pypi.org/project/syntok (last access: 2021-05-24).
  5. 5 For example, the pre-1850 dataset sets apart the first industrial revolution from later developments in Britain. Likewise, 1890-1900 is set off, especially in literary terms, by the emergence of ‘modernist’ sensibilities and the questioning of class and gender hierarchies associated with the term ‘fin de siècle’.
  6. 6 https://github.com/google-research/bert (last access: 2021-05-24).
  7. 7 https://github.com/huggingface/transformers (last access: 2021-05-24).
  8. 8 See for example the search tools provided by the Impresso interface https://impresso-project.ch (last access: 2021-05-24).

## References

  *   * Akbik et al. (2019) Akbik, A., Bergmann, T., Blythe, D., Rasul, K., Schweter, S., and Vollgraf, R.  (2019).  Flair: An easy-to-use framework for state-of-the-art nlp.  In _NAACL 2019, 2019 annual conference of the north american chapter of the association for computational linguistics (demonstrations)_ (pp. 54–59).
  * Azarbonyad et al. (2017) Azarbonyad, H., Dehghani, M., Beelen, K., Arkut, A., Marx, M., and Kamps, J.  (2017).  Words are malleable: Computing semantic shifts in political and media discourse.  In _Proceedings of the 2017 acm on conference on information and knowledge management_ (pp. 1509–1518).
  * Beelen et al. (2021) Beelen, K., Nanni, F., Coll Ardanuy, M., Hosseini, K., Tolfo, G., and McGillivray, B.  (2021).  When time makes sense: A historically-aware approach to targeted sense disambiguation.  In _Findings of acl-ijcnlp._ Bangkok, Thailand (Online): Association for Computational Linguistics.
  * Bojanowski et al. (2016) Bojanowski, P., Grave, E., Joulin, A., and Mikolov, T.  (2016).  Enriching word vectors with subword information.  _arXiv preprint arXiv:1607.04606_.
  * Coll Ardanuy et al. (2020) Coll Ardanuy, M., Nanni, F., Beelen, K., Hosseini, K., Ahnert, R., Lawrence, J., … McGillivray, B.  (2020, December).  Living machines: A study of atypical animacy.  In _Proceedings of the 28th international conference on computational linguistics_ (pp. 4534–4545).  Barcelona, Spain (Online): International Committee on Computational Linguistics.  Retrieved from https://www.aclweb.org/anthology/2020.coling-main.400 DOI: 10.18653/v1/2020.coling-main.400
  * Devlin et al. (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  (2019, June).  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 conference of the north American chapter of the association for computational linguistics: Human language technologies, volume 1 (long and short papers)_ (pp. 4171–4186).  Minneapolis, Minnesota: Association for Computational Linguistics.  Retrieved from https://www.aclweb.org/anthology/N19-1423 DOI: 10.18653/v1/N19-1423
  * Hämäläinen and Hengchen (2019) Hämäläinen, M., and Hengchen, S.  (2019).  From the paft to the fiiture: a fully automatic nmt and word embeddings method for ocr post-correction.  _arXiv preprint arXiv:1910.05535_.
  * Hengchen et al. (2019) Hengchen, S., Ros, R., and Marjanen, J.  (2019).  A data-driven approach to the changing vocabulary of the nation in english, dutch, swedish and finnish newspapers, 1750-1950.  In _In proceedings of the digital humanities (dh) conference._
  * Hochreiter and Schmidhuber (1997) Hochreiter, S., and Schmidhuber, J.  (1997).  Long short-term memory.  _Neural Computation_ , _9_(8), 1735–1780.
  * Honnibal et al. (2020) Honnibal, M., Montani, I., Van Landeghem, S., and Boyd, A.  (2020).  _spaCy: Industrial-strength Natural Language Processing in Python._ Zenodo.  Retrieved from https://doi.org/10.5281/zenodo.1212303 DOI: 10.5281/zenodo.1212303
  * Kingma and Ba (2014) Kingma, D. P., and Ba, J.  (2014).  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Mikolov et al. (2013) Mikolov, T., Chen, K., Corrado, G., and Dean, J.  (2013).  Efficient Estimation of Word Representations in Vector Space.  _arXiv preprint_.  Retrieved 2019-11-20, from http://arxiv.org/abs/1301.3781
  * Rehurek and Sojka (2011) Rehurek, R., and Sojka, P.  (2011).  Gensim–python framework for vector space modelling.  _NLP Centre, Faculty of Informatics, Masaryk University, Brno, Czech Republic_ , _3_(2).
  * Shoemark et al. (2019) Shoemark, P., Liza, F. F., Nguyen, D., Hale, S., and McGillivray, B.  (2019).  Room to glo: A systematic comparison of semantic change detection approaches with word embeddings.  In _Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (emnlp-ijcnlp)_ (pp. 66–76).
  * Smith (2019) Smith, N. A.  (2019).  Contextual word representations: A contextual introduction.  _arXiv preprint arXiv:1902.06006_.
  * van Strien et al. (2020) van Strien, D., Beelen, K., Ardanuy, M. C., Hosseini, K., McGillivray, B., and Colavizza, G.  (2020).  Assessing the impact of ocr quality on downstream nlp tasks.  In _Icaart (1)_ (pp. 484–496).
  * Wolf et al. (2019) Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., … Brew, J.  (2019).  HuggingFace’s Transformers: State-of-the-art Natural Language Processing.  _ArXiv_ , _abs/1910.03771_.


#  The contravariant functoriality of graph algebras

Piotr M. Hajac  Instytut Matematyczny, Polska Akademia Nauk, ul. Śniadeckich
8, Warszawa, 00-656 Poland<EMAIL_ADDRESS>and  Mariusz Tobolski  Instytut
Matematyczny, Uniwersytet Wrocławski, pl. Grunwaldzki 2, Wrocław, 50-384
Poland<EMAIL_ADDRESS>
###### Abstract.

We study pushouts in the category of directed graphs. Our first result is that
the subcategory given by strongly admissible monomorphisms is closed with
respect to pushouts. Next, we determine a subcategory for which the
construction of path algebras yields a contravariant functor into the category
of algebras, and then we restrict this subcategory even further to ensure that
now the construction of Leavitt path algebras induces a contravariant functor
into the category of algebras. Finally, we prove our main theorems stating
under which conditions these two contravariant functors turn pushouts of
directed graphs into pullbacks of algebras.

##  1\. Introduction

Graph theory is one of the most accessible parts of combinatorics and one
often uses graphs to visualize and study abstract mathematical objects. For
instance, the structure of a group can be encoded in its Cayley graph. Along
the same vein, with every (unital, basic, connected) finite-dimensional
associative algebra over an algebraically closed field, we can associate a
directed graph (or a quiver) from which the algebra in question can be
recovered via the path algebra construction (see, e.g. [3]). Furthermore,
every finite-dimensional hereditary associative algebra over an algebraically
closed field is Morita equivalent to a path algebra. These two results show
the importance of path algebras in the classification and representation
theory of finite-dimensional associative algebras. Furthermore, certain
quotients of path algebras, namely Leavitt path algebras, are closely
connected with graph C*-algebras (see, e.g. [1]).

There is a natural question: does the path algebra and the Leavitt path
algebra constructions give rise to functors from certain categories of graphs
to the category of algebras? In [7] (see also [2]), sufficient conditions
under which one obtains the covariant functoriality were found. In this paper,
we study the contravariant functoriality of path algebras and Leavitt path
algebras. Some results in this direction in the case of injective graph
homomorphisms already appeared in the literature. The paper [5] introduces
admissible inclusions, which are equivalent to quotient graphs by hereditary
subsets known from the graph algebra theory111The name quotient graph comes
from the fact that its Leavitt path algebra is a quotient algebra. However,
since the quotient of a given graph by a hereditary subset is in fact its
subgraph, this nomenclature might be misleading. (see, e.g. [1, Definition
2.4.1]). Our motivation comes from the theory of $q$-deformations of algebras
of functions on certain compact topological spaces. In [10], it was shown that
a pushout of graphs can lead to a pullback structure of the C*-algebra of the
quantum sphere. This remarkable feature was explored in [8, 9, 4], where more
general pushout-to-pullback theorems were proved. Similar results can be found
in the context of higher-rank graph C*-algebras [11] and Cuntz–Pimsner
algebras [13].

In Section 2, we introduce several conditions on graph homomorphisms, define
two subcategories of graphs, which we call POG and CRTBPOG, and we study
pushouts in these categories. Then, we relate our work with the previous known
results. In particular, we prove that an inclusion of graphs is admissible if
and only if it is a morphism in the category CRTBPOG. In Section 3, we show
that the path algebra construction gives rise to a contravariant functor from
the category POG to the category of algebras. Similarly, the Leavitt path
algebra construction gives rise to a contravariant functor from the category
CRTBPOG to the category of algebras. Finally, the results on the contravariant
functoriality of graph algebras enable us to prove two new pushout-to-pullback
theorems in Section 4. In the first theorem, we give sufficient conditions on
pushouts in the category POG under which the path algebra functor turns them
into pullbacks of algebras. The second theorem gives sufficient conditions on
pushouts in the category CRTBPOG under which the Leavitt path algebra functor
turns them into pullbacks of algebras.

##  2\. Graphs and morphisms

###  2.1. Graphs

A graph (directed graph, quiver) is a quadruple
$E:=(E^{0},E^{1},s_{E},t_{E})$, where:

  * •

$E^{0}$ is the set of vertices,

  * •

$E^{1}$ is the set of edges (arrows),

  * •

$E^{1}\overset{s_{E}}{\to}E^{0}$ is the source map assigning to each edge its
beginning,

  * •

$E^{1}\overset{t_{E}}{\to}E^{0}$ is the target (range) map assigning to each
edge its end.

Let $v$ be a vertex in a graph $E$. It is called a sink iff
$s^{-1}(v)=\emptyset$, it is called a source iff $t^{-1}(v)=\emptyset$, and it
is called regular iff it is not a sink and $|s^{-1}(v)|<\infty$. The subset of
regular vertices of a graph $E$ is denoted by ${\rm Reg}(E)$. A finite path in
$E$ is a vertex or a finite tuple $p_{n}:=(e_{1},\ldots,e_{n})$ of edges
satisfying

$t_{E}(e_{1})=s_{E}(e_{2}),\quad t_{E}(e_{2})=s_{E}(e_{3}),\quad\ldots,\quad
t_{E}(e_{n-1})=s_{E}(e_{n}).$

We denote the set of all finite paths in $E$ by $FP(E)$. The beginning
$s_{E}(p_{n})$ of $p_{n}$ is $s_{E}(e_{1})$ and the end $t_{E}(p_{n})$ of
$p_{n}$ is $t_{E}(e_{n})$. The beginning and the end of a vertex is the vertex
itself. Thus, we extend the source and target maps to $s_{PE},t_{PE}\colon
FP(E)\to E^{0}$. Vertices are considered as finite paths of length $0$. Every
edge is a path of length $1$. The length of a finite path that is not a vertex
is the size of the tuple.

###  2.2. Morphisms

Let $E:=(E^{0},E^{1},s_{E},t_{E})$ and $F:=(F^{0},F^{1},s_{F},t_{F})$ be
graphs. A homomorphism from $E$ to $F$ is a pair of maps

$(f^{0}:E^{0}\to F^{0},f^{1}:E^{1}\to F^{1})$

satisfying the conditions:

$s_{F}\circ f^{1}=f^{0}\circ s_{E}\,,\qquad t_{F}\circ f^{1}=f^{0}\circ
t_{E}\,.$

We denote the category of graphs and graph homomorphisms by OG. We call a
graph homomorphism $(f^{0},f^{1})$ _injective_ or _surjective_ iff both
$f^{0}$ and $f^{1}$ are injective or surjective, respectively.

If $(f^{0},f^{1})\colon E\to F$ is a homomorphism of graphs, then we define
$f\colon FP(E)\to FP(F)$ as follows

$\displaystyle\forall\;v\in E^{0}\colon f(v):=f^{0}(v),\quad\forall\;e\in
E^{1}\colon f(e):=f^{1}(e),$ $\displaystyle\forall\;(e_{1},\ldots,e_{n})\in
FP(E)\colon f((e_{1},\ldots,e_{n})):=(f^{1}(e_{1}),\ldots,f^{1}(e_{n}))\in
FP(F).$

If $(f^{0},f^{1})$ is injective, then so is $f$. Note also that now we can
think of $FP$ as a covariant functor from the category $OG$ of graphs and
graph homomorphisms to the category of sets and maps:

$\displaystyle\phantom{XXX}FP\big{(}(f^{0},f^{1})\circ(g^{0},g^{1})\big{)}(p)$
$\displaystyle=FP\big{(}(f^{0}\circ g^{0},f^{1}\circ g^{1})\big{)}(p)$
$\displaystyle=\begin{cases}(f^{0}\circ g^{0})(v)&\text{ for }p\in E^{0}\\\
\big{(}(f^{1}\circ g^{1}(e_{1})\big{)},\ldots,(f^{1}\circ
g^{1})(e_{n}))&\text{ for }p=(e_{1},\ldots,e_{n})\end{cases}$
$\displaystyle=\Big{(}FP\big{(}(f^{0},f^{1})\big{)}\circ
FP\big{(}(g^{0},g^{1})\big{)}\Big{)}(p).$

######  Definition 2.1.

A proper homomorphism of graphs $f\colon E\to F$ is a homomorphism of graphs
whose both maps are finite-to-one, i.e.

$\forall\;v\in F^{0}\colon|(f^{0})^{-1}(v)|<\infty,\quad\forall\;e\in
F^{1}\colon|(f^{1})^{-1}(e)|<\infty.$

We denote the category of graphs and proper graph homomorphisms by POG.

First, observe that POG is indeed a subcategory of OG due to the fact that a
composition of finite-to-one maps is again a finite-to-one map. If
$(f^{0},f^{1})\colon E\to F$ is a proper homomorphism of graphs, then the
induced map $f\colon FP(E)\to FP(F)$ is finite to one. Indeed, if $p\in FP(E)$
is a vertex, then $f^{-1}(p)=(f^{0})^{-1}(p)$ is a finite set. Next, let
$p=(p_{1},\ldots,p_{n})$, $p_{i}\in F^{1}$ for all $1\leq i\leq n$, and $q\in
f^{-1}(p)$. Then we can write $q=(q_{1},\ldots,q_{n})$, $q_{i}\in E^{1}$ for
all $1\leq i\leq n$, and
$f(q)=(f^{1}(q_{1}),\ldots,f^{1}(q_{n}))=(p_{1},\ldots,p_{n})$. Hence,
$q_{i}\in(f^{1})^{-1}(p_{i})$ for all $1\leq i\leq n$, so the number of
elements in $f^{-1}(p)$ is limited by the number of elements in

(2.1)
$(f^{1})^{-1}(p_{1})\times\ldots\times(f^{1})^{-1}(p_{i})\times\ldots\times(f^{1})^{-1}(p_{n}),$

which is a finite set. Finally, observe also that, much as before, we can view
$FP$ as a covariant functor from the category POG to the category of sets and
finite-to-one maps.

######  Definition 2.2.

The target bijectivity condition for a graph homomorphism $(f^{0},f^{1}):E\to
F$ is

(2.2) $\forall\;x\in F^{1}\colon(f^{1})^{-1}(x)\ni e\longmapsto
t_{E}(e)\in(f^{0})^{-1}(t_{F}(x))\;\text{is bijective}.$

Note that the bijectivity of $(f^{0},f^{1})$ implies the target bijectivity of
$(f^{0},f^{1})$, so (2.2) is satisfied for $(\mathop{\rm
id}\nolimits_{E^{0}},\mathop{\rm id}\nolimits_{E^{1}})$. An injective
homomorphism of graphs need not satisfy the target-bijectivity condition.
Indeed, mapping the one-vertex graph into the one-loop graph by assigning the
vertex to the base of the loop is an injective graph homomorphism but the
target-bijectivity condition fails. A graph homomorphism $(f^{0},f^{1})\colon
E\to F$ that is injective on vertices and satisfies the target-bijectivity
condition is injective. Indeed, if $e_{1}$ and $e_{2}$ are edges such that
$f^{1}(e_{1})=f^{1}(e_{2})$, then $e_{1},e_{2}\in(f^{1})^{-1}(f^{1}(e_{1}))$
and $|(f^{1})^{-1}\big{(}t_{F}(f^{1}(e_{1}))\big{)}|=1$, so $e_{1}=e_{2}$.
Moreover, if $(f^{0},f^{1})\colon E\to F$ and $(g^{0},g^{1})\colon F\to G$ are
morphisms satisfying (2.2), then so is their composition. Indeed, for
starters,

$\forall\;y\in G^{1}\colon(g^{1}\circ f^{1})^{-1}(y)\ni e\longmapsto
t_{E}(e)\in(g^{0}\circ f^{0})^{-1}(t_{G}(y))$

the above map is well defined. Next, it follows from

$\forall\;y\in G^{1}\colon(g^{1})^{-1}(y)\ni x\longmapsto
t_{F}(x)\in(g^{0})^{-1}(t_{G}(y))\;\text{is bijective}$

that

$\forall\;y\in
G^{1}\colon(g^{0})^{-1}(t_{G}(y))=t_{F}((g^{1})^{-1}(y))=\bigsqcup_{x\in(g^{1})^{-1}(y)}\\{t_{F}(x)\\},$

so

$\forall\;y\in G^{1}\colon(g^{0}\circ
f^{0})^{-1}(t_{G}(y))=(f^{0})^{-1}\big{(}(g^{0})^{-1}(t_{G}(y))\big{)}=\bigsqcup_{x\in(g^{1})^{-1}(y)}(f^{0})^{-1}(t_{F}(x)).$

Now combining this with

$\forall\;y\in G^{1}\colon(g^{1}\circ
f^{1})^{-1}(y)=(f^{1})^{-1}\big{(}(g^{1})^{-1}(y)\big{)}=\bigsqcup_{x\in(g^{1})^{-1}(y)}(f^{1})^{-1}(x)$

and

$\forall\;y\in G^{1}\;\forall\;x\in(g^{1})^{-1}(y)\colon(f^{1})^{-1}(x)\ni
e\longmapsto t_{E}(e)\in(f^{0})^{-1}(t_{F}(x))\;\text{is bijective},$

we conclude that

$\forall\;y\in G^{1}\colon(g^{1}\circ f^{1})^{-1}(y)\ni e\longmapsto
t_{E}(e)\in(g^{0}\circ f^{0})^{-1}(t_{G}(y))\;\text{is bijective}.$

Thus, we have arrived at:

######  Lemma 2.3.

Restricting morphisms of the category POG to the morphisms satisfying the
target bijectivity condition yields a subcategory of POG.

We denote the subcategory of POG obtained in Lemma 2.3 by TBPOG.

######  Definition 2.4.

A regular homomorphism of graphs $(f^{0},f^{1})\colon E\to F$ is a
homomorphism of graphs satisfying the following condition

(2.3) $f^{0}\big{(}E^{0}\setminus\mathrm{reg}(E)\big{)}\subseteq
F^{0}\setminus\mathrm{reg}(F).$

We denote the category of graphs and proper regular homomorphisms satisfying
the target bijectivity condition by CRTBPOG and call it the admissible
category of graphs.

###  2.3. Pushouts of graphs

We refer the reader to [6] for an extensive study of pushouts of directed
graphs. In the category of sets and maps, the pushout of
$X\stackrel{{\scriptstyle f}}{{\leftarrow}}Z\stackrel{{\scriptstyle
g}}{{\to}}Y$ is

$X\stackrel{{\scriptstyle\iota_{X}}}{{\longrightarrow}}X\underset{Z}{\amalg}Y\stackrel{{\scriptstyle\iota_{Y}}}{{\longleftarrow}}Y,\quad
X\underset{Z}{\amalg}Y:=(X\amalg Y)/R_{Z}\,,$

where $R_{Z}$ is the minimal equivalence relation generated by
$f(z)R_{Z}g(z)$, $z\in Z$, and $\iota_{X}$ and $\iota_{Y}$ are the obvious
maps. In the category $OG$ of graphs and graph homomorphisms, first we will
define the pushout graph of any two graph homorphisms with the same domain,
and then prove that it yields a pushout in the just recalled categorical
sense.

Let
$E\stackrel{{\scriptstyle(f^{0},f^{1})}}{{\longleftarrow}}G\stackrel{{\scriptstyle(g^{0},g^{1})}}{{\longrightarrow}}F$
be graph homomorphisms and let $E^{i}\amalg_{G^{i}}F^{i}$ be the coresponding
pushout of $E^{i}\stackrel{{\scriptstyle
f^{i}}}{{\leftarrow}}G^{i}\stackrel{{\scriptstyle g^{i}}}{{\to}}F^{i}$,
$i=0,1$, in the category of sets. Then we have the following diagrams:

$\textstyle{G^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{1}}$$\scriptstyle{g^{1}}$$\scriptstyle{s_{G}}$$\textstyle{G^{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{0}}$$\scriptstyle{g^{0}}$$\textstyle{E^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E^{1}}}$$\scriptstyle{s_{E}}$$\textstyle{F^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{F^{1}}}$$\scriptstyle{s_{F}}$$\textstyle{E^{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E^{0}}}$$\textstyle{F^{0}\,,\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{F^{0}}}$$\textstyle{E^{1}\underset{G^{1}}{\amalg}F^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s_{\amalg}}$$\textstyle{E^{0}\underset{G^{0}}{\amalg}F^{0}}$
$\textstyle{G^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{1}}$$\scriptstyle{g^{1}}$$\scriptstyle{t_{G}}$$\textstyle{G^{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{0}}$$\scriptstyle{g^{0}}$$\textstyle{E^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E^{1}}}$$\scriptstyle{t_{E}}$$\textstyle{F^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{F^{1}}}$$\scriptstyle{t_{F}}$$\textstyle{E^{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E^{0}}}$$\textstyle{F^{0}\,.\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{F^{0}}}$$\textstyle{E^{1}\underset{G^{1}}{\amalg}F^{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{t_{\amalg}}$$\textstyle{E^{0}\underset{G^{0}}{\amalg}F^{0}}$

Here the left and right square subdiagrams commute by the definition of a
pushout, and the top subdiagrams commute by the definition of a graph
homomorphism. Moreover, $s_{\amalg}$ and $t_{\amalg}$ are defined by the
universal property of the pushout $E^{1}\amalg_{G^{1}}F^{1}$, which applies
due to the equalities

$\displaystyle\iota_{E^{0}}\circ s_{E}\circ f^{1}=\iota_{E^{0}}\circ
f^{0}\circ s_{G}=\iota_{F^{0}}\circ g^{0}\circ s_{G}=\iota_{F^{0}}\circ
s_{F}\circ g^{1}\,,$ $\displaystyle\iota_{E^{0}}\circ t_{E}\circ
f^{1}=\iota_{E^{0}}\circ f^{0}\circ t_{G}=\iota_{F^{0}}\circ g^{0}\circ
t_{G}=\iota_{F^{0}}\circ t_{F}\circ g^{1}\,,$

which in turn follow, respectively, from the aforementioned commutativity in
the above diagrams.

######  Definition 2.5.

We call the graph

$E\underset{G}{\amalg}F:=\left(E^{0}\underset{G^{0}}{\amalg}F^{0},E^{1}\underset{G^{1}}{\amalg}F^{1},s_{\amalg},t_{\amalg}\right)$

the _pushout graph_ of
$E\stackrel{{\scriptstyle(f^{0},f^{1})}}{{\longleftarrow}}G\stackrel{{\scriptstyle(g^{0},g^{1})}}{{\longrightarrow}}F$.

It is straightforward to show that $E\underset{G}{\amalg}F$ is indeed a
pushout in the category OG of graphs and graph homomorphisms.

For the purposes of our study of path algebras, we consider the following
pushout in the category of sets and maps

$\textstyle{FP(E)\underset{FP(G)}{\amalg}FP(F)}$$\textstyle{FP(E)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{FP(E)}}$$\textstyle{FP(F).\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{FP(F)}}$$\textstyle{FP(G)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{f}$

This leads to the following natural question: Under which assumptions, the
covariant functor $FP$ from the category $OG$ of graphs and graph
homomorphisms to the category of sets and maps commutes with pushouts:

$FP(E)\underset{FP(G)}{\amalg}FP(F)=FP\left(E\underset{G}{\amalg}F\right)\text{?}$

The answer is:

######  Lemma 2.6.

Let
$E\stackrel{{\scriptstyle(f^{0},f^{1})}}{{\longleftarrow}}G\stackrel{{\scriptstyle(g^{0},g^{1})}}{{\longrightarrow}}F$
be graph homomorphisms. Then there exists a natural map

$h\colon FP(E)\underset{FP(G)}{\amalg}FP(F)\longrightarrow
FP\left(E\underset{G}{\amalg}F\right).$

Moreover, if the graph homomorphisms are such that

  1. (1)

both $f^{0}$ and $g^{0}$ are injective (vertex injectivity),

  2. (2)

$t_{\amalg}(x)=s_{\amalg}(y)\;\Rightarrow\;(x,y\in\iota_{E^{1}}(E^{1})\text{
or }x,y\in\iota_{F^{1}}(F^{1}))$ (one color),

then the natural map $h$ is bijective.

###### Proof.

The natural map $FP(E)\amalg FP(F)\rightarrow FP(E\amalg_{G}F)$ exists because
$FP$ is a functor. This map descends to $h$ by the universal property of
pushouts in the category of sets and maps. Since graph homomorphisms preserve
the length of paths, we obtain the decomposition

$FP(E)\underset{FP(G)}{\amalg}FP(F)=\bigcup_{n\in\mathbb{N}}FP_{n}(E)\underset{FP_{n}(G)}{\amalg}FP_{n}(F).$

Hence, we can write $h$ on elements as follows:

$h([p]):=\begin{cases}[p]&\text{for }p\in E^{0}\amalg F^{0}\cup E^{1}\amalg
F^{1},\\\ ([a_{1}],\ldots,[a_{n}])&\text{for }p:=(a_{1},\ldots,a_{n})\in
FP(E)\amalg FP(F),\\\ &a_{i}\in E^{1}\amalg F^{1},\;1\leq i\leq
n,\;n\in\mathbb{N}\setminus\\{0,1\\}.\end{cases}$

Now, using the two assumptions, we will define the inverse of $h$. For
starters, we put

(2.4) $h^{-1}([p]):=[p]\quad\text{when}\quad p\in E^{0}\amalg F^{0}\cup
E^{1}\amalg F^{1}.$

Next, let us take $([a_{1}],\ldots,[a_{n}])\in FP(E\amalg_{G}F)$ with
$[a_{i}]\in E^{1}\amalg_{G^{1}}F^{1}$, $1\leq i\leq n$,
$n\in\mathbb{N}\setminus\\{0,1\\}$. Since
$t_{\amalg}([a_{i}])=s_{\amalg}([a_{i+1}])$ for all $1\leq i\leq n-1$, from
the one-color condition we conclude that

$\forall\;1\leq i\leq n\colon a_{i}\in E^{1}\quad\text{or}\quad\forall\;1\leq
i\leq n\colon a_{i}\in F^{1}.$

Therefore, $t_{\amalg}([a_{i}])=s_{\amalg}([a_{i+1}])$ means
$[t_{E}(a_{i})]=[s_{E}(a_{i+1})]$ or $[t_{F}(a_{i})]=[s_{F}(a_{i+1})]$. We can
apply now the vertex-injectivity condition to infer that
$t_{E}(a_{i})=s_{E}(a_{i+1})$ or $t_{F}(a_{i})=s_{F}(a_{i+1})$. Consequently,
$(a_{1},\ldots,a_{n})\in FP(E)$ or $(a_{1},\ldots,a_{n})\in FP(F)$.

Furthermore,

(2.5) $\forall\;1\leq i\leq
n\colon[a_{i}]=[b_{i}]\quad\Rightarrow\quad[(a_{1},\ldots,a_{n})]=[(b_{1},\ldots,b_{n})].$

Indeed, let $c^{1}_{i},\ldots,c^{m}_{i}\in G^{1}$ be sequences such that

$\displaystyle\forall\;1\leq i\leq n\colon f^{1}(c^{1}_{i})=a_{i}\text{ and
}g^{1}(c^{1}_{i})=a^{1}_{i}\,,\ldots,\begin{cases}g^{1}(c^{m}_{i})=a^{m-1}_{i}\text{
and }f^{1}(c^{m}_{i})=b_{i}&\text{if $m$ is even},\\\
f^{1}(c^{m}_{i})=a^{m-1}_{i}\text{ and }g^{1}(c^{m}_{i})=b_{i}&\text{if $m$ is
odd},\end{cases}$ or $\displaystyle\forall\;1\leq i\leq n\colon
g^{1}(c^{1}_{i})=a_{i}\text{ and
}f^{1}(c^{1}_{i})=a^{1}_{i}\,,\ldots,\begin{cases}g^{1}(c^{m}_{i})=a^{m-1}_{i}\text{
and }f^{1}(c^{m}_{i})=b_{i}&\text{if $m$ is odd},\\\
f^{1}(c^{m}_{i})=a^{m-1}_{i}\text{ and }g^{1}(c^{m}_{i})=b_{i}&\text{if $m$ is
even}.\end{cases}$

Note that, although for each $i$ the length of the sequence
$c^{1}_{i},\ldots,c^{m}_{i}$ might be different, we can always choose the
longest such a sequence and extend shorter sequences by the constant
extrapolation. Next, we need to prove that
$t_{G}(c^{j}_{i})=s_{G}(c^{j}_{i+1})$. Depending on the parity of $j$ and the
above alternative between $E$ and $F$, we either have

$\displaystyle[f^{1}(c^{j}_{i})]=[a_{i}]\quad\text{and}\quad[f^{1}(c^{j}_{i+1})]=[a_{i+1}]$
or
$\displaystyle[g^{1}(c^{j}_{i})]=[a_{i}]\quad\text{and}\quad[g^{1}(c^{j}_{i+1})]=[a_{i+1}].$

In the former case, by the vertex injectivity, we obtain

(2.6) $t_{E}(f^{1}(c^{j}_{i}))=t(a_{i})\quad\text{and}\quad
s_{E}(f^{1}(c^{j}_{i+1}))=s(a_{i+1}),$

where $t$ and $s$ are, respectively, $t_{E}$ and $s_{E}$, or $t_{F}$ and
$s_{F}$, depending on whether $a_{i}\in E^{1}$ or $a_{i}\in F^{1}$. It follows
from (2.6) that

$f^{0}(t_{G}(c^{j}_{i}))=t_{E}(f^{1}(c^{j}_{i}))=t(a_{i})=s(a_{i+1})=s_{E}(f^{1}(c^{j}_{i+1}))=f^{0}(s_{G}(c^{j}_{i+1})),$

so, from the injectivity of $f^{0}$, we get
$t_{G}(c^{j}_{i})=s_{G}(c^{j}_{i+1})$, as needed. In the latter case, the
reasoning is completely analogous but uses the injectivity of $g^{0}$ instead
of the injectivity of $f^{0}$. Thus we have shown that
$(c^{j}_{1},\ldots,c^{j}_{n})\in FP(G)$, $1\leq j\leq m$, is a sequence of
paths implementing the desired equivalence relation between
$(a_{1},\ldots,a_{n})$ and $(b_{1},\ldots,b_{n})$.

Finally, it follows from (2.5) that we can define
$h^{-1}(([a_{1}],\ldots,[a_{n}])):=[(a_{1},\ldots,a_{n})]$. Combining it with
(2.4) gives us a map $FP(E\amalg_{G}F)\rightarrow FP(E)\amalg FP(F)$, which
is, clearly, the inverse of $h$. ∎

Next, consider the contravariant functors $\mathrm{Map}(\cdot,K)$ and
$\mathrm{Map}_{f}(\cdot,K)$, respectively. Here $K$ is a non-empty set with a
chosen element $0\in K$ and ${\rm Map}_{f}$ denotes finite-to-one maps. The
first functor is a contravariant functor from the category of sets and maps to
the category of sets and maps:

$X\longmapsto\mathrm{Map}(X,K),\quad(X\stackrel{{\scriptstyle
f}}{{\to}}Y)\longmapsto\left(\mathrm{Map}(Y,K)\stackrel{{\scriptstyle
f^{*}}}{{\to}}\mathrm{Map}(X,K)\right),\quad f^{*}(F):=F\circ f.$

Much in the same way, the second functor is a contravariant functor from the
category of sets and finite-to-one maps to the category of sets and maps:

$X\longmapsto\mathrm{Map}_{f}(X,K),\quad(X\stackrel{{\scriptstyle
f}}{{\to}}Y)\longmapsto\left(\mathrm{Map}_{f}(Y,K)\stackrel{{\scriptstyle
f^{*}}}{{\to}}\mathrm{Map}_{f}(X,K)\right),\quad f^{*}(F):=F\circ f.$

Here
$\mathrm{Map}_{f}(X,K):=\\{F\in\mathrm{Map}(X,K)\;|\;|F^{-1}(K\setminus\\{0\\})|<\infty\\}$,
and

$|(F\circ
f)^{-1}(K\setminus\\{0\\})|=|f^{-1}(F^{-1}(K\setminus\\{0\\}))|<\infty$

because a finite union of finite sets is a finite set.

We have the following lemma whose routine proof we omit.

######  Lemma 2.7.

Let $Y$ be any set. Then $\mathrm{Map}(\cdot,Y)$ is a contravariant functor
from the category of sets and maps to the category of sets and maps
transforming pushouts to pullbacks.

The same result is true for the functor ${\rm Map}_{f}(\cdot,Y)$. However, the
category of sets and finite-to-one maps is not closed with respect to
pushouts. In this context, we have the following result.

######  Lemma 2.8.

Let

$\textstyle{P}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{X}}$$\textstyle{Y\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{Y}}$$\textstyle{Z\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{f}$

be a pushout diagram in the category of sets and maps. If one of the maps $f$
and $g$ is injective and the other one is finite to one, then the above
diagram is a pushout diagram in the category of sets and finite-to-one maps.

###### Proof.

Assume without the loss of generality that $f$ is injective and $g$ is finite
to one. Then the canonical maps of their pushout

$X\stackrel{{\scriptstyle\iota_{X}}}{{\longrightarrow}}X\underset{Z}{\amalg}Y\stackrel{{\scriptstyle\iota_{Y}}}{{\longleftarrow}}Y$

are also finite to one. Indeed, if $\iota_{Y}(y_{1})=\iota_{Y}(y_{2})$, then
$y_{1}=y_{2}$ or there exists a finite sequence $(z_{1},\ldots,z_{2n})\in
Z^{2n}$ such that

$g(z_{1})=y_{1}\text{ and }f(z_{1})=x_{1}\,,\ldots,f(z_{2n})=x_{2n}\text{ and
}g(z_{2n})=y_{2}\,.$

In the latter case, from the injectivity of $f$, we also conclude that
$y_{1}=y_{2}$, so $\iota_{Y}$ is injective. Next, if
$\iota_{X}(x_{1})=\iota_{X}(x_{2})$, then $x_{1}=x_{2}$ or there exists a
finite sequence $(z_{1},\ldots,z_{2m})\in Z^{2m}$ such that

$f(z_{1})=x_{1}\text{ and }g(z_{1})=y_{1}\,,\ldots,g(z_{2m})=y_{2m}\text{ and
}f(z_{2m})=x_{2}\,.$

It follows from the injectivity of $f$ that all $y_{i}$ are equal to
$g(z_{1})$, where $z_{1}$ is uniquely determined by $x_{1}$, so we can denote
all of them $y$. Consequently, all $z_{i}$ in such sequence are in
$g^{-1}(y)$, which is a finite set by assumption. Hence, as any $x_{2}$ such
that $\iota_{X}(x_{1})=\iota_{X}(x_{2})$ either equals to $x_{1}$ or belongs
to the finite set $f(g^{-1}(y))$, the map $\iota_{X}$ is finite to one.

Finally, if $j_{X}\colon X\to Q$ and $j_{Y}\colon Y\to Q$ are finite-to-one
maps such that $j_{X}\circ f=j_{Y}\circ g$, then the universal-property map
$h\colon P\to Q$ is also finite to one. Indeed, suppose that the set
$h^{-1}(q)$ is infinite for some $q\in Q$. Then, as
$P=\iota_{X}(X)\cup\iota_{Y}(Y)$, one of the sets $h^{-1}(q)\cap\iota_{X}(X)$
and $h^{-1}(q)\cap\iota_{Y}(Y)$ is infinite, which contradicts the assumption
that both $j_{X}=h\circ\iota_{X}$ and $j_{Y}=h\circ\iota_{Y}$ are finite to
one. ∎

######  Lemma 2.9.

Let $K$ be a non-empty set with a chosen element $0\in K$, let $f$ be an
injective map, and let

$\textstyle{X\underset{Z}{\amalg}Y}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{X}}$$\textstyle{Y\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{Y}}$$\textstyle{Z\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{f}$

be a pushout diagram in the category of sets and finite-to-one maps. Then

$\mathrm{Map}_{f}\left(X\underset{Z}{\amalg}Y,K\right)=\mathrm{Map}_{f}(X,K)\underset{\mathrm{Map}_{f}(Z,K)}{\times}\mathrm{Map}_{f}(Y,K),$

and the contravariant functor $\mathrm{Map}_{f}(\cdot,K)$ transforms the above
pushout diagram into the pullback diagram

(2.7)
$\textstyle{\mathrm{Map}_{f}\left(X\underset{Z}{\amalg}Y,K\right)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{Y}^{*}}$$\scriptstyle{\iota_{X}^{*}}$$\textstyle{\mathrm{Map}_{f}(X,K)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{*}}$$\textstyle{\mathrm{Map}_{f}(Y,K)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{*}}$$\textstyle{\mathrm{Map}_{f}(Z,K).}$

in the category of sets and maps.

######  Lemma 2.10.

Let

$\textstyle{P}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota^{0}_{E},\iota^{1}_{E})}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota^{0}_{F},\iota^{1}_{F})}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(g^{0},g^{1})}$$\scriptstyle{(f^{0},f^{1})}$

be a one-injective pushout diagram in the category POG of graphs and graph
homomorphisms. If $(f^{0},f^{1})$ and $(g^{0},g^{1})$ are regular and satisfy
the target bijectivity condition, then the same is true for
$(\iota_{E}^{0},\iota_{E}^{1})$ and $(\iota_{F}^{0},\iota_{F}^{1})$.

###### Proof.

a ∎

The following straightforward lemma will be needed in the last section of the
paper.

######  Lemma 2.11.

Let

(2.8)
$\textstyle{E\underset{G}{\amalg}F}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota_{E}^{0},\iota_{E}^{1})}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota_{F}^{0},\iota_{F}^{1})}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(g^{0},g^{1})}$$\scriptstyle{(f^{0},f^{1})}$

be a pushout diagram in the admissible category of graphs. Then

$s^{-1}_{E}(w)\cap t^{-1}_{E}(E^{0}\setminus
f^{0}(G^{0}))=(\iota_{E}^{1})^{-1}(s^{-1}_{{\amalg}}(p)\cap
t^{-1}_{{\amalg}}((E\underset{G}{\amalg}F)^{0}\setminus\iota_{F}^{0}(F^{0})))$

for any two vertices $w\in E^{0}$ and $p\in(E\underset{G}{\amalg}F)^{0}$ such
that $(\iota_{E}^{0})^{-1}(p)=\\{w\\}$.

###### Proof.

Throughout the proof, let $P:=E\underset{G}{\amalg}F$. First, let $e\in
s^{-1}_{E}(w)\cap t^{-1}_{E}(E^{0}\setminus f^{0}(G^{0}))$. Then

$s_{P}(\iota_{E}^{1}(e))=\iota_{E}^{0}(s_{E}(e))=\iota_{E}^{0}(w)=p.$

Since $t_{E}(e)\notin f^{0}(G^{0})$ and $P$ is given by a pushout
construction, we have that

$t_{P}(\iota_{E}^{1}(e))=\iota_{E}^{0}(t_{E}(e))\notin\iota_{F}^{0}(F^{0}).$

Therefore, $e\in(\iota_{E}^{1})^{-1}(s^{-1}_{P}(p)\cap
t^{-1}_{P}(P^{0}\setminus\iota_{F}^{0}(F^{0})))$.

To prove the other inclusion, take an edge $e\in E^{1}$ such that
$\iota^{1}_{E}(e)\in s^{-1}_{P}(p)\cap
t^{-1}_{P}(P^{0}\setminus\iota_{F}^{0}(F^{0}))$. Since
$\iota_{E}^{0}(s_{E}(e))=s_{P}(\iota_{E}^{1}(e))=p$ and
$(\iota_{E}^{0})^{-1}(p)=\\{w\\}$, we conclude that $e\in s^{-1}_{E}(w)$.
Finally, since
$\iota_{E}^{0}(t_{E}(e))=t_{P}(\iota_{E}^{1}(e))\notin\iota_{F}^{0}(F^{0})$
and $P$ is given by a pushout construction, we obtain that $t_{E}(e)\notin
f^{0}(G^{0})$. ∎

###  2.4. Unions of graphs

Let $E$ and $F$ be directed graphs. If there is an injective graph
homomorphism $(f^{0},f^{1}):E\hookrightarrow F$, then we say that $E$ is a
subgraph of $F$, which we write as $E\subseteq F$.

Let $F$ and $G$ be graphs. Assume that $s_{F}$ and $t_{F}$ agree,
respectively, with $s_{G}$ and $t_{G}$ on $F^{1}\cap G^{1}$. Then we can
define the intersection graph

$F\cap G:=(F^{0}\cap G^{0},F^{1}\cap G^{1},s_{\cap},t_{\cap}),$

where $s_{\cap},t_{\cap}:F^{1}\cap G^{1}\to F^{0}\cap G^{0}$,

$\forall\;e\in F^{1}\cap G^{1}:\quad s_{\cap}(e)=s_{G}(e)=s_{F}(e),\quad
t_{\cap}(e)=t_{G}(e)=t_{F}(e).$

Next, assume that $s_{F}$ and $t_{F}$ agree, respectively, with $s_{G}$ and
$t_{G}$ on $F^{1}\cap G^{1}$. Then we can define the union graph

$F\cup G:=(F^{0}\cup G^{0},F^{1}\cup G^{1},s_{\cup},t_{\cup}),$

where $s_{\cup},t_{\cup}:F^{1}\cup G^{1}\to F^{0}\cup G^{0}$,

$\forall\;e\in F^{1}\cup G^{1}:\quad
s_{\cup}(e):=\begin{cases}s_{F}(e)&\text{for}\;e\in F^{1},\\\
s_{G}(e)&\text{for}\;e\in G^{1},\end{cases}\quad\text{and}\quad
t_{\cup}(e):=\begin{cases}t_{F}(e)&\text{for}\;e\in F^{1},\\\
t_{G}(e)&\text{for}\;e\in G^{1}.\end{cases}$

The intersection graph $F\cap G$ is a subgraph of both $F$ and $G$, and both
$F$ and $G$ are subgraphs of the union graph $F\cup G$. The intersection graph
$F\cap G$ exists if and only if the union graph $F\cup G$ exists.

Now we introduce the concept of hereditary and saturated subsets of the set of
vertices in a graph. Let $E$ be a graph. A subset $H\subseteq E^{0}$ is called
hereditary if any edge starting at $v\in H$ ends at $w\in H$. A vertex $v\in
H$ is called a prodigal vertex for $H$ in $E$ if it emits an edge ending
beyond $H$. Note that in the above definition one can replace the word “edge”
by the phrase “finite path”. Indeed, if $H$ is path-hereditary, then it is, in
particular, edge-hereditary. Also, if $H$ is not path hereditary, then there
exists a path starting in $H$ and ending outside of $H$. Such a path must
contain an edge starting at $H$ and ending outside of $H$, so it is also not
edge-hereditary. This proves the equivalence of these two definitions. Next,
let $H\subseteq E^{0}$ and set $F^{0}:=E^{0}\setminus H$ and
$F^{1}:=E^{1}\setminus t_{E}^{-1}(H)$. Then the formulas $s_{F}(e):=s(e)$,
$t_{F}(e):=t(e)$, for any $e\in F^{1}$, define a subgraph of $E$ if and only
if $H$ is hereditary.

A subset $H\subseteq E^{0}$ is called saturated if there does not exist a
regular vertex $v\in E^{0}\setminus H$ such that
$t_{E}(s_{E}^{-1}(v))\subseteq H$. Such a vertex is called a desaturating
vertex for $H$ in $E$. The intersection of all saturated subsets of $E^{0}$
containing $H$ is called the saturation of $H$ and is denoted by
$\overline{H}$. The saturation of any subset $H\subseteq E^{0}$ is the
smallest saturated subset contaning $H$. In particular, $H$ is saturated if
and only if it is equal to its saturation: $H=\overline{H}$.

Let $H\subseteq E^{0}$. We say that $v\in E^{0}$ is a breaking vertex for $H$
if

$v\in E^{0}\setminus H,\qquad|s^{-1}_{E}(v)|=\infty,\qquad\text{and}\qquad
0<|s^{-1}_{E}(v)\cap t^{-1}_{E}(E^{0}\setminus H)|<\infty.$

We define the set

$B_{H}:=\\{v\in E^{0}\setminus H~{}|~{}v\text{ is a breaking vertex for
}H\\}.$

A subset $H$ of $E^{0}$ is called _unbroken_ if and only if $B_{H}=\emptyset$.
Note that a breaking vertex of $H$ becomes regular in the subgraph obtained by
removing all vertices in $H$ and all edges ending in $H$.

Now we are ready to bundle up the three properties of being hereditary,
saturated and unbroken to restrict subgraphs to these that played a crucial
role in [9].

######  Definition 2.12.

An injective graph homomorphism $(f^{0},f^{1}):E\hookrightarrow F$ is called
admissible if it satisfies the following conditions:

  1. (A1)

$F^{0}\setminus f^{0}(E^{0})$ is saturated,

  2. (A2)

$t^{-1}_{F}(f^{0}(E^{0}))\subseteq f^{1}(F^{1})$.

We call an admissible inclusion _strongly admissible_ iff, in addition, the
subset $F^{0}\setminus f^{0}(E^{0})$ is unbroken. Furthermore, we call
intersecting graphs $F$ and $G$ (strongly) admissible if $F\cap G$ is a
(strongly) admissible subgraph in both $F$ and $G$. Much in the same way, we
call taking the union of graphs $F$ and $G$ (strongly) admissible if both $F$
and $G$ are (strongly) admissible subgraphs of $F\cup G$.

The above definition already appeared in [5, Definition 3.1] (see also [9,
Definition 2.1]), where it is also assumed that $f^{1}(E^{1})\subseteq
t^{-1}_{F}(f^{0}(E^{0}))$ and $F^{0}\setminus f^{0}(E^{0})$ is hereditary and
unbroken. However, the first condition is always true for any graph
homomorphism. Furthermore, the following proposition shows that hereditarity
follows from the condition (A2).

######  Proposition 2.13.

Let $(f^{0},f^{1}):E\to F$ be a graph homomorphism such that
$t_{F}^{-1}(f^{0}(E^{0}))\subseteq f^{1}(E^{1})$. Then $F^{0}\setminus
f^{0}(E^{0})$ is hereditary.

###### Proof.

Suppose that $F^{0}\setminus f^{0}(E^{0})$ is not hereditary, i.e. for some
$x\in F^{1}$ such that $s_{F}(x)\in F^{0}\setminus f^{0}(E^{0})$ we have that
$t_{F}(x)\in f^{0}(E^{0})$. Since $t_{F}^{-1}(f^{0}(E^{0}))\subseteq
f^{1}(E^{1})$, there is an edge $e\in F^{1}$ such that $f^{1}(e)=x$. Then
$s_{E}(x)=s_{E}(f^{1}(e))=f^{0}(s_{F}(e))$, which gives rise to a
contradiction. ∎

Next, we turn to unbroken subsets. Our next result shows that the assumption
of strong admissibility of taking the union in [9, Theorem 3.1] is
superfluous.

######  Proposition 2.14.

Let $F$ and $G$ be arbitrary graphs whose source and target maps agree,
respectively, on $F^{1}\cap G^{1}$. Then, if intersecting $F$ and $G$ is
strongly admissible so is taking the union of $F$ and $G$.

###### Proof.

The proof that admissibility of the union follows from the admissibility of
the intersection is in [9, Lemmas 2.2 and 2.3]. Assume that intersecting $F$
and $G$ is strongly admissible. Then, to prove that also taking the union of
$F$ and $G$ is strongly admissible, it suffices to show that both $(F^{0}\cup
G^{0})\setminus F^{0}$ and $(F^{0}\cup G^{0})\setminus G^{0}$ are unbroken in
$F\cup G$. To this end, suppose that $v\in F^{0}$ is a breaking vertex for
$(F^{0}\cup G^{0})\setminus F^{0}$ in $F\cup G$. Then $v$ emits inifinitely
many edges ending in $G^{0}\setminus F^{0}$, so $v\in F^{0}\cap G^{0}$. Also,
all these edges are from $G^{1}$. Furthermore, $v$ emits at least one and at
most finitely many edges ending in $F^{0}$. If all of them end in
$F^{0}\setminus G^{0}$, then they are all from $F^{1}$, and they render
$F^{0}\setminus G^{0}$ not saturated in $F$, which is not allowed by the
admissibility of $(F\cap G)\subseteq F$. Therefore, $v$ emits at least one
edge $e$ ending in $F^{0}\cap G^{0}$. Now, from the admissibility of $(F\cap
G)\subseteq F$ and $(F\cap G)\subseteq G$, we obtain

$e\in t_{\cup}^{-1}(F^{0}\cap G^{0})=t_{F}^{-1}(F^{0}\cap G^{0})\cup
t_{G}^{-1}(F^{0}\cap G^{0})=F^{1}\cap G^{1},$

so $e\in G^{1}$. Also, since $v$ emits only finitely many edges into $F^{0}$,
in particular it emits only finitely many edges from $G^{1}$ ending in
$F^{0}\cap G^{0}$. All this makes $v$ a breaking vertex for $G^{0}\setminus
F^{0}$ in $G$, which contradicts the strong admissibility of $(F\cap
G)\subseteq G$. Hence, $(F^{0}\cup G^{0})\setminus F^{0}$ is unbroken in
$F\cup G$. As before, the symmetric argument shows that also $(F^{0}\cup
G^{0})\setminus G^{0}$ is unbroken in $F\cup G$. ∎

Finally, let us show that admissible inclusions are special cases of morphisms
in the category CRTBPOG. This is why we say that CRTBPOG is the admissible
category of graphs.

######  Proposition 2.15.

Let $(f^{0},f^{1}):E\hookrightarrow F$ be an injective graph homomorphism.
Then $(f^{0},f^{1})$ is admissible if and only if it is a morphism in the
category CRTBPOG.

###### Proof.

($\Rightarrow$) Since $(f^{0},f^{1})$ is injective, it is clearly proper.
Next, we check regularity, i.e. whether

$f^{0}(E^{0}\setminus{\rm reg}(E))\subseteq F^{0}\setminus{\rm reg}(F).$

Since infinite emitters in the subgraph remain infinite emitters in the graph,
it suffices to prove the result for sinks. Assume that $v\in E^{0}$ is a sink.
Then $f^{0}(v)\in F^{0}\setminus{\rm reg}(F)$. Indeed, suppose that $f^{0}(v)$
is regular in $F$. From (A2), we would have that
$t_{F}(s^{-1}_{F}(f^{0}(v)))\subseteq F^{0}\setminus f^{0}(E^{0})$. However,
this contradicts the fact that $F^{0}\setminus f^{0}(E^{0})$ is saturated.
Finally, we have to show that the target bijectivity condition is satisfied,
namely that for all $x\in F^{1}$, the map

$(f^{1})^{-1}(x)\ni e\longmapsto t_{E}(e)\in(f^{0})^{-1}(t_{F}(x))$

is bijective. Due to the injectivity of $(f^{0},f^{1})$ we have that, for any
$x\in F^{1}$, the sets $(f^{1})^{-1}(x)$ and $(f^{0})^{-1}(t_{F}(x))$ are
either empty or consist of a single element. To prove the claim, it suffices
to exclude the possibility in which one of these sets is empty and the other
is not. First, if $(f^{1})^{-1}(x)=\\{e\\}$, then
$t_{E}(e)\in(f^{0})^{-1}(t_{F}(x))$. Next, since
$t_{F}^{-1}(f^{0}(E^{0}))\subseteq f^{1}(E^{1})$, if
$(f^{0})^{-1}(t_{F}(x))=\\{v\\}$, then $(f^{1})^{-1}(x)\neq\emptyset$.

($\Leftarrow$) Assume that $(f^{0},f^{1}):E\hookrightarrow F$ is a morphism in
CRTBPOG. First, let us prove that $t_{F}^{-1}(f^{0}(E^{0}))\subseteq
f^{1}(E^{1})$. Let $x\in F^{1}$ be such that $t_{F}(x)\in f^{0}(E^{0})$. This
implies that there is $v\in E^{0}$ such that $f^{0}(v)=t_{F}(x)$. In turn,
from the target bijectivity condition, we infer that there exists
$e\in(f^{1})^{-1}(x)$ such that $t_{E}(e)=v$. It is left to prove that
$F^{0}\setminus f^{0}(E^{0})$ is saturated. To this end, suppose that there is
a regular vertex $w\in f^{0}(E^{0})$ such that $t_{F}(s^{-1}_{F}(w))\subseteq
F^{0}\setminus f^{0}(E^{0})$. From (A2), we obtain that $s^{-1}_{F}(w)\cap
f^{1}(E^{1})=\emptyset$. If $v\in E^{0}$ is such that $f^{0}(v)=w$, it follows
that $s^{-1}_{E}(v)=\emptyset$, which contradicts the regularity of
$(f^{0},f^{1})$. ∎

Therefore, whenever intersecting graphs $F$ and $G$ is admissible, then taking
their union gives rise to a pushout in the admissible category of graphs.

##  3\. Graph algebras as contravariant functors

###  3.1. Path algebras

Let $k$ be a field, $E$ be any non-empty graph, and $FP(E)$ be the set of all
its finite paths. Consider the vector space

$kE:=\\{f\in{\rm Map}(FP(E),k)~{}|~{}f(p)\neq 0\text{ for finitely many }p\in
FP(E)\\},$

where ${\rm Map}(FP(E),k)$ is the vector space of all functions from $FP(E)$
to $k$ in which the addition and scalar multiplication are pointwise. Then the
set of functions $\\{\chi_{p}\\}_{p\in FP(E)}$ given by

$\chi_{p}(q)=\begin{cases}1&\text{for }p=q,\\\ 0&\text{otherwise},\end{cases}$

is a linear basis of $kE$. Next, we will use $\\{\chi_{p}\\}_{p\in FP(E)}$ to
define a bilinear map:

$m:kE\times kE\longrightarrow kE,\qquad
m(\chi_{p},\chi_{q}):=\begin{cases}\chi_{pq}&\text{if }t(p)=s(q),\\\
0&\text{otherwise}.\end{cases}$

The bilinear map $m:kE\times kE\to kE$ defines an algebra structure on $kE$
and the thus constructed algebra is called the path algebra of $E$. If
$E=\emptyset$, then $kE:=0$. The path algebra $kE$ is $\mathbb{N}$-graded by
the length of paths.

Let $KA$ denote the category of algebras over $k$ together with algebra
homomorphisms and let $UKA$ denote the category of unital algebras over $k$
together with unital algebra homomorphisms.

######  Proposition 3.1.

The assignment

$\displaystyle\mathrm{Obj}({\rm POG})\ni
E\stackrel{{\scriptstyle\mathrm{Map}_{f}}}{{\longmapsto}}kE\in\mathrm{Obj}(KA),$
$\displaystyle\mathrm{Mor}({\rm POG})\ni((f^{0},f^{1})\colon E\to
F)\stackrel{{\scriptstyle\mathrm{Map}_{f}}}{{\longmapsto}}(f^{*}\colon kF\to
kE)\in\mathrm{Mor}(KA),$ (3.1) $\displaystyle
kF\ni\chi_{p}\stackrel{{\scriptstyle f^{*}}}{{\longmapsto}}\sum_{q\in
f^{-1}(p)}\chi_{q}\in kE\,,$

where $f\colon FP(E)\to FP(F)$ is the map induced by $(f^{0},f^{1})$, defines
a contravariant functor. Furthermore, the same assignment restricted to the
subcategory given by graphs with finitely many vertices yields a contravariant
functor to the category $UKA$.

###### Proof.

If $f\colon FP(E)\to FP(F)$ is finite-to-one, then the sum in (3.3) is well
defined. Furthermore, for any $r\in FP(E)$ and $p\in FP(F)$, we have:

$f^{*}(\chi_{p})(r):=\left(\sum_{q\in
f^{-1}(p)}\chi_{q}\right)(r)=\left(\sum_{q\in
f^{-1}(p)}\delta_{q,r}\right)=\delta_{p,f(r)}=\chi_{p}(f(r))=(\chi_{p}\circ
f)(r).$

Hence, $f^{*}$ is the pullback linear map

$f^{*}\colon\mathrm{Map}_{f}(FP(F),k)\ni\alpha\longmapsto\alpha\circ
f\in\mathrm{Map}_{f}(FP(E),k).$

The contravariance is obvious because $(f\circ g)^{*}=g^{*}\circ f^{*}$.

To check that it is an algebra homomorphism, using the fact that $f$ preserves
the length of paths, we compute:

$\displaystyle f^{*}(\chi_{p}\chi_{q})$
$\displaystyle=\delta_{t_{F}(p),s_{F}(q)}f^{*}(\chi_{pq})=\delta_{t_{F}(p),s_{F}(q)}\sum_{r\in
f^{-1}(pq)}\chi_{r}$ $\displaystyle=\sum_{\begin{subarray}{c}r_{1}\in
f^{-1}(p)\\\ r_{2}\in
f^{-1}(q)\end{subarray}}\delta_{t_{E}(r_{1}),s_{E}(r_{2})}\chi_{r_{1}r_{2}}=\sum_{r_{1}\in
f^{-1}(p)}\chi_{r_{1}}\sum_{r_{2}\in f^{-1}(q)}\chi_{r_{2}}$
$\displaystyle=f^{*}(\chi_{p})f^{*}(\chi_{q}).$

Here, in the third step, we used the implication

$t_{F}(p)\neq s_{F}(q)\quad\Rightarrow\quad\forall\;r_{1}\in
f^{-1}(p),\,r_{2}\in f^{-1}(q)\colon t_{E}(r_{1})\neq s_{E}(r_{2}).$

Finally, the unitality of $f^{*}$ for unital path algebras follows from the
fact that $f^{-1}(F^{0})=E^{0}$:

$f^{*}(1)=f^{*}\left(\sum_{v\in F^{0}}\chi_{v}\right)=\sum_{w\in
f^{-1}(F^{0})}\chi_{w}=\sum_{w\in E^{0}}\chi_{w}=1\,.$

∎

###  3.2. Leavitt path algebras

Let $E=(E^{0},E^{1},s_{E},t_{E})$ be a graph. The extended graph
$\bar{E}:=(\bar{E}^{0},\bar{E}^{1},s_{\bar{E}},t_{\bar{E}})$ of the graph $E$
is given as follows:

$\bar{E}^{0}:=E^{0},\quad\bar{E}^{1}:=E^{1}\sqcup(E^{1})^{*},\quad(E^{1})^{*}:=\\{e^{*}~{}|~{}e\in
E^{1}\\},$ $\forall\;e\in E^{1}:\quad s_{\bar{E}}(e):=s_{E}(e),\quad
t_{\bar{E}}(e):=t_{E}(e),$ $\forall\;e^{*}\in(E^{1})^{*}:\quad
s_{\bar{E}}(e^{*}):=t_{E}(e),\quad t_{\bar{E}}(e^{*}):=s_{E}(e).$

Observe that every graph homomorphism $(f^{0},f^{1})\colon E\to F$ can be
extended to a graph homomorphism
$(\bar{f}^{0},\bar{f}^{1})\colon\bar{E}\to\bar{F}$ as follows

$\bar{f}^{0}(v):=f^{0}(v),\quad v\in
E^{0}=\bar{E}^{0},\quad\bar{f}^{1}(e):=f^{1}(e),\quad e\in
E^{0},\quad\bar{f}^{1}(e^{*}):=f^{1}(e)^{*},\quad e^{*}\in(E^{1})^{*}.$

We state the following straightforward result without a proof.

######  Lemma 3.2.

The assignment

$E\mapsto\bar{E},\qquad(f^{0},f^{1})\mapsto(\bar{f}^{0},\bar{f}^{1}),$

defines an endofunctor of the category OG of graphs and graph homomorphisms.
Furthermore, it restricts to an endofunctor of the category POG of graphs and
proper graph homomorphisms.

The Leavitt path algebra $L_{k}(E)$ of a graph $E$ is the quotient of the path
algebra $k\bar{E}$ of the extended graph $\bar{E}$ by the ideal generated by
the union of the following sets:

  1. (CK1)

$\\{\chi_{e^{*}}\chi_{f}-\delta_{e,f}\chi_{t(e)}~{}|~{}e,f\in E^{1}\\}$,

  2. (CK2)

$\Big{\\{}\chi_{v}-\sum_{e\in
s^{-1}_{E}(v)}\chi_{e}\chi_{e^{*}}~{}\Big{|}~{}v\in{\rm reg}(E)\Big{\\}}$.

Recall that ${\rm reg}(E)$ is the set of regular vertices of $E$. The elements
of $L_{k}(E)$ will be denoted by $[\chi_{p}]$ for any $p\in FP(\bar{E})$. The
algebra $L_{k}(E)$ is $\mathbb{Z}$-graded by lengths of paths, where edges
from $(E^{1})^{*}$ have length $-1$. Every $\mathbb{Z}$-graded two-sided ideal
$I$ of $L_{k}(E)$ is generated by the set

(3.2) $\\{[\chi_{v}]~{}|~{}v\in H\\}\cup\Big{\\{}[\chi_{w}]-\sum_{e\in
s^{-1}_{E}(w)\cap\,t_{E}^{-1}(E^{0}\setminus
H)}[\chi_{e}][\chi_{e^{*}}]~{}\Big{|}~{}w\in B_{H}\Big{\\}}$

for a hereditary saturated subset $H$ of $E^{0}$ defined as follows

(3.3) $H:=\\{v\in E^{0}~{}|~{}[\chi_{v}]\in I\\}$

(see, e.g., [1, Theorem 2.4.8]).

Let $KA$ denote the category of algebras over $k$ together with algebra
homomorphisms and $UKA$ denote its subcategory of unital algebras and unital
homomorphisms. The next theorem exploits the contravariant functoriality of
the Leavitt path algebra construction when restricted to the admissible
category of graphs CRTBPOG.

######  Theorem 3.3.

The assignment

$\displaystyle\mathrm{Obj}({\rm CRTBPOG})\ni
E\stackrel{{\scriptstyle}}{{\longmapsto}}L_{k}(E)\in\mathrm{Obj}(KA),$
$\displaystyle\mathrm{Mor}({\rm CRTBPOG})\ni((f^{0},f^{1})\colon E\to
F)\stackrel{{\scriptstyle}}{{\longmapsto}}\big{(}\bar{f}^{*}\colon L_{k}(F)\to
L_{k}(E)\big{)}\in\mathrm{Mor}(KA),$ $\displaystyle
L_{k}(F)\ni[\chi_{p}]\stackrel{{\scriptstyle\bar{f}^{*}}}{{\longmapsto}}\sum_{q\in\bar{f}^{-1}(p)}[\chi_{q}]\in
L_{k}(E)\,,$ $\displaystyle\text{ where }\bar{f}\colon FP(\bar{E})\to
FP(\bar{F})\text{ is the map induced by }(f^{0},f^{1}),$

defines a contravariant functor. Furthermore, the same assignment restricted
to the subcategory given by graphs with finitely many vertices yields a
contravariant functor to the category $UKA$.

###### Proof.

It follows from Proposition 3.1 combined with Lemma 3.2 that we have a
contravariant functor

$\displaystyle\mathrm{Obj}({\rm POG})\ni
E\stackrel{{\scriptstyle}}{{\longmapsto}}k\bar{E}\in\mathrm{Obj}(KA),$
$\displaystyle\mathrm{Mor}({\rm POG})\ni((f^{0},f^{1})\colon E\to
F)\stackrel{{\scriptstyle}}{{\longmapsto}}\big{(}\bar{f}^{*}\colon k\bar{F}\to
k\bar{E}\big{)}\in\mathrm{Mor}(KA),$ $\displaystyle
k\bar{F}\ni\chi_{p}\stackrel{{\scriptstyle\bar{f}^{*}}}{{\longmapsto}}\sum_{q\in\bar{f}^{-1}(p)}\chi_{q}\in
k\bar{E}\,.$

To complete the proof of the first statement, it suffices to show that
$\bar{f}^{*}$ descends to a homomorphism $L_{k}(F)\to L_{k}(E)$ when we
restrict to the admissible category of graphs without losing the functoriality
of the above assignment. First, we have to demonstrate that

$\forall\;f\in\mathrm{Mor}({\rm CRTBPOG})\;\forall\;x,y\in
F^{1}\colon[\bar{f}^{*}(\chi_{x^{*}})][\bar{f}^{*}(\chi_{y})]=\delta_{x,y}[\bar{f}^{*}(\chi_{t_{F}(x)})],$

which is equivalent to

(3.4) $\forall\;f\in\mathrm{Mor}({\rm CRTBPOG})\;\forall\;x,y\in
F^{1}\colon\sum_{e_{x}\in f^{-1}(x),\,e_{y}\in
f^{-1}(y)}[\chi_{e_{x}^{*}}][\chi_{e_{y}}]=\delta_{x,y}\sum_{v\in
f^{-1}(t_{F}(x))}[\chi_{v}].$

For $x\neq y$, we have $f^{-1}(x)\cap f^{-1}(y)=\emptyset$, so (3.4) clearly
holds. For $x=y$, using the target bijectivity condition (2.2), we compute:

$\sum_{e_{1},\,e_{2}\in f^{-1}(x)}[\chi_{e_{1}^{*}}][\chi_{e_{2}}]=\sum_{e\in
f^{-1}(x)}[\chi_{e^{*}}][\chi_{e}]=\sum_{e\in
f^{-1}(x)}[\chi_{t_{E}(e)}]=\sum_{v\in f^{-1}(t_{F}(x))}[\chi_{v}].$

Next, we show that

(3.5) $\forall\;w\in\mathrm{reg}(F)\colon\sum_{x\in
s_{F}^{-1}(w)}\sum_{e_{1},e_{2}\in(f^{1})^{-1}(x)}[\chi_{e_{1}}][\chi_{e_{2}^{*}}]=\sum_{v\in(f^{0})^{-1}(w)}[\chi_{v}].$

For starters, note that (2.3) is equivalent to

$(f^{0})^{-1}(\mathrm{reg}(F))\subseteq\mathrm{reg}(E),$

so

$\displaystyle\sum_{v\in(f^{0})^{-1}(w)}[\chi_{v}]$
$\displaystyle=\sum_{v\in(f^{0})^{-1}(w)}\sum_{e\in
s_{E}^{-1}(v)}[\chi_{e}][\chi_{e^{*}}]=\sum_{e\in(f^{0}\circ
s_{E})^{-1}(w)}[\chi_{e}][\chi_{e^{*}}]$ $\displaystyle=\sum_{e\in(s_{F}\circ
f^{1})^{-1}(w)}[\chi_{e}][\chi_{e^{*}}]=\sum_{x\in
s_{F}^{-1}(w)}\sum_{e\in(f^{1})^{-1}(x)}[\chi_{e}][\chi_{e^{*}}].$

Next, using the target bijectivity condition (2.2), now we compute the left-
hand side of (3.5):

$\sum_{x\in
s_{F}^{-1}(w)}\sum_{e_{1},e_{2}\in(f^{1})^{-1}(x)}[\chi_{e_{1}}][\chi_{e_{2}^{*}}]=\sum_{x\in
s_{F}^{-1}(w)}\sum_{e\in(f^{1})^{-1}(x)}[\chi_{e}][\chi_{e^{*}}].$

Summarizing, we have proved that $\bar{f}^{*}$ descends to an algebra
homomorphism $L_{k}(F)\to L_{k}(E)$. The functoriality of the assignment ${\rm
Mor}({\rm CRTBPOG})\ni(f^{0},f^{1})\mapsto\bar{f}^{*}\in{\rm Mor}(KA)$ is
immediate.

Finally, the unitality of $\bar{f}^{*}$ for graphs with finitely many vertices
follows from the fact that
$\bar{f}^{-1}(\bar{F}^{0})=f^{-1}(F^{0})=E^{0}=\bar{E}^{0}$:

$\bar{f}^{*}(1)=\sum_{v\in F^{0}}[\bar{f}^{*}(\chi_{v})]=\sum_{w\in
f^{-1}(F^{0})}[\chi_{w}]=\sum_{w\in E^{0}}[\chi_{w}]=1\,.$

∎

##  4\. Pullbacks of graph algebras from pushouts of graphs

In this section, we prove our main theorems stating under which conditions the
two contravariant functors given by Proposition 3.1 and Theorem 3.3 turn
pushouts of directed graphs into pullbacks of algebras. We begin with a
pushout-to-pullback theorem for path algebras.

######  Theorem 4.1.

Let

(4.1)
$\textstyle{E\underset{G}{\amalg}F}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota^{0}_{E},\iota^{1}_{E})}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota^{0}_{F},\iota^{1}_{F})}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(g^{0},g^{1})}$$\scriptstyle{(f^{0},f^{1})}$

be a pushout diagram in the category of graphs and proper graph homomorphisms
such that

  1. (1)

both $f^{0}$ and $g^{0}$ are injective (vertex injectivity),

  2. (2)

$t_{\amalg}(x)=s_{\amalg}(y)\;\Rightarrow\;(x,y\in\iota_{E^{1}}(E^{1})\text{
or }x,y\in\iota_{F^{1}}(F^{1}))$ (one color),

  3. (3)

$f^{1}$ or $g^{1}$ is injective (one-sided injectivity).

Then, for any field $k$, we have the equality of path algebras

$k\left(E\underset{G}{\amalg}F\right)=kE\underset{kG}{\times}kF\,,$

and the contravariant functor $\mathrm{Map}_{f}(\cdot,k)$ transforms the above
pushout diagram to the following pullback diagram in the category of algebras
over $k$:

$\textstyle{kE\underset{kG}{\times}kF\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E}^{*}}$$\scriptstyle{\iota_{F}^{*}}$$\textstyle{kE\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{*}}$$\textstyle{kF\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{*}}$$\textstyle{kG\,.}$

Here $f$ and $g$ are the maps induced by the graph homomorphisms
$E\stackrel{{\scriptstyle(f^{0},f^{1})}}{{\longleftarrow}}G\stackrel{{\scriptstyle(g^{0},g^{1})}}{{\longrightarrow}}F$,
respectively. Finally, if $E^{0}$ and $F^{0}$ are finite, then all algebras in
the above diagram and homomorphisms between them are unital, and the diagram
is a pullback diagram in the category of unital algebras.

###### Proof.

To begin with, Lemma 2.8 guarantees that (4.2) is a pushout diagram in the
category of graphs and proper graph homomorphisms for any proper graph
homomorphisms
$E\stackrel{{\scriptstyle(f^{0},f^{1})}}{{\longleftarrow}}G\stackrel{{\scriptstyle(g^{0},g^{1})}}{{\longrightarrow}}F$
satisfying the assumptions (1) through (3). Next, as proper graph
homomorphisms induce finite-to-one maps between the path spaces, and injective
graph homomorphisms induce injective maps between the path spaces, Lemma 2.6
yields the following pushout diagram in the category of sets and finite-to-one
maps:

$\textstyle{FP(E)\underset{FP(G)}{\amalg}FP(F)}$$\textstyle{FP(E)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E}}$$\textstyle{FP(F).\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{F}}$$\textstyle{FP(G)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\scriptstyle{f}$

Now, Proposition 3.1 turns this diagram into the commutative diagram in the
category of algebras:

$\textstyle{k\left(E\underset{G}{\amalg}F\right)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{E}^{*}}$$\scriptstyle{\iota_{F}^{*}}$$\textstyle{kE\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{*}}$$\textstyle{kF\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{*}}$$\textstyle{kG\,.}$

Furthermore, setting $K=k$ in Lemma 2.9, we conclude that the above diagram is
a pullback diagram in the category of sets and maps. We can combine these two
facts to conclude that the above diagram is a pullback diagram in the category
of algebras.

To prove the last part of the theorem, assume that both $E^{0}$ and $F^{0}$
are finite. As graph homomorphisms are assumed to be proper, not only the
finiteness of $E^{0}\amalg_{G^{0}}F^{0}$, but also the finiteness of $G^{0}$
follow from the finiteness of $E^{0}$ and $F^{0}$, so all algebras are unital,
as claimed. Next, the unitality of all homomorphisms follows from Proposition
3.1. Finally, under these circumstances, the maps witnessing the universality
in the category of unital algebras are evidently unital, so the above diagram
is a pullback diagram in the category of unital algebras. ∎

Before we consider our pushout-to-pullback theorem for Leavitt path algebras,
we need some lemmas. To simplify notation, in what follows, we write $f^{*}$
instead of $\bar{f}^{*}$ for the induced homomorphism defined in Theorem 3.3.

######  Lemma 4.2.

Let $G$ and $E$ be arbitrary graphs, let $(f^{0},f^{1}):G\to E$ be a morphism
in the admissible category of graphs, and let $f^{*}\colon L_{k}(E)\to
L_{k}(G)$ be the induced homomorphism as in Theorem 3.3. Then

$\forall v\in E^{0}\colon\quad[\chi_{v}]\in\ker f^{*}\quad\iff\quad v\in
E^{0}\setminus f^{0}(G^{0}).$

###### Proof.

The claim of the proposition is equivalent to the following statement

$\forall v\in E^{0}\colon\quad
f^{*}([\chi_{v}])=0\quad\iff\quad(f^{0})^{-1}(v)=\emptyset.$

The latter follows from the fact that the elements $[\chi_{w}]$,
$w\in(f^{0})^{-1}(v)$, would be non-zero and linearly independent (note that
we use the convention that the sum over the empty set equals $0$). ∎

Since $\ker f$ is a $\mathbb{Z}$-graded ideal, combining the previous results
with (3.2), we obtain the following corollary.

######  Corollary 4.3.

Let $(f^{0},f^{1}):G\to E$ be a morphism in the admissible category of graphs
and let $f^{*}\colon L_{k}(E)\to L_{k}(G)$ be the induced $\mathbb{Z}$-graded
homomorphism. Then

$\ker f^{*}=\Big{\langle}\\{[\chi_{v}]~{}|~{}v\in G^{0}\setminus
f^{0}(G^{0})\\}\cup\Big{\\{}[\chi_{w}]-\sum_{e\in
s^{-1}_{E}(w)\cap\,t^{-1}_{E}(E^{0}\setminus
f(F^{0}))}[\chi_{e}][\chi_{e^{*}}]~{}\Big{|}w\in B_{E^{0}\setminus
f(G^{0})}\Big{\\}}\Big{\rangle}.$

######  Lemma 4.4.

Let $(\iota^{0}_{E},\iota^{1}_{E}):E\to P$ and
$(\iota^{0}_{F},\iota_{F}^{1}):F\to P$ be morphisms in the admissible category
of graphs and let $\iota_{E}^{*}\colon L_{k}(P)\to L_{k}(E)$ and
$\iota_{F}^{*}:L_{k}(P)\to L_{k}(F)$ be the induced $\mathbb{Z}$-graded
homomorphisms. Then

$\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}=\\{0\\}\quad\iff\quad
P^{0}=\iota_{E}^{0}(E^{0})\cup\iota_{F}^{0}(F^{0}).$

###### Proof.

($\Leftarrow$) Since $\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}$ is a
$\mathbb{Z}$-graded ideal, we know that it is of the form (3.2), where

$H=\\{v\in
P^{0}~{}|~{}[\chi_{v}]\in\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}\\}.$

Suppose that $[\chi_{v}]\in\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}$. By the
above considerations and Lemma 4.2,

$v\in P^{0}\setminus(\iota_{E}^{0}(E^{0})\cup\iota_{F}^{0}(F^{0})).$

This leads to a contradiction since
$P^{0}=\iota_{E}^{0}(E^{0})\cup\iota_{F}^{0}(F^{0})$.

($\Rightarrow$) Suppose that there is a $v\in P^{0}$ such that
$v\notin\iota_{E}^{0}(E^{0})\cup\iota_{F}^{0}(F^{0})$. By Lemma 4.2,
$[\chi_{v}]\in\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}$. Since we assumed that
$\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}=\\{0\\}$ and $[\chi_{v}]\neq 0$ by
definition, we have a contradiction. ∎

######  Theorem 4.5.

Let

(4.2)
$\textstyle{E\underset{G}{\amalg}F}$$\textstyle{E\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota_{E}^{0},\iota_{E}^{1})}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\iota_{F}^{0},\iota_{F}^{1})}$$\textstyle{G\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(g^{0},g^{1})}$$\scriptstyle{(f^{0},f^{1})}$

be a pushout diagram in the admissible category of graphs satisfying

  1. (P1)

$(f^{0},f^{1})$ is injective,

  2. (P2)

$g^{0}$ restricted to $(f^{0})^{-1}(B_{E^{0}\setminus f^{0}(G^{0})})$ is
injective and $g^{0}((f^{0})^{-1}(B_{E^{0}\setminus f^{0}(G^{0})}))\subseteq
B_{E^{0}\setminus g^{0}(G^{0})}$ .

Then, for any field $k$, the commutative diagram of the induced homomorphisms

(4.3)
$\textstyle{L_{k}(E\underset{G}{\amalg}F)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota^{*}_{E}}$$\scriptstyle{\iota^{*}_{F}}$$\textstyle{L_{k}(E)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f^{*}}$$\textstyle{L_{k}(F)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g^{*}}$$\textstyle{L_{k}(G)}$

is a pullback diagram in the category of algebras over $k$.

###### Proof.

Throughout the proof, let $P:=E\,\underset{G}{\amalg}\,F$. To show that (4.3)
is a pullback, by [12, Proposition 3.1] (which is a C*-algebraic incarnation
of a more general result, see, e.g. [8, Lemma 4.1]), we have to prove that

  1. (1)

$\ker\iota_{E}^{*}\cap\ker\iota_{F}^{*}=\\{0\\}$,

  2. (2)

$(g^{*})^{-1}(f^{*}(L_{k}(E)))=\iota_{F}^{*}(L_{k}(P))$,

  3. (3)

$\ker f^{*}=\iota_{E}^{*}(\ker\iota_{F}^{*})$.

Since (4.2) is a pushout, it follows that

$P^{0}=\iota_{E}^{0}(E^{0})\cup\iota_{F}^{0}(F^{0}).$

Therefore, the condition (1) follows from Lemma 4.4.

Note that (P1) implies injectivity of $(\iota_{F}^{0},\iota_{F}^{1})$. Hence,
we obtain that both $f^{*}$ and $\iota_{F}^{*}$ are surjective, which proves
condition (2).

Since the diagram (4.3) is commutative, we only need to prove that $\ker
f^{*}\subseteq\iota_{E}^{*}(\ker\iota_{F}^{*})$. From Corollary 4.3, we know
that

$\ker f^{*}=\Big{\langle}\\{[\chi_{v}]~{}|~{}v\in E^{0}\setminus
f^{0}(G^{0})\\}\cup\Big{\\{}[\chi_{w}]-\sum_{e\in
s^{-1}_{E}(w)\cap\,t^{-1}_{E}(E^{0}\setminus
f(G^{0}))}[\chi_{e}][\chi_{e^{*}}]~{}\Big{|}~{}w\in B_{E^{0}\setminus
f^{0}(G^{0})}\Big{\\}}\Big{\rangle},$
$\ker\iota_{F}^{*}=\Big{\langle}\\{[\chi_{q}]~{}|~{}q\in
P^{0}\setminus\iota_{F}^{0}(F^{0})\\}\cup\Big{\\{}[\chi_{p}]-\sum_{a\in
s^{-1}_{P}(p)\cap\,t^{-1}_{P}(P^{0}\setminus\iota_{F}^{0}(F^{0}))}[\chi_{a}][\chi_{a^{*}}]~{}\Big{|}~{}p\in
B_{P^{0}\setminus\iota_{F}^{0}(F^{0})}\Big{\\}}\Big{\rangle}.$

Since (4.2) is a pushout, $\iota_{E}^{0}(E^{0}\setminus f^{0}(G^{0}))\subseteq
P^{0}\setminus\iota_{F}^{0}(F^{0})$ and $\iota_{E}^{0}$ is injective when
restricted to $E^{0}\setminus f^{0}(G^{0})$. Therefore, there exists a unique
vertex $q\in P^{0}\setminus\iota_{F}^{0}(F^{0})$ such that
$(\iota_{E}^{0})^{-1}(q)=\\{v\\}$. In turn, this implies that
$[\chi_{v}]=\iota_{E}^{*}([\chi_{q}])$, where $[\chi_{q}]\in\ker\iota_{F}^{*}$
by Lemma 4.2. Furthermore, observe that the condition (P2) is equivalent to
the following: $\iota_{E}^{0}$ restricted to $B_{E^{0}\setminus f^{0}(G^{0})}$
is injective and $\iota_{E}^{0}(B_{E^{0}\setminus f^{0}(G^{0})})\subseteq
B_{E^{0}\setminus\iota_{F}^{0}(F^{0})}$ . Hence, for every vertex $w\in
B_{E^{0}\setminus f^{0}(G^{0})}$ there exists a unique vertex $p\in
B_{P^{0}\setminus\iota_{F}^{0}(F^{0})}$ such that
$\iota_{E}^{*}([\chi_{p}])=[\chi_{w}]$. Observe that

$\displaystyle\iota_{E}^{*}\Big{(}[\chi_{p}]-\sum_{a\in
s^{-1}_{P}(p)\cap\,t^{-1}_{P}(P^{0}\setminus\iota_{F}^{0}(F^{0}))}[\chi_{a}][\chi_{a^{*}}]\Big{)}$
$\displaystyle=[\chi_{w}]-\sum_{e\in(\iota_{E}^{1})^{-1}(s^{-1}_{P}(p)\cap\,t^{-1}_{P}(P^{0}\setminus\iota_{F}^{0}(F^{0})))}[\chi_{e}][\chi_{e^{*}}]$
$\displaystyle=[\chi_{w}]-\sum_{e\in
s^{-1}_{E}(w)\cap\,t^{-1}_{E}(E^{0}\setminus
f(G^{0}))}[\chi_{e}][\chi_{e^{*}}].$

Here the last equality follows from Lemma 2.11. This concludes the proof. ∎

## Acknowledgements

We would like to thank Alexander Frei for numerous conversations about graph
C*-algebras and Cuntz–Pimsner algebras. This work is part of the project
"Applications of graph algebras and higher-rank graph algebras in
noncommutative geometry" partially supported by NCN grant
UMO-2021/41/B/ST1/03387.

## References

  * [1] G. Abrams, P. Ara, M. Siles Molina. Leavitt path algebras. Lecture Notes in Mathematics, 2191. Springer, London, 2017. xiii+287 pp.
  * [2] P. Ara, M. Moreno, E. Pardo. Nonstable $K$-theory for graph algebras. Algebr. Represent. Theory 10 (2007), no. 2, 157–178.
  * [3] I. Assem, D. Simson, A. Skowroński. Elements of the representation theory of associative algebras. Vol. 1. Techniques of representation theory. London Mathematical Society Student Texts, 65. Cambridge University Press, Cambridge, 2006. x+458 pp.
  * [4] S. Brooker, J. Spielberg. Relative graphs and pullbacks of relative Toeplitz graph algebras. arXiv:2207.10829.
  * [5] A. Chirvasitu, P. M. Hajac, M. Tobolski. Non-surjective pullbacks of graph C*-algebras from non-injective pushouts of graphs. Bull. Lond. Math. Soc. 53 (2021), no. 1, 1–15.
  * [6] H. Ehrig, H-J. Kreowski. Pushout-properties: an analysis of gluing constructions for graphs. Math. Nachr. 91 (1979), 135–149.
  * [7] K. R. Goodearl. Leavitt path algebras and direct limits. Rings, modules and representations, 165–187, Contemp. Math., 480, Amer. Math. Soc., Providence, RI, 2009.
  * [8] P. M. Hajac, A. Kaygun, M. Tobolski. A graded pullback structure of Leavitt path algebras of trimmable graphs. Quantum dynamics–dedicated to Professor Paul Baum, 47–52, Banach Center Publ., 120, Polish Acad. Sci. Inst. Math., Warsaw, 2020.
  * [9] P. M. Hajac, S. Reznikoff, M. Tobolski. Pullbacks of graph C*-algebras from admissible pushouts of graphs. Quantum dynamics–dedicated to Professor Paul Baum, 169–178, Banach Center Publ., 120, Polish Acad. Sci. Inst. Math., Warsaw, 2020.
  * [10] J. H. Hong, W. Szymański. Quantum spheres and projective spaces as graph algebras. Comm. Math. Phys. 232 (2002), no. 1, 157–188.
  * [11] A. Kumjian, D. Pask, A. Sims, M. F. Whittaker. Topological spaces associated to higher-rank graphs. J. Combin. Theory Ser. A 143 (2016), 19–41.
  * [12] G.K. Pedersen. Pullback and pushout constructions in C*-algebra theory. J. Funct. Anal. 167 (1999), no. 2, 243–344.
  * [13] D. Robertson, W. Szymański. C*-algebras associated to C*-correspondences and applications to mirror quantum spheres. Illinois J. Math. 55 (2011), no. 3, 845–870 (2013).