↓メインコンテンツへスキップ
組合せ論、楽しい！

【月刊組合せ論 Natori】Stanley-Stembridge 予想【2024 年 11 月号】

·
箱星
著者
箱星
のんびり暮らしたい。
目次

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回は彩色対称関数に関する未解決問題である Stanley-Stembridge 予想を紹介します。

彩色対称関数
#

彩色数や彩色多項式については過去記事で少し解説しました。

【月刊組合せ論 Natori】June Huh 氏の業績を解説【2022 年 12 月号】

グラフ G=(V,E)G=(V,E) の彩色多項式 cG(n)c_G(n) とは、グラフの頂点を nn 色のうちのいずれかで塗る方法であって、隣り合う 2 頂点が異なる色で塗られているものの個数です。

彩色対称関数は Stanley によって導入されました。色の集合を P={1,2,…}\mathbb{P}=\{1,2,\ldots\} とします。色塗りのことを関数 κ ⁣:V→P\kappa\colon V\to\mathbb{P} だと思うことにします。x=(x1,x2,…)x=(x_1,x_2,\ldots) を変数とします。彩色対称関数は

XG(x)=∑κ∏v∈Vxκ(v) X_G(x)=\sum_{\kappa}\prod_{v\in V}x_{\kappa(v)}

により定義されます。ここで κ\kappa は前述の通り隣り合う 2 頂点が異なる色であるような塗り方です。

例えば κ\kappa を次のような塗り方とします。

image

赤が 1、青が 2、黄色が 3 であるとするとき、XG(x)X_G(x) に x12x22x3x_1^2x_2^2x_3 という項が現れることになります。

XG(1,…,1⏟n,0,0,…)X_G(\underbrace{1,\ldots,1}_n,0,0,\ldots) は彩色多項式 cG(n)c_G(n) に等しいことがわかります。このことから彩色対称関数は彩色多項式より多くの情報をもっていることがわかります。

基底
#

対称関数のなす空間には代表的な基底があります。それは

  • mλm_{\lambda} : モノミアル対称関数
  • hλh_{\lambda} : 完全対称関数
  • eλe_{\lambda} : 基本対称関数
  • pλp_{\lambda} : べき和対称関数
  • sλs_{\lambda} : シューア対称関数

です。彩色対称関数もまた、これらの基底の線形結合として表すことができます。

線形結合として表したとき、係数が非負整数になることがあります。このとき何か特別な意味があるのではないかと期待できます。例えばシューア関数は対称群の既約表現と対応するので、シューア関数の非負整数線形結合として表せるということは、対称群の表現と対応することが期待されます。

では彩色対称関数はシューア関数の非負整数線形結合として表せるでしょうか？

長いので以降は ss-positive ということにします (ee-positive なども同様)。

まず GG を完全グラフ KnK_n とします。すると XG(x)=n!en=n!s(1,…,1)X_G(x)=n!e_n=n!s_{(1,\ldots,1)} となります。よって ee-positive であり ss-positive でもあります。

では次のようなグラフではどうでしょうか。

image

このグラフは爪 (claw) と呼ばれています。実は XG=4e4+5e31−2e22+e211X_G=4e_4+5e_{31}-2e_{22}+e_{211} となります。係数に −2-2 が現れるので ee-positive ではありません。ss-positive でもありません。

比較不能性グラフ
#

PP を半順序集合とします。PP から次のようにグラフを作ります。頂点集合は PP と同一とし、u,v∈Pu,v\in P に対して u≤vu\le v でも v≤uv\le u でもないとき辺を張ります。このグラフを inc(P)\mathrm{inc}(P) とし、比較不能性グラフと呼ぶことにします。

PP が次の図を induced subposet して含まないとき、PP は (3+1)(3+1)-free といいます。

image

PP がこの図のような poset であるとき、inc(P)\mathrm{inc}(P) は爪となります。爪は ee-positive でなかったので、(3+1)(3+1)-free poset から得られるグラフ inc(P)\mathrm{inc}(P) は ee-positive でない可能性が減っていると考えられます。

そして本題の Stanley-Stembridge 予想とは、このとき必ず ee-positive になるという予想です。

予想 (Stanley-Stembridge): PP が (3+1)(3+1)-free poset ならば、比較不能性グラフ inc(P)\mathrm{inc}(P) の彩色対称関数は ee-positive である。

なお ss-positive であることは Gasharov によって証明されています。一般に ee-positive ならば ss-positive なので、この結果は Stanley-Stembridge 予想よりも弱い結果ということになります。

証明？
#

Stanley-Stembridge 予想は長くの間未解決問題でしたが、最近になって証明が発表されました。

https://arxiv.org/abs/2410.12758

まだプレプリントの段階なので正しいかはわかりませんが、正しければ一大ニュースですね。

その他の話題
#

Hessenberg 多様体との関連など、近年では彩色対称関数の研究はますます盛り上がっています。それも解説したかったのですが、時間がなかったのでまたいつか解説したいと思います。