称号及び氏名

博士（理学）

大倉 健吾

学位授与の日付 2023 年 3 月 31 日

論文

名Polyhedral Join of Simplicial Complexes and its Application to GraphTheory（単体的複体のポリヘドラルジョイン、およびそのグラフ理論への応用）

論文審査委員

主査
副査
副査
副査
副査

山口 睦
壁谷 喜継
丸田 辰哉
蓮井 翔
源 泰幸

Polyhedral Join of Simplicial Complexes and its Application to Graph Theory（単体的複体のポリヘドラルジョイン、およびそのグラフ理論への応用）論文要旨
大倉健吾
大阪府立大学大学院 理学系研究科 博士後期課程 数理科学専攻
圏 C を適当な位相空間の圏や単体的複体の圏とする。結合的な演算 ⋆ : C × C → C が条件「iA : A → X,

iB : B → Y が包含写像ならば iA ⋆ iB : A ⋆ B → X ⋆ Y もそう」を満たすとき、[m] = {1, 2, . . . , m} を頂点集合とする単体的複体 K と空間（複体）対の族 (X, A) = {(Xi , Ai )}i∈[m] は X1 ⋆ X2 ⋆ · · · ⋆ Xm の部分空間（複体）の和集合⋆ZK(X, A) =[(Y1σ ⋆ Y2σ ⋆ · · · ⋆ Ymσ ,Yiσ =σ∈K

Xi(i ∈ σ),Ai(i ∈/ σ)⋆を定める。（以下、(X, A) のすべての対がある対 (X, A) に等しいときは、ZK(X, A) と表記する。）この構成の代表例は ⋆ が空間の積 × である「ポリヘドラルプロダクト」であり、Bahri, Bendersky, Cohen, andGitler [2, Deﬁnition 2.1] によって導入されて以来、多くの研究者によって調べられてきた。本研究が扱うのは、圏 C を単体的複体の圏、あるいは有限 CW 複体の圏とし、⋆ をジョイン ∗ とする「ポリヘドラルジョイン」である。ポリヘドラルジョインは Ayzenberg [1, Deﬁnition 4.2, Observation 4.3] によって定義された。
ポリヘドラルプロダクトと異なり、空間の圏だけでなく単体的複体の圏でもしばしば考えられている。本研究では単体的複体のポリヘドラルジョインについて、その shellability と呼ばれる性質、および幾何学的実現のホモトピー型について調べる。
（純とは限らない）単体的複体の shellability は Björner and Wachs [3, 4] によって導入された。単体的複体 K の極大単体の全順序 F1 , F2 , . . . , Ft を条件「F1 , . . . , Fk−1 で作られる K の部分複体と Fk の共通部分が (dim Fk − 1) 次元の純な部分複体である」が k = 2, 3, . . . , t で成り立つように定められることをいう。
（この全順序を shelling と呼ぶ。
）単体的複体の shellability は、その幾何学的実現が球面のウェッジにホモトピー同値（または可縮）であるための十分条件であるなど、重要な性質である。以下に本研究で得られた結果の一部を挙げる。これらの結果は、後でグラフ理論に応用される。（以下、単体的複体 K の極大単体全体をFK と書く。）
Theorem 1. M を V (M ) = {1, 2, . . . , m} なる単体的複体、(K, L) = {(Ki , Li )}i∈[m] を単体的複体の対の族とする。M が shellable であり、任意の i ∈ [m] に対し• FLi ⊂ {αi \ {x} | x ∈ αi } なる αi ∈ FKi が存在し、• αi が最小元になるような全順序で Ki の shelling であるようなものが存在する∗
とき、ZM(K, L) は shellable である。（この結果は、Moradi and Khosh-Ahang の結果 [7, Theorem 2.12]の拡張である。）∗Theorem 2. M を単体ではない単体的複体、K ⊋ L を単体的複体の対とする。ZM(K, L) が shellable ならば、σ ∈ FK \ FL と τ ∈ FL であって# (σ ∩ τ ) =maxρ∈FK \FLが成り立つようなものが存在する。

1# (ρ) − 1

Theorem 3. M を単体ではない単体的複体、K を単体的複体とする。K の頂点 v0 に対し、K の部分複体∗dlK (v0 ) = {σ ∈ K | v0 ∈/ σ} を考える。FdlK (v0 ) ⊂ FK が成り立つとき、ZM(K, dlK (v0 )) が shellable であるための必要十分条件は、K と dlK (v0 ) がともに shellable であることである。
次に、ポリヘドラルジョインの幾何学的実現について述べる。以下、単体的複体 K の幾何学的実現を |K|で書く。幾何学的実現のホモトピー型を調べるにあたっては、まず次の定理を証明した。

Theorem 4. M を V (M ) = {1, 2, . . . , m} なる単体的複体、(K, L) = {(Ki , Li )}i∈[m] を単体的複体の対の族とする。このとき、(|K|, |L|) = {(|Ki |, |Li |)}i∈[m] とおけば、∗∗|ZM(K, L)| ∼(|K|, |L|)
= ZMが成り立つ。
よって、ポリヘドラルジョインの幾何学的実現の研究は、有限 CW 複体の圏におけるポリヘドラルジョインの研究に帰着される。ただし、本研究では一般の有限 CW 複体の対 (X, A) ではなく、任意の i ∈ V (K) について Ai = ∅ なるような対についてのみについて考えることとした。（この場合のポリヘドラルジョインを∗(X) と書く。）さらに、単体的複体 K にも条件をつけて検討した。この条件は Björner and Wachs [4] のZK“vertex-decomposability” を強めたものであり、本研究では “s-vertex-decomposability” と名づけた。これらの仮定の下で、次の結果を得た。

Theorem 5. K を V (K) = {1, 2, . . . , m} なる空でない連結な単体的複体、X = {Xi }i=1,2,...,m を有限CW 複体の族とする。K が s-vertex-decomposable ならば、非負整数の組の族 {(rα , k1,α , . . . , km,α )}α∈A があって∗ZK(X) ≃_ ∗k∗km,αΣrα X1 1,α ∗ · · · ∗ Xm

α∈Aが成り立つ。ここで、Σr X は X と (r − 1) 次元球面 S r−1 のジョイン、X ∗k は k 個の X のジョインを表す。

Theorem 6. X を有限 CW 複体とする。I(Ln ) をI(Ln ) = {σ ⊂ {1, 2, . . . , n} | 任意の i, j ∈ σ について |i − j| ̸= 1}で定まる単体的複体とするとき、

XX ⊔X∗2∗
ZI(Ln ) (X) ≃ X ⊔ X_ _r ∗kΣXk+1
(n−2k−3r+1)(k+rr )(n = 1),(n = 2),(n = 3),(n ≥ 4)k,r∈N≥0が成り立つ。ただし、 pq は二項係数であり、q < 0 または p < q のときはpq

= 0 と定める。

これらのポリヘドラルジョインに関する結果を、「独立複体」を介してグラフ理論に応用する。以下、有限で多重辺やループのない無向グラフを考えることとし、単にグラフと呼ぶ。Ln は V (Ln ) = {1, 2, . . . , n} かつE(Ln ) = {ij | |i − j| = 1} なるグラフ、Cn は n 角形の形をしたグラフとする。グラフ G の独立複体 I(G)

2

とは、

I(G) = {σ ⊂ V (G) | 任意の u, v ∈ σ について uv ∈/ E(G)}と定義される単体的複体である。I(G) の単体は G の独立集合と呼ばれる。独立複体はグラフから定義される他の単体的複体と同様に重要であり、様々な文脈で研究されている。ポリヘドラルジョインとグラフの独立複体は、次の命題によって関連付けられる。

Proposition 7. グラフ G, H と H の頂点の集合 U ⊂ V (H) に対して、グラフ G[H; U ] を
V (G[H; U ]) = V (G) × V (H),
E(G[H; U ]) = (u1 , v1 )(u2 , v2 )
u1 = u2 and v1 v2 ∈ E(H), またはu1 u2 ∈ E(G) and v1 , v2 ∈ U

で定める。このとき、∗I(G[H; U ]) = ZI(G)(I(H), I(H \ U ))が成り立つ。ただし、H \ U は V (H \ U ) = V (H) \ U 、E(H \ U ) = {uv ∈ E(H) | u, v ∈/ U } なるグラフである。

G[H; U ] の特別な場合として、U = V (H) とおいたものは G と H の「辞書式積」（または「合成」）と呼ばれる。また、H の頂点 v0 について U = {v0 } とおいたものは、グラフ G の各頂点に H を頂点 v0 で貼り付けたグラフである。
グラフ G に対し、その独立複体 I(G) が単体的複体として shellable であるとき、グラフ G は shellable なグラフであるという。グラフの shellability は、十分条件である vertex-decomposability も含め、多くの研究者によって調べられている。Vander Meulen and Van Tuyl [8, Theorem 2.3] は、辞書式積の shellabilityについて調べ、G[H] が shellable であるのは H が完全グラフであるときに限ることを示した。（この事実は、本研究の Theorem 2 からも導かれる。）また、Hibi, Higashitani, Kimura, and O’Keefe [5, Theorem

1.1] は、グラフの各頂点に完全グラフを貼り付けて得られるグラフが常に shellable であることを示した。この結果を拡張したものとして、Theorem 3 から次が得られる。（グラフは、その独立複体が純であるとき、well-covered であるという。）
Theorem 8. H をグラフ、v0 を H の頂点とするとき、次の２つの条件は同値である。
1. 任意のグラフ G について、G[H; {v0 }] は well-covered かつ shellable である。
2. H は well-covered、H と H \ {v0 } はともに shellable であり、H \ {v0 } の任意の極大独立集合 τ はv0 に隣接する頂点 v ∈ τ を含む。
なお、条件 2. を満たし、完全グラフでないグラフ H の例には C5 がある。
次に、独立複体の幾何学的実現のホモトピー型の研究について述べる。独立複体の幾何学的実現は、Kozlov[6, Proposition 4.6, 5.2] が |I(Ln )| と |I(Cn )| のホモトピー型を求めて以来、盛んに研究されている。本研究では、まず次のことが示される。ここで、グラフ G の閉路とは、G の頂点の列 v0 , v1 , . . . , vn であり、任意のi = 1, 2, . . . , n に対して vn−1 vn ∈ E(G)、かつ任意の i, j = 0, 1, . . . , n − 1 に対して vi ̸= vj 、かつ v0 = vnなるものであり、閉路が存在しないグラフを森という。

3

Theorem 9. グラフ G が森ならば、I(G) は s-vertex-decomposable である。
この定理を用いることで、Theorem 5 から、グラフの辞書式積の独立複体の幾何学的実現について次の結果が得られる。

Theorem 10. G を森、H をグラフとする。G の任意の頂点 u について、u と隣接しない頂点 v が存在すると仮定する。また、|I(H)| は球面のウェッジにホモトピー同値であるとする。このとき、|I(G[H])| も球面のウェッジにホモトピー同値である。
先行研究では、独立複体の幾何学的実現が球面のウェッジになるようなグラフは多数発見されている。そのようなグラフを H とすれば、森 G との辞書式積 G[H] の独立複体の幾何学的実現もまた球面のウェッジにホモトピー同値になる。

Theorem 6 からは、次の結果が導かれる。先行研究でよく用いられる「離散モース理論」という手法が利用しづらい状況において、独立複体の幾何学的実現のホモトピー型を求めることに成功した。

Theorem 11. グラフ H の独立複体の幾何学的実現 |I(H)| が n 個の k 次元球面のウェッジ

WnSkにホモトピー同値であるとき、次が成り立つ。

_ kSn_ _kk
SS⊔
 _n n_
|I(Lm [H])| ≃2k+1kSS⊔2nn
_ _dS∑p+1d−pk+1p)p≥0 n (3(d−pk+1)−m)(p(m = 1),(m = 2),(m = 3),(m ≥ 4).

d≥0

特に、Kozlov [6, Proposition 4.6, 5.2] による |I(Ln )| と |I(Cn )| の計算を用いることで、Theorem 11 から|I(Lm [Ln ])| や |I(Lm [Cn ])| のホモトピー型が任意の m, n に対して求められる。グラフの積はいくつかの種類が知られており、その一つである「カルテシアン積」 × について、Lm × Ln や Lm × Cn は格子状のグラフである。これらのグラフは、m, n が大きいときは独立複体の幾何学的実現のホモトピー型を求めることは困難であり、本研究の成果とは対照的な状況である。
最後に、shellability をホモトピー型の側面からも調べた本研究の成果として、shellable なグラフの独立支配数と、独立複体上のポリヘドラルジョインの連結性の関係について述べる。独立支配数は、グラフの極大独立集合の要素の個数の最小値である。Woodroofe [9, Corollary 19] はグラフの独立支配数と独立複体のホモロジー連結性の間に成り立つ不等式を得た。本研究では、Theorem 1 を用いてポリヘドラルジョイン∗ZI(G)(S 0 ) のホモトピー型を調べることで、shellable なグラフ G の独立支配数 i(G)（グラフ不変量）と Gから構成される空間のホモロジー連結性（ホモトピー不変量）を、不等式ではなく等式で結びつける次の結果を得た。

Theorem 12. K が shellable な単体的複体であるとき、
∗
connH ZK(S 0 ) = min # (σ) − 2σ∈FKが成り立つ。特に、shellable なグラフ G に対して、

∗
connH ZI(G)(S 0 ) = i(G) − 2が成り立つ。

4

学位論文草稿の基礎となっている論文[1] Shellability of Polyhedral Join of Simplicial Complexes and its Application to Graph Theory, KengoOkura, The Electronic Journal of Combinatorics, 29(3) ⟨ #P3.53 ⟩ (2022).
[2] Independence Complex of the Lexicographic Product of a Forest, Kengo Okura, Discrete Mathematics, 投稿中.

論文要旨の参考文献[1] A. A. Ayzenberg, Substitutions of polytopes and of simplicial complexes, and multigraded Betti
numbers, Transactions of the Moscow Mathematical Society, 74:175–202, 2013.
[2] A. Bahri, M. Bendersky, F.R. Cohen, and S. Gitler, The polyhedral product functor: A method ofdecomposition for moment-angle complexes, arrangements and related spaces, Advances in Mathematics, 225:1634–1668, 2010.
[3] Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. I, Transactions of
the American Mathematical Society, 348(4):1299–1327, 1996.
[4] Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Transactions of
the American Mathematical Society, 349(10):3945–3975, 1997.
[5] Takayuki Hibi, Akihiro Higashitani, Kyouko Kimura, and Augustine B. O’Keefe, Algebraic study on
Cameron-Walker graphs, Journal of Algebra, 422:257–269, 2015.
[6] Dmitry N. Kozlov, Complexes of directed trees, Journal of Combinatorial theory, Series A, 88:112–122, 1999.
[7] Somayeh Moradi and Fahimeh Khosh-Ahang, Expansion of a simplicial complex, Journal of Algebraand Its Applications, 15(1):1650004, 2016.
[8] Kevin N. Vander Meulen and Adam Van Tuyl, Shellability, vertex decomposability, and lexicographical products of graphs, Contributions to Discrete Mathematics, 12(2):63–68, 2017.
[9] Russ Woodroofe, Vertex decomposable graphs and obstructions to shellability, Proceedings of theAmerican Mathematical Society, 137(10):3235–3246, 2009.

5学位論文審査結果の要旨
学位論文題目

Polyhedral Join of Simplicial Complexes and its Application to Graph Theory（単体的複体のポリヘドラルジョイン、およびそのグラフ理論への応用）
提出者氏名

大倉 健吾

本学大学院理学系研究科数理科学専攻博士後期課程 3 年に在籍の大倉健吾氏はグラフの独立複体の幾何学的実現のホモトピー型についての研究を行っている．グラフ G とは頂点の集合 V (G) とそれらを結ぶ辺の集合 E(G) から構成される 1 次元の図形である．連続的な図形の変形を許すホモトピー論の立場から見れば，グラフは 8 の字型のようにいくつかの円周を 1 点で束ねた図形の交わらない合併と「同じ形」と見なされ，幾何学的に単純な形をしているため，図形としてのグラフは位相幾何学の研究対象になるものではないが，どの 2 点も結ぶ辺が存在しない頂点のなす集合から「独立複体」と呼ばれる単体的複体 I(G) が定義される．ここで，単体的複体とは集合を用いて記述される「図形のデータ」であり，その「幾何学的実現」と呼ばれる高次元の位相空間が得られる．従って，グラフの独立複体の幾何学的実現は元のグラフの頂点の繋がり方という組み合わせ論的な情報を反映するため，グラフの研究のためには単体的複体についてのより深い知見が必要である．
大倉氏はまず論文 [2] において，2 つのグラフ G, H の「辞書式積」と呼ばれる一種の積 G[H] の独立複体について考察し，G が 1 列に並んだ n + 1 個の点を順に n 本の辺で結んで得られるグラフで H の独立複体の幾何学的実現が球面のウェッジ和とホモトピー同値になる場合に G[H] の幾何学的実現が球面のウェッジ和とホモトピー同値になることを示し，その際に現れる球面の次元と個数を決定した．また論文 [1] では
単体的複体 M と単体的複体の対の族 (K, L) = {(Ki , Li )}i=1,2,...,m から構成されるポリヘドラルジョインと呼ばれる単体的複体 ZM (K, L) とその幾何学的実現がもつ性質について種々の基礎的な結果を証明した．
その中で特にポリヘドラルジョインが “shellability”という良い性質を持つための条件について詳細な考察を行い，ポリヘドラルジョインが shellable であるための必要条件と十分条件について種々の結果を示すことにより，ポリヘドラルジョインの shellability に関して一つの理論を構築した点で，大倉氏の独創性が高く評価される．さらに大倉氏は論文 [1] において，グラフ G と H の辞書式積 G[H] の独立複体 I(G[H]) がG の独立複体 I(G) と H の独立複体 I(H) から構成されるポリヘドラルジョイン ZI(G) (I(H), ∅) が一致することを示した．この結果とすでに示したポリヘドラルジョインに関する結果をグラフ理論に応用して，
グラフ H に対して任意のグラフ G との辞書式積 G[H; {v0 }] の独立複体が shellable かつ “well-covered”であるための必要十分条件を記述したことが論文 [1] の主定理である.
さらに学位論文において，位相空間のポリヘドラルジョインについても考察を行い，K が大倉氏によって定義された “s-vertex-decomposable”と呼ばれる性質を持つ連結な単体的複体の場合に，K と有限 CW複体の族 X = {(Xi , ∅)}i=1,2,...,m から構成されるポリヘドラルジョインが，X1 , X2 , . . . , Xm のジョインを用いて構成される CW 複体にホモトピー同値であることを示した．この結果と論文 [1] で示した，グラ
フ G と H の辞書式積の独立複体が G と H の独立複体から構成されるポリヘドラルジョインとして表されるという結果を用いることで，より見通しが良い方法で論文 [2] の主定理を一般化した定理を証明した．
以上のことを踏まえて，当学位論文審査委員会は本論文を学位論文として十分な内容を持つものと判断した．
主査

山口睦

壁谷喜継

丸田辰哉

蓮井翔

源泰幸

論文[1] Kengo Okura, Shellability of Polyhedral Join of Simplicial Complexes and its Application to GraphTheory, The Electronic Journal of Combinatorics, 29(3) (♯P3.53) (2022).
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i3p53[2] Kengo Okura, Independence Complex of the Lexicographic Product of a Forest, Discrete Mathematics に 2021 年 9 月投稿（査読中）. https://arxiv.org/abs/2109.04181

発表リスト
1.

大倉健吾, Polyhedral Join of Simplicial Complexes and Its Application to Graph Theory, 2022 年

11 月, ホモトピー論シンポジウム, オンライン開催