Poset について

冨江 雅也

筑波大学数理物質科学研究科Ｄ２

1 Word と order

Section １では Word と subword order, generalized subword order について述べる。これは筆者が若手会で発表した内容である。

A を文字の集合とし A^{∗} を A から生成される有限語の集合とする。このとき subword order を以下のように定義する。

Definition 1 ([1]) a_{1} ⋯ a_{r}, b_{1} ⋯ b_{s} ∈ A^{∗} とする。このとき a_{1} ⋯ a_{r}, ≤_{s} b_{1} ⋯ b_{s} ⟺_{def} ∃i_{1} < ⋯ < ∃i_{r} s.t a_{1} = b_{i_{1}}, ⋯ a_{r} = b_{i_{r}}.

そして subword order のメビウス関数は以下のように計算できる。

Theorem 1 ([1]) μ(u, w) = (−1)^{|w|−|u|} < u, w >. ここで < u, w > は u, v から決まる normal embedding の個数。

P を poset とし P^{∗} を P から生成される有限語の集合とする。このとき generalized subword order を以下のように定義する。

Definition 2 ([4]) p_{1} ⋯ p_{r}, q_{1} ⋯ q_{s} ∈ A^{∗} とする。 p_{1} ⋯ p_{r}, ≤_{ge} q_{1} ⋯ q_{s} ⟺_{def} ∃i_{1} < ⋯ < ∃i_{r} s.t p_{1} ≤ q_{i_{1}}, ⋯ p_{r} ≤ q_{i_{r}}.

generalized subword order から定まるメビウス関数は P が rooted forest のときは計算されている。

Theorem 2 ([4]) P が rooted forest のとき u ≤ w ∈ P^{∗} に対して μ(u, w) = Σ_{η_{u}}(−1)^{d(η_{u,w})}. ただし η_{u,w} は u, v から定まる normal embedding とする。

そして non rooted forest の場合に関しては P = {a, b, c | a < c, b < c} のとき以下のことが予想されていた。 Conjecture 1 ([4]) 0 ≤ i ≤ j としたとき μ(a^{i}, c^{j}) は T_{i+j}(X) における X^{j−i} の係数になるであろう。

ここで T_{m}(X) は第一種 Chebyshev 多項式。即ち T_{m}(cosθ) = cosmθ.

今回上記の予想に関して以下の結果を得た。まず Chebyshev 多項式の一般化〔？〕と思われる式を定義する。

Definition 3 s (≥ 2), m ∈ ℕ とする。 このとき T_{m}^{s} を以下で特徴付けられる多項式とする。（s = 2 のときは Chebyshev 多項式となる。）

（１） T_{0}^{s}(X) = 1, T_{1}^{s}(X) = (s − 1)X （２） T_{m}^{s}(X) + T_{m+2}^{s}(X) = sX · T_{m+1}^{s}(X)

この式を用いて P_{s} = {a_{1}, ⋯ a_{s}, c | a_{i} < c, for i = 1, ⋯ r} のメビウス関数を記述した。

Theorem 3 s(≥ 2), 0 ≤ m ≤ n ,{a^{m}} ∈ {a_{i_{1}} ⋯ a_{i_{m}} | i_{1}, ⋯ i_{m} ∈ {1, ⋯ s}} とする。このとき μ({a^{m}}, c^{n}) は T_{m+n}^{s}(X) における X^{n−m} の係数になる。

2 Phillip-Hall の定理の代数的証明

Section ２ではメビウス関数に関する Phillip-Hall の定理を接合環を用いて証明する。

Theorem 4 (Phillip-Hall) x ≤ y ∈ P に対してメビウス関数は以下のように書ける。 μ([x, y]) = Σ_{0≤i}(−1)^{i}P_{i} ここで P_{i} := ♯{ (x_{0}, x_{1} ⋯ x_{i}) | x = x_{0} < x_{1} < ⋯ < x_{i} = y }

Definition 4 ([5]) P を locally-finite-poset とし K を体とする。いま形式的なベクトル空間 A(P) := Span_{K}{ [x, y] | x ≤ y ∈ P } に対して積を以下のように定義する。

[x, y] · [z, w] := δ_{yz}[x, w]

このとき A(P) は K 代数になる。これを接合環（incidence-algebra）という。単位元は Σ_{x∈P} [x, x] となる

Exercise 1 A(P) が K 代数になることをチェックせよ。また P が有限 poset であるとき A(P) は有限サイズの行列で表現できることを示せ。

つぎに接合環の双対代数を定義する。

Definition 5 ([5]) P を locally-finite-poset とし K を体とする。集合 Hom(A(P), K) := {f |f : A(P) ⟼ K, K − linear} に対して積を以下のように定義する。 f ∗ g([x, y]) := Σ_{x≤z≤y}f([x, z]) · g([z, y]), for x ≤ y ∈ P. このとき Hom(A(P), K) は K 代数になる。そして写像 e : [x, y] ↦ δ_{xy} が単位元となる。 Exercise 2 Hom(A(P), K) が K 代数になることをチェックせよ。

