トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS

過去のセミナー/2013年度 の履歴(No.10)


2013年度 組合せ数学セミナー

  • 世話人: 溝口 佳寛(九大IMI),谷口 哲至(松江高専),島袋 修(崇城大),田上真(九州工大), 栗原大武(北九州高専)

Organizers:
  Yoshihiro Mizoguchi (Kyushu University),
  Tetsuji Taniguchi (Matsue College of Technology),
  Osamu Shimabukuro (Sojo University),
  Makoto Tagami (Kyushu Institute of Technology),
  Hirotake Kurihara (Kitakyushu National College of Technology)

  • アドバイザー: 坂内 英一(上海交通大学/九州大学)

Advisary:
  Eiichi Bannai (Shanhai Jiao Tong University / Kyushu University)

第1回 2013年 6月 29日(土)

  • 場所:リファレンス駅東ビル 会議室I(2階)
  • 時間:13:00-18:00
  • 講演者: 坂内英一(上海交通大/九州大学),栗原大武(北九州高専),澤正憲(名古屋大),江藤宏(九工大),大輪拓也(NII)
  • プログラム(Program)
    講演者(Speaker)タイトル(Title)
    12:55-13:00開会宣言(谷口 哲至)
    Opening (Tetsuji Taniguchi)
    13:00-13:50坂内 英一
    (Eiichi Bannai)
    デザイン理論のめざすもの、特に tight relative t-designs について
    (A survey on tight relative t-designs)
    14:00-14:50栗原 大武
    (Hirotake Kurihara)
    複素グラスマン空間上の大対蹠集合のデザインによる特徴付け
    (A characterization of great antipodal sets of complex Grassmannian manifolds by designs)
    15:00-15:50澤 正憲
    (Masanori Sawa)
    ワーリング問題に関するある代数的恒等式と単体上のデザインの相互関係について ~ ヒルベルトの定理の別証明他
    (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)
    16:00-16:50江藤 宏
    (Hiroshi Eto)
    頂点数が最大となる正則誘導部分グラフの探索
    (Finding Maximum Regular Induced Subgraphs)
    17:00-17:50大輪 拓也
    (Takuya Ohwa)
    検索連動型広告における予測と最適化
    (Prediction and optimization for search engine advertising)
    17:55-18:00総括(溝口 佳寛)
    Closing (Yoshihiro Mizoguchi)
 
  • アブストラクト(Abstract)

坂内 英一 (上海交通大/九州大学)

  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 の理論に拡張されるべきで現在のところ何が分かっていて何がわかっていないかを解説する。といっても分かっている 部分は非常に少ない。その分かっている部分は、最近 の2つのプレプリント, 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): 斉次多項式 を有限個の 乗項 の和により記述する代数的恒等式をヒルベルト恒等式という.この恒等式はワーリング問題におけるヒルベルトの解(1909, Math. Ann.)に由来するが,その後の研究を通じてヒルベルトの第17問題をはじめ様々な代数的問題との関わりが指摘されてきた.またヒルベルト恒等式は球面積分に対する求積公式とも深く関与することが知られており,その相互関係の解析は両分野に多くの知見をもたらしている.
    本講演ではヒルベルト恒等式と球面的な求積公式との相互関係,および関連する基礎的事項を幾つか紹介する.そのうえで,球面的な求積公式と"単体的な"求積公式との関係付けや,ヒルベルトによるある有名な定理の組合せ論的別証明を行う.

江藤 宏(九州工業大学)

  Hiroshi Eto (Kyushu Institute of Technology)

  • タイトル(Title): 頂点数が最大となる正則誘導部分グラフの探索
      (Finding Maximum Regular Induced Subgraphs)
  • アブストラクト(Abstract): 頂点数を最大とする正則部分グラフ探索問題は,グラフ が与えられたとき,頂点部分集合 によって誘導される部分グラフ が指定した次数 の正則であり,頂点数が最大となるような を見つけ出す問題集合である.本問題は,グラフ の頂点がすべて連結である解を探索する問題(Maximum r-Regular Induced Connected Subgraph,r-MaxRICS問題)と,2つ以上の非連結な正則誘導部分グラフの頂点数が最大となるような解を探索する問題(Maximum r-Regular Induced Subgraph,r-MaxRIS問題)の2つに大別することができる.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): インターネット広告の一つである検索連動型広告は、広告効果が高く効率も良いため、近年の広告費に占める割合は非常に大きくなってきている。実際に運用するためには検索ワードの選定や入札などの業務が必要だが、キーワード数が膨大なため人手の管理が難しく、予測や最適化の機能を有した自動ツールのサービスが広く利用されている。本講演では、講演者が前職で携わっていた自動ツールにおける予測と最適化について紹介をする。また、インターネット広告やそれにまつわる研究についても概観する。