Limits of kernel operators and the spectral regularity lemma

Balazs Szegedy
http://arxiv.org/abs/1003.5588

論文がスタックにたまってきたので，ちょっと吐き出します．まだ溜まってますが．

これは，いわゆるSzemerediのregularity lemma (正則性補題) を解析の観点から見直して，そのスペクトル版を証明する，というもの．
こういうのがすらすら読めないと本当はいけないんだけど，そういうところにまで自分は達していない．

Are there any good digraph width measures?

Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar
http://arxiv.org/abs/1004.1485

グラフの木幅 (treewidth) の果たす役割はグラフ理論，グラフ・アルゴリズムの世界ではとても大きいが，その有向グラフ版をどうすればよいか，ということに対して，うまい一般化がまだできていないという現状がある．
この論文 (の結果の1つ) は，そのような一般化が持っていて欲しい性質を満たすときには，結局向きを無視したグラフの木幅と同等なものしか一般化として現れない，ということを示している．これは真の一般化がうまくできなそうだということを示す否定的な結果と捉えることができる．

Polynomial Time Algorithm for Graph Isomorphism Testing

Michael I. Trofimov
http://arxiv.org/abs/1004.1808

グラフ同型性問題を多項式時間で解くといっていて，にわかには信じられないのだけども，謝辞を見るとこの分野の大御所が名を連ねているので，読んでみる価値はあるかもしれない．私は読んでないけども．もしどなたかお読みになったら，ご意見をお聞かせ下さい．

Complexity Analysis of Balloon Drawing for Rooted Trees

Chun-Cheng Lin, Hsu-Chun Yen, Sheung-Hung Poon, Jia-Hao Fan
http://arxiv.org/abs/1004.2338

グラフ描画 (graph drawing) のこういう論文はなんか好きです．根付き木のballoon drawingについてはこの論文の中身を見て下さい．根を中心して，その子供を同心円上に配置する，というのを再帰的に繰り返したものです．そのときに，いろいろな評価基準 (目的関数) に対して最適なballoon drawingを得ることがどれくらい難しいかを考察してます．他にもいろんなことができそう．