Markov Random Fields, Homomorphism Counting, and Sidorenko’s Conjecture

Graph covers and the Bethe free energy (BFE) have been useful theoretical tools for producing lower bounds on various counting problems in graphical models, including the permanent and the ferromagnetic Ising model. Here, we investigate homomorphism counting problems over bipartite graphs that are related to a conjecture of Sidorenko. We show that the BFE does yield a lower bound in various natural settings. When it yields a lower bound, it necessarily improves upon the lower bound conjectured by Sidorenko. Conversely, we show that there exist bipartite graphs for which the BFE does not yield a lower bound on the homo- morphism number. Finally, we use the characterizations developed as part of this work to provide a simple proof of Sidorenko’s conjecture in some particular cases.