Lubell%E2%80%93Yamamoto%E2%80%93Meshalkin_inequality
組み合わせ 数学では、Lubell-Yamamoto-Meshalkin 不等式、より一般的には LYM 不等式 として知られているが、Bollobás (1965)、Lubell (1966)、Meshalkin (1963)によって証明された、 Sperner ファミリのセットのサイズに関する不等式です。と山本 (1954)。3人の発見者のイニシャルにちなんで名付けられました。4 人の発見者全員のイニシャルを含めるために、 YBLM 不等式と呼ばれることも
この不等式は集合の組み合わせ論の分野に属し、組み合わせ論で多くの用途が特に、 Sperner の定理の証明に使用できます。その名前は、同様の不等式にも使用されます。
定理のステートメント
Uをn要素集合とし、AをUのサブセットのファミリとし、 A内のセットがA内の別のセットのサブセットとならないようにし、a kがA内のサイズkのセットの数を表すようにします。それで ∑ k= 0 n a k n k )
≤ 1. { sum _{k=0}^{n}{frac {a_{k}}{n choose k}}leq 1.}
ルベルの証明
Lubell (1966)は、 Uの順列を2 つの異なる方法でカウントする二重カウントの議論によって、Lubell–Yamamoto–Meshalkin の不等式を証明しています。まず、 {1， …， n } で識別されるUのすべての順列を直接数えることによって、 nがあることがわかります。そのうちの。しかし 2 番目に、Aの集合Sを選択し、{1， … ， | さ| } にS。|場合 | さ| = kの場合、集合Sはこのようにk !( n − k )!に関連付けられます。順列、およびそれらのそれぞれで、Uの最初のk 個の要素のイメージは正確にSです。各順列は、 Aの単一のセットにのみ関連付けることができます。これは、順列の 2 つのプレフィックスが両方ともA のセットを形成した場合、一方が他方のサブセットになるためです。したがって、この手順で生成できる順列の数は ∑ Sε あ
| | S | | ! ( n − | | S | |)! = ∑
k= 0 n a k k !( n− k ) ! .
{ sum _{Sin A}|S|!(n-|S|)!=sum _{k=0}^{n}a_{k}k!(nk)!.}
この数はせいぜいすべての順列の合計数なので、 ∑ k= 0 n a k k !( n− k ) ! ≤ n ! .
{ sum _{k=0}^{n}a_{k}k!(nk)!leq n!.}
最後に、上記の不等式をnで割ります! 結果につながります。
参考文献
Bollobás， B. (1965)， “”On generalized graphs””， Acta Mathematica Academiae Scientiarum Hungaricae ， 16 (3–4): 447–452， doi : 10.1007/BF01904851 ， MR 0183653 ， S2CID 122892253.
Lubell， D. (1966)， “”Sperner’s lemma の短い証明””， Journal of Combinatorial Theory ， 1 (2): 299， doi : 10.1016/S0021-9800(66)80035-2 ， MR 0194348.
Meshalkin、LD (1963)、「有限集合の部分集合の数に関する Sperner の定理の一般化」、確率論とその応用、8 (2): 203–204、doi : 10.1137/1108023、MR 0150049.
山本浩一 (1954)， “”自由分配格子の対数次数”，日本数学会誌， 6 (3–4): 343–353， doi : 10.2969/jmsj/00630343 ， MR 0067086.”