組合せ数学セミナー
発表内容の概要
単純グラフGの，自己同型群をAとする．Aが部分群として，軌道の個数が有限であるような，Gに
自由に作用するランクnの自由アーベル群を持つとき，Gをn次元周期グラフという．定義より，G
は無限グラフである．Betweenness
centralityは，有限グラフH上の頂点について定義される値で，直感的には，その頂点が"どの程
度最短路に使われているか"を表す指標である．有限グラフH上の頂点vのbetweenness
centralityは，Hの各頂点対s, tについて，s, t間の最短路のうちvを通るものの個数を，s,
t間のすべての最短路の個数で割った値を足し上げたものとして定義される．
周期グラフは結晶など，様々なもののモデルとして用いられる．特に，1次元周期グラフは，電
車のダイヤといった，周期的な時系列をモデルするのにも用いられる[1]．
Betweenness
centralityは複雑ネットワークの研究で，頂点の重要性の指標としてよく用いられるものである．
例えば，国際空港のネットワークでは，betweenness
centralityの大きい頂点の除去が，連結性に大きく影響することが知られている[2, 3]．
本研究では，結晶構造の解析，及び時系列を考慮したネットワークの解析などを動機として，be
tweenness
centralityの定義を，無限グラフである1次元周期グラフ上のものへ拡張し，これを計算する(正
確には，真の値に十分に近い近似値を出力する)アルゴリズムを提案する．更に，このアルゴリ
ズムの時間計算量が，集積点を持たないような描画をもつ平面的周期グラフでは，多項式時間で
あることを示す．
(本講演は，V. Suppakitpaisarn氏との共同研究に基づく)
[1] L. Anderegg, S. Eidenbenz, M. Gantenbein, C. Stamm, D. S. Taylor, B.
Weber, P. Widmayer: Train Routing Algorithms: Concepts, Design Choises, and
Practical Considerations. Proceedings. of 5th Workshop on Algorithm
Engineering and Experiments (ALENEX), pp. 106-118 (2003)
[2] R. Guimerà and L. A. N. Amaral. Modeling the world-wide airport
network. The European Physical Journal B - Condensed Matter and Complex
Systems, Volume 38, Issue 2, pp 381-385 (2004)
[3] R. Guimerà, S. Mossa, A. Turtschi, L. A. N. Amaral and Kenneth W.
Wachter. The Worldwide Air Transportation Network: Anomalous Centrality,
Community Structure, and Cities' Global Roles. Proceedings of the National
Academy of Sciences of the United States of America
Vol. 102, No. 22, pp. 7794-7799 (2005)
A block graph is a graph in which every block is a clique. Let G be a block
graph and let A be the adjacency matrix of G. We obtain a formula for the
determinant of A. It is shown that A is nonsingular over GF(2), the Galois
field of {0,1}, if and only if the removal of any vertex from G produces
a graph with exactly one odd component. A formula for the inverse of A over
GF(2) is obtained, whenever it exists. It is well-known that the nullity of
the line graph of a tree is at most one. We point out the connection of this
result with the present work. Finally, a combinatorial formula for the inverse
of a triangular matrix is described.
「結婚問題（1対1マッチング問題）」とは、それぞれ男性と女性と呼ばれる
2 つの有限集合と、各プレイヤー（男性と女性の総称）の持つ選好関係の組
として与えられる。各プレイヤーの選好関係とは、異性のプレイヤーおよび「結
婚しない」というオプションを好ましい順に並べた順序関係として定義される。
ここでは、プレイヤーの集合を固定して考える。「マッチング」とは、各問題
において、どの男女が結婚するのか（あるいは結婚しないのか）を指定する写
像のことである。「マッチング・メカニズム」とは、考察対象とする問題の全
体（これをメカニズムの「ドメイン」と呼ぶ）からマッチングの集合への写像
であり、すなわち各問題に対して１つのマッチングを指定する。「メカニズム
設計問題」とは、制度設計者が何らかの意味で望ましいと考える諸性質を満た
すメカニズムが存在するのか否か、存在するのであれば、その具体的な形（関
数型やアルゴリズム）はどのようなものであるのかを考察する研究課題である。
マッチング・メカニズム設計問題において中心的な役割を果たしてきたのは、
「安定性」と「耐戦略性」と呼ばれる２つの性質であるが、あらゆる問題を含
むドメインを考えた場合に、上記の２つの性質を同時に満たすメカニズムは存
在しないことが知られている（Roth, 1982, Math of OR）。
本講演では、安定性および耐戦略性の２つを満たすようなメカニズムが存在
するようなドメインの性質について考え、所望の性質を満たすメカニズムが存
在するための必要十分条件を提示する。
d頂点の任意の有限単純グラフと，グラフに付随する辺凸多面体を考える．
辺凸多面体とは，有限グラフの各辺に対して多面体の頂点を対応させる
ことで得られる0/1-多面体の特別なクラスのことを言う．一般の凸多面
体においては，面の個数の上限は巡回凸多面体が与えることが知られてい
るが，辺凸多面体の範疇で面の個数の最大値を与えるもの（また，その
ような辺凸多面体を生起するグラフ）は知られていない．すなわち，各d
に対する辺凸多面体の面の個数の最大値と，最大値を与えるようなグラ
フの構造を求めることが目標である．
特に，辺（1次元面）の個数に関して議論する．
3次元空間の多面体を想定する限り，任意のdに対して常に完全グラフが
最大値を与えると思われるが，13次元以上の辺凸多面体においては，必
ずしもこの限りではないことが判明した．また，完全グラフが最大値を
与えるときと，そうでないときを分類することに成功した．これらの結果
を紹介し，辺の個数の最大値を与えるグラフの構造に関する予想を述べる．
整凸多面体のEhrhart多項式とは、整凸多面体をn倍に膨らませたものに含まれ
る整数点の個数を表した数え上げ関数である。
一般に、Ehrhart多項式の母関数は有理式になり、分子は必ず非負整数係数の
多項式になることが知られている。
その非負整数係数の多項式の係数の列を整凸多面体のδ列と呼ぶ。
また、一方で、ある（整）数列が unimodal であるとは、その数列に“山”が
高々１つしかないときに言う。
つまり、数列のある箇所までは広義単調増加、そこから先は広義単調減少であ
るときに言う。
内部に少なくとも１つ整数点を含む整凸多面体が integer decomposition
property と呼ばれる性質を満たすとき、
整凸多面体のδ列が unimodal になる、という予想が知られている。
本講演では、この予想の解決に向けて、“膨らませた”整凸多面体のδ列の
unimodal性、および、
unimodal性に関連する２つの性質 log-concave と alternatingly increasing
について議論する。
さらに、δ列がunimodalにならない整凸多面体の例についても合わせて紹介す
る。
トップに戻る