Finite homomorphism basis conjecture for first-order equivalence
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Martin Grohe, “Counting Bounded Tree Depth Homomorphisms”, arXiv:2003.08164 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.