The Namer-Claimer game

Consider the following game played on the integers from $1$ to $n$ . In each round Namer names a forbidden distance $d$ , then Claimer claims a subset of $[n]$ that does not contain any two integers at distance $d$ . After finitely many rounds, Claimer will have claimed sets that cover the whole of $[n]$ , at which point the game ends. How many rounds will there be with best play?

I’ve run this question out at a number of workshops and open problems sessions, and haven’t yet heard back about a success. I’ll explain the known upper and lower bounds below the fold, but encourage you to spend a few minutes thinking about it before taking a look.

Upper bound

An upper bound on the length of the game is a strategy for Claimer. I’ll show that Claimer can claim half of the uncovered points in each round, so the length of the game is at most $\log_2 n$ .

Given a forbidden distance $d$ , we can form the restriction graph $G_d$ with vertex set $[n]$ and edges between each pair of integers at distance $d$ . This graph is a vertex-disjoint union of paths. In particular, it is bipartite, so we can fix a bipartition $(X,Y)$ of $[n]$ so that all edges cross between $X$ and $Y$ . Now $X$ and $Y$ are both legal choices for Claimer in this round, and at least one of them contains at least half of the uncovered points in $[n]$ .

Lower bound

A lower bound is a strategy for Namer. I’ll show that if Namer names the most common difference between the uncovered points of $[n]$ then the game will last at least $\log_2 \log n$ rounds.

Suppose at some stage there are $\alpha n$ points remaining. There are only $n-1$ possible distances between pairs of points in $[n]$ , so some distance occurs at least $(\alpha n)^2/n = \alpha^2 n$ times. Thinking about the restriction graph on the uncovered points, by naming the most common distance Namer can ensure that there are at least $\alpha^2n/3$ uncovered points in the next round (the worst case being that the restriction graph consists of paths of length $3$ ). Repeated squaring takes time $\log_2 \log n$ to reduce the density to $1/n$ (being deliberately vague about the base of the second logarithm).

The truth

I don’t have a good conjecture for the true value. Roughly speaking, the upper bound is correct if Namer can ensure that, at each stage, if there are $m$ points uncovered then some distance appears $\Omega(m)$ times. Conversely, the lower bound is correct if Claimer can ensure that each distance appears roughly equally often, for example by making the set of uncovered points look as random as possible. But building this sort of random structure seems hard when we have less than $\log \log n$ time to do it.

Hereditarily non-uniform sets have been mentioned to me in connection with this problem, but haven’t enabled me to make any headway.

Upper bound

Lower bound

The truth

Leave a Reply Cancel reply