以前、simple polytopeはグラフから組合せ構造が復元できるというKalaiの結果を紹介しました。そこで登場したgeneric directonによる頂点の順位付けに関する話です。 定理 を-次元単純凸多面体とする。をgenericな一次関数とし、の頂点は、を満たすとする。…

次のような極値組合せ論のBollabas*1の結果を紹介します。 定理 をなる自然数とする。が以下を満たしているとする。 各について. 各について ならば、 このとき、が成り立つ。 ちなみに定理内の上界を等号で達成する例として、があります。 linear algebraic…

3週間くらい全然記事を書けていませんでした。というかアクセス解析をしてもアクセス0のこのブログを書き続ける理由などあるのでしょうか。だからこそ自由に書けるというメリットがあるのだみたいな論理で納得させています。長いものを紹介するのはハードル…

最近ようやく症状に気づいたのですが、以前は組合せ論周りで面白そうだと思うことがあまりにも多すぎて収集がつかなくなっていたようです。それも当然で、problem facingな分野であることは間違い無いですが、論文を書くまで至るにはある程度の流れを汲む必…

多面体の組合せ論にずっとうっすら興味を持っていたのですが、なかなか重い腰が上がらず何も進んでいませんでした。今週思い立ってある論文を読もうとしましたが、読み始めたのが平日でその日は読みきれず、日を跨いだらNotationを忘れてしまい、結局絶賛放…

できれば毎週末投稿をしたいと思っていましたが、今週は何か特別紹介したいことがないので、適当に思っていることを書きます。 僕は勉強する時に教科書っぽい本があまり読めません。その代わり、短めの話題を集めたようなものを好き勝手読んだりしています。…

かなりニッチな話題を紹介します． 定理(Smith) 無向グラフがある．次数が偶数の頂点はのみで，それ以外の頂点の次数は奇数である．このときを両端に持つハミルトンパスは偶数個である． 証明 から補助グラフを次のように作る． の頂点集合はを端点にもつハ…

はじめての投稿です。問題から始まる記事を書こうと思います。 問題 次元単体がの中に個ある．どの二つも内部を共有せず，境界も含めるとどの二つも次元の交わりを持つ．としてあり得る最大値はいくらか． の時を考える．つの三角形を条件を満たすように配置…