超平面配置

$X\in L(\mathcal{A})$ について $\nu(X):=\sum_{\mathcal{B}:\,\bigcap\mathcal{B}=X}(-1)^{\lvert\mathcal{B}\rvert}$ とおくと、右辺は $\sum_X\nu(X)t^{\dim X}$ である。$\nu=\mu$ を示せばよい。$\mathcal{A}_X:=\{H\in\mathcal{A}\mid H\supset X\}$ とおく。$\bigcap\mathcal{B}\supset X$ は $\mathcal{B}\subset\mathcal{A}_X$ と同値で、そのとき $\bigcap\mathcal{B}$ は $X$ を含むので空でなく $L(\mathcal{A})$ に属する。よって
$$ \sum_{Y\supset X}\nu(Y)=\sum_{\mathcal{B}\subset\mathcal{A}_X}(-1)^{\lvert\mathcal{B}\rvert} $$
である。右辺は $\mathcal{A}_X=\emptyset$ なら $1$、そうでなければ二項定理により $(1-1)^{\lvert\mathcal{A}_X\rvert}=0$ である。$X=V$ なら $\mathcal{A}_X=\emptyset$（超平面は $V$ を含まない）で、$X\neq V$ なら $X$ は空でない $\mathcal{B}$ の交わりなので $\mathcal{A}_X\neq\emptyset$ である。こうして $\nu$ は $\mu$ と同じ漸化式をみたし、$\nu=\mu$ である。$\square$

thm-ha-whitney で $\mathcal{B}=\emptyset$ は $t^n$ を、$\lvert\mathcal{B}\rvert=1$ は $-t^{n-1}$ を 1 つずつ与える。相異なる 2 つ以上の超平面の空でない交わりの次元は $n-2$ 以下である。$\square$

中心的な配置ではどの $\mathcal{B}$ も中心的で、$\bigcap\mathcal{B}$ は空でない連立 1 次方程式の解の集合なので $\dim\bigcap\mathcal{B}=n-\operatorname{rank}\mathcal{B}$ である。thm-ha-whitney の右辺は $\sum_{\mathcal{B}}(-1)^{\lvert\mathcal{B}\rvert}t^{n-\operatorname{rank}\mathcal{B}}=t^{n-r}\sum_{\mathcal{B}}(-1)^{\lvert\mathcal{B}\rvert}t^{r-\operatorname{rank}\mathcal{B}}$ となる。$\square$

包除原理 により $\#M(\mathcal{A})=\sum_{\mathcal{B}\subset\mathcal{A}}(-1)^{\lvert\mathcal{B}\rvert}\#\bigcap\mathcal{B}$ である。$\bigcap\mathcal{B}$ は空か、$\mathbb{F}_q$ 上の $\dim\bigcap\mathcal{B}$ 次元のアフィン部分空間なので $q^{\dim\bigcap\mathcal{B}}$ 個の点をもつ。よって右辺は thm-ha-whitney の右辺に $t=q$ を代入したものである。$\square$

1：$\mathcal{A}_G$ は原点を含むので中心的で、$F\subset E$ に対応する交わりは「$F$ の各辺の両端で座標が等しい」点の集合、すなわち $F$ の各連結成分の上で座標が一定の点の集合で、次元は $c(F)$ である。thm-ha-whitney から 1 つめの等号を得る。右辺は $K$ によらないので $K=\mathbb{F}_p$（$p$ は素数）で計算してよく、thm-ha-finite-field により $\chi_{\mathcal{A}_G}(p)$ は、隣接する頂点で値が異なる写像 $\{1,\dots,n\}\to\mathbb{F}_p$、すなわち $p$ 色の正しい塗り分けの個数 $P_G(p)$ である。2 つの多項式が無限個の素数で一致するので $\chi_{\mathcal{A}_G}=P_G$ である。
2：完全グラフの $p$ 色の正しい塗り分けは相異なる $n$ 個の値の列なので $p(p-1)\cdots(p-n+1)$ 個あり、1 と同じ理由で多項式として等しい。$\square$

