The asymptotic unlabeled compression conjecture for powers of C5C_5

Let C5C_5 be the family defined earlier in the source, let Fn\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.

limnUCS(C5n)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.

Sources & referencesView supporting material

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.