Finite homomorphism basis conjecture for first-order equivalence

From papers

Let k1k\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,GG,G' and a finite set Fk\mathcal F_k of graphs, say that GG and GG' 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

FkTDk\mathcal F_k\subseteq\mathcal{TD}_k

such that, for all graphs G,GG,G', if GG and GG' are homomorphism-indistinguishable over Fk\mathcal F_k, then GG and GG' 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.

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

No solutions have been posted yet.