Finite homomorphism basis conjecture for first-order equivalence
Let . Fix a set of colours and consider graphs whose colour interpretations satisfy . For graphs and a finite set of graphs, say that and are homomorphism-indistinguishable over when their homomorphism counts from every graph in agree. Finite homomorphism basis conjecture. There is a finite set
such that, for all graphs , if and are homomorphism-indistinguishable over , then and satisfy the same -sentences. This asks whether bounded-quantifier-rank first-order equivalence can be captured by finitely many homomorphism counts from graphs of tree depth at most ; the source presents it as a tempting conjecture, and no resolution is supplied here.
References
Primary source
Martin Grohe, “Counting Bounded Tree Depth Homomorphisms”, arXiv:2003.08164 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.