Technical Program

Paper Detail

Paper Title Counting Homomorphisms in Bipartite Graphs
Paper IdentifierWE1.R5.3
Authors Shahab Shams, Nicholas Ruozzi, University of Texas at Dallas, United States; Péter Csikvári, ELTE Eötvös Loránd University, Hungary
Session Information Theory Methods in Graph Theory
Location Saint Victor, Level 3
Session Time Wednesday, 10 July, 09:50 - 11:10
Presentation Time Wednesday, 10 July, 10:30 - 10:50
Manuscript  Click here to download the manuscript
Abstract Graph covers and the Bethe free energy have been useful theoretical tools for producing lower bounds on a variety of counting problems in graphical models, including the permanent and the ferromagnetic Ising model. Here, we propose a new conjecture that the Bethe free energy yields a lower bound on the weighted homomorphism counting problem over bipartite graphs. We show that this conjecture strengthens existing conjectures, and we prove the conjecture in several special cases using a novel reformulation of the graph cover characterization of the Bethe free energy.