本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
關於不連續滲濾轉變的機制和性質，還有很多有待發現。過去的大部分工作都考慮了稱為 Achlioptas 過程的圖演化演算法，其中在每個時間步從一組 k 個隨機選擇的候選邊中將一條邊添加到圖中，直到出現一個巨大的組件。幾種 Achlioptas 過程似乎會產生不連續的滲濾轉變，但 Riordan 和 Warnke 證明，這種轉變在熱力學極限內必須是連續的。然而，他們也證明，如果候選邊的數量k(n)隨著節點數量的增加而增加，那麼滲流過渡可能是不連續的。在這裡，我們試圖找到最簡單的此類過程，該過程會在熱力學極限內產生不連續的轉變。我們引入一個僅考慮候選邊緣的程度而不考慮組件大小的過程。我們計算臨界點 t(c) =(1 - theta(1/k))n 並嚴格證明臨界窗口的大小為 O(n/k(n)。如果 k(n) 增長非常緩慢，例如 k(n) = log n，則臨界窗口的大小為 O(n/k(n)。如果 k(n) 增長非常緩慢，例如 k(n) = log n，則臨界窗口幾乎不是次線性的，因此相變是不連續的，但在有限系統中看起來是連續的論點：即使我們也提出了具有無限的規則，即使是 Aoplitaschtaschtaschtas，具有有限的規則。製程也將始終具有連續的滲流轉變。