代数的組合せ論

同義語:algebraic combinatorics

概要

代数的組合せ論(algebraic combinatorics)とは、有限の組合せ構造についての問題を線形代数・群の作用・表現・対称関数などの代数の道具で解き、逆に代数に現れる量を組合せの対象の個数として記述する分野である。主な主題は、行列による歩道や全域木の数え上げ、群の作用による数え上げ、Young 図形と盤、対称関数、半順序、アソシエーションスキームである。たとえば Young 図形の上で箱を 1 個加える作用素 $U$ と除く作用素 $D$ は $DU-UD=I$ を満たし、この関係だけから標準盤の個数の平方和が $n!$ に等しいことが従う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 組合せ論, 線形写像, Young図形

代数的組合せ論(algebraic combinatorics)とは、有限の組合せ構造についての問題を線形代数・群の作用・表現・対称関数などの代数の道具で解き、逆に代数に現れる量を組合せの対象の個数として記述する分野である。中心の問いは、数えたいものを行列や作用素の言葉に写せるか、代数の計算で現れる非負整数は何を数えているか、対称性をどう計算に使うか、である。
この記事は分野の地図である。主な問いと代表的な結果を表にして、それぞれの記事へ案内する。続いて、分野の味が分かる例として、Young 図形の上の 2 つの作用素の交換関係だけから $\sum_\lambda(f^\lambda)^2=n!$ を証明する。

定義

分野の出発点は、集合をベクトル空間に置き換え、関係を行列に置き換えることである。

集合と関係の線形化

集合 $S$ に対し、$S$ を基底とする実ベクトル空間($S$ の元の有限個の線形結合の全体)を $\mathbb{R}S$ と書く。$S$ と $T$ の間の関係 $R\subset S\times T$ が、各 $s\in S$ について $(s,t)\in R$ となる $t$ を有限個しかもたないとき、線形写像 $\varphi_R\colon\mathbb{R}S\to\mathbb{R}T$ を $\varphi_R(s):=\sum_{(s,t)\in R}t$ で定める。これを $R$ の 線形化 という。

線形化の要点は、写像の合成が「途中の点を数える」ことになる点である。$R\subset S\times T$、$R'\subset T\times U$ について、$\varphi_{R'}\circ\varphi_R(s)$ における $u$ の係数は、$(s,t)\in R$ かつ $(t,u)\in R'$ となる $t$ の個数に等しい。したがって $k$ 回の合成の係数は長さ $k$ の鎖の個数を数える。グラフの隣接関係を線形化したものが 隣接行列 であり、$A^k$ の成分が長さ $k$ の歩道の個数を与えるのはこの特別な場合である(Sta13 Theorem 1.1、p. 10)。
数えたい量を線形写像の行列式・固有値・トレースで表せれば、線形代数の定理がそのまま数え上げの定理になる。逆向きの流れもある。対称多項式や群の表現に現れる係数が非負整数であるとき、それが何かの個数であることを示すと、計算が組合せの操作に置き換わる。Schur多項式 が半標準盤の重みの和で表されることがその典型である。

主な問題と結果の一覧

問い代表的な結果入る記事
歩道はいくつあるか$A^k$ の成分が長さ $k$ の歩道の個数で、閉じた歩道の総数は固有値の $k$ 乗和である隣接行列
全域木はいくつあるか全域木の個数は Laplacian 行列の余因子に等しい(BH11 Proposition 1.3.4)行列木定理
交わらない道の組はいくつあるか道の重みの和を並べた行列の行列式は、頂点を共有しない道の組の符号つきの和に等しいLindström–Gessel–Viennotの補題
対称性を除くといくつあるか軌道の個数は固定点の個数の平均である。塗り分けでは巡回指数に重みの冪和を代入すれば目録が得られるBurnsideの補題、Pólyaの数え上げ定理
盤はいくつあるか標準盤の個数は $n!$ を鉤の長さの積で割ったものであるYoung図形
置換と盤はどう対応するかRSK 対応は、非負整数の行列と同じ形の半標準盤の組の全単射であるRobinson–Schensted–Knuth対応
対称多項式の良い基底は何かSchur 関数は対称関数環の $\mathbb{Z}$ 基底で、Hall 内積の正規直交基底である対称関数、Schur多項式、Macdonald多項式
順序の中の反鎖はどこまで大きいか$n$ 元集合の反鎖の大きさは $\binom{n}{\lfloor n/2\rfloor}$ 以下であるSpernerの定理、Dilworthの定理
半順序の上で包除原理はどうなるかMöbius 関数が反転公式を与える数え上げ組合せ論、Möbiusの反転公式
関係の表はどんな代数をなすかアソシエーションスキームの関係の行列は可換な Bose–Mesner 代数を張り、Delsarte の線形計画限界を与えるアソシエーションスキーム
集合族の大きさを次元で抑えられるか$n$ 元集合の部分集合の族で、各元の大きさが奇数、2 つの共通部分の大きさが偶数なら、族の大きさは $n$ 以下である(Oddtown の定理)組合せ論
多面体の格子点はいくつあるか格子多面体を $t$ 倍したものの格子点の個数は $t$ の多項式であるEhrhart多項式
鏡映の群の組合せは何を数えるか対称群の Coxeter 関係式を満たす差分商から Schubert 多項式が定まるCoxeter系、Schubert多項式

