We prove a tight upper bound on the independence polynomial (and total number of independent sets) of cubic graphs of girth at least 5. The bound is achieved by unions of the Heawood graph, the point line incidence graph of the Fano plane. We also give a tight lower bound on the total number of independent sets of triangle-free cubic graphs. This bound is achieved by unions of the Petersen graph. We conjecture that in fact all Moore graphs are extremal for the scaled number of independent sets in regular graphs of a given minimum girth, maximizing this quantity if their girth is even and minimizing if odd. The Heawood and Petersen graphs are instances of this conjecture, along with complete graphs, complete bipartite graphs, and cycles.
The method we use is an extension of the method used in @cite_9 to prove Theorem and the analogous theorem for random matchings in regular graphs. At a high level, the method works as follows. To bound the occupancy fraction of the hard-core model on a graph @math , we consider the experiment of drawing an independent set @math from the hard-core model, then independently choosing a vertex @math uniformly from the graph. We then record a local view of both @math and @math from the perspective of @math . The depth- @math local view from @math includes both the information of the graph structure of the depth- @math neighborhood of @math as well as the boundary conditions the independent set @math induces on this neighborhood (that is, which vertices at the boundary are blocked from being in the independent set by some external vertex). @cite_9 , the local view considered was of the first neighborhood of @math , with each neighbor labeled according to whether or not it had an occupied neighbor among the second neighbors of @math .
@cite_9
2963702702
We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of Kahn's result that a disjoint union of copies of Kd;d maximizes the number of independent sets of a bipartite d-regular graph, Galvin and Tet ali's result that the independence polynomial is maximized by the same, and Zhao's extension of both results to all d-regular graphs. For matchings, this shows that the matching polynomial and the total number of matchings of a d-regular graph are maximized by a union of copies of Kd;d. Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom. In probabilistic language, our main theorems state that for all d-regular graphs and all �, the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity � are maximized by Kd;d. Our method involves constrained optimization problems over distributions of random variables and applies to all d-regular graphs directly, without a reduction to the bipartite case. Using a variant of the method we prove a lower bound on the occupancy fraction of the hard-core model on any d-regular, vertex-transitive, bipartite graph: the occupancy fraction of such a graph is strictly greater than the occupancy fraction of the unique translationinvariant hard-core measure on the infinite d-regular tree