2020/12/08 by Noah Brüstle, Sarah Clusiau, Brustle, Noah +9
Computer Science · Economics, Econometrics and Finance · #05C57 #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2012.04289
openalex publication_date 2020/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that Maker wins the Maker-Breaker perfect matching game in (n)/(2)+o(n) turns when the bias is at least \fracnlogn-\fracf(n)n(logn)5/4, for any f going to infinity with n and n sufficiently large (in terms of f).