thm-ha-whitney の和を、$H_0\notin\mathcal{B}$ の部分と $H_0\in\mathcal{B}$ の部分に分ける。前者は $\chi_{\mathcal{A}'}(t)$ である。後者で $\mathcal{B}=\{H_0\}\cup\mathcal{C}$（$\mathcal{C}\subset\mathcal{A}'$）と書く。$\mathcal{B}$ が中心的なら $\mathcal{C}$ の各元は $H_0$ と交わり、$\varphi(H):=H\cap H_0$ として $\bigcap\mathcal{B}=\bigcap_{H\in\mathcal{C}}\varphi(H)$ である。したがって後者は
$$ -\sum_{\substack{\mathcal{D}\subset\mathcal{A}''\\ \mathcal{D}\text{ は中心的}}}\Bigl(\sum_{\mathcal{C}:\ \varphi(\mathcal{C})=\mathcal{D}}(-1)^{\lvert\mathcal{C}\rvert}\Bigr)t^{\dim\bigcap\mathcal{D}} $$
となる（$\mathcal{C}$ は $\varphi$ の定義される元からなる $\mathcal{A}'$ の部分集合、$\bigcap\mathcal{D}$ は $H_0$ の中でとり、$\bigcap\emptyset=H_0$）。$\varphi(\mathcal{C})=\mathcal{D}$ となる $\mathcal{C}$ は、各 $E\in\mathcal{D}$ について $\varphi^{-1}(E)$ の空でない部分集合を選んで合わせたものなので、内側の和は $\prod_{E\in\mathcal{D}}\bigl(\sum_{\emptyset\neq S\subset\varphi^{-1}(E)}(-1)^{\lvert S\rvert}\bigr)=\prod_{E\in\mathcal{D}}(0-1)=(-1)^{\lvert\mathcal{D}\rvert}$ である。よって後者は、$H_0\cong K^{n-1}$ の配置 $\mathcal{A}''$ に thm-ha-whitney を当てた $-\chi_{\mathcal{A}''}(t)$ である。$\square$

$C_\sigma$ は開半空間の共通部分なので凸な開集合で、とくに連結である。$M(\mathcal{A})$ は空でない $C_\sigma$ の非交和で、各 $C_\sigma$ の補集合（$M(\mathcal{A})$ の中での）はほかの $C_\tau$ の和なので開である。よって各 $C_\sigma$ は $M(\mathcal{A})$ の中で開かつ閉な連結集合であり、連結成分である。$\square$

$\mathcal{A}'$ の領域 $R$ が $H_0$ と交わらなければ、$R$ は $\mathcal{A}$ の領域でもある（lem-ha-regions-convex で $\ell_{H_0}$ の符号は $R$ の上で一定）。$R$ が $H_0$ と交われば、$R$ は凸な開集合なので $\ell_{H_0}>0$ の部分と $\ell_{H_0}< 0$ の部分はどちらも空でなく、$R$ は $\mathcal{A}$ の 2 つの領域に分かれる。よって $r(\mathcal{A})=r(\mathcal{A}')+N$ で、$N$ は $H_0$ と交わる $\mathcal{A}'$ の領域の個数である。
一方 $H_0\setminus\bigcup_{E\in\mathcal{A}''}E=H_0\setminus\bigcup_{H\in\mathcal{A}'}H$ は、$H_0$ と交わる $\mathcal{A}'$ の領域 $R$ についての $R\cap H_0$ の非交和である。各 $R\cap H_0$ は $H_0$ の中の凸な開集合なので、prf-lem-ha-regions-convex と同じ議論でこれらがちょうど $\mathcal{A}''$ の領域である。よって $N=r(\mathcal{A}'')$ である。$\square$

$\mathcal{A}=\emptyset$ なら $r=1$、$\chi_{\mathcal{A}}(t)=t^n$ で成り立つ。$\lvert\mathcal{A}\rvert\ge1$ とし、超平面の個数がより少ない配置（次元は問わない）で主張が成り立つとする。$H_0\in\mathcal{A}$ をとると、$\mathcal{A}'$ と $H_0\cong\mathbb{R}^{n-1}$ の配置 $\mathcal{A}''$ はどちらも $\lvert\mathcal{A}\rvert$ より少ない超平面からなる。prop-ha-deletion-restriction と帰納法の仮定から
$$ (-1)^n\chi_{\mathcal{A}}(-1)=(-1)^n\chi_{\mathcal{A}'}(-1)+(-1)^{n-1}\chi_{\mathcal{A}''}(-1)=r(\mathcal{A}')+r(\mathcal{A}'') $$
で、lem-ha-region-recursion によりこれは $r(\mathcal{A})$ に等しい。$\square$

lem-ha-regions-convex により、領域は $x_i-x_j$（$\{i,j\}\in E$）の符号の組で決まる。領域 $R$ に、$R$ の上で $x_i< x_j$ なら辺を $i\to j$ と向ける向き付け $o(R)$ を対応させる。$o(R)$ に有向閉路 $i_1\to i_2\to\cdots\to i_k\to i_1$ があれば $x_{i_1}< x_{i_2}< \cdots< x_{i_1}$ となり矛盾するので、$o(R)$ は非巡回的である。異なる領域は符号の組が異なるので $o$ は単射である。逆に非巡回な向き付けには、すべての辺が番号の小さい頂点から大きい頂点へ向くような頂点の番号づけ（位相的整列）がある（有向非巡回グラフ の定理「有向非巡回グラフの言い換え」）。頂点 $i$ の番号を $x_i$ とした点は、その向きに対応する符号の組の領域に属するので、$o$ は全射である。後半は thm-ha-zaslavsky と ex-ha-braid-graphic の 1 から従う。完全グラフの非巡回な向き付けは頂点の全順序と 1 対 1 に対応するので $n!$ 個である。$\square$