Kronecker 二重被覆はグラフに対して標準的に定まる二重被覆である。 Kronecker 二重被覆は常に二部グラフになり、一方で二部グラフでない連結グラフの場合、その Kronecker 二重被覆はそのグラフの二重被覆のうち唯一の連結な二部グラフになる。 Kronecker 二重被覆が共通のグラフは次数列などの比較的精密なグラフの不変量や、グラフから定まる近傍幾何構造が一致し、非常に似た性質を持つことがわかるが、一般には Kronecker 二重被覆が一致していても同型であるとは限らない。与えられたグラフ X に対し、 Kronecker 二重被覆が X になるようなグラフを分類するという問題は Imrich と Pisanski によって考えられており、超立方体や一般 Petersen グラフなどの場合において、それらの分類がなされている。

本講演では Kneser グラフと共通の Kronecker 二重被覆を持つグラフを完全に分類したことについて述べる。ここで Kneser グラフ K(n,k) とは、頂点集合を n-元集合 {1, …, n} の k-元部分集合全体とし、二つの頂点は交わりがないときに辺で結ばれるものとして定義されるグラフである。本研究では Kneser グラフ K(n,k) と共通の Kronecker 二重被覆を持つグラフは、同型を除いてちょうど k 個存在することを示し、さらにそれらの彩色数と自己同型群を決定した。これらのグラフの彩色数を決定する際に、グラフから定まる近傍複体という単体複体の位相的性質と、 Kronecker 二重被覆との間にある密接な関係を用いる。

このセミナーはzoomによりオンラインで行われます。下記のリンクからご登録ください。

https://docs.google.com/forms/d/e/1FAIpQLSd_7IP7AotScrfK7g1YwqDDrOR3_ii…