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

About 9 years old · traced to

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

∣S∣≥n2(log⁡log⁡n)c1,|S|\geq\frac{n^2}{(\log\log n)^{c_1}},

then

∣Sˉ∣≥n3(log⁡log⁡n)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.

References

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.