Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Homomorphisms are indeed a good basis for counting: Three fixed-template
  dichotomy theorems, for the price of one   Many natural combinatorial quantities can be expressed by counting the number
of homomorphisms to a fixed relational structure. For example, the number of
3-colorings of an undirected graph $G$ is equal to the number of homomorphisms
from $G$ to the $3$-clique. In this setup, the structure receiving the
homomorphisms is often referred to as a template; we use the term template
function to refer to a function, from structures to natural numbers, that is
definable as the number of homomorphisms to a fixed template. There is a
literature that studies the complexity of template functions.
  The present work is concerned with relating template functions to the
problems of counting, with respect to various fixed templates, the number of
two particular types of homomorphisms: surjective homomorphisms and what we
term condensations.
  In this article, we explain how any problem of counting surjective
homomorphisms to a fixed template is polynomial-time equivalent to computing a
linear combination of template functions; we also show this for any problem of
counting condensations to a fixed template. Via a theorem that characterizes
the complexity of computing such a linear combination, we show how a known
dichotomy for template functions can be used to infer a dichotomy for counting
surjective homomorphisms on fixed templates, and likewise a dichotomy for
counting condensations on fixed templates. Our study is strongly inspired by,
based on, and can be viewed as a dual of the graph motif framework of
Curticapean, Dell, and Marx (STOC 2017); that framework is in turn based on
work of Lov\'asz (2012).

25
The categories of this paper are: patt-sol
28
The categories of this paper are: alg-geom
3
The categories of this paper are: physics
22
The categories of this paper are: chao-dyn
9
The categories of this paper are: nlin
24
The categories of this paper are: dg-ga
5
The categories of this paper are: gr-qc
33
The categories of this paper are: plasm-ph
10
The categories of this paper are: q-bio
27
The categories of this paper are: comp-gas
23
The categories of this paper are: solv-int
20
The categories of this paper are: acc-phys
34
The categories of this paper are: chem-ph
32
The categories of this paper are: atom-ph
18
The categories of this paper are: econ
14
The categories of this paper are: math-ph