UC Santa Cruz

The independent set polynomial plays a prominent role in combinatorics, statistical mechanics, and the probabilistic method. Specifically, in combinatorics the independent set polynomial appears as the generating function of the independent sets of a graph, in statistical mechanics as the partition function of the hard-core model, while in probabilistic method, due to the seminal work of Shearer, it expresses the full range of applicability of the celebrated Lov asz Local Lemma (LLL).

The first three chapters of this thesis are concerned with the study the computability and approximability of the independent set polynomial, with emphasis on its applications in the probabilistic method.

In particular, in Chapter 1, we briefly review previous work, and present our first results: (i) an exact computation procedure of the independent set polynomial in linear time, for all arguments (ii) an improved version of the asymmetric LLL, (iii) two novel local lemmata inspired from non-backtracking walks, which we use to improve the rigorous bound of the ``negative fugacity singularity of hard core model" for the triangular lattice, a central problem in statistical physics of lattice gases.

In Chapter 2 we show a rigorous correspondence between walks and local lemmata, which we use to develop a hierarchy of increasingly powerful, increasingly non-local lemmata. To demonstrate the power of our hierarchy, we prove new rigorous lower bounds for aforementioned negative fugacity singularity of the hard core model on several lattices, matching their conjectured values up to three decimal digits.

In Chapter 3 we prove that Shearer's connection between the probabilistic method and the independent set polynomial holds for \emph{arbitrary supermodular} functions, not just probability measures. This means that all LLL machinery can be employed to bound from below an arbitrary supermodular function, based only on information regarding its value at singleton sets and partial information regarding their interactions. We show that our lemma readily implies both the ``Quantum LLL" of Ambainis, Kempe, and Sattath, and the ``Quantum Shearer" criterion of Sattath, Morampudi, Laumann, and Moessner.

Finally, in Chapter 4 we turn on the Bethe approximation for partition functions of general graphical models. While, a priori, there is no connection between the (analytically defined) Bethe approximation and the independent set polynomial, we use a recent combinatorial characterization of the Bethe approximation by Vontobel~\cite{pascalcounting} to suggest precisely such a connection, by relating typical random $k$-lifts of graphs where $k \to \infty$, with the aforementioned tree of non-backtracking walks. In particular, we revisit a recent result of Ruozzi showing that the Bethe partition function is a lower bound for the true partition function, for every graphical model whose constituent factors are log-supermodular. We give a significantly shorter proof of this result.More importantly, we give a new much shorter proof of the celebrated four functions theorem.