mlsanityData to 7 Oct 2026

Counting Bounded Tree Depth Homomorphisms

arXiv 2003.08164 ↗First posted 18 Mar 2020cs.LO cs.DM math.COcited by 1

Not on the map. Why?

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

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). First posted on arXiv 18 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 1.

1 paper.

  1. 2021Graph Neural Networks with Local Graph Parameterscited by 51