No.3034 Cohen-Macaulay Abstract Simplicial Complex
タグ : / 解いたユーザー数 6
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
Problem Statement
Positive integers $N, Q$ are given at the beginning of the input. Initially, the set $\Delta$ is the empty set. Process the $Q$ queries described below in the given order.
The $q$-th query is given as integers $A_q, B_q, C_q$ satisfying $1 \leq A_q < B_q < C_q \leq N$. Update $\Delta$ by adding as elements all the non-empty subsets $\{A_q\},\{B_q\},\{C_q\},\{A_q,B_q\},\{B_q,C_q\},\{A_q,C_q\},\{A_q,B_q,C_q\}$ of $\{A_q,B_q,C_q\}$.
For each query, determine whether $\Delta$ is Cohen-Macaulay.
Here, $\Delta$ is said to be "Cohen-Macaulay" if it satisfies the following three conditions.
- (
CO) $\Delta$ is connected - (
H1) $H_1(\Delta; \mathbb{F}_2) = 0$ - (
LK) For each $i$ such that $\{i\} \in \Delta$, ${\rm link}_\Delta \{i\}$ is connected
We now explain the terminology. $\Delta$ satisfies $\emptyset \not\in \Delta$ and $\sigma \in \Delta, \emptyset \neq \tau \subseteq \sigma \Rightarrow \tau \in \Delta$. Such an object is called an abstract simplicial complex. An abstract simplicial complex with a finite number of vertices is nothing but an independence system with the empty set removed.
An abstract simplicial complex $\Delta$ is said to be disconnected if it can be written as $\Delta = \Delta_1 \cup \Delta_2$ with two non-empty disjoint abstract simplicial complexes $\Delta_1, \Delta_2$.
If it is not disconnected, it is said to be connected.
${\rm link}_\Delta \{i\} := \{ \sigma \in \Delta \, | \, i \not\in \sigma$ and $\{i\} \cup \sigma \in \Delta \}$ is an abstract simplicial complex.
The condition H1 can be rephrased as follows.
Call the one-element sets belonging to $\Delta$ "points", the two-element sets "edges", and the three-element sets "faces".
Consider coloring the edges of $\Delta$ white or black. A "good coloring" is one in which, for each point $\{i\}$, the number of edges of the form $\{i, j\}$ colored black is even.
A "coloring by faces" is a "good coloring" obtained by first coloring all edges white and then repeatedly performing the operation of choosing one face $\{i, j, k\}$ and flipping the colors of the three edges $\{ i, j \}, \{ j, k \}, \{ k, i \}$.
The second condition can be rephrased as: every "good coloring" is a "coloring by faces".
Background
Abstract simplicial complexes are easiest to understand by considering their "geometric realization".
Take a vertex $v_i$ corresponding to each $i$ such that $\{i\} \in \Delta$. When $\{ i, j \} \in \Delta$, draw a line segment between $v_i, v_j$. When $\{ i, j, k \} \in \Delta$, fill in the triangle formed by the three points $v_i, v_j, v_j$.
The figure obtained in this way is the "geometric realization". Of course, it must be placed suitably in a high-dimensional space so that the edges and triangles do not intersect in strange ways.
For example, the "geometric realization" of the abstract simplicial complex $\{ \{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\} \}$ is a regular tetrahedron.
In other words, an abstract simplicial complex extracts the information of how the faces, edges, and points of the triangles are connected in a polyhedron made by gluing triangles together.
With this geometric view, an abstract simplicial complex is disconnected if and only if its geometric realization is disconnected.
For those familiar with the language of commutative algebra
Let $I_\Delta$ be the ideal of $\mathbb{F_2}[X_1, \dots, X_N]$ generated by the monomials $X_{\underline{i}} := X_{i_1} \cdots X_{i_k}$ for $\underline{i} = (i_1, \dots, i_k), 1 \leq i_1 < \dots < i_k \leq N, \{ i_1, \dots, i_k \} \not\in \Delta$.$\mathbb{F}_2[\Delta] := \mathbb{F_2}[X_1, \dots, X_N] / I_\Delta$ is called the Stanley-Reisner ring of $\Delta$. This problem asks whether this ring is Cohen-Macaulay.
Side note
Let $C(N, d)$ denote the convex hull of $N > d$ distinct points on the $d$-dimensional moment curve $M_d = \{ (t, t^2, \dots, t^d) \,|\, t \in \mathbb{R} \}$.For a $d-1$-dimensional convex polytope $\Delta$, let $f_{\Delta, i}$ be the number of its $i$-dimensional faces, and write $f_\Delta = (f_{\Delta, 0}, \dots, f_{\Delta, d-1})$, which is called the $f$-vector.
The "Upper Bound Conjecture" is the conjecture that, when $\Delta$ is homeomorphic to the $d-1$-dimensional sphere and $v$ is the number of vertices of $\Delta$, we have $f_{\Delta, i} \leq f_{C(v, d), i} \ (i = 0, \dots, d-1)$.
This is naturally conjectured from the fact that it holds for $i \leq \lfloor d/2 \rfloor$ and that the $f$-vector has a certain symmetry, but Stanley did not know how to prove it.
Then one day, a person named Reisner published a topological and combinatorial criterion for the Reisner ring to be Cohen-Macaulay, in a degree thesis, without knowing of the Upper Bound Conjecture.
From this criterion it follows that the Reisner ring of $\Delta$ is Cohen-Macaulay when $\Delta$ is homeomorphic to the $d-1$-dimensional sphere, and it is also immediate that the above inequality holds for Cohen-Macaulay rings, so the Upper Bound Conjecture was solved!
References are listed in the editorial, so please refer to them if you are interested.
Input
$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$.
Output
For the queries $1 \leq A_q < B_q < C_q \leq N \ (q = 1, \dots, Q)$ given by the problem, print the following on the $q$-th line, regarding $\Delta$ after processing up to the $q$-th query:
- If $\Delta$ does not satisfy
CO, printCO. - Otherwise, if $\Delta$ does not satisfy
H1, printH1. - Otherwise, if $\Delta$ does not satisfy
LK, printLK. - Otherwise, that is, if it is Cohen-Macaulay, print
CM.
Print a newline at the end.
Sample
Sample 1
Input
4 4 1 2 3 1 2 4 1 3 4 2 3 4
Output
CM CM CM CM
The final $\Delta$ is an abstract simplicial complex whose geometric realization is a regular tetrahedron.
For example, ${\rm link}_\Delta \{ 1 \} = \{ \{ 2, 3 \}, \{ 2, 4 \}, \{ 3, 4 \}, \{2\}, \{3\}, \{4\} \} $ has a triangle (its edges only) as its geometric realization and is connected.
You can verify that every good coloring is a coloring by faces by enumerating all colorings.
Sample 2
Input
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
Output
CM CM CM CM CM CM CM CM CM CM
The final $\Delta$ is an abstract simplicial complex whose geometric realization is a regular octahedron. Note that the sets $\{A_m, B_m, C_m\}$ may contain duplicates.
Sample 3
Input
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
Output
CM CO LK H1 H1 H1 H1 H1 H1 H1 H1 H1 H1 H1
The final $\Delta$ is an abstract simplicial complex whose geometric realization is a torus.
In this figure, the vertex $1$, the edge $12$, and so on appear multiple times, but there is actually only one of each (they are glued together). They are drawn separately on purpose in order to depict the complex in a two-dimensional plane.
Sample 4
Input
100 6 1 2 3 2 3 5 3 4 5 4 5 6 2 4 6 1 2 6
Output
CM CM CM CM H1 H1
The final $\Delta$ is an abstract simplicial complex whose geometric realization is a Möbius strip.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。