本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
我們研究有效反駁圖的 k-可著色性的問題，或等效地證明其色數的下界。我們在稀疏隨機正則圖中給出了該問題的平均情況計算難度的正式證據，顯示了簡單光譜證書的最優性。證據採用計算安靜種植的形式：我們建立了一個 d-正則圖的分佈，其色數比均勻隨機繪製的典型正則圖要小得多，同時提供證據表明這兩種分佈無法透過一大類演算法區分。我們將我們的結果推廣到更普遍的問題，即證明最大 k 割的上限。這種安靜的種植是透過最大限度地減少種植結構（例如著色或切割）對圖譜的影響來實現的。具體來說，植入的結構與鄰接矩陣的特徵向量完全對應。這避免了隨機矩陣理論的推出效應，並延遲了種植在光譜或局部統計中變得可見的點。為了進一步說明這一點，我們對該問題的高斯模擬給出了類似的結果：尖峰模型的安靜版本，我們在其中植入特徵空間而不是添加通用的低階擾動。我們區分兩個分佈的計算難度的證據是基於三種不同的啟發式：置信傳播的穩定性、局部統計層次結構和低度似然比。具有獨立意義的是，我們的結果包括多尖峰矩陣模型的低度似然比的通用界限，以及隨機塊模型的改進的低度分析。