Waiter-client clique-factor game (Q2092418)

Fix two integers \(n\) and \(k\) with \(n\) being divisible by \(k\), and consider the following game played by two players, Waiter and Client, on the edges of \(K_n\). Starting with all the edges marked as unclaimed, in each round, Waiter picks two yet unclaimed edges. Client then chooses one of these edges to be added to Client's graph, while the other edge is added to Waiter's graph. Waiter wins if she eventually forces Client to create a \(K_k\)-factor in Client's graph. If she does not manage to do that, Client wins. An important question that can be asked is how long the game will last if Waiter aims to win as fast as she can, Client tries to delay her as much as he can, and they both play optimally? In this paper, the author obtains the first non-trivial lower bound on this optimal number of rounds for large \(k\). The proofs are well-written and easy to follow.