Finite homomorphism basis conjecture for first-order equivalence

At least 5 years old · documented by

Let k≥1k\ge 1. Fix a set Γ\Gamma of colours and consider graphs GG whose colour interpretations satisfy rg⁡(γG)⊆Γ\operatorname{rg}(\gamma^G)\subseteq\Gamma. For graphs G,G′G,G' and a finite set Fk\mathcal F_k of graphs, say that GG and G′G' are homomorphism-indistinguishable over Fk\mathcal F_k when their homomorphism counts from every graph in Fk\mathcal F_k agree. Finite homomorphism basis conjecture. There is a finite set

Fk⊆TDk\mathcal F_k\subseteq\mathcal{TD}_k

such that, for all graphs G,G′G,G', if GG and G′G' are homomorphism-indistinguishable over Fk\mathcal F_k, then GG and G′G' satisfy the same FOk\textsf{FO}_k-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 kk; 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

Never refreshed

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.