組合せ数学セミナー
発表内容の概要

6/13(金): 八森正泰（筑波大学）
Nonpureな単体的複体のpartitionabilityとh-triangle

単体的複体の面ポセットがファセット（極大面）を上端とする区間で分割で
きることを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の性質や、それらの間の関係について議論する。

7/11(金): 水沼柚人（千葉大学）
組合せ論的グループテストのための二値行列構成法

disjunct行列は組合せ論的グループテストと呼ばれる分野において重要な役割を
担っている二値行列であり、その構成法や理論的な限界に関する理解を深めるこ
とは当該分野における主要な課題の一つとなっている。本講演では、まず組合せ
論的グループテスト理論を概観し、disjunct行列に関する既知の性質や構成法を
紹介する。その後、general inhibitor modelと呼ばれる特殊なグループテストの
モデルを導入し、このモデルに適した性質をもつdisjunct行列の効率的かつ決定
的な構成法を提案する。

7/18(金): 浅井大晴（早稲田大学）
精度保証付き数値計算と離散数学：計算機援用証明の可能性

精度保証付き数値計算は、数値計算における誤差を数学的に厳密に評価・制御
し、その正しさを保証するための数値的枠組みです。近年では、純粋数学の問
題に対する計算機援用証明にも活用されつつあります。本講演では、精度保証
付き数値計算の基本原理と理論的背景を紹介し、離散数学、特に組合せ論やグ
ラフ理論における応用の可能性について概観します。さらに、連続的な解析手
法と離散的構造との橋渡しを目指す今後の展望についても議論します。

9/22(月): Shivani Goel (Indian Institute of Management Ahmedabad)
Resistance distance in directed graphs

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.

11/21(金): 大角道子（長崎大学）
距離分布で測る"遠回しさ" : グラフと会議から生まれるメッセージの精密さ

話者が社会的関係に注意を払う会話における言語的間接性を分析する．社会的
な関係をグラフでモデル化し，会議をメッセージを聞く人の集合として扱う．
会議の価値はグラフ上の距離多項式であり，それをマイヤーソン価値で各参加
者に配分する．これらで各参加者の会議での交渉力を定めて，均衡メッセージ
分割を割り出すバイアス効果を求める．結果：(i) 木構造の中で星構造が価値
を最大化し，均衡メッセージ分割が少ない；(ii) 星構造でバイアス効果を導出；
葉の追加による均衡メッセージ分割低下の限界効果はδ*=0.6で符号が反転する；
(iii) 1つのリンクでつながる2つの星構造と，それと同じノード数の一つの星
構造の均衡メッセージ精度は，8/15で逆転する；葉間で私的に行う会議でのメッ
セージが最も多くの情報量を持つ．

11/21(金): 藤井海斗（国立情報学研究所）
ベイズ相関均衡とリグレット最小化ダイナミクス

本発表では、プレイヤー間で情報が共有されていないゲーム（不完備情報ゲーム）
における相関均衡、学習ダイナミクス、社会厚生の保障について議論します。
完備情報ゲームでは、仲介者による推薦によってプレイヤーたちの行動を調整す
る「相関均衡」が、自然な学習ダイナミクスによって実現されるとともに、都市
交通やオークションなどの重要なモデルにおいて全体としての利得が近似的に最
大化されることが知られています。一方で、不完備情報ゲームでは相関均衡の自
然な拡張が複数存在します（Forges, 1993）。本研究では、これらの均衡概念を
整理し、それぞれに対応する自然な学習ダイナミクスや、社会厚生の保証につい
て議論します。    

12/12(金): 飯田礼美子（横浜市立大学）
グラフの proper orientation の拡張問題

無向グラフの各辺に向きを与えるとき、任意の隣接する2頂点の入次数が異なる
向き付けを proper orientation という。Proper orientation は、各頂点の入
次数を色に対応させる点彩色を構成する面白さから、広く関心を持たれている。
実際、この proper orientation の概念にアレンジを加えたものを含め、多様な
問題が提起されている。そのような研究の一つの方向性として、proper
orientation を頂点に重みのついたグラフに拡張した問題を考えることができる。
本講演では、この重み付きグラフにおける proper orientation の拡張問題に
ついての基礎的な結果や未解決問題を紹介する。