これらの主題の教科書的な入口として Sta13 がある。歩道(第 1〜3 章)、Sperner 性(第 4〜6 章)、群の作用による数え上げ(第 7 章)、Young 盤(第 8 章)、行列木定理(第 9 章)、電気回路(第 11 章)を、線形代数を共通の道具として扱っている。

具体例:Young 束の 2 つの作用素

$n$ の分割 $\lambda$ を Young図形 と同一視し、箱の集合の包含で順序を入れる。空の図形 $\emptyset$ も含めた全体を Young 束 $Y$ という。$\lvert\lambda\rvert$ で箱の個数を表す。$\lambda$ を箱を 1 個ずつ増やして作る列($\emptyset\subset\lambda^{(1)}\subset\dots\subset\lambda^{(n)}=\lambda$、$\lvert\lambda^{(i)}\rvert=i$)は、箱に入る順に $1,\dots,n$ を書いたものが標準盤になるので、$\lambda$ の標準盤の個数 $f^\lambda$ はこの列の個数に等しい。

上昇作用素と下降作用素

$\lambda\subset\mu$、$\lvert\mu\rvert=\lvert\lambda\rvert+1$ である組の関係を線形化して、線形写像 $U,D\colon\mathbb{R}Y\to\mathbb{R}Y$ を
$$ U\lambda:=\sum_{\mu\supset\lambda,\ \lvert\mu\rvert=\lvert\lambda\rvert+1}\mu,\qquad D\lambda:=\sum_{\nu\subset\lambda,\ \lvert\nu\rvert=\lvert\lambda\rvert-1}\nu $$
で定める($D\emptyset:=0$)。

交換関係

$\mathbb{R}Y$ の上で $DU-UD=I$ である。

$\lvert\lambda\rvert=i$ とする。$DU\lambda$ と $UD\lambda$ はどちらも箱 $i$ 個の図形の線形結合なので、箱 $i$ 個の図形 $\mu$ の係数を比べる。
$\mu\ne\lambda$ のとき。$DU\lambda$ の $\mu$ の係数は、$\lambda$ と $\mu$ をともに含む箱 $i+1$ 個の図形の個数である。そのような図形は和集合 $\lambda\cup\mu$ を含むので、$\lvert\lambda\cup\mu\rvert=i+1$ のときに限り、$\lambda\cup\mu$ の 1 個だけある(2 つの Young 図形の和集合と共通部分はまた Young 図形である)。同様に、$UD\lambda$ の $\mu$ の係数は、$\lvert\lambda\cap\mu\rvert=i-1$ のとき $1$、それ以外のとき $0$ である。$\lvert\lambda\cup\mu\rvert+\lvert\lambda\cap\mu\rvert=2i$ なので 2 つの条件は同値であり、2 つの係数は等しい。
$\mu=\lambda$ のとき。$DU\lambda$ の $\lambda$ の係数は箱を加えられる場所の個数で、$UD\lambda$ の $\lambda$ の係数は箱を除ける場所の個数である。$\lambda$ の行の長さの相異なる正の値が $r$ 個あるとする。箱を除けるのは同じ長さの行の並びの最後の行の右端だけなので $r$ 個ある。箱を加えられるのは同じ長さの行の並びの最初の行の右と、最初の空の行だけなので $r+1$ 個ある。差は $1$ である。$\square$

標準盤の個数の平方和

$n\ge0$ について $\displaystyle\sum_{\lvert\lambda\rvert=n}(f^\lambda)^2=n!$ である。

