| Autor: |
Csikvari, Peter, Ruozzi, Nicholas, Shams, Shahab |
| Předmět: |
|
| Zdroj: |
IEEE Transactions on Information Theory; Sep2022, Vol. 68 Issue 9, p6052-6062, 11p |
| Abstrakt: |
Graph covers and the Bethe free energy (BFE) 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 investigate weighted 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 a variety of natural settings, and when it does yield 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 homomorphism number. Finally, we use the characterizations developed as part of this work to provide a simple proof of Sidorenko’s conjecture in a number of special cases. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
