The hardcore model is a fundamental probabilistic model extensively studied in statistical physics, probability theory, and computer science. For graphs of maximum degree $Δ$, a well-known computational phase transition occurs at the tree-uniqueness threshold $λ_c(Δ) = \frac{(Δ-1)^{Δ-1}}{(Δ-2)^Δ}$, where the mixing behavior of the Glauber dynamics (a simple Markov chain) undergoes a sharp transition. It is conjectured that random regular graphs exhibit different mixing behavior, with the slowdown occurring far beyond the uniqueness threshold. We confirm this conjecture by showing that, for the hardcore model on random $Δ$-regular graphs, the Glauber dynamics mixes rapidly with high probability when $λ= O(1/\sqrtΔ)$, which is significantly beyond the uniqueness threshold $λ_c(Δ) \approx e/Δ$. Our result establishes a sharp distinction between the hardcore model on worst-case and beyond-worst-case instances, showing that the worst-case and average-case complexities of sampling and counting are fundamentally different. This result of rapid mixing on random instances follows from a new criterion we establish for rapid mixing of Glauber dynamics for any distribution supported on a downward closed set family. Our criterion is simple, general, and easy to check. In addition to proving new mixing conditions for the hardcore model, we also establish improved mixing time bounds for sampling uniform matchings or $b$ matchings on graphs, the random cluster model on matroids with $q \in [0,1)$, and the determinantal point process. Our proof of this new criterion for rapid mixing combines and generalizes several recent tools in a novel way, including a trickle down theorem for field dynamics, spectral/entropic stability, and a new comparison result between field dynamics and Glauber dynamics.

翻译：硬核模型是统计物理学、概率论和计算机科学中广泛研究的基本概率模型。对于最大度为$Δ$的图，一个著名的计算相变发生在树唯一性阈值$λ_c(Δ) = \\frac{(Δ-1)^{Δ-1}}{(Δ-2)^Δ}$处，此时Glauber动力学（一种简单的马尔可夫链）的混合行为会发生急剧转变。据推测，随机正则图表现出不同的混合行为，其减速现象远在唯一性阈值之外发生。我们通过证明在随机$Δ$-正则图上的硬核模型中，当$λ= O(1/\\sqrtΔ)$时（该值显著超越唯一性阈值$λ_c(Δ) \\approx e/Δ$），Glauber动力学以高概率实现快速混合，从而证实了这一推测。我们的结果确立了硬核模型在最坏情况与超越最坏情况实例之间的显著差异，表明采样与计数问题的最坏情况复杂度与平均情况复杂度存在本质区别。这一随机实例上的快速混合结果源于我们为任意支撑在向下封闭集族上的分布建立的Glauber动力学快速混合新判据。该判据简洁、通用且易于验证。除了证明硬核模型的新混合条件外，我们还为图上均匀匹配或$b$匹配的采样、$q \\in [0,1)$时拟阵上的随机簇模型，以及行列式点过程建立了改进的混合时间边界。我们对这一快速混合新判据的证明以新颖方式结合并推广了多项近期工具，包括场动力学的滴流定理、谱/熵稳定性，以及场动力学与Glauber动力学之间的新比较结果。