組合せ論セミナー

組合せ論セミナー

セミナー講演記録(2007年4月9日～2008年2月21日)

日時	2008年2月21日(木)15:00--（下記セミナーと連続して開催）
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	中本敦浩（横浜国立大学教育人間科学部）
講演題目	曲面の三角形分割の支配集合について
講演要旨	グラフ G の頂点の部分集合 S が支配集合であるとは、「G の任意の頂点が S に属しているか、 S のある頂点に隣接する」が成り立つことである。講演では、射影平面、トーラス、クラインの壷の n 頂点の三角形分割は大きさ n/3 以下の支配集合を持つことを証明する。また、任意の曲面上の representativity が十分に大きい三角形分割についても同様の結論が成り立つことを証明する。

日時	2008年2月21日(木)15:00--（上記セミナーと連続して開催）
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	山下登茂紀（朝日大学歯学部）
講演題目	triangle-free graphにおける閉路の研究
講演要旨	triangle-free graphにおける閉路の研究は盛んに行なわれている。しかし、それらの結果の関係についてはあまり研究されていない。本講演では、まず初めにそれらの関係について述べ、それを踏まえて、triangle-free graphにおける閉路の存在に関する問題や予想を紹介する。

日時	2008年1月28日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小関健太（慶應義塾大学大学院理工学研究科）
講演題目	k-tree の存在のための toughness 型条件
講演要旨	最大次数が k 以下の全域木を k-tree と呼ぶ。 k-treeの存在するための toughness 型条件に関しては Win による結果が有名であるが、その条件が最善であるかどうかについては不明である。従ってこの Win の結果の改良を試みるのは自然なことであるが、同時にこれは難しい問題と直結していることが知られている。本講演ではグラフの族を制限した上でこの結果の改善を試みる。

日時	2008年1月21日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小関健太（慶應義塾大学大学院理工学研究科）
講演題目	k 個の点素な chord 付き閉路、K₄, K₄^- の存在について
講演要旨	k 個の点素な cycle が存在するための十分条件については様々な研究がなされている。本講演では cycle だけに留まらず、 chorded cycle、4 頂点完全グラフや 4 頂点完全グラフから 1 辺を取り除いたグラフなどを点素に k 個取るための十分条件について議論する。

日時	2008年1月7日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	山下登茂紀（朝日大学歯学部）
講演題目	k-linked in chordal graphs
講演要旨	本講演では、chordal graphにおけるk-linkedに関する結果を紹介するとともに、 chordal graphとk-linkedそれぞれに関連するいくつかの結果について紹介し、それらについて議論する。

日時	2007年12月10日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	山下登茂紀（朝日大学歯学部）
講演題目	支配閉路に関する予想について
講演要旨	1984年、MatthewsとSumnerによって、「4連結クローフリーグラフはハミルトンである」という予想がなされた。 1986年、Thomassenによって、「4連結線グラフはハミルトンである」という予想がなされた。 1997年、Ryjacekによって、これらの予想が同値であることが示された。本講演では、これらの予想と同値な予想について議論する。

日時	2007年12月3日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	杉山武史（慶應義塾大学大学院理工学研究科）
講演題目	禁止部分グラフとハミルトンサイクルの存在について
講演要旨	特定の誘導部分グラフを含まない2-連結グラフがハミルトンサイクルを含むための十分条件は多く知られている。当講演ではその様な定理を紹介していき、またそれに関する予想も紹介する。

日時	2007年11月26日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	石井啓嗣（慶應義塾大学大学院理工学研究科）
講演題目	regular graph が hamilton cycle をもつための次数に関する十分条件
講演要旨	一般に n 頂点のグラフが hamilton cycle をもつための条件としては Dirac の定理が有名であり、これは最小次数が n/2 以上であればグラフが hamilton cycle をもつことを示している。今回はグラフを regular graph に限定することで、この条件が n/3 まで下げることができることを紹介し、 regular graph に近いグラフにおいても下げることができるかについて議論する。

日時	2007年11月19日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	津垣正男
講演題目	指定点を通る k-tree
講演要旨	11月12日に講演された、指定点を通るk-treeに関する定理から導かれる系をいくつか紹介する。なお本研究は、千葉周也（東京理科大学大学院）、小関健太(慶應義塾大学大学院)、松原良太（東京理科大学）との共同研究である。

