A construction of pairs of graphs with applications to homomorphism counting
We will discuss a construction of pairs of graphs that is inspired by a construction of pairs of non-isomophic but quantum isomorphic graphs. Given any connected graph $G$, we construct graphs $G_0$ and $G_1$ such that the homomorphisms from a given graph $F$ to either $G_0$ or $G_1$ can be partitioned into sets whose elements are in bijection with the solutions to linear systems over $\mathbb{Z}_2$. The coefficient matrices for these systems are the same for both $G_0$ and $G_1$, and in the former case the systems are homogenous but not in the latter case. As a consequence $G_0$ admits at least as many homomorphisms as $G_1$ from any graph $F$. Moreover we can use the linear systems to characterize to a certain extent which graphs $F$ have strictly more homomorphisms to $G_0$ than $G_1$. Using this we are able to show that homomorphism counts from graphs of bounded degree do not determine a graph up to isomorphism. We end with a hopefully intriguing open question relating homomorphism counts and graph minors.