平成 20 年 1 月 29 日版

第4回組合せ論若手研究集会プログラム

平成 20 年 2 月 4 日 (月) ∼ 2 月 6 日 (水) 慶應義塾大学矢上キャンパス創想館 2 階セミナールーム 2 (14-202)

2 月 4 日 (月)

[一般講演]

9:05 ∼ 9:30 水飼巌 (横浜国立大学大学院環境情報学府)

「トーラス上の 5-連結三角形分割の 2-拡張可能性について」

9:30 ∼ 9:55 小関健太 (慶應義塾大学大学院理工学研究科)

「A sufficient condition for graphs to be prism hamiltonian」

9:55 ∼ 10:20 阿部利孝 (金沢大学大学院自然科学研究科数物科学専攻博士前期課程)

「Z_{9} 上の拡張巡回符号」

—————————————- 休憩 10 分 —————————————-

10:30 ∼ 10:55 松井泰子 (東海大学理学部)

「A fast algorithm for generating all perfect sequences」

10:55 ∼ 11:20 Hadi Shaikh Zaker (電気通信大学電気通信学研究科情報通信工学専攻)

「A Hypergraph Version of the Erdős-Stone Theorem」

11:20 ∼ 11:45 黒瀬竜一 (電気通信大学電気通信学研究科情報通信工学専攻)

「A large complete subhypergraph in a dense hypergraph」

————————————————– 昼食休憩 ————————————————–

2 月 4 日 (月)

[招待講演]

13:30 ∼ 15:20 石上嘉康氏 (電気通信大学電気通信学部)

「離散構造の中の擬ランダム性（Szemeredi の一様化補題、ランダムサンプリング、プロパティテスト、ラムゼー理論）」

次はｖ an der Waerden の定理 (1927) の拡張で、 Szemeredi の定理 (1975) と呼ばれる。”N を十分大きな整数とする。１から N までの N 個の整数の中から N/1000 個以上の整数をもってきたとき、その中に長さ 1000 の等差数列が存在する。” （２つの 1000 はより大きな定数に置き換えてもよい。）この定理のオリジナルの証明は、一様化補題 (regularity lemma) というグラフ理論の補題が鍵になっている。この補題には、グラフ理論・数論や離散数学全般から理論計算機科学まで、様々な応用が知られてきたが、最近、さらに急速にその理解が増してきている。ここでは最近わかった例として、この補題の簡潔な構成法を説明する。さらにそれは自然に超グラフ (hypergraphs) へと拡張可能であり、より短い Szemeredi の定理の別証明を与える。この構成は、ランダムサンプリングによるもので、理論計算機科学で研究されてきたプロパティテスト (property test) と本質的に同じものである。応用例などを含めて、このあたりの最新の事情を説明するつもりです。

15:30 ∼ 17:20 大杉英史氏 (立教大学理学部数学科)

「トーリックイデアルのグレブナー基底」

多項式環のイデアルの特別な生成系である，グレブナー基底に纏わる基本的な内容を解説するとともに，トーリックイデアルのグレブナー基底による，諸分野への応用（凸多面体の三角形分割，整数計画問題など）について幾つか紹介する。

2 月 5 日 (火)

[一般講演]

9:00 ∼ 9:25 木村健司 (電気通信大学電気通信学研究科情報工学専攻)

「k-Factors in regular graphs and edge-connectivity」

9:25 ∼ 9:50 中本敦浩 (横浜国立大学教育人間科学部)

「Dominating sets on triangulations on surfaces」

9:50 ∼ 10:15 縫田光司 (産業技術総合研究所情報セキュリティ研究センター)

「A Characterization of Edge-Bicolored Graphs with Generalized Perfect Elimina tion Orderings」

—————————————- 休憩 15 分 —————————————-

10:30 ∼ 10:55 堀田幸嗣 (金沢大学大学院自然科学研究科数物科学専攻博士前期課程)

「２つの正則元から生成される４元 BCH 符号」

10:55 ∼ 11:20 高藤政典 (東京理科大学)

「横断数 3 の 4 一様な有限交差族について」

11:20 ∼ 11:45 徳重典英 (琉球大学教育学部)

「互いに交差する集合族の Erdős-Ko-Rado 型不等式」

————————————————– 昼食休憩 ————————————————–

2 月 5 日 (火)

[招待講演]

