Dado un torneo con $ 2 ^ n $ vértices, muestre que hay un sub-torneo con al menos $ N + 1 $ vértices que son acíclicos

Question

Entonces, un torneo es solo un gráfico dirigido completo, creo.

Estoy teniendo problemas para demostrar este problema.Sé que es inducción sin embargo.yo estaba pensando El caso base es $ 2 ^ 1 $ vértices, y por lo tanto tenemos un sub-torneo de 1 + 1 vértices, que sostiene.

Luego, en nuestro paso de inducción, tenemos que mostrar $ 2 ^ {n + 1} $ .Pero no estoy seguro de cómo abordar esto.Cualquier idea sería extremadamente apreciada.

Answer 1

Un torneo es un gráfico dirigido por la bucle $ g= (v, e) $ en el que, para cada par de vértices distintos $ u, v \ in v $ , exactamente uno de $ (u, v) $ y $ (v, u) $ está en $ e $ .

La prueba de su reclamación es por inducción.

para $ n= 0 $ La reclamación es verdadera desde un torneo $ g $ con $ 2 ^ 0= 1 $ Los vértices son trivialmente acíclicos, y su único sub-torneo con $ 0 + 1= 1 $ Los vértices son $ G $ en sí.

Asumir ahora que la reclamación se mantiene hasta un lugar $ n \ ge 0 $ y considere un torneo $ g= ( V, e) $ con $ | v |= 2 ^ {n + 1} $ . Elija un vértice arbitrary $ v \ in v $ y particione los vértices de $ v \ setminus \ {v \} $ $ en dos sets $ l={u \ in v \ setminus \ {v \ \ \ \ \ {v \} \ mid (u, v) \ in e \} $ y $ r={u \ in v \ setminus \ {v \ \ \ \ mid (v, u) \ in e \} $ . Uno de $ l $ y $ r $ debe contener al menos $ \ izquierda \ lceil \ frac {| v \ setminus \ {v \} |} {2} \ derecha \ rceil=izquierda \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ derecha \ rceil= 2 ^ n $ vértices. Seleccione arbitrariamente $ 2 ^ n $ vértices de este conjunto, y llame al conjunto de los vértices seleccionados $ s $ . Por hipótesis inductiva $ s $ contiene un sub-torneo acíclico $ s '$ de tamaño $ n + 1 $ y, ya sea $ s '\ subesteq s \ subestesteq l $ o $ s '\ subestesteq s \ subsetaq r $ , tenemos que $ s' \ cuco \ {v \} $ es también acíclico . Esto demuestra la reclamación desde $ | s '\ Cup \ {v \} |= | S '| + 1= N + 2 $ .