Polyadic sets and homomorphism counting

DOI10.1016/J.AIM.2022.108712zbMATH Open1499.18005arXiv2110.11061OpenAlexW3205614780MaRDI QIDQ2094593FDOQ2094593

Authors: Luca Reggio 

Publication date: 8 November 2022

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

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.

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

Recommendations

• scientific article; zbMATH DE number 1341918
• Discrete density comonads and graph parameters
• An universality argument for graph homomorphisms
• On k-homogeneous posets and graphs
• Large systems of independent objects in concrete categories. I
• Two Fraïssé-style theorems for homomorphism-homogeneous relational structures
• scientific article; zbMATH DE number 4105023
• Bowtie‐free graphs and generic automorphisms
• The Catalan simplicial set
• scientific article; zbMATH DE number 1686998

zbMATH Keywords

profinite algebraslocally finitely presentable categorylocally finite categoryhomomorphism countingpolyadic setStirling 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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Categories of continuous functors. I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Continuous Lattices and Domains
• Title not available (Why is that?)
• Categories and Sheaves
• Title not available (Why is that?)
• The Theory of Representation for Boolean Algebras
• On finitely generated profinite groups. I: Strong completeness and uniform bounds. II: Products in quasisimple groups.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Profinite groups.
• Une théorie combinatoire des séries formelles
• Theorems on Compact Totally Disconnected Semigroups and Lattices
• Title not available (Why is that?)
• Categories of Boolean sheaves of simple algebras
• Operations with structures
• Adjointness in foundations
• Counting bounded tree depth homomorphisms
• On recognizing graphs by numbers of homomorphisms
• Some inequalities in hom sets
• Title not available (Why is that?)
• The pebbling comonad in finite model theory
• Relating structure and power: comonadic semantics for computational resources
• On finitary functors
• Polyadic spaces and profinite monoids
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• On duality and model theory for polyadic spaces
• Discrete density comonads and graph parameters

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)