組合せ数学セミナー
発表内容の概要
n頂点のラベル付き根つき木の個数はCayleyの公式を用いてn^{n-1}で与え
られることが知られている。
その他にも様々な条件を持つ木グラフの数え上げ公式が知られている。
しかし、ラベルのない根付き木の個数を与える明示公式は未だ得られてい
ない。
従来は、根から葉に向かって頂点を隣接させて木を構築し、その方法に基
づいて数え上げを行っていた。
今回は逆に、葉から根に向かって頂点を隣接させて数え上げを行う。
その方法により、根付き木をYoung tableauxの列に対応させることができる。
本講演では、その組合せを考えることにより得られた、"ある条件"を満た
す根つき木の個数を与える明示公式を紹介する。
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.
前回の講演 (6/29) では、
組合せ論的ゼータ函数が示す「三種の表示」の鼎立、
すなわち、指数表示・オイラー表示・橋本表示を
同時に兼ね備えることの理由を探るため、
より広いクラスである「有限集合族のゼータ」を
指数表示で定義し、それがオイラー表示をもつための
条件「仮説 E」、および橋本表示をもつための条件
「仮説 D」を紹介した。
本講演では、伊原ゼータに始まる組み合わせ路的ゼータ
とよぶべき既存の例が、「擬有限力学系のゼータ」として
統一的に記述されることを紹介する。かつその定礎の上に
「荷重の循環性」のもと、仮説 E および仮説 D が自然に
みたされることを論じ、もって既存の組合せ論的ゼータに
対して、三種の表示が自然に成立することをみる。
無向グラフGが平面的グラフであるための必要十分条件は、GがK_5とG_{3,3}
のどちらのマイナーも含まないことであるということが知られている。近年
では、Archdeaconたちによって、“平面的な有向グラフ”についての研究が
盛んに行われている。
平面有向グラフDとは、平面に対して辺が交差なく描かれ、かつDの各頂点
について、その点を始点とする辺と終点とする辺が交互に描かれた有向グラ
フのことである。また、そのような描き方が存在する有向グラフのことを平
面的な有向グラフという。
本発表では、平面的な有向グラフについてグラフの変形操作を用いたアプ
ローチと、それに付随する問題について紹介する。
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 が決定されている．
本講演では，この不変量に関する先行研究と未解決問題を中心に紹介する予定である．
閉多様体の三角形分割を与える単体的複体を考える事, 特に,
組合せ多様体と呼ばれる組合せ論的に扱いやすい三角形分割を調べる事は単体的複体
の組合せ論の研究における興味深い研究課題の一つである.
この分野における基本的な結果の一つに, PL同相な任意の二つの組合せ多様体は
Pachner move (bistellar flip) と呼ばれる簡単な操作で移り合う, という Pachner
による結果がある.
一方で, 近年 balanced と呼ばれる性質を満たす単体的複体に興味が持たれている.
d-次元単体的複体がbalanced であるとはその一次元部分のグラフが (d+1)彩色可能で
あるときにいう. 特に,2次元の balanced な組合せ多様体とは閉曲面の3彩色可能な
三角形分割に他ならない.
2017年に Izmestiev, Klee, Novik は cross flip と呼ばれる Pachner move の類似
を定義し,PL同相な任意の二つの balanced な組合せ多様体が cross flip で移り合う,
というPachner の定理の類似を与える結果を証明した. 本発表ではこの cross flip
に関する研究について紹介したい.
最初に Pachner move や Izmestiev, Klee, Novik らの結果を簡単に紹介した後,
2次元の場合,即ち, 閉曲面の三角形分割の場合に cross flip に関するいくつかの性
質を紹介する予定である.
尚, 本発表は鈴木有祐(新潟大学)及び Steven Klee (Seattle Univ.)との共同研究に
よる結果を含む.
トップに戻る