組合せ数学セミナー
発表内容の概要
単体的複体の面ポセットがファセット（極大面）を上端とする区間で分割で
きることをpartitionableといい、これはshellableより弱い性質にあたる。
単体的複体がpure（ファセットの次元がすべて同じ）であるときには
partitionabilityはh-vectorの非負性を導くが、nonpureな場合にはh-vector
やそのnonpure版にあたるh-triangleの非負性は保証できない。Nonpureな
場合には、partitionabilityを強めたlayer-compatibly partitionable
という性質を満たす場合にはh-triangleの非負性が導かれる。
このlayer-compatibly partitionableとpartitionableの間にはsequentially
partitionable, ps-partitionable, という中間的な強さの性質があり、
本講演ではlayer-compatibly partitionableからpartitionableまでの各性質
に対応するh-triangleの性質や、それらの間の関係について議論する。
disjunct行列は組合せ論的グループテストと呼ばれる分野において重要な役割を
担っている二値行列であり、その構成法や理論的な限界に関する理解を深めるこ
とは当該分野における主要な課題の一つとなっている。本講演では、まず組合せ
論的グループテスト理論を概観し、disjunct行列に関する既知の性質や構成法を
紹介する。その後、general inhibitor modelと呼ばれる特殊なグループテストの
モデルを導入し、このモデルに適した性質をもつdisjunct行列の効率的かつ決定
的な構成法を提案する。
精度保証付き数値計算は、数値計算における誤差を数学的に厳密に評価・制御
し、その正しさを保証するための数値的枠組みです。近年では、純粋数学の問
題に対する計算機援用証明にも活用されつつあります。本講演では、精度保証
付き数値計算の基本原理と理論的背景を紹介し、離散数学、特に組合せ論やグ
ラフ理論における応用の可能性について概観します。さらに、連続的な解析手
法と離散的構造との橋渡しを目指す今後の展望についても議論します。
PDF
Let G = (V,E) be a strongly connected and balanced digraph with vertex set
V = {1, . . . , n}. The Laplacian matrix of G is then the matrix (not
necessarily symmetric) L := D - A, where A is the adjacency matrix of G and D
is the diagonal matrix such that the row sums and the column sums of L are equal to zero.
Let L^\dagger= [l^\dagger_{ij} ] be the Moore-Penrose inverse of L.
We define the resistance between any two vertices i and j of G by
r_{ij} := l^\dagger_{ii} + l^\dagger_{jj} - 2l^\dagger_{ij}. Some interesting
properties of the resistance and the corresponding resistance matrix [r_{ij} ]
will be discussed in the talk.
The classical distance d_{ij} between any two vertices i and j in G is the minimum
length of all the directed paths joining i and j. Numerical examples show that
the resistance distance between i and j is always less than or equal to the
classical distance, i.e. r_{ij} \geq d_{ij} . However, no proof of this
inequality is known. In the talk, we will show that this inequality holds for
all directed cactus graphs. This is a joint work with Dr. R. Balaji and
Professor R. B. Bapat.
話者が社会的関係に注意を払う会話における言語的間接性を分析する．社会的
な関係をグラフでモデル化し，会議をメッセージを聞く人の集合として扱う．
会議の価値はグラフ上の距離多項式であり，それをマイヤーソン価値で各参加
者に配分する．これらで各参加者の会議での交渉力を定めて，均衡メッセージ
分割を割り出すバイアス効果を求める．結果：(i) 木構造の中で星構造が価値
を最大化し，均衡メッセージ分割が少ない；(ii) 星構造でバイアス効果を導出；
葉の追加による均衡メッセージ分割低下の限界効果はδ*=0.6で符号が反転する；
(iii) 1つのリンクでつながる2つの星構造と，それと同じノード数の一つの星
構造の均衡メッセージ精度は，8/15で逆転する；葉間で私的に行う会議でのメッ
セージが最も多くの情報量を持つ．
本発表では、プレイヤー間で情報が共有されていないゲーム（不完備情報ゲーム）
における相関均衡、学習ダイナミクス、社会厚生の保障について議論します。
完備情報ゲームでは、仲介者による推薦によってプレイヤーたちの行動を調整す
る「相関均衡」が、自然な学習ダイナミクスによって実現されるとともに、都市
交通やオークションなどの重要なモデルにおいて全体としての利得が近似的に最
大化されることが知られています。一方で、不完備情報ゲームでは相関均衡の自
然な拡張が複数存在します（Forges, 1993）。本研究では、これらの均衡概念を
整理し、それぞれに対応する自然な学習ダイナミクスや、社会厚生の保証につい
て議論します。
無向グラフの各辺に向きを与えるとき、任意の隣接する2頂点の入次数が異なる
向き付けを proper orientation という。Proper orientation は、各頂点の入
次数を色に対応させる点彩色を構成する面白さから、広く関心を持たれている。
実際、この proper orientation の概念にアレンジを加えたものを含め、多様な
問題が提起されている。そのような研究の一つの方向性として、proper
orientation を頂点に重みのついたグラフに拡張した問題を考えることができる。
本講演では、この重み付きグラフにおける proper orientation の拡張問題に
ついての基礎的な結果や未解決問題を紹介する。
系統ネットワークは，生物の網状進化を記述するグラフ構造である．複雑で解釈
困難な系統ネットワークに対処するために，全域系統樹などの妥当な部分構造を
抽出するアプローチが盛んに研究されてきた．特に早水(2022)は系統ネットワーク
の構造定理を与え，全域系統樹に関する計算論的性質を解明した(2019年12月20日
の本セミナー講演内容)．しかし一般の系統ネットワークが全域系統樹をもつとは
限らず，拡張版となる「全域系統ネットワーク」を考察することには意義がある．
本講演ではまず，与えられた系統ネットワークに含まれる全域系統ネットワーク
の集合とその2つの部分集合が，それぞれ直積の形で特徴づけられることを示す．
興味深いことに，3つの集合の数え上げ公式にはフィボナッチ数列・リュカ数列
など，古典的な整数列が自然な形で現れる．
さらに，全域系統ネットワークの「系統樹らしさ」を最適化する2つの問題の計算
複雑性について議論する．1つは線形時間求解可能であり，もう1つはNP困難である．
本講演ではこのNP困難性の証明における，3-SATからの帰着の構成方法について詳
しく述べる．
本講演内容は早水桃子氏との共同研究に基づく．
フランクルの予想（Union-Closed Sets Conjecture）は、50年近くにわたり未解
決の組合せ論の予想である。本研究では、その部分ケースを解決した。
本研究では、フランクルの予想を閉集合族を使った同値な予想に変形してして扱う。
空集合を要素として含む閉集合族に対して全体の半分以下の閉集合にしか含まれな
い点（rare 頂点）が存在する、という主張になる。ここで閉集合族とは、共通部分
に関して閉じており、全体集合を含む集合族である。閉集合族は Horn ルールで記
述できるクラスと同一視できる。Horn ルールとは、「ある前提集合 P を含む集合
は、必ず head h も含む」という形の規則である。
本研究ではさらに、集合族を表現するHornルールに「各頂点が head として現れる
回数が高々1回である」という追加制約を課す。この制約の下では、rare 頂点の存
在よりも強い結論が得られる。具体的には、主定理として「このクラスの集合族の
要素（集合）の大きさの平均が、台集合の大きさの半分以下である」ことを示す。
これは直ちに rare 頂点の存在を導く。
証明は台集合の大きさに関する帰納法による。ただしこのクラスの閉集合族のみを
対象にした単純な帰納法では閉じないため、帰納法で扱う対象を少し拡張する。具
体的には、禁止集合 A を導入し、この制約付きクラスの閉集合族から、A を部分
集合として含む要素（集合）を除いてできる集合族のクラスを併せて扱うことで、
帰納法が成立する形に整える。
また本研究では、反例探索など様々な局面で AI を活用して研究を進めており、そ
の経験についても紹介する。さらに、主定理の証明は Lean 4 により形式的に検証
済みであり、数学的正しさが機械的に厳密に保証されている。Lean 4 の実装には
Codex 等の支援も利用しており、その点についても触れる予定である。
本研究は、筑波大学の八森正泰氏との共同研究が元になっている。
トップに戻る