分野別セミナー

坂内 英一 (上海交通大/九州大学)
Eiichi Bannai (Shanhai Jiao Tong University / Kyushu University)
Title: デザイン理論のめざすもの、特に tight relative t-designs について
　　(A survey on tight relative t-designs)
Abstract：球面 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-designs in 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 にもとずいている。



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




澤 正憲 (名古屋大学)
Masanori Sawa (Nagoya University)
Title: ワーリング問題に関するある代数的恒等式と単体上のデザインの相互関係について
　　～ ヒルベルトの定理の別証明他
　　(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)
Abstract： 斉次多項式 (x21+…+x2n)r を有限個の 2r 乗項 (α1x1+…+αnxn)2r の和により記述する代数的恒等式をヒルベルト恒等式という．この恒等式はワーリング問題におけるヒルベルトの解（1909, Math. Ann.）に由来するが，その後の研究を通じてヒルベルトの第17問題をはじめ様々な代数的問題との関わりが指摘されてきた．またヒルベルト恒等式は球面積分に対する求積公式とも深く関与することが知られており，その相互関係の解析は両分野に多くの知見をもたらしている．
　本講演ではヒルベルト恒等式と球面的な求積公式との相互関係，および関連する基礎的事項を幾つか紹介する．そのうえで，球面的な求積公式と"単体的な"求積公式との関係付けや，ヒルベルトによるある有名な定理の組合せ論的別証明を行う．




江藤 宏(九州工業大学)
Hiroshi Eto (Kyushu Institute of Technology)
Title: 頂点数が最大となる正則誘導部分グラフの探索
　　(Finding Maximum Regular Induced Subgraphs)
Abstract：頂点数を最大とする正則部分グラフ探索問題は，グラフ G=(V,E) が与えられたとき，頂点部分集合 S によって誘導される部分グラフ G[S] が指定した次数 r の正則であり，頂点数が最大となるような S を見つけ出す問題集合である．本問題は，グラフ G[S] の頂点がすべて連結である解を探索する問題（Maximum r-Regular Induced 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困難であった問題を効率良く解くことが可能に なることを述べる．より厳密には，木幅を限定したグラフにおいては，線形時間 で最適解を求めるアルゴリズムを示し，弦グラフにおいては多項式時間で最適解 を求めるアルゴリズムを示す．
（共同研究者： 朝廣雄一（九産大），伊藤健洋（東北大），宮野英次（九工大））




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





リンク
　九州大学組合せ数学セミナーWebsite
　リファレンス駅東ビルWebsite