English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Many natural combinatorial quantities can be expressed by counting the numberof homomorphisms to a fixed relational structure. For example, the number of3-colorings of an undirected graph $G$ is equal to the number of homomorphismsfrom $G$ to the $3$-clique. In this setup, the structure receiving thehomomorphisms is often referred to as a template; we use the term templatefunction to refer to a function, from structures to natural numbers, that isdefinable as the number of homomorphisms to a fixed template. There is aliterature that studies the complexity of template functions.  The present work is concerned with relating template functions to theproblems of counting, with respect to various fixed templates, the number oftwo particular types of homomorphisms: surjective homomorphisms and what weterm condensations.  In this article, we explain how any problem of counting surjectivehomomorphisms to a fixed template is polynomial-time equivalent to computing alinear combination of template functions; we also show this for any problem ofcounting condensations to a fixed template. Via a theorem that characterizesthe complexity of computing such a linear combination, we show how a knowndichotomy for template functions can be used to infer a dichotomy for countingsurjective homomorphisms on fixed templates, and likewise a dichotomy forcounting condensations on fixed templates. Our study is strongly inspired by,based on, and can be viewed as a dual of the graph motif framework ofCurticapean, Dell, and Marx (STOC 2017); that framework is in turn based onwork of Lov\'asz (2012).

Homomorphisms are indeed a good basis for counting: Three fixed-template dichotomy theorems, for the price of one