Counting bounded tree depth homomorphisms

DOI10.1145/3373718.3394739MaRDI QIDQ5145659zbMATH OpenOpenAlexFDO

Authors Martin Grohe

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

counting homomorphismsfirst-order logichomomorphism indistinguishabilitytree depth

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We prove that graphs G, G' satisfy the same sentences of first-order logic with counting of quantifier rank at most k if and only if they are homomorphism-indistinguishable over the class of all graphs of tree depth at most k. Here G, G' are homomorphism-indistinguishable over a class C of graphs if for each graph F in C, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'.

Recommendations

• Tree-depth, quantifier elimination, and quantifier rank
• Where first-order and monadic second-order logic coincide
• Where first-order and monadic second-order logic coincide
• On recognizing graphs by numbers of homomorphisms
• Expressivity and succinctness of order-invariant logics on depth-bounded structures

Cited in

(32)

• Polyadic sets and homomorphism counting
• Discrete density comonads and graph parameters
• Graphs identified by logics with counting
• Counting and Enumeration Problems with Bounded Treewidth
• On Hanf-equivalence and the number of embeddings of small induced subgraphs
• Graphs Identified by Logics with Counting
• scientific article; zbMATH DE number 7560520 (Why is no real title available?)
• Tree-depth, quantifier elimination, and quantifier rank
• The pebble-relation comonad in finite model theory
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Logical equivalences, homomorphism indistinguishability, and forbidden minors
• The pebble-relation comonad in finite model theory
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
• On homomorphism indistinguishability and hypertree depth
• Homomorphism-distinguishing closedness for graphs of bounded tree-width
• The complexity of homomorphism reconstructibility
• Modal logic with relations over paths: a theoretical development through comonadic semantics
• On algorithms based on finitely many homomorphism counts
• The complexity of homomorphism reconstructibility
• Monotonicity of the cops and robber game for bounded depth treewidth
• An algorithmic meta theorem for homomorphism indistinguishability
• Graph similarity and homomorphism densities
• Homomorphism counts to trees
• Finite variable counting logics with restricted requantification
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• Adaptive query algorithms for relational structures based on homomorphism counts
• Color refinement for relational structures
• Homomorphism indistinguishability and game comonads for restricted conjunction and requantification
• NPA hierarchy for quantum isomorphism and homomorphism indistinguishability
• Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree
• Counting and coding identity trees with fixed diameter and bounded degree

This page was built for publication: Counting bounded tree depth homomorphisms

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