2010年11月17日水曜日

Lovasz Workshop で Lovasz と少しだけ話ができた

今日は京都賞を取った Lovasz の受賞記念ワークショップということで、話を聞きに行ってきた。
他にも作業があったのであまりたくさんは聞けなかったが、William Cook の話では TSP の話だった。TSP は有名な問題であるが、厳密解を求める理論的なオーダーは半世紀も改善されていない、という点が驚きであった。

今日の最後が Lovasz の話であり、graphon の話であった。graphon はグラフの隣接行列を拡張したようなものであって、グラフの隣接行列であれば各要素は 0 or 1 であるが、graphon の場合には 0 から 1 の値が取れるように拡張されている。
この graphon の説明や、その性質、それから導かれる内容などが話であった。

そのあとの懇親会でも Lovasz は色々な研究者と話をしていたが、タイミング的に暇になっているところがあったで「このタイミングはラッキーなのでは?」と思い、話しかけてみたところ、少しだけ話をすることができた。

どうやら、graphon の勉強を始めたのは 5,6 年前ぐらいで、行列の収束などに興味を持ったのが研究のスタート地点だったようである。
ワークショップの話では数学的な側面に話が集中していたが、このような収束はインターネットなどのネットワークの研究に役立つ、といった応用がある、とのことであった。
graphon について知りたいのであれば、
"Very Large Graph" http://arxiv.org/abs/0902.0132
がサーベイを兼ねていて取っ付きやすいかもしれない、とのことであった。
(注:英語で話している関係で、一部に間違いを含む可能性あり)


graphon は SDP と直接関係があるかどうかはわからないが、Lovasz theta は SDP においても重要な問題のひとつなので、ひょっとしたら関係があるのかもしれない。


今日の作業内容: Lovasz Workshop
今日のランチ:弁当 チキンガーリック
今日の夕飯:ワークショップ懇親会

0 件のコメント:

コメントを投稿