| 日時 | 2007年3月19日(月)15:00-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 山下 登茂紀（朝日大学歯学部） |
| 講演題目 | 平面的グラフにおける線形樹化数について |
| 講演要旨 | 線形樹化数とは、グラフの辺を分割する線形林の最小数のことである。 本講演では、平面的グラフにおける線形樹化数について考える。 |
| 日時 | 2007年3月1日(木)17:00-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | Antoine Deza (McMaster University, Canada) |
| 講演題目 | Colourful Simplicial Depth |
| 講演要旨 | Inspired by Barany's colourful Caratheodory theorem, we introduce a colourful generalization of Liu's simplicial depth of a point $p$ in $R^d$ relative to a fixed set $S$ of sample points, i.e. the number of simplices generate by points in $S$ that contain $p$. We prove a parity property and conjecture that the minimum colourful simplicial depth of any core point in any $d$-dimensional configuration is $d2+1$ and that the maximum is $d^{d+1}+1$. We exhibit configurations attaining each of these depths, and apply our results to the problem of bounding monochrome (non-colourful) simplicial depth. Independently found recent quadratic lower bounds by Barany and Matousek and by Stephen and Thomas are also presented and algorithmic issues are highlighted. |
| 日時 | 2007年2月19日(月)15:00-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 中本 敦浩（横浜国立大学教育人間科学部） |
| 講演題目 | K6-Minors in triangulations on surfaces |
| 講演要旨 | 6以上の整数nについて、完全グラフK_nをマイナーとして含むグラフの 特徴付けはたいへん難しいことがわかってきている。 本講演では、K_6をマイナーとして含む閉曲面の三角形分割を特徴付けることを目標とする。 既存の研究として、射影平面、トーラスの三角形分割がK_6マイナーを含むための 必要十分条件は、5頂点以下の完全グラフによる四角形分割を含まないことであることが 知られていた。 特に今回は、それ以外の閉曲面の三角形分割がK_6マイナーを含むための条件を、 Sulankeが分類した既約三角形分割の完全リストをもとに議論する。 |
| 日時 | 2007年1月29日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 石井 啓嗣（慶應義塾大学大学院理工学研究科） |
| 講演題目 | k-ordered graphsの一般化 |
| 講演要旨 | 指定された頂点を全て通るようなcycleや、指定された順に通るcycleが存在するような条件が 近年研究されている。本講演では、その概念の一つであるk-ordered graphsの一般化を考え、 その場合における次数に関する十分条件を与えた。 |
| 日時 | 2007年1月22日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 山下 登茂紀（朝日大学歯学部） |
| 講演題目 | 半径と独立数とハミルトン閉路の存在について |
| 講演要旨 | １９８８年、Fajtlowiczによって、「半径ｒと独立数が等しいグラフは、 頂点数が２ｒのパスかサイクルを誘導部分グラフとして含む」ことが示されている。 本講演では、半径と独立数が等しいグラフがハミルトン閉路を持つための条件について議論する。 |
| 日時 | 2007年1月15日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 榎本 彦衛（慶應義塾大学） |
| 講演題目 | 社会的選好関係 |
| 講演要旨 | Arrow の不可能性定理の簡単な証明と、 各人の選好関係が single peaked のときには中央値が存在することの証明を与 えた。 |
| 日時 | 2006年12月18日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 小関 健太（慶應義塾大学大学院理工学研究科） |
| 講演題目 | Hamiltonicity of 3-connected claw-free graphs |
| 講演要旨 | いままでに claw-free グラフのハミルトン性について、 2-連結、3-連結、4-連結、それぞれの場合で 多数の研究がなされている。 本講演ではその中でも3-連結の場合について焦点をあて、 その最新の結果を紹介した。 |
| 日時 | 2006年12月11日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 山下 登茂紀（朝日大学歯学部） |
| 講演題目 | Relative Length of Longest Paths and Cycles |
| 講演要旨 | 多くの研究者によって、最長道や最長閉路の長さの評価に関する研究が行われている。 また、最長道と最長閉路の長さの関係についての研究も盛んである。 本講演では、特に最長道と最長閉路の長さの差について、幾つかの結果を述べる。 本研究は、津垣正男氏と慶應義塾大学の小関健太氏との共同研究である。 |
| 日時 | 2006年12月4日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 杉山 武史（慶應義塾大学大学院理工学研究科） |
| 講演題目 | 連結claw-freeグラフにおけるP_{\geq d+1}-factorの存在について |
| 講演要旨 | 連結claw-freeグラフにおけるP_{\geq d+1}-factorが存在するための 最小次数条件は既に知られている。 本講演ではその拡張として連結claw-freeグラフにおいてm-claw 上の指定した頂点にのみに次数条件を与えることにより P_{\geq d+1}-factorの存在を示す。 |
| 日時 | 2006年11月27日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 小関 健太（慶應義塾大学大学院理工学研究科） |
| 講演題目 | 5-連結平面グラフ上の3-因子の存在について |
| 講演要旨 | いままでに 3-連結および 4-連結平面グラフ上の因子、 さらに連結因子に関していくつかの研究がなされている。 そこで本講演では、 この問題を 5-連結平面グラフについて考え、 「位数偶数の 5-連結平面グラフには 3-因子が存在する」 という定理を証明する。 |
| 日時 | 2006年11月20日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 木村 健司（電気通信大学大学院電気通信学研究科） |
| 講演題目 | 正則グラフから1頂点を削除した部分グラフが持つ因子について |
| 講演要旨 | 本講演では、正則グラフ G から1頂点を削除した部分グラフが k-因子を持つとき、 G の辺連結度との関係性を考察する。 |
| 日時 | 2006年11月13日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 山下 登茂紀（朝日大学歯学部） |
| 講演題目 | Hamiltonian cycles passing through a matching |
| 講演要旨 | 「ハミルトン閉路」、その拡張である「指定された辺を通るハミルトン閉路」が存在 するための非隣接２頂点次数和条件が知られている。また、「ハミルトン閉路」が存 在するための３頂点次数和条件も知られている。本講演では、「指定された辺を通る ハミルトン閉路」が存在するための３頂点次数和条件について幾つかの結果を述べる。 本研究は、慶應義塾大学の小関健太氏との共同研究である。 |
| 日時 | 2006年11月6日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 藤沢 潤 (日本大学文理学部) |
| 講演題目 | 閉包操作とk-ended 全域木の存在について |
| 講演要旨 | グラフの全域木がk個以下の葉を持つとき、k-ended 全域木と呼ぶ。 また、"グラフの非隣接2頂点で次数和がrのものを結ぶ"という操作を 繰り返して得られるものを、元のグラフのr-閉包と呼ぶ。 本講演では、n頂点のグラフの(n-1)-閉包がk-ended 全域木を持つとき、 元のグラフにもk-ended 全域木が存在することを示す。 また、n頂点グラフでその(n-2)-閉包が完全グラフになるにも関わらず 元のグラフがk-ended 全域木を持たない例を示す。 本研究は、TU Bergakademie FreibergのIngo Schiermeyer氏、 日本大学の斎藤 明氏との共同研究である。 |
| 日時 | 2006年10月30日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 藤沢 潤 (日本大学文理学部) |
| 講演題目 | Forbidden subgraphs and E(k,1) property on graphs |
| 講演要旨 | あるグラフにおいて、そのグラフの任意のk+l本の独立な辺 e_1, e_2, …, e_{k+l}に対し、"e_1, …, e_kを含み、 e_{k+1}, …, e_{k+l}を含まない"ような完全マッチングを持つとき、 そのグラフはE(k,l)であるという。 本講演では、グラフの族Hに対し"グラフがm-連結、H-freeならばE(k,1)である" という命題を考え、Hが一つのグラフから成るときはH=K_{1,r} (2≦r≦m-2k+1) であることを示す。また、Hが二つのグラフから成るとき、そのうちの一つは スターK_{1,r}になるが、rの値が(2≦r≦m-2k+1)に限らないことを示す。 この"rの値が(2≦r≦m-2k+1)に限らない"ことから、性質E(0,0)について 同様の問題を考えた際との差異が生じることがわかる。 本研究は、Vanderbilt UniversityのMichael D. Plummer氏、 TU Bergakademie FreibergのIngo Schiermeyer氏、 日本大学の斎藤 明氏との共同研究である。 |
| 日時 | 2006年10月23日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | Ingo Schiermeyer (TU Bergakademie Freiberg, Germany) |
| 講演題目 | k-colourability and forbidden subgraphs |
| 講演要旨 | In this talk we will consider the k-colourability problem. We will show upper bounds for the chromatic number for several classes of graphs in terms of forbidden subgraphs. Especially we will show that all (K_3, P_6)-free graphs are 4-colourable. Moreover, if a (K_3, P_6)-free graph is 4-chromatic and contains no twins, then it contains the Mycielski-Grotzsch Graph as a subgraph and is a subgraph of the Clebsch graph. |
| 日時 | 2006年10月16日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | Michael D. Plummer (Vanderbilt University, USA) |
| 講演題目 | On the matching extendability of graphs in surfaces |
| 講演要旨 | A graph $G$ with at least $2n+2$ vertices is said to be $n$-extendable if every matching of size $n$ in $G$ extends to a perfect matching. It is shown that (1) if a graph is embedded on a surface of Euler characteristic $\chi$, and the number of vertices in $G$ is large enough, the graph is not 4-extendable; (2) given $g>0$, there are infinitely many graphs of orientable genus $g$ which are 3-extendable, and given $\overline g>2$, there are infinitely many graphs of non-orientable genus $\overline g$ which are 3-extendable; and (3) if $G$ is a 5-connected triangulation with an even number of vertices which has genus $g$ and sufficiently large representativity, then it is 2-extendable. |
| 日時 | 2006年10月2日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 杉山 武史（慶應義塾大学大学院理工学研究科） |
| 講演題目 | 禁止部分グラフと指定点を通るサイクルの存在について |
| 講演要旨 | ２連結グラフにおいて指定された頂点を全て通るようなサイクルが 存在するための十分条件を、「特定のグラフの族を禁止する」という 観点から考察していく。 |
| 日時 | 2006年7月19日(水)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 藤沢 潤 (日本大学文理学部) |
| 講演題目 | グラフ理論における最新の話題 |
| 講演要旨 | 「Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications」 において発表されたいくつかの最新の話題を紹介し、 それらについて議論をする。 |
| 日時 | 2006年7月13日(木)16:00--17:30 |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-207 |
| 講演者 | 城本 啓介（愛知県立大学情報科学部） |
| 講演題目 | 符号の部分符号とデザイン |
| 講演要旨 | （名古屋大学でのセミナーのインターネット中継） |
| 日時 | 2006年7月10日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 中本 敦浩 (横浜国立大学教育人間科学部) |
| 講演題目 | 曲面の偶三角形分割の染色数について |
| 講演要旨 | 固定された曲面に埋め込めるグラフの染色数、 また、偶角形分割として埋め込めるグラフの染色数の上界は、 曲面の種数のみに依存する関数により抑えられることが知られている。 一方、曲面上の偶三角形分割（すべての頂点が偶次数の三角形分割）の染色数については、 球面、射影平面の場合、また、それ以外の任意の曲面上でrepresentativity が十分高い場合のみ完全決定されている。 本講演では、クラインの壷の偶三角形分割の染色数の上界はちょうど6であることを証明する。 さらに、6-染色的偶三角形分割の特徴付けにむけて、いくつかの考察を与える。 |
| 日時 | 2006年7月3日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 小田 芳彰 (慶應義塾大学理工学部) |
| 講演題目 | transpositionによるソート |
| 講演要旨 | 0,1,2の３文字からなる列を昇順にソートすることを考える。 行える操作をtranspositionとよばれる部分列に関するある変形だけに限った場合、 その必要な操作回数について考察する。 |
| 日時 | 2006年6月26日(月)17:00--18:00 |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | David Avis (McGill University, Canada) |
| 講演題目 | A Few Million More Tight Bell Inequalities |
| 講演要旨 |
Bell's 1964 theorem has been described as "one of the profound
scientific discoveries of the (20th) century". His inequality, and
generalizations of it, are at the heart of quantum computation and
information processing. Related inequalities have been well studied in
areas such as probability theory, metric embeddings, number theory and
discrete optimization in connection with cut and correlation polyhedra.
I will explain this connection, and using it describe a method of
generating a large number of new, distinct, tight Bell inequalities and
a convex body that contains the quantum correlation set.
If time permits, I will also discuss briefly how such inequalities can
be used for nonlocal games.
(Joint work with H. Imai, T. Ito and Y. Sasaki.) （名古屋大学へインターネット中継も行います。） |
| 日時 | 2006年6月19日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 山下 登茂紀（朝日大学歯学部） |
| 講演題目 | 指定された頂点を通る閉路の長さについて |
| 講演要旨 | 「最小次数がdでk連結グラフは、任意のk頂点を通る長さが2d以上の閉路が存在する」 ことが知られている。 k連結グラフは任意のk頂点を通る閉路が存在するが、 任意の(k+1)頂点を通る閉路が存在するかはわからない。 そこで、「最小次数がdでk連結グラフは、ある閉路上の(k+1)頂点を通る長さが2d 以上の閉路が存在する」という予想について議論する。 |
| 日時 | 2006年6月15日(木)16:00--17:00 |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-207 |
| 講演者 | Thomas Britz (University of New South Wales, Australia) |
| 講演題目 | Matroids, codes, and designs |
| 講演要旨 |
講演資料 （名古屋大学でのセミナーのインターネット中継） |
| 日時 | 2006年6月12日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 藤沢 潤（日本大学文理学部） |
| 講演題目 | グラフの頂点連結度、スターフリー条件、最小次数条件と2-factorの存在について |
| 講演要旨 | 本講演では、5/22の講演で得られた結果に加え、 ある与えられた2つの整数 n \ge 3 ,k \ge 2 に対し、 「グラフがK_{1,n}-フリー、k-頂点連結であるときに2-factorの存在を保証する」 ための最小次数に関する最善な条件を与える定理を紹介する。 本研究は、University of OtagoのRobert E. L. Aldred氏、 東京理科大学の江川嘉美氏、慶應義塾大学の太田克弘氏、日本大学の斎藤明氏 との共同研究である。 |
| 日時 | 2006年6月5日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 津垣 正男 |
| 講演題目 | Pan-factorial Property in Regular Graph |
| 講演要旨 |
加納らにより、任意の辺に対しその辺を含む1-factorを持つ奇数位数の連結なr-正則グラフには、任意の辺を含むk-factorと含まないk-factor(0 |
| 日時 | 2006年5月29日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 向江 頼士 (横浜国立大学大学院教育学研究科) |
| 講演題目 | K_6 Minors in triangulations on the torus |
| 講演要旨 | これまでの研究で、 射影平面上の三角形分割 G がK_6をマイナーとして持つための必要十分条件は、 GがK_4-四角形分割を部分グラフとして含まないことであることが知られていた。 本講演では、トーラス上の三角形分割 G がK_6をマイナーとして持つ必要十分条件は、 GがK_5-四角形分割を部分グラフとして含まないという定理を証明する。 その証明には、既約三角形分割の完全リストを用いる。 今回得られた定理の応用として、この２つの曲面を三角形分割するグラフに対して、 Hadwiger's Conjectureの n=6 の場合が成り立つことが容易に確認できる。 |
| 日時 | 2006年5月22日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 藤沢 潤（日本大学文理学部） |
| 講演題目 | グラフの辺連結度、スターフリー条件、最小次数条件と2-factorの存在について |
| 講演要旨 | 本講演では、ある与えられた2つの整数 n \ge 4 ,k \ge 2 に対し、 「グラフがK_{1,n}-フリー、k-辺連結であるときに2-factorの存在を保証する」 ための最小次数に関する最善な条件を与える定理を紹介する。 本研究は、University of OtagoのRobert E. L. Aldred氏、 東京理科大学の江川嘉美氏、慶應義塾大学の太田克弘氏、日本大学の斎藤明氏との 共同研究である。 |
| 日時 | 2006年5月15日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 藤沢 潤（日本大学文理学部） |
| 講演題目 | スターフリーグラフにおける、辺連結度と2-factorの存在について |
| 講演要旨 | 本講演では、 グラフがK_{1,n}-フリーである時、2-factorの存在を保証するための 辺連結度に関する最善な条件を与える定理を紹介する。本研究は、University of Ot agoのRobert E. L. Aldred氏、日本大学の斎藤明氏との共同研究である。 |
| 日時 | 2006年5月8日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 小関 健太（慶應義塾大学大学院理工学研究科） |
| 講演題目 | グラフの連結度と独立数に関する次数条件について |
| 講演要旨 | 「指定した点を全て通る閉路」が存在するための十分条件については、 「連結度と3頂点次数和」に関してはすでに知られている。 そこで、本講演ではその延長として考えられた 「連結度と独立数と4頂点次数和」に関する条件について議論する。 |
| 日時 | 2006年5月1日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 太田 克弘（慶應義塾大学理工学部） |
| 講演題目 | Toughness of K_{a,t}-minor-free graphs |
| 講演要旨 | It is well known that every 3-connected K_{3,3}-free graph is planar, and hence is (1/2)-tough. As a generalization of this fact, we prove the following theorem: Let t\ge a\ge 3 be integers. Then, there exists a positive constant f(a,t) such that every a-connected K_{a,t}-minor-free graph is f(a,t)-tough. This is a joint work with G. Chen, K. Kawarabayashi and B. Mohar. |
| 日時 | 2006年4月24日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 小関 健太（慶應義塾大学大学院理工学研究科） |
| 講演題目 | 指定点と指定辺を通る辺支配閉路について |
| 講演要旨 | かつて Bondy は「辺支配閉路の存在を保証する次数和条件」 に関する結果を示した。 これを拡張し、 「指定点と指定辺を全て通るような辺支配閉路 の存在を保証する次数和条件」 に関して議論する。 |
| 日時 | 2006年4月17日(月)16:30-- |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | 杉山 武史（慶應義塾大学大学院理工学研究科） |
| 講演題目 | 禁止部分グラフと指定点を通るサイクルの存在について |
| 講演要旨 | ２連結グラフがclawとP_6を誘導部分グラフとして含まないならば、 そのグラフにハミルトンサイクルが存在するということは既に知られている。 本講演ではその定理をさらに拡張していくことを考える。 |
| 日時 | 2006年4月10日(月)16:30--17:30 |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス数理科学棟2階 36-205/207 |
| 講演者 | Bojan Mohar (Simon Fraser University, Canada) |
| 講演題目 | Coloring Graphs on Surfaces |
| 講演要旨 | Map and graph coloring problems have been motivated by the famous
Four-Color Problem. Even today, three decades after the Four-Color
Problem has been solved, new fundamental theorems about colorings of
graphs embedded in surfaces are discovered. Some results about usual
colorings, list colorings and acyclic colorings will be presented with
intention to show how combinatorial, topological and probabilistic
methods interplay in this area of graph theory.
(A copy of OHP sheets is available.) |
| 日時 | 2006年4月8日(土)11:00--12:00 |
|---|---|
| 場所 | 慶應義塾大学矢上キャンパス14棟2階 14-203(セミナールーム3) |
| 講演者 | Bojan Mohar (Simon Fraser University, Canada) |
| 講演題目 | Hadwiger's Conjecture |
| 講演要旨 |
Hadwiger has conjectured in 1943 that every graph whose chromatic number
is k contains a k-clique as a minor. He formulated this problem as
an attempt to generalize the Four Color Problem without using
topological notions. Hadwiger's Conjecture remains a mystery. It has
been solved for values of k up to 6 and is open for k\ge 7. By many,
this conjecture is considered as one of the central open problems in
graph theory.
The talk, which will be intended for general audience, will show some of the ideas behind this conjecture, reveal the history, and uncover some recent developments related to the Hadwiger Conjecture. (A copy of OHP sheets is available.) |