No.3034 コーエン-マコーレー抽象単体複体
タグ : / 解いたユーザー数 5
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
入力の最初に正整数 $N, Q$ が与えられる。最初に集合 $\Delta$ が空集合として与えられている。以下で説明する $Q$ 個のクエリを与えられた順に処理せよ。
$q$ 個目のクエリは $1 \leq A_q < B_q < C_q \leq N$ を満たす整数 $A_q, B_q, C_q$ として与えられる。$\Delta$ に $\{A_q,B_q,C_q\}$ の空でない部分集合 $\{A_q\},\{B_q\},\{C_q\},\{A_q,B_q\},\{B_q,C_q\},\{A_q,C_q\},\{A_q,B_q,C_q\}$ 全てを要素として追加することで更新する。
各クエリに対して、$\Delta$ がコーエン-マコーレーかを判定せよ。
ただし、$\Delta$ が「コーエン-マコーレー」であるとは、以下の三つの条件を満たすことをいう。
- （
CO）$\Delta$ は連結である - （
H1）$H_1(\Delta; \mathbb{F}_2) = 0$ - （
LK）$\{i\} \in \Delta$ となる $i$ に対して、${\rm link}_\Delta \{i\}$ は連結である
用語を解説する。$\Delta$ は $\emptyset \not\in \Delta$ かつ $\sigma \in \Delta, \emptyset \neq \tau \subseteq \sigma \Rightarrow \tau \in \Delta$ を満たす。このようなものを抽象単体複体という。頂点数が有限な抽象単体複体は、独立性システムから空集合を取り除いたものにほかならない。
抽象単体複体 $\Delta$ が非連結であるとは、空でない二つの交わらない抽象単体複体 $\Delta_1, \Delta_2$ によって $\Delta = \Delta_1 \cup \Delta_2$ と表せることをいう。
非連結でないとき、連結であるという。
${\rm link}_\Delta \{i\} := \{ \sigma \in \Delta \, | \, i \not\in \sigma$ かつ $\{i\} \cup \sigma \in \Delta \}$ は抽象単体複体である。
条件 H1 についてだが、これは以下のように言い換えられる。
$\Delta$ に属する一元集合を「点」、二元集合を「辺」、三元集合を「面」と呼ぶことにする。
$\Delta$ の辺を、白か黒で彩色することを考える。「良い彩色」とは、各点 $\{i\}$ について、黒く彩色された $\{i, j\}$ という形で表される辺の個数が偶数になることをいう。
はじめに全ての辺を白で彩色し、面 $\{i, j, k\}$ を一つ選び、三つの辺 $\{ i, j \}, \{ j, k \}, \{ k, i \}$ の色を反転する操作を繰り返すことで得られる「良い彩色」を「面による彩色」という。
二番目の条件は、「良い彩色」は必ず「面による彩色」であると言い換えられる。
背景
抽象単体複体は、その「幾何学的実現」を考えるのが分かりやすい。
$\{i\} \in \Delta$ となるような $i$ と対応する頂点 $v_i$ を持ってくる。$\{ i, j \} \in \Delta$ のとき、$v_i, v_j$ の間に線分を描く。$\{ i, j, k \} \in \Delta$ のとき、$v_i, v_j, v_j$ の三点がなす三角形を塗りつぶす。
これによって得られる図形が「幾何学的実現」である。もちろん、辺や三角形が変な交差をしないように高次元空間内にうまく配置する必要がある。
たとえば、抽象単体複体 $\{ \{1, 2, 3\}, \{1, 3, 4\}, \{1, 2, 4\}, \{2, 3, 4\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{ 3, 4\}, \{1\}, \{2\}, \{3\}, \{4\} \}$ の「幾何学的実現」は、正四面体である。
つまり、抽象単体複体は三角形を貼り合わせた多面体の、三角形たちの面、辺、点の繋がり方の情報を抽出したものである。
このように幾何学的に捉えることで、抽象単体複体が非連結であることと、その幾何学的実現が非連結であることは同値になる。
可換代数の言葉を知っている人向け
$\underline{i} = (i_1, \dots, i_k), 1 \leq i_1 < \dots < i_k \leq N, \{ i_1, \dots, i_k \} \not\in \Delta$ に対して単項式 $X_{\underline{i}} := X_{i_1} \cdots X_{i_k}$ から生成される $\mathbb{F_2}[X_1, \dots, X_N]$ のイデアルを $I_\Delta$ とおく。$\mathbb{F}_2[\Delta] := \mathbb{F_2}[X_1, \dots, X_N] / I_\Delta$ を $\Delta$ のスタンレー-ライズナー環と呼ぶ。この環がコーエン-マコーレーであるかを判定する問題である。
余談
$d$-次元のモーメント曲線 $M_d = \{ (t, t^2, \dots, t^d) \,|\, t \in \mathbb{R} \}$ 上の相異なる $N > d$ 個の点の凸包を $C(N, d)$ と書く。$d-1$-次元 凸多面体 $\Delta$ の $i$-次元の面の個数を $f_{\Delta, i}$ として $f_\Delta = (f_{\Delta, 0}, \dots, f_{\Delta, d-1})$ と書き、これを $f$-列と呼ぶ。
$\Delta$ が $d-1$-次元球面と同相であるとき、$\Delta$ の頂点数を $v$ として、$f_{\Delta, i} \leq f_{C(v, d), i} \ (i = 0, \dots, d-1)$ ではないかという予想を「上限予想」と呼ぶ。
これは、$i \leq \lfloor d/2 \rfloor$ のとき成り立つことと、$f$-列にはある種の対称性があることから自然に予想されるのだが、スタンレーははこれの証明法が分からずにいた。
そんなある日、ライズナーという人が、ライズナー環がコーエンマコーレーであることの位相・組み合わせ的な判別条件を上限予想を知らずに学位論文で発表した。
$\Delta$ が $d-1$-次元球面と同相であるとき、$\Delta$ のライズナー環はコーエンマコーレーであることが判別条件から分かると同時に、コーエンマコーレー環では先の不等式が成り立つことがすぐ分かるので、上限予想が解かれてしまったのである！
解説に参考文献があるので、興味のある方はそちらも参考に。
入力
$N \ M$ $A_1 \ B_1 \ C_1$ $\vdots$ $A_M \ B_M \ C_M$
$3 \leq N \leq 10^3,$
$1 \leq M \leq 10^3,$
$1 \leq A_M < B_M < C_M \leq N$.
出力
問題から与えられるクエリ $1 \leq A_q < B_q < C_q \leq N \ (q = 1, \dots, Q)$ について、$q$ 番目のクエリまで処理した際の $\Delta$ について、$q$ 行目に以下のように出力せよ:
- $\Delta$ が
COを満たさないときはCOを出力する。 - そうでないとき、$\Delta$ が
H1が満たさないときはH1を出力する。 - そうでないとき、$\Delta$ が
LKを満たさないときはLKを出力する。 - そうでないとき、すなわちコーエン-マコーレーであるときは
CMを出力する。
最後に改行せよ。
サンプル
サンプル1
入力
4 4 1 2 3 1 2 4 1 3 4 2 3 4
出力
CM CM CM CM
最終的にできる $\Delta$ は幾何学的実現が正四面体であるような抽象単体複体である。
例えば ${\rm link}_\Delta \{ 1 \} = \{ \{ 2, 3 \}, \{ 2, 4 \}, \{ 3, 4 \}, \{2\}, \{3\}, \{4\} \} $ は幾何学的実現が三角形（の辺だけ）であり、連結である。
全ての良い彩色は面による彩色であることは、全ての彩色を列挙することで確認できるだろう。
サンプル2
入力
8 10 1 2 3 1 2 3 1 2 5 1 2 5 1 3 4 1 4 5 2 3 6 2 5 6 3 4 6 4 5 6
出力
CM CM CM CM CM CM CM CM CM CM
最終的な $\Delta$ は幾何学的実現が正八面体であるような抽象単体複体である。$\{A_m, B_m, C_m\}$ たちが重複するかもしれないことに注意。
サンプル3
入力
100 14 1 2 4 5 6 7 4 6 7 1 5 6 2 3 7 1 3 7 2 4 5 2 5 7 1 4 7 1 2 6 2 3 6 3 4 6 3 4 5 1 3 5
出力
CM CO LK H1 H1 H1 H1 H1 H1 H1 H1 H1 H1 H1
最終的な $\Delta$ は幾何学的実現がトーラスであるような抽象単体複体である。
この図では $1$ という頂点や $12$ という辺などが複数個存在するが、本来は一つしかない(貼り合わせる)。二次元平面内で図示するためにあえて別々に描画している。
サンプル4
入力
100 6 1 2 3 2 3 5 3 4 5 4 5 6 2 4 6 1 2 6
出力
CM CM CM CM H1 H1
最終的な $\Delta$ は幾何学的実現がメビウスの帯であるような抽象単体複体である。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。