Dado um torneio com $ 2 ^ n $ vértices, mostre que há um sub-torneio com pelo menos $ n + 1 $ vértices que é acíclico

Question

Portanto, um torneio é apenas um gráfico completo dirigido, eu acredito.

Estou tendo problemas para provar esse problema.Eu sei que é indução no entanto.eu estava pensando O caso da base é $ 2 ^ 1 $ vértices e, portanto, temos um sub-torneio de 1 + 1 vértices, que detém.

Então, em nosso passo de indução, temos que mostrar $ 2 ^ {N + 1} $ .Mas não tenho certeza de como abordar isso.Alguma ideia seria extremamente apreciada.

Answer 1

Um torneio é um gráfico dirigido sem loop $ g= (v, e) $ em que, para cada par de vértices distintos $ u, v \ in v $ , exatamente uma das $ (u, v) $ e $ (v, u) $ está em $ e $ .

A prova de sua reivindicação é por indução.

para $ n= 0 $ A reivindicação é verdadeira desde um torneio $ g $ com $ 2 ^ 0= 1 $ vértices é trivialmente acíclico, e seu único sub-torneio com $ 0 + 1= 1 $ Vértices é $ g $ em si.

Suponha agora que a reivindicação mantém até algumas $ n \ GE 0 $ e considere um torneio $ g= ( V, e) $ com $ | v |= 2 ^ {n + 1} $ . Escolha uma vértice arbitrária $ v \ in v $ e particionar os vértices de $ v \ setminus \ {v \} $ em dois conjuntos $ l= {u \ in v \ setminus {v \} \ mid (u, v) \ in e \} $ e $ r= {u \ in v \ setminus {v \} \ mid (v, u) \ in e \} $ . Um dos $ l $ e $ R $ deve conter pelo menos $ \ left \ lceil \ frac {| v \ setminus {v \} |} {2} \ rceil=left \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ direito \ rceil= 2 ^ n $ vértices. Selecione arbitrariamente $ 2 ^ n $ vértices deste conjunto e ligue para o conjunto dos vértices selecionados $ S $ . Por hipótese indutiva $ S $ contém um subzaminamente acíclico $ s '$ de tamanho $ n + 1 $ , e desde as $ s '\ subseteq s \ subseteq l $ ou $ s '\ subseteq s \ subseteq r $ , temos que $ s' \ copo \ {v \} $ também é acíclico . Isto prova a reivindicação desde a $ | s '\ copo \ {v \} | |= | S '| + 1= n + 2 $ .