Reggio, L;
(2022)
Polyadic sets and homomorphism counting.
Advances in Mathematics
, 410
, Article 108712. 10.1016/j.aim.2022.108712.
Preview |
Text
1-s2.0-S0001870822005291-main.pdf - Published Version Download (714kB) | Preview |
Abstract
A classical result due to Lovász (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 K→G is the same as the number of homomorphisms K→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 trees and profinite algebras.
| Type: | Article |
|---|---|
| Title: | Polyadic sets and homomorphism counting |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.aim.2022.108712 |
| Publisher version: | https://doi.org/10.1016/j.aim.2022.108712 |
| Language: | English |
| Additional information: | © 2022 The Author(s). Published by Elsevier Inc. under a Creative Commons license (https://creativecommons.org/licenses/by/4.0/). |
| Keywords: | Homomorphism counting, Polyadic set, Stirling kernel, Locally finite category, Locally finitely presentable category, Profinite algebras |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10158138 |
Archive Staff Only
 |
View Item |