次に Map(P, K) := {ψ | ψ : P ⟼ K } に対して Hom(A(P), K) を作用させる。

Proposition 1 ([5]) ψ ∈ Map(P, K), f ∈ Hom(A(P), K) とする。このとき (ψ)f(x) := Σ_{y≤x}f([y, x])ψ(y) により Map(P, K) は右 Hom(A(P), K) 加群になる。

Proof ψ ∈ Map(P, K), x ∈ P および f, g ∈ Hom(A(P), K) に対して ((ψ)f)g(x) = (ψ)f ∗ g(x) を示せ

ばよい。

((ψ)f)g(x) = Σ_{y≤x}g([y, x])(ψ)f(y) = Σ_{y≤x}Σ_{z≤y}g([y, x])f([z, y])ψ(z) = Σ_{z≤y≤x}f([z, y])g([y, x])ψ(z) = Σ_{z≤x}f ∗ g([z, x])ψ(z) (ψ)f ∗ g(x). □

いま ζ, μ ∈ Hom(A(P), K) を以下のように定める。 ζ([x, y]) := 1, ∀x ≤ y ∈ P. μ([x, x]) := 1, ∀x ∈ P, μ([y, z]) := −Σ_{y≤w<z}μ(y, w) ∀y < z . 〔μ についてはメビウス関数の定義そのものである。〕

Notation 1 メビウス関数の定義を μ([x, x]) := 1, ∀x ∈ P, μ([y, z]) := −Σ_{y<w≤z}μ(w, z) ∀y < z とすることもあるが前述の定義と同値である。一方 ζ をゼータ関数という。

Proposition 2 ([5]) k ∈ ℕ, x ≤ y ∈ P に対して ζ^{k}([x, y]) = ♯{(p_{0}, p_{1}, ⋯ p_{k}) | x = p_{0} ≤ p_{1} ≤ ⋯ ≤ p_{k} = y } (ζ − 1)^{k}([x, y]) = ♯{ (p_{0}, p_{1}, ⋯ p_{k}) | x = p_{0} < p_{1} < ⋯ < p_{k} = y } となる。また十分大きな k ∈ ℕ に対して (ζ − 1)^{k}([x, y]) = 0 が成り立つ。

Proposition 3 ([5]) ζ は Hom(A(P), K) において μ の逆元になる。即ち ζ ∗ μ = 1, μ ∗ ζ = 1。

Proof x ≤ y ∈ P に対して ζ ∗ μ([x, y]) = Σ_{x≤z≤y}ζ([x, z])μ([z, y]) = Σ_{x≤z≤y}μ([z, y]) = δ_{xy} よって ζ ∗ μ = 1. μ ∗ ζ = 1 も同様。 □

Proposition 4 ([5]) ζ の逆元は一意に存在する。 即ち μ は ζ の逆元であり、 f ∈ Hom(A(P), K) に対して f ∗ ζ = 0 ならば f = 0。

Proof 後半部のみ示す。 f ∗ ζ = 0 ⟺ Σ_{x≤z≤y}f([x, z])ζ([z, y]) = 0, ∀x ≤ y ∈ P ⟺ Σ_{x≤z≤y}f([x, z]) = 0 あとは x と y の距離に関する帰納法より従う。 □ Theorem 5 (Phillip-Hall) x ≤ y ∈ P に対してメビウス関数は以下のように書ける。

μ([x, y]) = Σ_{0≤i}(−1)^{i}P_{i} ここで P_{i} := ♯{ (x_{0}, x_{1} ⋯ x_{i}) | x = x_{0} < x_{1} < ⋯ < x_{i} = y }。

Proof μ ∗ ζ([x, y]) = δ_{xy} ⟺ μ([x, y]) = 1 ∗ (ζ)^{−1}([x, y]) = 1 ∗ (1 + (ζ − 1))^{−1}([x, y]) ⟺ μ([x, y]) = Σ_{0≤i}(−1)^{i}(ζ − 1)^{i}([x, y]) ⟺ μ([x, y]) = Σ_{0≤i}(−1)^{i}P_{i} □ 次に poset におけるメビウス反転公式を示す。

Theorem 6 ([5]) ψ, ϕ ∈ Map(P, K), x ∈ P に対して、 ψ(x) = Σ_{y≤x}ϕ(y) ⟺ ϕ(x) = Σ_{y≤x}μ([y, x])ψ(y)。

Proof これは Map(P, K) を Hom(A(P), K) 加群とみたときに (ψ)μ = ϕ ⟺ (ϕ)ζ = ψ となることより

従う。 □

3 Subword order, composition order, symmetric group...

Section ３では subword order{a, b}^{∗} と composition order そして対称群の間に成り立つ興味深い対応について述べる。詳しくは [3] を参照のこと。

α = (a_{1}, a_{2}, ⋯ a_{r}) が n の composition であるとは Σ_{i=1}^{r}a_{i} = n, a_{i} ∈ ℕ_{≥1} をなるときをいう。そして n の composition 全体を Σ(n) と書く。また Σ := ⨄ Σ(n) とおく。たとえば Σ(3) = { (111), (12), (21), (3) } である。

