Dato un torneo con $ 2 ^ N $ $ vertici, mostra che c'è un sub-torneo con almeno $ N + 1 $ $ vertici che è aciclica

Question

Quindi un torneo è solo un grafico diretto completo, credo.

Sto avendo problemi a dimostrare questo problema.So che è comunque l'induzione.stavo pensando Il caso base è $ 2 ^ 1 $ vertici, e quindi abbiamo un sub-torneo di 1 + 1 vertici, che detiene.

Poi nel nostro punto di riferimento induzione dobbiamo mostrare $ 2 ^ {n + 1} $ .Ma non sono sicuro di come affrontare questo.Qualsiasi idea sarebbe estremamente apprezzata.

Answer 1

Un torneo è un grafico diretto senza anello $ g= (v, e) $ in cui, per ogni coppia di vertici distinti $ u, v \ in V $ , esattamente una di $ (u, v) $ e $ (v, u) $ è in $ e $ .

La prova del tuo reclamo è per induzione.

per $ n= 0 $ Il reclamo è vero da un torneo $ G $ con $ 2 ^ 0= 1 $ I vertici sono banale acyclic e il suo unico sub-torneo con $ 0 + 1= 1 $ I vertici sono $ G $ stessa.

Assumere ora che il reclamo regge a un po 'di class class="container di matematica"> $ n \ Ge 0 $ e considera un torneo $ g= ( V, e) $ con $ | v |= 2 ^ {n + 1} $ . Scegli un vertice arbitrario $ v \ in V $ e partizione i vertici di $ v \ setminus \ {v \} $ in due set $ l={u \ in v \ setminus \ {v \ \} \ metà (u, v) \ in e \} $ e $ r={u \ in v \ setminus \ {v \ \} \ metà (v, u) \ in e \} $ . Uno dei $ l $ e $ R $ deve contenere almeno $ \ sinistra \ lceil \ frac {| v \ setminus \ {v \ \ \}} {2} \ destra \ rceil=sinistra \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ destra \ rceil= 2 ^ n $ vertici. Selezionare arbitrariamente $ 2 ^ N $ Vertici da questo set e chiama il set dei vertici selezionati $ S $ . Per ipotesi induttiva $ s $ contiene un sub-torneo acyclico $ s '$ di dimensioni $ N + 1 $ , e dal momento che $ s '\ SOTETETQ S \ SOTETEQ L $ o $ s '\ SOTETETQ S \ SOCSETETQ R $ , abbiamo quella $ s' \ Cup \ {v \ \} $ è anche aciclica . Questo dimostra il reclamo poiché $ | s '\ cup \ {v \} |= | S '| + 1= n + 2 $ .