2013 年度
第 1 回 九州大学 組合せ数学セミナー1

下記のようにセミナーを開催しますので, ご案内申し上げます。
世話人:アドバイザー :溝口 佳寛（九大 IMI）
谷口 哲至（松江高専）
島袋 修（崇城大学）
田上 真（九州工大）
栗原 大武（北九州高専）
坂内 英一（上海交通大学/九大数理）記

日時: 2013 年 6 月 29 日 (土) 13:00–18:00
場所: リファレンス駅東ビル 会議室 I(2 階)
URL: http://comb.math.kyushu-u.ac.jp/

プログラム

12:55 – 13:00 開会宣言 （谷口 哲至）
13:00–13:50 坂内 英一（上海交通大/九州大学）
デザイン理論のめざすもの、特に tight relative t-designs について
(A survey on tight relative t-designs)
14:00–14:50 栗原 大武 (北九州高専)
複素グラスマン空間上の大対蹠集合のデザインによる特徴付け(A characterization of great antipodal sets of complex Grassmannian manifolds bydesigns)
15:00–15:50 澤 正憲 (名古屋大学)
ワーリング問題に関するある代数的恒等式と単体上のデザインの相互関係について〜 ヒルベルトの定理の別証明他(On the relationship between designs on the simplex and algebraic identities comingfrom Waring’s Problem – An alternative combinatorial proof of Hilbert’s theorem
and some other topics)
16:00–16:50 江藤 宏 (九州工業大学)
頂点数が最大となる正則誘導部分グラフの探索(Finding Maximum Regular Induced Subgraphs)
1

2013 年度、この研究集会は【科学研究費補助金 挑戦的萌芽研究課題番号:25610034 研究代表者:溝口佳寛】（日本学術振興会）の支援のもと開催されます。

17:00–17:50 大輪 拓也 (国立情報学研究所)検索連動型広告における予測と最適化(Prediction and optimization for search engine advertising)
17:55–18:00 総括 （溝口 佳寛）
18:30 – 懇親会Abstract
坂内 英一 (上海交通大/九州大学)
タイトル: デザイン理論のめざすもの、特に tight relative t-designs について (Asurvey on tight relative t-designs)
概要: 球面 t-デザインと組合せ論的 t-デザインの類似性、それらをそれぞれ拡張しているユークリッド t-デザインと relative t-design in H(n, 2) （あるいは一般の Q-多項式アソシエーションスキームにおける relative t-design）の類似性、などを我々はデザイン理論においてどのような問題を考えたいかという観点から議論したい。具
体的には、tight ユークリッド t-デザインの理論がどのように tight relative t-designの理論に拡張されるべきで現在のところ何が分かっていて何がわかっていないかを解説する。といっても分かっている 部分は非常に少ない。その分かっている部分
は、最近 の２つのプレプリント, Bannai-Bannai-Suda-Tanaka, On relative t-designsin polynomial association schemes, arXiv:1303.7163 と Bannai-Bannai-Bannai, On
the existence of tight relative 2-designs on binary Hamming association schemes,arXiv:1304.5760 に基づいている。

栗原 大武 (北九州高専)
タイトル: 複素グラスマン空間上の大対蹠集合のデザインによる特徴付け (A characterization of great antipodal sets of complex Grassmannian manifolds by designs)
概要: デザインとは、ある空間内の有限個の点集合で全体を「うまく」近似するような性質を持ったものである。 「良い」デザインは、対称性が高い、アソシエーショ
ンスキームの構造が付随する、様々な分野の重要なものから得られる、など興味深い性質を持つ。 これまでにデザイン理論は球面や Q 多項式アソシエーションスキームなど多くの空間の上で考えられてきた。
本講演では主に複素グラスマン空間上のデザイン理論について考察する。また、複素グラスマン空間上の大対蹠集合と呼ばれる微分幾何学的に「良く」散らばった有限集合をとある「良い」デザインとして特徴付られるということを説明する。今回の結果は奥田隆幸氏（東北大）との共同研究によって得られたものである。

澤 正憲 (名古屋大学)
タイトル: ワーリング問題に関するある代数的恒等式と単体上のデザインの相互関係について 〜 ヒルベルトの定理の別証明他 ( On the relationship between designs on
the simplex and algebraic identities coming from Waring’s Problem – An alternative
combinatorial proof of Hilbert’s theorem and some other topics)
概要: 斉次多項式 (x21 + · · · + x2n )r を有限個の 2r 乗項 (α1 x1 + · · · + αn xn )2r の和により記述する代数的恒等式をヒルベルト恒等式という．この恒等式はワーリング問題におけるヒルベルトの解（1909, Math. Ann.）に由来するが，その後の研究を通じてヒルベルトの第 17 問題をはじめ様々な代数的問題との関わりが指摘されてきた．
またヒルベルト恒等式は球面積分に対する求積公式とも深く関与することが知られており，その相互関係の解析は両分野に多くの知見をもたらしている．

本講演ではヒルベルト恒等式と球面的な求積公式との相互関係，および関連する基礎的事項を幾つか紹介する．そのうえで，球面的な求積公式と”単体的な”求積公式との関係付けや，ヒルベルトによるある有名な定理の組合せ論的別証明を行う．

江藤 宏 (九州工業大学)
タイトル: 頂点数が最大となる正則誘導部分グラフの探索 (Finding Maximum Regular Induced Subgraphs)
概要: 頂点数を最大とする正則部分グラフ探索問題は，グラフ G = (V, E) が与えられたとき，頂点部分集合 S によって誘導される部分グラフ G[S] が指定した次数 rの正則であり，頂点数が最大となるような S を見つけ出す問題集合である．本問題
は，グラフ G[S] の頂点がすべて連結である解を探索する問題（Maximum r-RegularInduced Connected Subgraph，r-MaxRICS 問題）と，2 つ以上の非連結な正則誘導部分グラフの頂点数が最大となるような解を探索する問題（Maximum r-Regular
Induced Subgraph，r-MaxRIS 問題）の２つに大別することができる．r-MaxRICS問題，r-MaxRIS 問題のいずれも，一般グラフにおいて，NP 困難であることが知られている．
本講演では，特別なグラフクラスに限定した場合について考える．まずは，平面グラフまたは 2 部グラフに入力を限定したとしても，整数 r における r-MaxRICS 問題
および r-MaxRIS 問題が NP 困難であることを示す．さらに，それら 2 つのグラフが木に近い構造を持ことで，NP 困難であった問題を効率良く解くことが可能になることを述べる．より厳密には，木幅を限定したグラフにおいては，線形時間で最適解を求めるアルゴリズムを示し，弦グラフにおいては多項式時間で最適解を求めるアルゴリズムを示す．
（共同研究者： 朝廣雄一（九産大），伊藤健洋（東北大），宮野英次（九工大））

大輪拓也 (国立情報学研究所)
タイトル: 検索連動型広告における予測と最適化 (Prediction and optimization forsearch engine advertising)
概要: インターネット広告の一つである検索連動型広告は、広告効果が高く効率も良いため、近年の広告費に占める割合は非常に大きくなってきている。実際に運用するためには検索ワードの選定や入札などの業務が必要だが、キーワード数が膨大なため人手の管理が難しく、予測や最適化の機能を有した自動ツールのサービスが広く利用されている。本講演では、講演者が前職で携わっていた自動ツールにおける予測と最適化について紹介をする。また、インターネット広告やそれにまつわる研究についても概観する。