数学セミナー9月号

数学セミナー 2009年 09月号 [雑誌]

「解けそうで解けない数学の問題」ということで，私の専門に関わりが深いものとして「イルミネーション問題」と「交差する集合族の問題」について記事が出ています．
特に，徳重先生の「交差する集合族の問題」には昔の榎本先生の授業の思い出から始まり，最後には (若干間違いがあるものの) 計算量理論との関わりも述べられていて，楽しいです．
その記事はいわゆる「極値集合論 (extremal set theory)」の問題を扱っているのですが，極値問題 (extremal problems) が組合せ論や離散数学の興味のほとんどの部分を占めているということはあまり知られていないように思います．
私が昔『理系への数学』に書いた記事は極値問題を強調したつもりです．
そして，アルゴリズム理論や計算量理論というのも極値問題を扱っているわけです．そういうことを意識してアルゴリズムを眺めるかそうでないかというのは，アルゴリズムを理解する上で大きな違いをもたらすので，気を付けなければなりません．