Inclusion conjecture for homomorphism indistinguishability relations

Let F1\mathcal{F}_1 and F2\mathcal{F}_2 be minor- and union-closed families of graphs. Write F1F2\cong_{\mathcal{F}_1}\Rightarrow\cong_{\mathcal{F}_2} when the first homomorphism indistinguishability relation implies the second for all graphs. Inclusion conjecture.

F1F2F1F2.\cong_{\mathcal{F}_1}\Rightarrow\cong_{\mathcal{F}_2}\quad\Longleftrightarrow\quad\mathcal{F}_1\supseteq\mathcal{F}_2.

One direction is immediate from inclusion of the testing families, and the conjecture asserts the converse for minor- and union-closed families. The paper states that this conjecture is open and equivalent to the distinctness conjecture.

Sources & referencesView supporting material

Primary source

David E. Roberson, “Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree”, arXiv:2206.10321 (2022).

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.