Random list threshold conjecture for Latin hypercubes

About 4 years old · traced to

For d∈Nd\in\mathbb N, a dd-dimensional order-nn Latin hypercube is a dd-dimensional array indexed by [n]d[n]^d with entries from [n][n], such that every line contains each symbol exactly once. For each x∈[n]d\mathbf{x}\in[n]^d, let Lx⊆[n]L_{\mathbf{x}}\subseteq[n] be chosen independently by including each symbol with probability pp. Latin-hypercube threshold conjecture. If p=ω(log⁡n/n)p=\omega(\log n/n), then with probability tending to one there exists a dd-dimensional order-nn Latin hypercube L\mathcal L satisfying Lx∈Lx\mathcal L_{\mathbf{x}}\in L_{\mathbf{x}} for every x∈[n]d\mathbf{x}\in[n]^d. The cases d=1d=1 and d=2d=2 connect this claim to perfect matchings and Latin squares, respectively, while the general case remains open in the source.

References

Primary source

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku and Deryk Osthus, “Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor”, arXiv:2206.14472 (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.