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


11/9: 石川彩香(横浜国立大学)
Young tableau を用いた根つき木の数え上げ

n頂点のラベル付き根つき木の個数はCayleyの公式を用いてn^{n-1}で与え
られることが知られている。
その他にも様々な条件を持つ木グラフの数え上げ公式が知られている。
しかし、ラベルのない根付き木の個数を与える明示公式は未だ得られてい
ない。
従来は、根から葉に向かって頂点を隣接させて木を構築し、その方法に基
づいて数え上げを行っていた。
今回は逆に、葉から根に向かって頂点を隣接させて数え上げを行う。
その方法により、根付き木をYoung tableauxの列に対応させることができる。
本講演では、その組合せを考えることにより得られた、"ある条件"を満た
す根つき木の個数を与える明示公式を紹介する。


12/7: Stephen Kobourov (University of Arizona)
Contact Representation of Planar Graphs in 2D and 3D

In a proportional contact representation of a planar graph,
each vertex is represented by a simple polygon with area proportional
to a given weight, and edges are represented by adjacencies between
the corresponding pairs of polygons. We show how to use Schnyder
realizers and canonical orders for planar graphs to obtain different
types of contact representations. Specifically, we describe an
algorithm that constructs proportional contact representation for
arbitrary planar graphs using 10-sided rectilinear polygons. We also
describe a construction with 8-sided polygons, which is optimal in
terms of polygonal complexity, as 8-sided polygons are sometimes
necessary. In 3D vertices are represented by polytopes and edges by
contacts between the corresponding polytopes contacts. We show that
planar 3-trees have contact representations with cubes and
proportional contact representations with boxes.


12/21: 森田英章(室蘭工業大学)
組合せ論的ゼータ函数について(その2)

前回の講演 (6/29) では、
組合せ論的ゼータ函数が示す「三種の表示」の鼎立、
すなわち、指数表示・オイラー表示・橋本表示を
同時に兼ね備えることの理由を探るため、
より広いクラスである「有限集合族のゼータ」を
指数表示で定義し、それがオイラー表示をもつための
条件「仮説 E」、および橋本表示をもつための条件
「仮説 D」を紹介した。

本講演では、伊原ゼータに始まる組み合わせ路的ゼータ
とよぶべき既存の例が、「擬有限力学系のゼータ」として
統一的に記述されることを紹介する。かつその定礎の上に
「荷重の循環性」のもと、仮説 E および仮説 D が自然に
みたされることを論じ、もって既存の組合せ論的ゼータに
対して、三種の表示が自然に成立することをみる。


1/11: 川谷元(東京理科大学)
有向グラフの埋め込みと、それに付随する問題について

無向グラフGが平面的グラフであるための必要十分条件は、GがK_5とG_{3,3} 
のどちらのマイナーも含まないことであるということが知られている。近年
では、Archdeaconたちによって、“平面的な有向グラフ”についての研究が
盛んに行われている。
 平面有向グラフDとは、平面に対して辺が交差なく描かれ、かつDの各頂点
について、その点を始点とする辺と終点とする辺が交互に描かれた有向グラ
フのことである。また、そのような描き方が存在する有向グラフのことを平
面的な有向グラフという。
 本発表では、平面的な有向グラフについてグラフの変形操作を用いたアプ
ローチと、それに付随する問題について紹介する。


2/1 14:00〜: 松本直己(成蹊大学)
Proper orientation number of graphs

Gを単純グラフとする.任意の辺uvに対し,uとvの入次数が異なるGの向き付けを 
proper orientation と呼ぶ.また,最大入次数がkの向き付けを k-orientation 
と呼び,Gが proper k-orientation を持つ最小のkをグラフGの proper orientation 
number という. Proper orientation number は Ahadi and Dehghan (2013)
によって定義された比較的新しいグラフの不変量である.一般に proper 
orientation number を決定する問題はNP-完全であることが知られているが,
これまでにいくつかのグラフクラスに対して,その クラスに属するグラフの proper
orientation number が決定されている.
本講演では,この不変量に関する先行研究と未解決問題を中心に紹介する予定である.


2/1 16:30〜: 村井聡(早稲田大学)
未定



トップに戻る