Exercise 3 ♯Σ(n) = 2^{n−1} を示せ。

次に Σ に order を入れて poset にする。

Definition 6 (a_{1}, ⋯ a_{k}), (b_{1} ⋯ bl) ∈ Σ とする。

(a_{1}, ⋯ a_{k}) ≺ (b_{1} ⋯ b_{l}) ⟺_{def} (b_{1} ⋯ b_{l}) = (a_{1}, ⋯ a_{i−1}, t, a_{i} + 1 − t, a_{i+1}, ⋯ a_{k}) for some i, and 1 ≤ t ≤ a_{i}.

注意 poset の元 a, b に対して a ≺ b とは a < c < b なる c が存在しないときをいう。いま Σ と {a, b} の間に順序同型を構成する。 Ψ : {a, b} ⟹ {1, +1}

Ψ(c_{1}c_{2} ⋯ c_{r}) ⟼ 1ψ(c_{1})ψ(c_{2}) ⋯ ψ(c_{r})

但し ψ(a) = +1, ψ(b) = 1

Φ : {1, +1} ⟹ Σ

Φ(\underbrace{1 ⋯ 1}_{i_{1}times} + \underbrace{1 ⋯ 1}_{i_{2}times} ⋯ + \underbrace{1 ⋯ 1}_{i_{k}times}) = (i_{1}, i_{2} ⋯ i_{k})

但し i_{1}, i_{k} ≥ 1, i_{≥2} ≥ 0

とおく。 Example 1 Φ ∘ Ψ(aabababb) = 1 + 1 + 11 + 11 + 111 ⟼ (1, 1, 2, 2, 3).

Φ ∘ Ψ(baabbabbb) = 11 + 1 + 111 + 1111 ⟼ (2, 1, 3, 4).

Exercise 4 Φ ∘ Ψ が順序同型であることを確かめよ。

つぎに対称群の元と composition order における saturated chain の間に一対一対応をつける。 w ∈ S_{n} を数列 (w(1), w(2), ⋯ w(n)) と同一視して考える。

Definition 7 w ∈ S_{n} としたとき w の descent D(w) を以下のように定める。 D(w) = {i | w(i) > w(i + 1)}. 対応する descent composition C(w) = (α_{1}, ⋯ α_{k}) ∈ Σ_{n} を D(w) = {α_{1}, α_{1} + α_{2}, α_{1} + α_{2} + α_{3}, ⋯ α_{1} + ⋯ α_{k−1}} となるように定める。

Example 2 w = (2, 4, 3, 1) とした時は D(w) = {2, 3}, C(w) = (2, 1, 1) となる。

いま w ∈ S_{n} を {1, ⋯ i} に制限したものを w[i] ∈ S_{i} とし Σ_{n} において 1 を始点とする長さ n − 1 の saturated chain の集合を Sat_{n} とする。

𝔐 : S_{n} ⟶ Sat_{n} 𝔐(w) ⟼ {1 = C(w[1]) ≺ C(w[2]) ≺ ⋯ ≺ C(w[n])}.

Example 3 w = (3, 1, 4, 5, 2) としたとき w([1]) = (1), w([2]) = (1, 2), w([3]) = (3, 1, 2), w([4]) = (3, 1, 4, 2), w([5]) = (3, 1, 4, 5, 2) となる。

そして D(w[1]) = ϕ, D(w[2]) = ϕ, D(w[3]) = {1}, D(w[4]) = {1, 3}, D(w[5]) = {1, 4} より C(w[1]) = {1}, C(w[2]) = {2}, C(w[3]) = {1, 2}, C(w[4]) = {1, 2, 1}, C(w[5]) = {1, 3, 1} となる。明らかに {1} ≺ {2} ≺ {1, 2} ≺ {1, 2, 1} ≺ {1, 3, 1}). よって (C(w[1]), C(w[2]), C(w[3]), C(w[4]), C(w[5])) は saturated-chain になっている。

Exercise 5 𝔐 が一対一対応になっていることを確かめよ。

以上をまとめると Φ ∘ Ψ 及び 𝔐 という自然な写像によって {a, b} と composition order、そして対称群が結ばれている。

Reference

[1] Björner, A. The Mobius function of factor order. Theoret. Comput. Sci. 117, 1-2 (1993) 91-98

[2] Björner, A. Sagan, B, E. Rationality of the Mobius function of the composition poset. Theoret. Comput. Sci. 359 (2006), no.1-3, 282-298.

[3] Björner, A. Stanley, R, P. An analogue for compositions. arXiv:math.CO/0508043.

[4] Sagan, B, E. Vatter, V. The Mobius function of the composition poset. J. Algebraic, Combin. 24 (2006), no.2,117-136.

[5] Stanley, R, P. Enumerative combinatorics. Vol. 1, vol. 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press Cambridge, 1997.