日時	2007年11月12日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	千葉周也（東京理科大学大学院理学研究科）
講演題目	指定点を通る k-tree
講演要旨	全ての頂点の次数が k 以下であるような tree を k-tree と呼ぶ。本講演では、指定した頂点を全て通る k-tree と次数和条件との関係について議論する。

日時	2007年11月5日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	藤沢潤（日本大学文理学部）
講演題目	Cubic graph における Akiyama and Kano の予想について
講演要旨	「3-連結なcubic graphで頂点数が3で割り切れるものは、 P₃-factor を持つ」という Akiyama and Kano の予想について、本講演ではグラフが bipartite かつ planar であっても2-連結ではこの予想が成り立たないことを示す。

日時	2007年10月29日(月)17:00--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	山中雅則（日本大学理工学部物理学科）
講演題目	Topological classification of protein and related topics between graph embedding and statistical physics
講演要旨	蛋白質の分類を２次構造のトポロジー着目して提案し、蛋白質周期律表を作成した。具体的には蛋白質の３次元構造から骨格をグラフとして抽出し、それをトーラスへ埋め込み、トーラスの種数を原子番号に対応させた。蛋白質に含まれる水素結合数の関数として種数は線形に増加するなどの結論を得た。３次元構造からのグラフの抽出方法はいくつか考えられ、それぞれが異なる種数を与える。これ以外にも結晶格子の埋め込みによる分類や、四色問題に代表される地図の染色を基底状態にもつ電子模型など、グラフの埋め込みと統計物理学に関する話題も簡単に紹介を行う。

日時	2007年10月22日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小関健太（慶應義塾大学大学院理工学研究科）
講演題目	Branch の数が制限された全域木について
講演要旨	木において、次数が 3 以上の頂点をその木の branch vertex と呼ぶ。様々な性質を持つ全域木について、いままでに多くの研究がなされてきたが、本講演ではこの branch vertex の数が制限された全域木の存在に関して議論する。

日時	2007年10月15日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	Aung Kyaw (East Yangon University, Myanmar)
講演題目	Spanning trees with at most k leaves in a K_1,4-free graph
講演要旨	For a connected graph G and an integer k ≧ 2, we define σ_k(G) := \min {deg_G(U) : U is an independent set of G with \|U\| = k}. We prove that for a connected K_1,4-free graph G, (i) if σ₃(G) ≧ \|G\|, then G has a hamiltonian path (ii) if σ_k+1(G) ≧ \|G\| -(k/2) for an integer k ≧ 3, then G has a spanning tree with at most k leaves.

日時	2007年7月30日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小関健太（慶應義塾大学大学院理工学研究科）
講演題目	An extension of k-ordered
講演要旨	与えられた任意の k 頂点に対し、その順序通りに通る閉路が存在するときグラフは k-ordered であるという。 k-ordered に関しては、いろいろな研究がなされている。本講演では、この k-ordered の概念を拡張させた Set-ordered を定義し、グラフが Set-ordered であるための十分条件について議論する。なお本研究は、石井啓嗣氏(慶應義塾大学大学院)、善本潔氏(日本大学理工学部)との共同研究である。

日時	2007年7月23日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	藤沢潤（日本大学文理学部）
講演題目	ハミルトンパスに関するある種の性質を満たすグラフについて
講演要旨	あるグラフにおいて、「v以外の任意の頂点uに対してuとvを結ぶハミルトンパスが存在する」という頂点vが存在するとき、そのグラフは性質P_Aを満たすと呼ぶ。本講演では、十分大きいnに対して、性質P_Aを満たすn頂点グラフのうち辺の数が最小なものの辺数について議論する。

日時	2007年7月9日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	太田克弘（慶應義塾大学理工学部）
講演題目	閉曲面上の既約三角形分割の頂点数の上限
講演要旨	閉曲面上の既約三角形分割の頂点数の上限はその閉曲面のEuler genus を使って表せることが知られている。今回はこの上限に関する新しい結果を紹介する。

