# Counting Bounded Tree Depth Homomorphisms

@article{Grohe2020CountingBT, title={Counting Bounded Tree Depth Homomorphisms}, author={Martin Grohe}, journal={Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science}, year={2020} }

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

#### Figures and Topics from this paper

#### 8 Citations

On the Expressive Power of Homomorphism Counts

- Computer Science, Mathematics
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- 2021

The results unveil striking differences between the expressive power of the left profile and the right profile, including fractional isomorphism, equivalence in counting logics with a fixed number of variables, and co-spectrality cannot be captured by restricting theright profile to a class of graphs. Expand

Graph Similarity and Homomorphism Densities

- Computer Science, Mathematics
- 2021

The fairly general statement that, for every “reasonably” defined graphon pseudometric, an exact correspondence to homomorphism densities can be turned into an approximate one is proved. Expand

Graph Similarity and Homomorphism Densities

- Computer Science
- ICALP
- 2021

The fairly general statement that, for every “reasonably” defined graphon pseudometric, an exact correspondence to homomorphism densities can be turned into an approximate one is proved. Expand

Lovász-Type Theorems and Game Comonads

- Computer Science, Mathematics
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- 2021

This work proposes a new categorical formulation, which applies to any locally finite category with pushouts and a proper factorisation system, and presents a novel application to homomorphism counts in modal logic. Expand

word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data

- Computer Science, Mathematics
- PODS
- 2020

This paper proposes two theoretical approaches that it sees as central for understanding the foundations of vector embeddings and draws connections between the various approaches and suggests directions for future research. Expand

Graph Neural Networks with Local Graph Parameters

- Computer Science
- ArXiv
- 2021

This work proposes local graph parameter enabled GNNs as a framework for studying “higher-order” and “finite model theory and finite variable logics” approaches and precisely characterize their distinguishing power, in terms of a variant of the WL test, and in Terms of the graph structural properties that they can take into account. Expand

Polyadic Sets and Homomorphism Counting

- Mathematics, Computer Science
- 2021

A classical result due to Lovász (1967) shows that the isomorphism type of a graph is determined by homomorphism counts. That is, graphs G and H are isomorphic whenever the number of homomorphisms K… Expand

The Pebble-Relation Comonad in Finite Model Theory

- Computer Science, Mathematics
- ArXiv
- 2021

The pebbling comonad, introduced by Abramsky, Dawar and Wang, provides a categorical interpretation for the k-pebble games from finite model theory. The coKleisli category of the pebbling comonad… Expand

#### References

SHOWING 1-10 OF 58 REFERENCES

The Complexity of Homomorphism Indistinguishability

- Computer Science, Mathematics
- MFCS
- 2019

There is a polynomial-time-decidable class F of undirected graphs of bounded treewidth such that HomInd(F) is undecidable, and the second hardness result concerns the class K of complete graphs, which is shown to be co-NP-hard and completeness for the class C=P (under P-time Turing reductions). Expand

On recognizing graphs by numbers of homomorphisms

- Mathematics
- 2010

Let hom (G, H) be the number of homomorphisms from a graph G to a graph H. A well-known result of Lovasz states that the function hom (·, H) from all graphs uniquely determines the graph H up to… Expand

Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs

- Computer Science, Physics
- 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
- 2020

This combinatorial proof leverages the quantum automorphism group of a graph, a notion from noncommutative mathematics, and shows that homomorphism counts from graphs of bounded treewidth do not determine a graph up to isomorphism. Expand

Limitations of Algebraic Approaches to Graph Isomorphism Testing

- Mathematics, Computer Science
- ICALP
- 2015

We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Grobner basis computation. The idea of these algorithms is to encode two graphs into a system of… Expand

Describing Graphs: A First-Order Approach to Graph Canonization

- Mathematics
- 1990

In this paper we ask the question, “What must be added to first-order logic plus least-fixed point to obtain exactly the polynomial-time properties of unordered graphs?” We consider the languages L k… Expand

Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

- Mathematics, Computer Science
- IPEC
- 2014

It is established that graph canonisation, and thus graph isomorphism, is \(\mathsf {FPT}\) when parameterized by elimination distance to bounded degree, generalising results of Bouland et al. Expand

Linear time low tree-width partitions and algorithmic consequences

- Mathematics, Computer Science
- STOC '06
- 2006

It is proved that any fixed graph property of type "∃X: (|X| ≤ p) ⇿(G[X]=φ)" may be decided in linear time for input graphs in a fixed class with bounded expansion. Expand

What Is Mathematical Logic

- Computer Science
- 2016

We show that short bounded-depth Frege proofs of matrix identities, such as PQ = I ⊃ QP = I (over the field of two elements), imply short bounded-depth Frege proofs of the pigeonhole principle. Since… Expand

Graph limits and parameter testing

- Computer Science, Mathematics
- STOC '06
- 2006

We define a distance of two graphs that reflects the closeness of both local and global properties. We also define convergence of a sequence of graphs, and show that a graph sequence is convergent if… Expand

Tree-depth, quantifier elimination, and quantifier rank

- Computer Science, Mathematics
- LICS
- 2018

Monadic second-order logic MSO and FO have the same expressive power on every class of graphs of bounded tree-depth and the implication (i) ⟹ (iii) holds for MSO; it is the analogue of Courcelle's Theorem for tree- depth and para-AC0. Expand