モノトーンそしてmP≠mNP その5

おはようございます。昨日神社にお参りしたら、七五三さんのかわいらしいお嬢ちゃんがいたりと華やかでした。男の子は五歳の時一度、女の子とは三歳と七歳の二度、参拝するわけですが、幼い頃は理由が分らず、だだをこねた記憶があるような。もっとも、千歳飴がうらやましかったんですけどね。


さて、今日は、近似サーキットに関する補題を一つ説明します。テキストによると、エルデス(Erdös)とラドー(Rado)によるものだそうです。

【ErdösとRadoによる補題】
　いまŹを集合の集合で、Źの元となる集合の濃度(単位集合あたりの元の数)は高々lとします。

　　|Ź|>(p-1)^l・l!   　　　　　　　　　 (1)

ならば、その中にはp個の花びらによるヒマワリが存在する

【証明】
　数学的帰納法によって証明します

(i)l=1の場合
　Źの元になる集合の濃度が1という意味ですので明らかにどんなｐ個の元集合を持ってきてもヒマワリになります。
　例えば　

(ii)l≧2の場合
　ḾをŹのなかの互いに素な集合の集合の中で極大なものとします。そのうえでS=∪Ḿと定義します

　
　　（例）l=8 とし、元である集合の元を10進整数で示すことにすると
　　　 Ź1={{1},{1,2},{2,3},{4,5,6},{7,8}}

　　　　の場合　その互いに素な元の集合は

　　　　{{1}},　{{1,2}},　{{2,3}},　{{4,5,6}},　{{7,8}},
　　　　{{1}},　{{2,3}},　{{1},{4,5,6}},　{{1},{7,8}},
　　　　{{1,2},{4,5,6}},　{{1,2},{7,8}}
　　　　{{2,3},{4,5,6}},　{{{2,3},{7,8}},　
　　　　{{4,5,6},{7,8}}
　　　　{{1},{2,3},{4,5,6}},
　　　　{{1},{2,3},{7,8}},
　　　　{{1},{4,5,6},{7,8}},
　　　　{{1,2},{4,5,6},{7,8}},
　　　　{{2,3},{4,5,6},{7,8}},
　　　　{{1},{2,3},{4,5,6},{7,8}}

     　の19通り

　　　　大きい方から3つ選びこれをSとすると
　　　　　S1={{{1},{2,3},{4,5,6},{7,8}},　{{1},{4,5,6},{7,8}},
         　　{{1,2},{4,5,6},{7,8}}}



　さて、いま|S|≧pならば、Ḿ同士がひまわりでそこで花つみをすれば良いということになります。


　　（例）上の例でp=2 とする　|S1|=3 だから、

　　　　　S1={{{1},{2,3},{4,5,6},{7,8}},　{{1},{4,5,6},{7,8}},
         　　{{1,2},{4,5,6},{7,8}},{{2,3},{4,5,6},{7,8}}}

  　　　の、どの元を二つとっても元同士がひまわりになり、
　　　　そこで花つみをすればŹ1の花つみにもなっている


次に　|S|<pの時を考えます。このとき次のことが成立します

　　|S|≦(p-1)l　　　　　　　　　(2)

上の式はとりあえずはいまは意味がないのですが、lは正の整数ですので|S|<pから導き出せる当然の式です。

また、Ḿに属する集合が互いに素である事と、Mが極大であることから、次のことが言えます

　　Z∈Ź　→　S∩Z≠φ

いまi∈Sなるiについて、iがどれだけのŹの元（げん）Zの元（げん）になっているかを考えると、(2)式よりあるi∈Sで少なくどもŹの1/{(p-1)l}部分のZの元になっていますので、この元iを固定して、Ź'を

　　Ź'={Z-{i}|i∈ZでZ∈Ź}

と定義すれば、仮定(1)式を用いて次の式が出てきます。

　　|Ź'|=|Z|/{(p-1)l}＞(p-1)^(l-1)・(l-1)!

lについての数学的帰納法の仮定よりŹ濃度l-1においてp個のひまわりを持っています。

以上(i)と(ii）によって数学的帰納法によりŹはp個のひまわりを持っていることが証明されました。


この補題の証明はは数学的帰納法を用いるということと(i)がポイントとなっていますね。


さて、次回は、近似サーキットの定義を完成させます。少々難しいですがどうかついてきて下さるとうれしく存じます。