Homomorphism-preserving bijections of finite graphs are trivial

About 20 years old · traced to

Let G\mathcal{G} be the class of finite simple graphs, and let π:G→G\pi:\mathcal{G}\rightarrow\mathcal{G} be a bijection. For graphs G,H∈GG,H\in\mathcal{G}, write hom(G→H)hom(G\rightarrow H) for the number of graph homomorphisms from GG to HH.

Homomorphism cancellation conjecture. If, for all graphs G,H∈GG,H\in\mathcal{G},

hom(G→H)=hom(π(G)→π(H)),hom(G\rightarrow H)=hom(\pi(G)\rightarrow\pi(H)),

then π\pi is the identity map.

This is posed as a generalisation of Lovász's homomorphism cancellation laws in the setting of reconstruction from subgraph posets. The supplied text presents it as a problem, and gives no resolution.

References

Primary source

Bhalchandra D. Thatte, “Subgraph posets and graph reconstruction”, arXiv:math/0609574 (2015).

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.