Counting Bounded Tree Depth Homomorphisms

Proceedings - Symposium on Logic in Computer Science, pp. 507–520

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 F of graphs if for each graph F ϵ F, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'.

Authors 1

1. Martin Grohe corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany

   RWTH Aachen University (Germany)