// TAG
#combinatorics
3 件の関連解説
ランダムハイパーグラフにおけるスター衝突
私が今回取り上げるのは、$k$-一様ランダムハイパーグラフにおける「スター衝突」という現象を、組合せ論・確率論・スペクトル理論の交差点で解析した論文です。頂点 $v$ の「スター」$\mathrm{Star}(v)$ とは $v$ を含む全超辺の集合を指しますが、著者らはまず、行…
★★★★★
幾何的グラフの閾値定理
ランダムグラフにおける「閾値現象」とは、確率パラメータが臨界値を越えた瞬間に特定のグラフ性質が突然出現する相転移現象です。Erdős-Rényi のランダムグラフモデル $G(n, p)$ においては、1987 年の Bollobás-Thomason 定理が任意の単調増加グラフ…
★★★★★
パーキング関数と Dyck パス上のバーンサイド過程
私が今回扱うのは、有限群の作用を持つ有限集合上で軌道を一様にサンプリングするための古典的道具であるバーンサイド過程を、Catalan 構造へ系統的に適用した論文です。具体的には、長さ $n$ のパーキング関数の集合に対称群 $S_n$ が座標の置換として作用する場合と、長さ $2…
★★★★★