The asymptotic unlabeled compression conjecture for powers of C5C_5

About 8 years old · traced to

Let C5C_5 be the family defined earlier in the source, let F∗n\mathcal F^{*n} denote its nn-fold join, and let UCS(F)\mathrm{UCS}(\mathcal F) be the minimum size of an unlabeled compression scheme for F\mathcal F. The C5C_5 asymptotic conjecture.

lim⁡n→∞UCS(C5∗n)n\lim_{n\to\infty}\frac{\mathrm{UCS}(C_5^{*n})}{n}

exists and is strictly larger than 22. The question concerns the asymptotic gap between VC-dimension and unlabeled compression size for joins; the source does not establish either the existence of the limit or the strict inequality.

References

Primary source

Dömötör Pálvölgyi and Gábor Tardos, “Unlabeled Compression Schemes Exceeding the VC-dimension”, arXiv:1811.12471 (2021).

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.