組合せ数学セミナー
発表内容の概要
有限単純グラフからstable set polytopeと呼ばれる(0,1)凸多面体、
つまり全ての頂点の成分が0または1である凸多面体が構成できる。
この多面体の性質を使い、付随するグラフがperfectとなる特徴づけが与えられ
ている。
本講演では、この特徴付けに加え、新しいperfectグラフの凸多面体による特徴
付けを複数紹介する。
この研究は大阪大学の日比孝之教授との共同研究に基づく。
任意の2点を結ぶ測地線が存在する距離空間を測地距離空間という. 測地距離
空間には自然な形で凸構造が定義されるが, その幾何学的な性質を曲率κをパ
ラメタとした不等式によって仮定することで, CAT(κ)空間と呼ばれる空間を定
義できる.
本講演では, 完備CAT(κ)空間上の下半連続凸関数に対する凸最小化問題を考え
る. この問題ではリゾルベントと呼ばれる作用素が重要な役割を果たすが, と
くにκが正の場合において, リゾルベント作用素がどのように定義されるかを
説明し, 関連する結果を解説する.
In order to protect copyrighted digital information, digital fingerprinting was
introduced to trace the sources of pirate copies, thereby discouraging attempts
at collusion attacks for unauthorized redistribution of the information. Various
fingerprinting schemes have been proposed since the late 1990s. In this talk, we
focus on two combinatorial structures used in broadcast encryption, namely,
t-traceability schemes (t-TS) and t-parentidentifying schemes (t-IPPS). First,
from the viewpoint of extremal set theory, we derive new upper bounds for t-TS
and t-IPPS, respectively. Second, by virtue of combinatorial designs, we provide
several constructions for t-TS, which can produce several infinite families of
optimal t-TS. Third, by using the probabilistic expurgation method, we show a
lower bound for t-IPPS, which has the same order of magnitude as our new upper
bound for certain cases.
This talk is based on joint work with Ying Miao.
球面上の結び目射影図や図式が「可約」であるとは、
ちょうどひとつの交点を横断的に通過するような円周が球面上に存在することをいいます。
可約でないとき既約といいます。
結び目の射影図や図式に一方向の向きを入れると各交点の周りにも向きが入ります。
ある交点において、交点がなくなるように、そして向きが「保たれない」ように、
つなぎかえを行うことを「半ひねりスプライス」といいます。
結び目射影図の「既約度」とは、その結び目射影図を可約にするために必要な
半ひねりスプライスの最小回数のことであり、任意の結び目射影図に対して、
既約度が４以下であることがわかっています。
つまり、任意の結び目射影図は４回以下の半ひねりスプライスで可約にできるのです。
しかし、現在までに既約度がちょうど４である結び目射影図の例は見つかっていません。
この講演では、この「既約度問題」の、「不可避集合」を用いたアプローチ等について
お話いたします。
二分系統樹 (binary phylogenetic tree)は種の進化を記述するモデルとして古くから用いられ
てきたが，木構造では現実の複雑な進化を記述することができないため，今日では binary
phylogenetic network が使われることも多い．ところが，binary phylogenetic network
は非常に広いネットワークのクラスであるため進化のモデルとして色々な欠点があり，より適切
なサブクラスを探求することは生物学的に重要な課題となっている．とりわけFrancis と Steel
によって2015年に導入された tree-based networkは生物学的にも組合せ論的にも興味深いサブ
クラスで，2016年にHayamizu と Zhang が universal tree-based network をそれぞれ独立に
見出すなど，活発に研究が行われている．この講演では universal tree-based networkに関
する研究のごく最近の展開を紹介し，今後の広がりについて述べる．
トップに戻る