Extremal regular graphs: the case of the infinite regular tree

Abstract

In this paper we study the following problem. Let $A$ be a fixed graph, and let $\mathrm{hom}(G,A)$ denote the number of homomorphisms from a graph $G$ to $A$. Furthermore, let $v(G)$ denote the number of vertices of $G$, and let ${\mathcal{G}}_d$ denote the family of $d$--regular graphs. The general problem studied in this paper is to determine $$\underset{G\in {\mathcal{G}}_d}{\inf }\mathrm{hom}(G,A{)}^{1/v(G)}.$$ It turns out that in many instances the infimum is not achieved by a finite graph, but a sequence of graphs with girth (i. e., length of the shortest cycle) tending to infinity. In other words, the optimization problem is solved by the infinite $d$--regular tree. We prove this type of results for the number of independent sets of bipartite graphs, evaluations of the Tutte-polynomial, Widom-Rowlinson configurations, and many more graph parameters. Our main tool will be a transformation called $2$-lift.

References in corpus (9)

• Ising models on locally tree-like graphs
• The computational hardness of counting in two-spin models on d-regular graphs
• The Bethe Partition Function of Log-supermodular Graphical Models
• Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation
• Extremal regular graphs: independent sets and graph homomorphisms
• The Bipartite Swapping Trick on Graph Homomorphisms
• Extremes of the internal energy of the Potts model on cubic graphs
• Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function
• Sidorenko's conjecture, colorings and independent sets

Cited by in corpus (4)

• Extremal regular graphs: independent sets and graph homomorphisms
• Extremes of the internal energy of the Potts model on cubic graphs
• Tight bounds on the coefficients of partition functions via stability
• $PC$-polynomial of graph