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 G0 and G1 such that the homomorphisms from a given graph F to either G0 or G1 can be partitioned into sets whose elements are in bijection with the solutions to linear systems over Z2. The coefficient matrices for these systems are the same for both G0 and G1, and in the former case the systems are homogenous but not in the latter case. As a consequence G0 admits at least as many homomorphisms as G1 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 G0 than G1. 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.