Cube-cover conjecture for diagonalization games

About 3 years old · traced to

Let nn and mm satisfy 2n−1+1≤m<2n2^{n-1}+1\leq m<2^n, and set

d=2n−m<2n−1.d=2^n-m<2^{n-1}.

For a nonempty subset J⊆[n]J\subseteq[n], a JJ-cube is the set of binary vectors obtained by fixing all coordinates outside JJ and allowing the coordinates in JJ to vary. Cube-cover conjecture. For any collection J1,J2,…,JqJ_1,J_2,\ldots,J_q of nonempty subsets of [n][n] satisfying

∑i=1q∣Ji∣=d,\sum_{i=1}^q |J_i|=d,

there are cubes C1,…,CqC_1,\ldots,C_q such that CiC_i is a JiJ_i-cube and

∣⋃i=1qCi∣≥d+q.\left|\bigcup_{i=1}^{q} C_i\right|\geq d+q.

This condition is equivalent to Kronecker having a winning strategy when Cantor uses mn−(2n−m)mn-(2^n-m) queries. The statement concerns covering the Boolean cube under prescribed coordinate freedoms and would establish optimality of the proposed strategy; its resolution is not given in the supplied text.

References

Primary source

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran and Shlomo Moran, “Diagonalization Games”, arXiv:2301.01924 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.