Counting bounded tree depth homomorphisms

DOI10.1145/3373718.3394739zbMATH Open1498.05135arXiv2003.08164OpenAlexW3031354613MaRDI QIDQ5145659FDOQ5145659

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)

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'.

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

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

zbMATH Keywords

first-order logictree depthcounting homomorphismshomomorphism indistinguishability

Mathematics Subject Classification ID

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

Cited In (10)

• Title not available (Why is that?)
• The pebble-relation comonad in finite model theory
• Counting and Enumeration Problems with Bounded Treewidth
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Graphs Identified by Logics with Counting
• The pebble-relation comonad in finite model theory
• Logical equivalences, homomorphism indistinguishability, and forbidden minors
• Counting and coding identity trees with fixed diameter and bounded degree
• Polyadic sets and homomorphism counting
• Discrete density comonads and graph parameters

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)