今日はPeter WidmayerのグループのMark Cieliebakのディフェンス (公聴会? 審査会?) があって、それを聞きにいった。
彼のテーマは計算生物学で、その中でもいろいろな問題の計算困難性を示した結果が多かった。
ディフェンスでの質問にもあったのだけれども、例えば、NP困難性を示す結果では最悪ケースの問題例を考えることになってしまうので、
生物学的な問題意識から組合せ的な部分を抽出したときに、一般的に成りすぎてしまうことがあったり、
そのような一般的な場合の最悪ケースが生物学の方から得られるものからかけはなれてしまうことがありそうになるので、
そのようなところは注意しなくてはならない点でもある。
しかし、そのような視点はアルゴリズムの分野から見ると割と工学的な視点である。
ここら辺はいわゆる「理論と実務の橋渡し」が必要な部分なのかもしれない。
先週ぐらいにインドのIIT Dehliのある学生からインターンをやりたいというメールが来ていて、
こういうメールははじめてなので、どうしたらよいかわからなくて、
今日指導教官に聞いてみた。
そうしたら、指導教官は毎日そういうのを3通ぐらいは受け取っているようなのである。
IIT Dehliの学生はどこか外国でインターンをやらなくてはならないらしく、
しかも大学自体は面倒を見ないようなのである。
それでそのようなメールが日々世界中を飛びまわっているらしい。
そのようなシステムでうまくいっているのかわからないけれども、うまくいっているとしたらすごいと思う。
ということで、指導教官からのアドバイスは「無視すればよい」と。
送る方は送る方でwebから適当にアドレスを引っ張ってきて、返事を期待せずに送っているのだから、と。
中にはよい学生もいるかもしれないけどねぇ、と。
もうそろそろEurocombについて何か書いておかないと申し訳ないような気もするので書きます。
Eurocombというのはヨーロッパの組合せ論の会議です。
組合せ論の会議はあまり出ないので、なかなか新鮮でよかったです。
なかでも、マトロイドのセッションがいくつかあってよかったです。
しかもマトロイドといっても組合せ最適化から見たマトロイドではなくて、もっと普通のマトロイドなのです。
これはなかなか刺激的でした。マトロイドの連結性とか忘れそうになっていたものも思い出せました。
他にも、グラフ、デザイン、極値集合論、組合せ数論、アルゴリズム、離散幾何、
多面体的組合せ論、半順序集合、ランダムネス、などなどテーマは盛り沢山で、
パラレルで聞きたいのが聞けなかったりして残念な思いをしたこともありました。
招待講演は毎日2件ずつあって、中でもBill CookとRobin ThomasはISMPのときと同じ話しを
同じスライドを用いてしていました。
特にRobin Thomasはstable marrigeの説明をするときに
「大事なことを言い忘れた..」とISMPのときと同じことを言い忘れていて、
何かすごくデ・ジャブを感じました。
あと、Joel SpencerはCOCOONのときと同じ話しをしていました。
2回目だったのでもう少しよく理解できるかと思いましたが、そうでもなかったです。
他に印象に残った招待講演はGerardsのマトロイドマイナーの話
(これはマトロイドとかグラフマイナーに興味が無い人にはちょっと早かったと思うけど自分にはよかった)、
KalaiのColored Topological Helly Theoremの話、
Luczakのphase transitionの話です。
とても勉強になった気がします。
一般講演は玉石混合といった感じでよいものはよかったけれどそうでないものはまぁそうでない、
といった感じでした。
アクセプト率はたしか40%ぐらいで、この手の組合せ論の会議にしては思い切って落しているなぁ、
という感じがしました。
そういう意味では、どうして自分のが通ったのかちょっとよく分かりませんが、まぁよいです。
場所は、プラハのチェコ農業大学という、
市街地からはちょっとはなれたところにある大学で行ないました。
そこには新しい建物があって、その講堂がちょうどよい感じの大きさでした。
プラハ自体もはじめてだったのですが、なかなかよい街です。
古い街並や建造物がよく保存されていて、去年の洪水の被害を思わせないほどでした。
ただ、あまりにも観光地っぽくなっていて、
カレル橋の上なんかはあまりにも出店が出過ぎていてちょっと興覚めしました。
excursionで街の図書館にある塔に登りました。
眺めがとてもよくて、ここでデジカメが壊れました。
その後、その図書館のところにある小さなチャペルで四重奏のコンサート (ドボルザークとヤナーチェク)
を聞きました。
そのときに、The European prize in Combinatoricsという賞の受賞者の発表がありました。
これは35歳以下のヨーロッパで研究している組合せ論の人で、最近良い仕事をした人に送られるようです。
Eurocombのときに受賞されるようで、今回が第1回だそうです。
で、第1回の受賞者はDeryk Osthus & Daniela Kühn (グラフ) と
Alain Plagne (組合せ数論) でした。
ということで、次回のEurocombは2年後の2005年にベルリンで行われるそうです。
よい論文を持って発表しにいきたいものです。
ちょっとLovaszの演習書の問題を解いてみました。
どういう問題かというと、
「0は1-factorを持たない二部グラフの隣接行列の固有値である」というものです。
かなり悩んでしまって、ヒントを見たときに1つ上の別のヒントを間違えて見てしまって、それで混乱して、
しかし、正しいヒントを見た瞬間に解けました。
なかなかよい問題だと思います。楽しみました。
かなり悩んでしまった理由は、はじめHallの定理を使おうと思っていたからです。
でもそれはうまくいかなくて困ってしまった、という感じでした。
そのために、LaTeXの上で今までに書いたところからの変更箇所がすぐに分かるようにするにはどうしたらいいか、と考えた。
自分に分かるだけではダメでDVIファイルとかPostscriptファイルにしたときに分からないといけない。
しかも、レイアウトは壊したくない。
このような要求を満たすようなスタイルファイルがないとかなり探してまわったけど見付からなかった。
ということで、あきらめようとおもったのだけども、ここで妙案を思い付いた。
ただ、色を変えればよかった。
色を変えるだけなら、色を変えないときとレイアウトは変わらない。
しかも前のバージョンからの変更箇所は一目瞭然。
ちなみに色を変えるためのスタイルファイルはcolorです。
多面体ファンの人にお知らせ。
9月のSAORで
八森さんがシェラビリティーについて話しをします。
この話題がなんでORなのかとかそういうことを話しだすと長くなるのでそれはしないことにして、
とにかく、多面体ファン、単体的複体ファンの人は必見です。
壊れたのはプラハにいる間でした。
リンツにいる頃からちょっとやばそうな感じもしていましたが、プラハでもうだめになってしまいました。
ちょうどexcursionが終わったときで、コンサート場のきれいな建物の写真も撮れませんでした。
なので、チェスケ・ブデヨビッチェとチェスキ・クルムロフの写真はその場でカメラ (film with lensなんですが日本語でなんていうんでしょうか) を買って、一応写真そのものを撮ることはできました。
ということで、この旅については徐々に書いていきます。
今日はISMPのときに宇野さんとちょっと議論した問題について考えてみたりしました。
どんどんダメな例が見付かっていってしまうので、なかなか2次元の場合でも特徴付けまでたどり付けないです。
今日は台集合の大きさが4のところまでは列挙したので、どんどんと大きくしていって、傾向を眺めたいと思います。
ということで、プラハを最終目的地として旅立ちます。
写真整理のためだけにコンピュータを持っていくというのはどういうことなんでしょう。
最近寒いのでちょっと荷物がコンパクトになるかどうか心配ですが。
失敗だったのは印刷する前にスペルチェックを行わなかったこと。
スペルチェックしたら2箇所ひっかかってしまったので、2枚印刷しなおしました。
OHPを使うのは久し振りなので、ちょっと練習もしました。
難しいのはフォイルの交換だと思います。
しかも今回はOHPを2台使えるようなので、それをどのように活用したらよいのかも考える必要があります。
とはいえ、実はビーマーも使用可能なのです。
しかも、自分のノートPC (これはヨーロッパでは「ラップトップ」と呼ばれる) を持っていく必要すらないんです。
でもそれなのに、なぜOHPを使うのか、というのが自然な質問だと思うので、ちょっと答えてみたいと思います。
まず1点目は、聴衆を考えたからです。
聴衆がコンピュータサイエンスの人だと、ビーマーを使う発表に慣れていると思います。
そういう人にとってはビーマーを使った発表の方がよいでしょう。
しかし今回の聴衆はもっと数学に近い方だと思われます。
数学だとビーマーはまだ主流ではない、という勝手な思い込みがあるので、
OHPの方が好感を持ってもらえるのではないか、というこれまた勝手な思い込みでそうしてみます。
本当にそうなのかどうかもちょっと試してみたいところなので。
2点目は、たまにOHPを使わないとOHPでの発表の仕方を忘れてしまうからたまにはやりたい、ということです。
実は、OHPを使う場合とビーマーを使う場合では、作るスライドが異なってきます。
例えば、色の使い方です。
OHPだと色があまり効果的になりにくい、という点があります。
赤をいわゆるRGBのff0000にしてしまってもほとんど強調されなかったりします。
私がff0000の代りに使っているのは、b22222 (firebrick) や dc143c (crimson) です。
あと、今日ちょっと練習するまで気付かなかったのは、
紺色 (00008b, darkblue) がほとんど黒 (000000, black) と識別不可能であるということです。
darkblueの部分は普通のblueで十分だったかもしれません。
あと、緑色 (00ff00, lime) で文字を書く人がいますが、これだと字自体が全く見えないです。
緑は図の中のベタ塗りなどや線などで用いる以外に用いてはいけないでしょう。
緑っぽい字を書きたいときは、008b8b (darkcyan) などを用いればよいと思います。
試していないけれども、2e8b57 (seagreen) もよいかもしれません。
ということが今回OHPを使ってみたい理由になっています。
ちょっと議論をした。
最近の役割はほとんど反例づくりになってる。
例を通して考える、というのは柏原さんから学んだ気がする。
柏原さんと議論しているときはたくさん例が出てくる。
そして、例をたくさん見ていく中でいろいろな事がだんだんと分かってくる。
組合せ論はそういうものなのだと思う。
まだ自分自身は例を作る力が強くない気がするので、
ここら辺りはもう少し鍛えていかないといけない点だと思う。
やっぱりちょっと疲れてるかもしれない。
7月と8月に旅をしすぎだったのかもしれない。
去年は夏に割と研究した気がするのだけども、今年はそうでもないので、その分を挽回しないといけないけども、
やっぱりちょっと疲れてるので、とりあえずはプラハとベルリンを無事に終えてから挽回については考えていきたい。
とりあえずプラハへの準備続行。
ちょっと最近気になるトポロジー的組合せ論について少々。
組合せ的な2つのもの (単体的複体とか半順序集合とか) がトポロジー的に同じであることを示す方法は
方法論としてあまりないのかもしれない。
よく出てくるのは、いわゆる「fiber定理」とか「nerve定理」を使うもので、
これだとホモトピー同値性がいえるので、なかなか嬉しい道具である。
もう1つの道具は離散モース関数を使ったもので、これはRobin Formanが導入して以来、いろいろなところで使われてきているようである。
こちらの場合はcollapsingによってホモトピー同値性を示すような感じになっている。
一方、代数的な視点から扱うものがあって、例えば、Stanley-Reisner環を考えるような方向である。
こちらの視点では、ホモトピー型よりもホモロジーの方が表に出てくるようである。
ホモロジーの方がトポロジーの分類としては緩いわけだけども、この視点では代数が使えるのでそこがよい点だと考えられている気がする。
この手法に含まれるものとして、代数的シフティングというのがあり、そこでは可換環を使うバージョンと外積代数を使うバージョンがある。
こう見てくると、用いられる手法自体はそれ程多くない気がする。
上の中でも離散モース理論と代数的シフティングは比較的新しい手法であるが、やはり基本的な方法論が不足しているような感じがする、というのが個人的な感想。
ちなみに、どうしてそういうことに個人的な興味がいくのかというと、
あるものを「組合せ的」に特徴付けるというのはなかなか難しくて、そうすると、
もう少し荒削りでよいから、そのものについて知りたい、という要求が出てくる。
トポロジーというのは、そのような「荒削り」な視点だと思っている。
なので、トポロジー的な視点をそのような位置付けで捉えるというのも1つの方向性なのかな、と思ったりする今日この頃。
以上、いつものようにとりとめなくなりました。