Counting Bounded Tree Depth Homomorphisms

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 homomorphismindistinguishable 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 ′ .