グラフの接続性、限界見つけた！💻✨
超要約: グラフのつながりやすさの限界、見つけたった！IT業界で役立つかも？
● グラフ（図みたいなやつ）のつながりやすさ、大事じゃん？🙆♀️ ● 効率よく「つながってるか」調べる方法の限界を暴いた！😎 ● ITインフラ（ITの基盤）の信頼性UPに貢献できるかもってこと！✨
詳細解説 背景 ネットワーク（情報の通り道）とか、システム（色んなものが連携してるやつ）の信頼性ってめっちゃ大事じゃん？ グラフ理論っていう、そういうのを数学的に考える分野があるんだけど、そこで「k-接続性」っていう、どれだけ頑丈かを表す指標があるんだよね。今回の研究は、そのk-接続性を調べる「k-接続性オラクル」ってやつが、どれだけ効率的（メモリとか使わないか）かの限界を明らかにしたんだ！
方法 グラフの「k-接続性オラクル」っていう、ある2点間がどれだけつながってるかを調べる方法があるんだけど、その方法に必要なメモリ量の下限（最低限必要なメモリ量）を数学的に証明したんだって！ 具体的には、k-接続性グラフ（k個以上の道でつながってるグラフ）の場合、最低でもΩ(kn)ビットのメモリが必要ってことを示したらしい！ 難しけど、すごいことなんだよ！
続きは「らくらく論文」アプリで
On $k$-connectivity oracles in $k$-connected graphs
A $k$-connectivity oracle for a graph $G=(V,E)$ is a data structure that given $s,t \in V$ determines whether there are at least $k+1$ internally disjoint $st$-paths in $G$. For undirected graphs, Pettie, Saranurak & Yin [STOC 2022, pp. 151-161] proved that any $k$-connectivity oracle requires $\Omega(kn)$ bits of space. They asked whether $\Omega(kn)$ bits are still necessary if $G$ is $k$-connected. We will show by a very simple proof that this is so even if $G$ is $k$-connected, answering this open question.