Closure-size conjecture for three-dimensional line-sparse sets

Let [n]={1,,n}[n]=\{1,\ldots,n\}, and let S[n]3S\subseteq[n]^3 be a set that meets every line at most once. Write Sˉ\bar{S} for the closure of SS under the closure operation considered in the paper.

Closure-size conjecture. There are constants c1,c2>0c_1,c_2>0 such that, if

Sn2(loglogn)c1,|S|\geq\frac{n^2}{(\log\log n)^{c_1}},

then

Sˉn3(loglogn)c2.|\bar{S}|\geq\frac{n^3}{(\log\log n)^{c_2}}.

Non-trivial lower bounds on the closure size would improve the lower bounds on χ3(n,n){\chi}_3(n,n); the surrounding discussion indicates that this remains open, with only weak bounds known for higher dimensions.

Sources & referencesView supporting material

Primary source

Nati Linial, and Toniann Pitassi and Adi Shraibman, “On The Communication Complexity of High-Dimensional Permutations”, arXiv:1706.02207 (2018).

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.