摘要 當我們在平面上的點之間添加剛性桿時，在什麼點上會出現一個巨大的（線性大小的）剛性組件，它可以旋轉和

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

當我們在平面上的點之間添加剛性桿時，在什麼點上會出現一個巨大的（線性大小的）剛性組件，它可以旋轉和平移，但沒有內部靈活性？如果這些點是通用的，則這僅取決於由條形形成的圖形的組合。我們證明，如果該圖是 Erdos-Renyi 隨機圖 G(n,c/n)，則存在出現巨大剛性組件的尖銳閾值。對於 c < c_2，w.h.p。所有剛性組件跨越一個、兩個或三個頂點，並且當 c > c_2 時，w.h.p.有一個巨大的剛性部件。常數 c_2 \approx 3.588 是 2 定向性的閾值，由 Fernholz 和 Ramachandran 以及 Cain、Sanders 和 Wormald 在 SODA'07 中獨立發現。我們也對巨型剛性組件出現時的大小給出了定量界限，證明它跨越了 (3+2)-核心中頂點的 (1-o(1))-部分。通俗地說，(3+2)核是從 3 核開始，然後將迄今為止獲得的圖中具有 2 個鄰居的頂點歸納相加而獲得的最大誘導子圖。