Consider the following game played on the integers from to . \u00a0In each round Namer names a forbidden distance , then Claimer claims a subset of that does not contain any two integers at distance . \u00a0After finitely many rounds, Claimer will have claimed sets that cover the whole of , at which point the game ends. \u00a0How many rounds will there be with best play?<\/p>\n

I’ve run this question out at a number of workshops and open problems sessions, and haven’t yet heard back about a success. \u00a0I’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.<\/p>\n

<\/p>\n

Upper bound<\/h3>\n

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

Given a forbidden distance , we can form the restriction graph<\/em> with vertex set and edges between each pair of integers at distance . \u00a0This graph is a vertex-disjoint union of paths. \u00a0In particular, it is bipartite, so we can fix a bipartition of so that all edges cross between and . \u00a0Now and are both legal choices for Claimer in this round, and at least one of them\u00a0contains at least half of the uncovered points in\u00a0.<\/p>\n

Lower bound<\/h3>\n

A lower bound is a strategy for Namer. \u00a0I’ll show that if Namer names the most common difference between the uncovered points of then the game will last at least rounds.<\/p>\n

Suppose at some stage there are points remaining. \u00a0There are only possible distances between pairs of points in , so some distance occurs at least times. \u00a0Thinking about the restriction graph on the uncovered points, by naming the most common distance Namer can ensure that there are at least uncovered points in the next round (the worst case being that the restriction graph consists of paths of length ). \u00a0Repeated squaring takes time to reduce the density to (being deliberately vague about the base of the second logarithm).<\/p>\n

The truth<\/h3>\n

I don’t have a good conjecture for the true value. \u00a0Roughly speaking, the upper bound is correct if Namer can ensure that, at each stage, if there are points uncovered then some distance appears times. \u00a0Conversely, 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. \u00a0But building this sort of random structure seems hard when we have less than time to do it.<\/p>\n

Hereditarily non-uniform sets have been mentioned to me in connection with this problem, but haven’t enabled me to make any headway.<\/p>\n","protected":false},"excerpt":{"rendered":"

Consider the following game played on the integers from to . \u00a0In each round Namer names a forbidden distance , then Claimer claims a subset of that does not contain any two integers at distance . \u00a0After finitely many rounds, Claimer will have claimed sets that cover the whole of , at which point the … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[13,25],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/178"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=178"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/178\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}