Homomorphism indistinguishability over immersion-closed classes

Series
Graph Theory Seminar
Time
Tuesday, November 3, 2026 - 3:45pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho Yoo
Organizer
Rose McCarty and Caleb McFarland

Abstract: Lov\'{a}sz proved that two graphs $G$ and $H$ are isomorphic if they have the same homomorphism counts from all graphs, and Dvo\v{r}\'{a}k showed that it suffices to count homomorphisms from all $2$-degenerate graphs. Homomorphism counts from various other graph classes have been shown to give interesting graph relations weaker than isomorphism. Many such classes are minor-closed, and Roberson conjectured that homomorphism indistinguishability over any proper minor-closed class $\mathcal{M}$ is a strictly weaker relation than isomorphism; that is, there exist graphs $G$ and $H$ that are non-isomorphic but satisfy $\hom(K,G)=\hom(K,H)$ for all $K\in\mathcal{M}$. We prove an analogue of this conjecture for immersions. Joint work with Andrea Jim\'enez, Benjamin Moore, and Daniel A. Quiroz.