Counting Bounded Tree Depth Homomorphisms

2020/03/18 by Grohe, Martin · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2003.08164

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

Cited by

• Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
• Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification

Related

• Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth
• Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
• On Homomorphism Indistinguishability and Hypertree Depth
• An Algorithmic Meta Theorem for Homomorphism Indistinguishability