Galvin's biregular homomorphism conjecture

About 14 years old · traced to

Let GG be a bipartite graph, let dud_u denote the degree of u∈V(G)u\in V(G), and let HH be a loop-graph. Write hom⁡(G,H)\hom(G,H) for the number of graph homomorphisms from GG to HH. Galvin's biregular homomorphism conjecture.

hom⁡(G,H)≤∏uv∈E(G)hom⁡(Kdu,dv,H)1/(dudv).\hom(G,H)\le \prod_{uv\in E(G)}\hom(K_{d_u,d_v},H)^{1/(d_ud_v)}.

This would extend the regular and biregular homomorphism inequalities, as well as the bipartite case of Kahn's irregular independent-set conjecture. Its status is open.

References

Primary source

Yufei Zhao, “Extremal regular graphs: independent sets and graph homomorphisms”, arXiv:1610.09210 (2017).

Additional references

4 papers in this index state this conjecture (2012–2016). The statement above is taken from the most recent of them; the others are arXiv:1512.06398, arXiv:1307.5919, arXiv:1205.2718.

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.