|
Session 27. Probabilistic and Extremal Combinatorics
|
Waiter-Client \(H\)-games |
Małgorzata Bednarska-Bzdęga, Adam Mickiewicz University, Poznań, Poland
|
The talk is based on the joint work with Dan Hefetz and Tomasz Łuczak
|
|
|
Let \(H\) be a fixed graph and \(n,q\) be positive integers. In the
Waiter-Client \(H\)-game (known in the literature as a Picker-Chooser
game) in each round Waiter selects exactly \(q+1\) free edges of the
complete graph \(K_n\) and offers them to Client. Then Client selects
one of them which he keeps and the remaining \(q\) elements are
claimed by Waiter. The game ends when there is no free edge left.
Waiter tries to force as many Client's copies of \(H\) in \(K_n\) as
possible, while the aim of Client is opposite. We will talk on some
relations between the value of the game and the expected number of
copies of \(H\) in the random graph \(G(n,1/(q+1))\).
|
|
| Print version |
|