13:30 ∼ 16:10 樋口雄介氏 (昭和大学富士吉田教育部)

「被覆構造を持つグラフの解析」

講演は前半「被覆グラフとスペクトル (入門)」と後半「被覆グラフとスペクトル (応用)」の 2 部構成で行う予定である．具体的な内容 (予定) は以下の通りである：・前半「被覆グラフとスペクトル (入門)」 ”平面被覆予想” や ”周期性を持つ無限グラフのスペクトル幾何” などに見られるグラフの”被覆構造” について，初歩的なところからの解説を主たる目的として，与えられた有限グラフに対しての被覆グラフの作り方，被覆変換群と自己同型写像，正則 (正規) 被覆などの概念を，具体例を通して紹介する．また併せて， google の page rank(TM) などにも応用されているグラフのスペクトルについても，アーベル被覆グラフのスペクトル表現を中心に具体例を通して紹介する．・後半「被覆グラフとスペクトル (応用)」有限グラフの正則被覆グラフである無限グラフのスペクトル構造の解析においては，被覆変換群の構造と商グラフである有限グラフの幾何構造の解析が鍵となる．ここでは商グラフの持つ組合せ的性質がアーベル被覆グラフのスペクトル構造に強い影響を及ぼす場合に重点を置き，各種の具体例や得られている結果，そして未解決問題などを紹介する．

16:20 ∼ 18:00 善本潔氏 (日本大学理工学部数学科)

「２因子とハミルトンサイクルについて」

Claw-free グラフにおける最も有名な予想の一つ、 Matthews & Sumner の予想や Thomassen の予想を中心において、前半では Zhan や Jackson、 Chen-Lai の結果や予想などこれまでの研究を紹介し、後半では講演者が最近得た結果と関連する予想や問題を紹介します．時間があったら、 Dirac 型条件における２因子やハミルトンサイクルの問題を紹介します．

2 月 6 日 (水)

[一般講演]

9:00 ∼ 9:25 西田真也 (慶應義塾大学大学院理工学研究科)

「Chords of longest cycles on a surface」

9:25 ∼ 9:50 村上寛 (熊本大学大学院自然科学研究科)

「有限群における素数グラフの補グラフ」

9:50 ∼ 10:15 篠原英裕 (大阪大学情報科学研究科)

「クリークグラフと同じ最大重み全域木を持つグラフの重み」

—————————————- 休憩 15 分 —————————————-

10:30 ∼ 10:55 篠原雅史 (九州大学数理学研究院 COE 研究員)

「On locally two-distance sets」

10:55 ∼ 11:20 城戸浩章 (九州大学大学院数理学研究院 COE 研究員)

「４次元ユークリッド空間における isosceles set の分類と maximum cardinality について」

11:20 ∼ 11:45 大嶌彰昇 (東京理科大学)

「Recursive constructions of consecutively super-edge-magic trees 〜consecutively super-edge-magic な木の漸化的構成〜」

————————————————– 昼食休憩 ————————————————–

2 月 6 日 (水)

[招待講演]

13:30 ∼ 15:10 中上川友樹氏 (湘南工科大学工学部情報工学科)

「多重三角形分割について」

円周の n 等分点を端点とする線分の集合 E_{n} を考える。 k 本の線分の集合 C ⊆ E_{n} について、 C のどの２本の線分も円の内部で交差するとき、 C を k-交差と呼ぶ。 (k + 1)-交差のない極大な線分の集合 T ⊆ E_{n} を k-三角形分割と呼ぶ。 k = 1 の場合は通常の三角形分割に相当する。本講演では、 k-三角形分割の基本的性質、最新の結果及び未解決問題について概観する。

15:20 ∼ 17:30 来嶋秀治氏 (京都大学数理解析研究所)

「列挙、数え上げ、サンプリングのはなし」

本講演では、組合せ的対象の列挙、数え上げ、ランダムサンプリングについて話をする。列挙、ランダムサンプリングは、共に（有限）集合中の要素生成・探索に対する汎用手法であり、関連も深い。効率的な計算法という観点から、両者の関連、そして集合要素の数え上げとの関連について議論する。講演では、特に MCMC(Markov chain Monte Carlo) 法について、マルコフ連鎖の収束スピードに関する研究分野を紹介し、マルコフ連鎖を用いた完璧サンプリング法について説明する。

注) 招待講演は間に 10 分間の休憩を挟みます．