By implementing algorithm
Based on results from the physics and mathematics literature which suggest a series of clearly defined conjectures, we formulate three simple scenarios for the fate of hard sphere crystallization in high dimension: (A) crystallization is impeded and
the glass phase constitutes the densest packing, (B) crystallization from the liquid is possible, but takes place much beyond the dynamical glass transition and is thus dynamically implausible, or (C) crystallization is possible and takes place before (or just after) dynamical arrest, thus making it plausibly accessible from the liquid state. In order to assess the underlying conjectures and thus obtain insight into which scenario is most likely to be realized, we investigate the densest sphere packings in dimension $d=3$-$10$ using cell-cluster expansions as well as numerical simulations. These resulting estimates of the crystal entropy near close-packing tend to support scenario C. We additionally confirm that the crystal equation of state is dominated by the free volume expansion and that a meaningful polynomial correction can be formulated.
We define a potential-weighted connective constant that measures the effective strength of a repulsive pair potential of a Gibbs point process modulated by the geometry of the underlying space. We then show that this definition leads to improved boun
ds for Gibbs uniqueness for all non-trivial repulsive pair potentials on $mathbb R^d$ and other metric measure spaces. We do this by constructing a tree-branching collection of densities associated to the point process that captures the interplay between the potential and the geometry of the space. When the activity is small as a function of the potential-weighted connective constant this object exhibits an infinite volume uniqueness property. On the other hand, we show that our uniqueness bound can be tight for certain spaces: the same infinite volume object exhibits non-uniqueness for activities above our bound in the case when the underlying space has the geometry of a tree.
Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exis
ts. This motivates an average-case question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree $Delta$. We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are IID Gaussians with variance larger than a constant depending only on the inverse temperature and $Delta$. The main challenge comes from the positive density of vertices at which the external field is small. These regions, which may have connected components of size $Theta(log n)$, are a barrier to algorithms based on establishing a zero-free region, and cause worst-case analyses of Glauber dynamics to fail. The analysis of our algorithm is based on percolation on a self-avoiding walk tree.
We give an FPTAS for computing the number of matchings of size $k$ in a graph $G$ of maximum degree $Delta$ on $n$ vertices, for all $k le (1-delta)m^*(G)$, where $delta>0$ is fixed and $m^*(G)$ is the matching number of $G$, and an FPTAS for the num
ber of independent sets of size $k le (1-delta) alpha_c(Delta) n$, where $alpha_c(Delta)$ is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size $k leq (1-delta)m^*(G)$ and independent sets of size $k leq (1-delta)alpha_c(Delta)n$. Our results are based on a new framework for exploiting local central limit theorems as an algorithmic tool. We use a combination of Fourier inversion, probabilistic estimates, and the deterministic approximation of partition functions at complex activities to extract approximations of the coefficients of the partition function. For our results for independent sets, we prove a new local central limit theorem for the hard-core model that applies to all fugacities below $lambda_c(Delta)$, the uniqueness threshold on the infinite $Delta$-regular tree.
We determine the asymptotics of the number of independent sets of size $lfloor beta 2^{d-1} rfloor$ in the discrete hypercube $Q_d = {0,1}^d$ for any fixed $beta in [0,1]$ as $d to infty$, extending a result of Galvin for $beta in [1-1/sqrt{2},1]$. M
oreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $lambda>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.
We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the `frozen 1-RSB structure conjectured by Krauth and Mezard in the physics literature; that is, typical solutions of the mod
el lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density $alpha_c(Delta)$ and provide (i) for $alpha < alpha_c(Delta)$ randomiz
ed polynomial-time algorithms for approximately sampling and counting independent sets of given size at most $alpha n$ in $n$-vertex graphs of maximum degree $Delta$; and (ii) a proof that unless NP=RP, no such algorithms exist for $alpha>alpha_c(Delta)$. The critical density is the occupancy fraction of hard core model on the clique $K_{Delta+1}$ at the uniqueness threshold on the infinite $Delta$-regular tree, giving $alpha_c(Delta)simfrac{e}{1+e}frac{1}{Delta}$ as $Deltatoinfty$.
For $Delta ge 5$ and $q$ large as a function of $Delta$, we give a detailed picture of the phase transition of the random cluster model on random $Delta$-regular graphs. In particular, we determine the limiting distribution of the weights of the orde
red and disordered phases at criticality and prove exponential decay of correlations and central limit theorems away from criticality. Our techniques are based on using polymer models and the cluster expansion to control deviations from the ordered and disordered ground states. These techniques also yield efficient approximate counting and sampling algorithms for the Potts and random cluster models on random $Delta$-regular graphs at all temperatures when $q$ is large. This includes the critical temperature at which it is known the Glauber and Swendsen-Wang dynamics for the Potts model mix slowly. We further prove new slow-mixing results for Markov chains, most notably that the Swendsen-Wang dynamics mix exponentially slowly throughout an open interval containing the critical temperature. This was previously only known at the critical temperature. Many of our results apply more generally to $Delta$-regular graphs satisfying a small-set expansion condition.
We prove that the `Upper Matching Conjecture of Friedland, Krop, and Markstrom and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every $d$ and every
large enough $n$ divisible by $2d$, a union of $n/(2d)$ copies of the complete $d$-regular bipartite graph maximizes the number of independent sets and matchings of size $k$ for each $k$ over all $d$-regular graphs on $n$ vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.
