Учитывая турнир с $ 2 ^ n $ вершинами, показать, что есть суб-турнир с не менее $ n + 1 $ вершинами, который является ациклическим

Question

Так что турнир - это просто полный направленный график, я полагаю.

У меня проблемы с доказыванием этой проблемы.Я знаю, что это это индукция, однако.я подумал Базовый случай - вершины $ 2 ^ 1 $ вершины, и поэтому у нас есть субъект 1 + 1 вершин, который удерживает.

Тогда на нашем шаге индукции мы должны показать $ 2 ^ {N + 1} $ .Но я не уверен, как пойти по этому поводу.Любые идеи были бы крайне оценены.

Answer 1

Турнир - это бесплатный циклический график $ G= (V, E) $ , в котором для каждой пары отчетных вершин $ u, v \ in v $ , именно один из $ (u, v) $ и $ (v, u) $ в $ e $ .

Доказательство вашей претензии по индукции.

Для $ n= 0 $ Претензия верна, поскольку турнир $ g $ с $ 2 ^ 0= 1 $ вершины тривиально Acyclic, а его единственный субъект с $ 0 + 1= 1 $ Вершины - $ g $ сам.

Предположим, что претензия удерживается до некоторого $ n \ Ge 0 $ и рассмотреть турнир $ G= ( V, e) $ с $ | v |= 2 ^ {n + 1} $ . Выберите произвольную вершину $ v \ in v $ и раздел вершины $ v \ setminus \ {v \} $ $ на два набора $ l={u \ in v \ setminus \ {v \} \ midminus \ {v \} \ mid (u, v) \ in \} $ и $ r={u \ in v \ setminus \ {v \} \ midminus \ {v \} \ mid (v, u) \ in \} $ . Один из $ l $ и $ R $ должен содержать, по крайней мере, $ \ Left \ lceil \ frac {| v \ setminus \ {v \} |} {2} \ Right \ RCEIL=Left \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ Rights \ RCEIL= 2 ^ n $ вершины. Произвольно выберите $ 2 ^ n $ вершины из этого набора, и вызовите набор выбранных вершин $ S $ Отказ По индуктивной гипотезе $ S $ содержит ациклический подзер-турнир $ S '$ размером $ n + 1 $ , и поскольку либо $ s '\ subsretq s \ subsEtq l $ или $ s '\ subsretq s \ subseTq r $ , у нас есть, что $ S' \ Cup \ {V \} $ также ациклическая Отказ Это доказывает претензию, поскольку $ | s '\ Cup \ {v \} |= | S '| + 1= n + 2 $ .