組合せ論セミナー

組合せ論セミナーは、主に若手研究者の情報収集と身近な発表の場として、慶應関係者のみならず、
関東・全国から多数の組合せ論研究者・大学院生が集まって開催されているセミナーです。
毎回グラフ理論など組合せ論に関する新しい研究成果や予想、論文紹介などを中心に議論を進めています。
なお、発表者にはなるべく証明の詳細まで説明していただきたいと考えています。
関連する研究集会、学会等がある週を除き、ほぼ週に1回のペースで開催しています。
興味のある方のご参加をお待ちしております。

過去のページ: 2005年度 2006年度 2007年度 2008年度 2009年度 2010年度 2011年度 2012年度 2013年度 2014年度 2015年度 2016年度 2017年度 2018年度

このセミナーについてのお問い合わせはこちら

慶應義塾大学理工学部数理科学科
 太田 克弘 (ohta@math.keio.ac.jp)
 小田 芳彰 (oda@math.keio.ac.jp)

セミナー 講演予定

日時 2019年5月20日(月)16:30--
場所 慶應義塾大学矢上キャンパス創想館6階14-631B
講演者
講演題目
日時 2019年6月3日(月)16:30--
場所 慶應義塾大学矢上キャンパス創想館6階14-631B
講演者 山口 勇太郎(大阪大学)
講演題目 Finding a Path with Two Labels Forbidden in Group-Labeled Graphs
講演内容 群ラベル付きグラフ (group-labeled graph) とは,有向グラフの各辺に,群の要素をラベルとして付したものであり,基礎グラフ (underlying graph) 中の歩道 (walk) のラベルを,「通った辺のラベル(逆向きに通る場合はその逆元)の積」として定義する. 群ラベル付きグラフに関して,「2点間のパス (path) が取り得るラベルが1種類(以下)である」ことは,「全ての閉路 (cycle) のラベルが単位元である」こととほぼ等価であることが知られており,この特徴付けを用いると,容易に「指定した要素以外のラベルを持つ$s$--$t$パスを見つける」ことができる. これは,グラフに関して,「2部グラフである」ことが,「奇数長の閉路を持たない」ことと等価であるという事実の一般化となっている. 本講演では,「2点間のパスが取り得るラベルがちょうど2種類である」ような群ラベル付きグラフの特徴付けを与え,その判定が容易であることの帰結として,「指定した2つの要素以外のラベルを持つ$s$--$t$パスを見つける」ことが容易であることを示す. この問題は,「無向グラフ中で2つの頂点対を結ぶ点素パスを見つける」問題を一般化しており,本結果はその存在に関する特徴付け (Seymour 1980) の一般化となっている.

セミナー 講演記録

日時 2019年5月13日(月)16:30--
場所 慶應義塾大学矢上キャンパス創想館6階14-631B
講演者 土屋 翔一(専修大学)
講演題目 {K1,3, B1,2, P6}-freeグラフとfat-pathについて
日時 2019年4月22日(月)16:30--
場所 慶應義塾大学矢上キャンパス創想館6階14-631B
講演者 藤沢 潤(慶應義塾大学)
講演題目 3-conn. claw-freeグラフにおけるハミルトンサイクルの存在について
日時 2019年4月15日(月)16:30--
場所 慶應義塾大学矢上キャンパス創想館6階14-631B
講演者 前澤 俊一(横浜国立大学環境情報学府)
講演題目 格子点を2色で塗ったときの同色の正方形の存在