大阪組合せ論セミナー

大阪組合せ論セミナーは、月1回、大阪梅田で開催されているセミナーで、 組合せ論やその周辺の分野の専門家を招き、講演をしていただき、みんなで勉強するものです。 毎回講演者の方には、じっくり時間をかけて、基本的な定義の部分からお話ししていただいています。
本セミナーは、組合せ論に興味のある方でしたらどなたでも参加いただけるセミナーです。 身分、所属に関わらず、興味のある方はいつでも参加していただければ幸いです。

場所

大阪駅前第2ビル6階(大阪公立大学梅田サテライト、文化交流センター)・小セミナー室
         →アクセス方法はこちら

次回以降の日程


第79回
日時:2025年8月1日(金)13:30~17:00
講演者:林 興養(東京大学大学院情報理工学系研究科)
題目:木幅とグリッドマイナー定理
要旨:グラフの木幅は, グラフが木にどの程度近いかを測る指標であり, グラフの大域的な連結度を捉えるパラメータとして, 理論とアルゴリズムの両面で重要な役割を果たす. Robertson--Seymour によって証明されたグリッドマイナー定理は, 木幅がf(k) 以上である任意のグラフが必ず k×k のグリッドグラフをマイナーとして含むような関数 f(k)が存在することを主張するものであり, グラフマイナー理論の構造定理の根幹をなす. この関数 f(k) については, Chekuri--Chuzhoy により初めて多項式的な上界が与えられた. 本講演では, 木幅の基本的性質に触れた上で, グリッドマイナー定理の背景や関数 f(k) の上界の改善に向けた近年の研究について紹介する.


第80回
日時:2025年10月31日(金)13:30~17:00
講演者:盧 暁南(岐阜大学工学部)
題目:
要旨:

過去の講演

        こちらをご覧ください

主催者

東谷 章弘(大阪大学 大学院情報科学研究科)
枡田 幹也(大阪公立大学 大学院理学研究科)
(あいうえお順)


本セミナーはJSPS科研費
基盤研究(B) #24K00521
の助成を受けたものです。

問い合わせなどは、東谷(higashitani あっとまーく ist.osaka-u.ac.jp)までご連絡ください。