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

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