$v_k:=U^k\emptyset$ とおく。$Dv_k=kv_{k-1}$($k\ge1$)を $k$ についての帰納法で示す。$k=1$ なら $DU\emptyset=UD\emptyset+\emptyset=\emptyset$ である。$k\ge2$ なら thm-ac-commutator により
$$ Dv_k=DUv_{k-1}=UDv_{k-1}+v_{k-1}=(k-1)Uv_{k-2}+v_{k-1}=kv_{k-1} $$
である。したがって $D^nv_n=n!\,\emptyset$ である。
$U^n\emptyset$ の $\lambda$ の係数は $\emptyset$ から $\lambda$ まで箱を 1 個ずつ増やす列の個数なので $f^\lambda$ であり、$v_n=\sum_{\lvert\lambda\rvert=n}f^\lambda\lambda$ である。同様に $D^n\lambda$ は $f^\lambda\emptyset$ である。よって $n!\,\emptyset=D^nv_n=\sum_\lambda f^\lambda\cdot f^\lambda\,\emptyset$ である。$\square$

交換関係は Sta13 Lemma 8.3(pp. 135–136)、平方和は Corollary 8.5(p. 138)にある(そこでは一般の語の場合の定理から導く)。

箱が 3 個の場合

$U\emptyset=(1)$、$U(1)=(2)+(1,1)$、$U(2)=(3)+(2,1)$、$U(1,1)=(2,1)+(1,1,1)$ なので、$U^3\emptyset=(3)+2\,(2,1)+(1,1,1)$ である。係数の平方の和は $1+4+1=6=3!$ である。

同じ等式は Robinson–Schensted–Knuth対応 の全単射からも、対称群の既約表現の次元の平方和としても得られる。ここでの証明は全単射を作らず、$DU-UD=I$ という 1 つの関係だけで進む。線形化すると、証明が交換関係の計算になる。

反例:どの半順序でも同じではない

thm-ac-commutator は Young 束の性質であり、半順序の一般の性質ではない。$n$ 元集合の部分集合全体(ブール束)で同じように上昇作用素と下降作用素を定めると、$\lvert S\rvert=i$ の $S$ について $US$ は $n-i$ 項、$DS$ は $i$ 項の和である。非対角成分は Young 束のときと同じように打ち消し合い、対角成分の比較から
$$ DU-UD=(n-2i)I $$
となり(Sta13 Lemma 4.6、p. 52)、右辺は $i$ によって変わる。実際、cor-ac-sum に当たる式も成り立たない。

半順序主張反例
ブール束階数 $k$ の元への極大鎖の個数の平方和は $k!$ である空集合から $S$ への鎖は $\lvert S\rvert!$ 本なので、$n=k=2$ で平方和は $(2!)^2=4\ne2!$ である

ブール束の式の右辺が $i$ によって変わることも無駄ではなく、$i< n/2$ で $U$ が単射になることが出て、Spernerの定理 の線形代数による証明になる(Sta13 第 4 章、Corollary 4.8、p. 53)。

読み進め方

段階記事身につくこと
1. 土台組合せ論、数え上げ組合せ論、隣接行列数え上げの基本と、行列で数えること
2. 行列式と対称性行列木定理、Lindström–Gessel–Viennotの補題、Burnsideの補題 → Pólyaの数え上げ定理行列式と群の作用による数え上げ
3. 盤と対称関数Young図形 → Robinson–Schensted–Knuth対応、対称多項式 → Schur多項式 → 対称関数盤の組合せと対称関数の基底
4. 発展Macdonald多項式、Coxeter系 → Schubert多項式、アソシエーションスキーム、Ehrhart多項式主題ごとの深い構造

段階 2 と段階 3 は独立に読める。段階 3 は 対称群 の基本を使う。

未解決問題

いずれも Sta13(2013 年の版)の時点の記述である。

  • Hadamard 予想:$4$ の倍数のすべての $n$ に $n$ 次の Hadamard行列 が存在するか。
  • 巡回 Hadamard 行列の予想:巡回行列である $n$ 次の Hadamard 行列は $n=1,4$ に限るか(Sta13 §12.6)。
  • 再構成予想:頂点が 3 個以上のグラフは、頂点を 1 個ずつ除いた部分グラフの多重集合から決まるか。辺を除く形の予想の特別な場合には、ブール束への群の作用の線形代数による証明がある(Sta13 Theorem 5.10、pp. 67–68)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する