組合せ数学セミナー
発表内容の概要
単体的複体の面ポセットがファセット（極大面）を上端とする区間で分割で
きることを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.
トップに戻る