2010-04-21

Klaus Dohmen http://arxiv.org/abs/1004.3416 Chordalグラフのクリークの族に対して，Bonferroniの不等式のようなものが成り立つ，ということを言っている．いわゆる包除原理は球体 (ball) のcontractibilityと同じことをいってるようなものなので，chordalグラフのクリーク複体がcontractibleであるということを知っていれば (これは私が関連する論文を書いたEdelman-Reiner ('00) の結果である)，この論文の結果はさほど驚きではない，と思う． Russell Impagliazzo, Valentine Kabanets http://eccc.hpi-web.de/report/2010/072/ さて，離散数学における確率論的手法の分野において「constructive proof」が最近注

[wanpac]

何か面白そうだけど、読む暇あるのか・・・？