Polyadic sets and homomorphism counting (Q2094593)

A celebrated result in [\textit{L. Lovász}, Acta Math. Acad. Sci. Hung. 18, 321--328 (1967; Zbl 0174.01401)] claims that the isomorphism type of a graph is determined by homomorphism counts, showing that graphs \(G\) and \(H\) are isomorphic iff the number of homomorphisms \(K\rightarrow G\) is the same as the number of homomorphisms \(K\rightarrow H\) for all graphs \(K\). Extensions and variations of this theorem have been exploited in a broad range of research area such as graph theory, finite model theory and quantum information [\textit{Z. Dvořák}, J. Graph Theory 64, No. 4, 330--342 (2010; Zbl 1207.05128); \textit{M. Grohe}, in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 507--520 (2020; Zbl 1498.05135); \textit{L. Mančinska} and \textit{D. E. Roberson}, ``Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs'', in: Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS'20. Los Alamitos, CA: IEEE Computer Society (2020; \url{doi:10.1109/FOCS46700.2020.00067})]. Categorical generalizations of Lovász' result were established in [\textit{A. Pultr}, Acta Sci. Math. 35, 155--160 (1973; Zbl 0278.18001); \textit{J. Isbell}, J. Pure Appl. Algebra 76, No. 1, 87--110 (1991; Zbl 0754.18003)] via a direct generalization of Lovász' combinatorial counting argument. This paper adopts a different approach after [\textit{A. Dawar} et al., ``Lovász-type theorems and game comonads'', in: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '21. New York, NY: Association for Computing Machinery (ACM) (2021; \url{doi:10.1109/LICS52264.2021.9470609})]. The aim of the paper is twofold. On the one hand, it is shown that homomorphism counting results are basically a consequence of a more general result about polyadic sets, a special case of Joyal's polyadic spaces [\textit{A. Joyal}, ``Polyadic spaces and elementary theories'', Notices Am. Math. Soc. 18, 563 (1971)]. On the other hand, the paper exploits the framework of polyadic sets, combined with a topological argument, to extend homomorphism counting results beyond categories of finite structures. The synopsis of the paper goes as follows. \begin{itemize} \item[\S 2] recalls some basic categorical definitions and facts, introducing the notion of left- and right- combinatorial category, in which the isomorphism types of objects are determined by homomorphism counts. \item[\S 3] studies polyadic sets, establishing some of their main properties. \item[\S 4] establishes homomorphism counting results for locally finite categories, i.e. categories with only finitely many morphisms between any two objects. \item[\S 5] proves a general theorem characterizing the isomorphism type of certain objects in categories that are not necessarily locally finite, specializing it to the setting of locally finitely presentable categories. \item[\S 6] discusses applications. \item[Appendix A] is concerned with proper factorisation systems. \item[Appendix B] is concerned with comonads of finite rank. \end{itemize}