日時	2007年7月2日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	藤沢潤（日本大学文理学部）
講演題目	Cycles passing through k+1 vertices in k-connected graphs
講演要旨	本講演では、与えられたk-連結グラフGと、その中のあるサイクルに属するk+1点の頂点集合Xに対し、 Xの頂点を全て含む長いサイクルがGにおいて存在することを示す。この定理は、Lockeによる未解決問題 [Discrete Math. 257 (2002) 599-624]を肯定的に解決し、さらに連結度に対しての一般化に成功している結果となっている。また本研究は、朝日大学の山下登茂紀氏との共同研究である。

日時	2007年6月25日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	杉山武史（慶應義塾大学大学院理工学研究科）
講演題目	禁止部分グラフと指定点を通るサイクルの存在について
講演要旨	2連結グラフがCW-freeならばそのグラフはハミルトンサイクルを含むことが知られている。本講演では上記の事実をより一般的に拡張することを考えていく。

日時	2007年6月18日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	津垣正男
講演題目	relative lengthが小さいグラフの性質について
講演要旨	relative lengthが小さいグラフの性質はまだあまり知られていない。本講演では、relative lengthが小さいグラフが長いサイクルを持つことと、 relative lengthが2以下のグラフに対してThomassenによるある予想が成立することを紹介する。

日時	2007年6月4日(月)16:30--18:00
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	Cun-Quan Zhang (West Virginia University)
講演題目	Integer Flows
講演要旨	This is an introductory lecture for graduate students who have some basic knowledge in graph theory. Integer flow was introduced by Tutte as a dual version of the map-coloring problem. This lecture will introduce some basic concepts, fundamental theorems of the area (based on the textbook, "Integer flows and cycle covers of graphs" by the instructor), and, some recent progress in this area as well. (The abstract of his talk is available.)

日時	~~2007年5月28日(月)16:30--~~はしか流行のため中止になりました。(5/27)
場所	~~慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207~~
講演者	未定
講演題目	未定
講演要旨	未定

日時	2007年5月21日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小関健太（慶應義塾大学大学院理工学研究科）
講演題目	平面グラフのトータル彩色について
講演要旨	グラフの頂点と辺の彩色で、隣接及び接続する二つの要素が異なる色となるものをトータル彩色と呼ぶ。このトータル彩色に関していくつかの研究がなされているが、特に平面グラフについて研究が盛んである。本講演では最大次数が大きい平面グラフのトータル彩色の結果を紹介する。

日時	2007年5月14日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	藤沢潤（日本大学文理学部）
講演題目	Some recent problems on graph theory
講演要旨	本講演では、C5 Workshop on Graph theory において発表されたグラフ理論の最新の未解決問題をいくつか紹介するとともに、それらについて議論する。

日時	2007年5月7日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小田芳彰 (慶應義塾大学理工学部)
講演題目	Flipによる平面上の閉路の交差の解消
講演要旨	平面上のn点を通る閉路に対し、flipとよぶ変形操作をO(n^3)回繰り返すことにより、交差のない閉路が得られることおよびその周辺の話題を紹介する。このflipとは交差する２辺を別の２辺に交換することで閉路を保存するような変形のことであり、巡回セールスマン問題の近似解法の１つとして知られる2-OPTの変形操作(2-change)と似ている。

日時	2007年4月16日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	小関健太（慶應義塾大学大学院理工学研究科）
講演題目	指定した頂点及び辺を通る閉路の存在に関する近傍和条件
講演要旨	グラフ理論において閉路の存在に関する問題は、特に次数条件に関して多くの先行研究が存在するが、次数和条件と類似点も多い近傍和条件に関してもまた同様に研究がなされている。本講演では、次数条件との比較を考慮しつつ、近傍和条件と閉路問題の関係を話す予定である。特に、指定した頂点及び辺を通る閉路へと焦点を当て講演を行う。

日時	2007年4月9日(月)16:30--
場所	慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207
講演者	藤沢潤（日本大学文理学部）
講演題目	Chromatic game on graphs
講演要旨	本講演では、グラフにおけるchromatic gameの概念とその性質について紹介する。さらに、平面グラフにおいて解明されている結果や、未解決問題について述べる。