# Counting Bounded Tree Depth Homomorphisms

arXiv: https://arxiv.org/abs/2003.08164 · HTML: https://mlsanity.com/paper/2003.08164/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)

## Abstract (arXiv)

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