Polyadic sets and homomorphism counting

DOI10.1016/J.AIM.2022.108712MaRDI QIDQ2094593zbMATH OpenOpenAlexFDO

Publication date 8 November 2022

Published in Advances in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.11061

profinite algebras locally finitely presentable category locally finite category homomorphism counting polyadic set Stirling kernel

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Model theory of finite structures (03C13) General theory of categories and functors (18A99)

Abstract: A classical result due to Lovasz (1967) shows that the isomorphism type of a graph is determined by homomorphism counts. That is, graphs G and H are isomorphic whenever the number of homomorphisms from K to G is the same as the number of homomorphisms from K to H for all graphs K. Variants of this result, for various classes of finite structures, have been exploited in a wide range of research fields, including graph theory and finite model theory. We provide a categorical approach to homomorphism counting based on the concept of polyadic (finite) set. The latter is a special case of the notion of polyadic space introduced by Joyal (1971) and related, via duality, to Boolean hyperdoctrines in categorical logic. We also obtain new homomorphism counting results applicable to a number of infinite structures, such as finitely branching trees and profinite algebras.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Polyadic sets and homomorphism counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2094593)