受験生向け188bet体育_188bet备用网址紹介
松下 尚弘
数学科 幾何学分野
現在の188bet体育_188bet备用网址テーマ：代数的トポロジー、組合せ論
私は位相的組合せ論という数学の分野で188bet体育_188bet备用网址をしています。位相的組合せ論という分野は、グラフ理論へのトポロジーの応用を目的の一つとしています。主にグラフから形成される幾何学的対象を、トポロジーの観点から分析しています。まずグラフやトポロジーという言葉について説明します。
純粋数学全体は代数学や解析学など、いくつか大きな分野に分けることができますが、その中で組合せ論という分野があります。グラフ理論というのは、組合せ論において最大の分野です。ここでいうグラフとは、関数のグラフのことではありません。グラフ理論におけるグラフとは、「点（頂点）」と、それらを結ぶ「線（辺）」で構成されるようなものです。グラフのことをネットワークと呼ぶこともあります。
例えば、友達の関係をグラフで表すことができます。それぞれの人間を一つの点（頂点）とみなし、友達同士の関係であるときに線（辺）でつなげば、友達関係のネットワークのグラフができます。他にも、地図上の市区町村の領域を点とみなし、隣接する市区町村の間に辺を結ぶことで、グラフができます。このように、グラフという概念は様々なところに現れ、現実的な問題への応用範囲も広い数学的な対象です。
グラフ理論には、グラフの彩色問題という古典的な問題があります。この問題は次のような問題です。まず何かグラフが与えられたとします。続いて、そのグラフの各頂点に次のようなルールで色を与えることを考えます。そのルールとは、辺で結ばれている二つの頂点の色は、常に異なるようにすることです。グラフの彩色問題とは、このようなルールの下に、全ての頂点に色を与えることができる必要最小限の色の個数を求めてください、という問題です。この必要最小限の色の個数のことを、元々のグラフの彩色数と言われます。
例えば、３つの点がそれぞれ他の２つの点と辺でつながっている三角形のグラフを考えてみましょう。この場合、すべての頂点が隣り合っているので、３つの異なる色を使う必要があります。したがって、この三角形のグラフの彩色数は３ということになります。このような小さなグラフの場合、彩色数を求めることは簡単ですが、一般には彩色数を決定することは非常に難しい問題です。
グラフの彩色問題において有名な定理として、四色定理という問題があります。四色定理とは、どのような平面上の地図でもは隣接する領域が異なる色になるように最大４色で塗ることができるという定理です。ただし、それぞれの領域は飛び地のようなものがなく、つながっているとします。地図上の各領域を点とみなして、領域が隣接しているときに対応する点が辺で結ばれていると考えることで、グラフの彩色問題とみなすことができます。四色定理は、四色問題として十九世紀の頃に定式化された問題ですが、解決には百年以上の月日を要したとても難しい問題です。
この文章の最初で、私の188bet体育_188bet备用网址分野である位相的組合せ論とは、グラフ理論へのトポロジーの応用を目的の一つとしている、ということを述べました。続いてトポロジーという数学の分野について、説明したいと思います。
トポロジーとは、数学の大きな枠組みでいうと、幾何学に分類される分野です。トポロジーは位相幾何学ともいわれます。幾何学とは物体（図形）の形状などを188bet体育_188bet备用网址する数学の分野ですが、トポロジーは物体の「連続的な変形」を施しても不変な性質に着目する幾何学の分野です。ここでいう「物体」とか「連続的な変形」という言葉を厳密に取り扱うには、「位相空間」という抽象的な概念を理解する必要がありますが、大雑把に言うと、連続的変形とは、物体を切り分けたり、異なる部分をくっつけたりせずに、物体の形状を変えることを意味します。例えば、ドーナツとコーヒーカップは、切り分けたり異なる部分をくっつけたりすることなく、連続的な変形で移り変えることができるため、トポロジーの観点では同じ物体（図形）である、とみなすことができます。一方で、ドーナツと、ボールは、このような連続的な変形で移り変えることができない（この事実を証明するのは大変ですが）ので、トポロジーの観点では異なる図形である、とみなします。
私の188bet体育_188bet备用网址分野である、位相的組合せ論の大きな目的の一つに、グラフ理論における彩色問題などの問題を、トポロジーの手法を用いて188bet体育_188bet备用网址するというものがあります。それではトポロジーをグラフの彩色問題に応用する、ということは、具体的にどういうことでしょうか？ その典型的な例として、ここでは1979年 Lovász における Kneser 予想の解決を紹介したいと思います。
Lovász はグラフ理論を専門とする数学者ですが、彼は次のようなことを考えました。まずグラフが与えられたとします。このとき、そのグラフから、近傍複体という幾何学的対象（図形）を構成します。Lovász が示したことは、与えられたグラフの近傍複体に対し、その近傍複体の連結度という位相的不変量（連続的な変形によって変化しない幾何学的な量）と、元々のグラフの彩色数の間には、ある不等式が成立する、ということです。彼の証明には、 Borsuk-Ulam の定理というトポロジーの有名な定理が使われています。
実際に、 Lovász はこのような手法を通じて、次のようなグラフに対する彩色問題を解決しました。nとkを正の整数で、n ≥ 2kとします。このときグラフKG(n,k)を次のように定義します。まずKG(n,k)の頂点は、n-点集合{1, ? ? ? , n} のk個の元からなる部分集合全体です。KG(n,k)の二つの頂点vとwは、vとwが今日つする元を持たないとき、辺で結ばれているとします。このように定式化されるグラフKG(n,k)を Kneser グラフと言います。
Kneser という数学者は1955年にKG(n,k)の彩色数はn-2k+2である、ということを予想しました。これを Kneser 予想と言います。ここで、予想とは、「おそらく成り立つと思うけれども証明ができていない主張」のことです。実際に、KG(n,k)がn-2k+2個の色を用いれば隣接する頂点の色が異なるように塗分けることができる、ということはそれほど難しくなく示すことができます。一方で、n-2k+2個よりも少ない色で塗分けることができない、ということを示すのは簡単ではありません。 Lovász は上に述べた近傍複体と彩色数との関係を発見し、さらにKG(n,k)の近傍複体の位相的性質を調べることで、 Kneser グラフKG(n,k)の彩色数が実際にn-2k+2であることを証明しました。したがって現在では「KG(n,k)の彩色数はn-2k+2である」という主張は、予想ではなく定理となっていますが、 Lovász と Kneser の活躍にちなんで、現在では Lovász-Kneser の定理という、組合せ論における基本的な定理の一つとなっています。
以上のような Lovász による Kneser 予想の解決に用いられた手法は、その後も大きく発展しており、位相的組合せ論という数学の分野を形成しています。私はこの分野において、近傍複体の一般化である箱複体および Hom 複体や、188bet体育_188bet备用网址のグラフから構成される図形として、独立複体という幾何学的対象に興味を持って188bet体育_188bet备用网址をしています。近年では、与えられた単体複体（性質の良い図形）がどの次元の空間に埋め込むことができるか、という性質と、彩色数との関連性についても188bet体育_188bet备用网址しています。
純粋数学全体は代数学や解析学など、いくつか大きな分野に分けることができますが、その中で組合せ論という分野があります。グラフ理論というのは、組合せ論において最大の分野です。ここでいうグラフとは、関数のグラフのことではありません。グラフ理論におけるグラフとは、「点（頂点）」と、それらを結ぶ「線（辺）」で構成されるようなものです。グラフのことをネットワークと呼ぶこともあります。
例えば、友達の関係をグラフで表すことができます。それぞれの人間を一つの点（頂点）とみなし、友達同士の関係であるときに線（辺）でつなげば、友達関係のネットワークのグラフができます。他にも、地図上の市区町村の領域を点とみなし、隣接する市区町村の間に辺を結ぶことで、グラフができます。このように、グラフという概念は様々なところに現れ、現実的な問題への応用範囲も広い数学的な対象です。
グラフ理論には、グラフの彩色問題という古典的な問題があります。この問題は次のような問題です。まず何かグラフが与えられたとします。続いて、そのグラフの各頂点に次のようなルールで色を与えることを考えます。そのルールとは、辺で結ばれている二つの頂点の色は、常に異なるようにすることです。グラフの彩色問題とは、このようなルールの下に、全ての頂点に色を与えることができる必要最小限の色の個数を求めてください、という問題です。この必要最小限の色の個数のことを、元々のグラフの彩色数と言われます。
例えば、３つの点がそれぞれ他の２つの点と辺でつながっている三角形のグラフを考えてみましょう。この場合、すべての頂点が隣り合っているので、３つの異なる色を使う必要があります。したがって、この三角形のグラフの彩色数は３ということになります。このような小さなグラフの場合、彩色数を求めることは簡単ですが、一般には彩色数を決定することは非常に難しい問題です。
グラフの彩色問題において有名な定理として、四色定理という問題があります。四色定理とは、どのような平面上の地図でもは隣接する領域が異なる色になるように最大４色で塗ることができるという定理です。ただし、それぞれの領域は飛び地のようなものがなく、つながっているとします。地図上の各領域を点とみなして、領域が隣接しているときに対応する点が辺で結ばれていると考えることで、グラフの彩色問題とみなすことができます。四色定理は、四色問題として十九世紀の頃に定式化された問題ですが、解決には百年以上の月日を要したとても難しい問題です。
この文章の最初で、私の188bet体育_188bet备用网址分野である位相的組合せ論とは、グラフ理論へのトポロジーの応用を目的の一つとしている、ということを述べました。続いてトポロジーという数学の分野について、説明したいと思います。
トポロジーとは、数学の大きな枠組みでいうと、幾何学に分類される分野です。トポロジーは位相幾何学ともいわれます。幾何学とは物体（図形）の形状などを188bet体育_188bet备用网址する数学の分野ですが、トポロジーは物体の「連続的な変形」を施しても不変な性質に着目する幾何学の分野です。ここでいう「物体」とか「連続的な変形」という言葉を厳密に取り扱うには、「位相空間」という抽象的な概念を理解する必要がありますが、大雑把に言うと、連続的変形とは、物体を切り分けたり、異なる部分をくっつけたりせずに、物体の形状を変えることを意味します。例えば、ドーナツとコーヒーカップは、切り分けたり異なる部分をくっつけたりすることなく、連続的な変形で移り変えることができるため、トポロジーの観点では同じ物体（図形）である、とみなすことができます。一方で、ドーナツと、ボールは、このような連続的な変形で移り変えることができない（この事実を証明するのは大変ですが）ので、トポロジーの観点では異なる図形である、とみなします。
私の188bet体育_188bet备用网址分野である、位相的組合せ論の大きな目的の一つに、グラフ理論における彩色問題などの問題を、トポロジーの手法を用いて188bet体育_188bet备用网址するというものがあります。それではトポロジーをグラフの彩色問題に応用する、ということは、具体的にどういうことでしょうか？ その典型的な例として、ここでは1979年 Lovász における Kneser 予想の解決を紹介したいと思います。
Lovász はグラフ理論を専門とする数学者ですが、彼は次のようなことを考えました。まずグラフが与えられたとします。このとき、そのグラフから、近傍複体という幾何学的対象（図形）を構成します。Lovász が示したことは、与えられたグラフの近傍複体に対し、その近傍複体の連結度という位相的不変量（連続的な変形によって変化しない幾何学的な量）と、元々のグラフの彩色数の間には、ある不等式が成立する、ということです。彼の証明には、 Borsuk-Ulam の定理というトポロジーの有名な定理が使われています。
実際に、 Lovász はこのような手法を通じて、次のようなグラフに対する彩色問題を解決しました。nとkを正の整数で、n ≥ 2kとします。このときグラフKG(n,k)を次のように定義します。まずKG(n,k)の頂点は、n-点集合{1, ? ? ? , n} のk個の元からなる部分集合全体です。KG(n,k)の二つの頂点vとwは、vとwが今日つする元を持たないとき、辺で結ばれているとします。このように定式化されるグラフKG(n,k)を Kneser グラフと言います。
Kneser という数学者は1955年にKG(n,k)の彩色数はn-2k+2である、ということを予想しました。これを Kneser 予想と言います。ここで、予想とは、「おそらく成り立つと思うけれども証明ができていない主張」のことです。実際に、KG(n,k)がn-2k+2個の色を用いれば隣接する頂点の色が異なるように塗分けることができる、ということはそれほど難しくなく示すことができます。一方で、n-2k+2個よりも少ない色で塗分けることができない、ということを示すのは簡単ではありません。 Lovász は上に述べた近傍複体と彩色数との関係を発見し、さらにKG(n,k)の近傍複体の位相的性質を調べることで、 Kneser グラフKG(n,k)の彩色数が実際にn-2k+2であることを証明しました。したがって現在では「KG(n,k)の彩色数はn-2k+2である」という主張は、予想ではなく定理となっていますが、 Lovász と Kneser の活躍にちなんで、現在では Lovász-Kneser の定理という、組合せ論における基本的な定理の一つとなっています。
以上のような Lovász による Kneser 予想の解決に用いられた手法は、その後も大きく発展しており、位相的組合せ論という数学の分野を形成しています。私はこの分野において、近傍複体の一般化である箱複体および Hom 複体や、188bet体育_188bet备用网址のグラフから構成される図形として、独立複体という幾何学的対象に興味を持って188bet体育_188bet备用网址をしています。近年では、与えられた単体複体（性質の良い図形）がどの次元の空間に埋め込むことができるか、という性質と、彩色数との関連性についても188bet体育_188bet备用网址しています。