Homomorphism-preserving bijections of finite graphs are trivial

From papers

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

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

hom(GH)=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.

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

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

Solutions 0

No solutions have been posted yet.