$ 2 ^ n $頂点を持つトーナメントを考えると、少なくとも$ N + 1 $頂点を持つサブトーナメントがあることを示します。

Question

それでトーナメントはただ完全な指示されたグラフです、私は信じています。

この問題を証明するのに問題があります。しかし私はそれが誘導であることを知っています。私が考えていた ベースケースは $ 2 ^ 1 $ 頂点であり、したがって、1 + 1頂点のサブトーナメントを持っています。

その後、誘導ステップでは、 $ 2 ^ {n + 1} $ を表示する必要があります。しかし、私はこれに近づく方法はわかりません。どんなアイデアも非常に高く評価されます。

Answer 1

トーナメントはループフリーの指向グラフ $ g=（v、e）$ です。 $ u、v x $ 、 $（u、v）$ と $（v、u）$ は $ e $ です。

あなたの主張の証明は誘導によるものです。

$ n= 0 $ の場合は、 class="math-container"> $ 2 ^ 0= 1 $ 頂点は自然に非環境であり、 $ 0 + 1= 1 $ でのみその唯一のサブトーナメントです。頂点は $ g $ それ自体です。

クレームは、いくつかの $ n \ ge 0 $ までのものであり、トーナメント $ g=（ v、e）$ $ | v |= 2 ^ {n + 1} $ 。任意の頂点 v $ を選択し、 $ v \ setminus \ {v \} $の頂点を分割します。 2セットに $ l={v \ setminus \ {v \} \ mid（u、v）\} $ $ r={v \ setminus \ {v \} \ mid（v、u）\ in} $ 。 $ l $ 、 $ r $ のいずれかには、少なくとも $ \ left \ lceil \ frac {| v \ setminus \ {v \} |} {2} \ right \ rceil=left \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ right \ RCEIL= 2 ^ n $ 頂点。このセットから $ 2 ^ n $ 頂点を選択し、選択した頂点のセットを呼び出します。 $ s $ 。 誘導的仮説によって $ S $ のサイズの非巡回サブトーナメント="$ s' $ が含まれています。 "Math-Container"> $ n + 1 $ 、および $ s '\ subseteq s \ subseteq l $ または $ s '\ subeteq s \ subseteq r $ 、 $ s' \ cup \ {v \} $ も非公式です。 。これは $ | s '\ cup \ {v \}= | S '| + 1= n + 2 $ 。