組合せ数学セミナー
発表内容の概要
単体的複体の面ポセットがファセット（極大面）を上端とする区間で分割で
きることを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）。本研究では、これらの均衡概念を
整理し、それぞれに対応する自然な学習ダイナミクスや、社会厚生の保証につい
て議論します。
トップに戻る