The Speed and Threshold of the Biased Hamilton Cycle Game
| Autor: | Brustle, Noah, Clusiau, Sarah, Narayan, Vishnu V., Ndiaye, Ndiamé, Reed, Bruce, Seamone, Ben |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We show that there is a constant C such that for any $b<\frac{n}{\ln{n}}-\frac{Cn}{(\ln{n})^{3/2}}$, Maker wins the Maker-Breaker Hamilton cycle game in $n+\frac{Cn}{\sqrt{\ln{n}}}$ steps. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|