Implicit representation for sub-polynomial speed hereditary families
Question (Section 3, implicit representation for speed $2^{n^{1+\varepsilon}}$) · arXiv:2201.00328
Status open high confidence
No follow-up work resolving this question was found. The source paper (published in Discrete & Computational Geometry, 2024) establishes only the weaker bound O(n^{1-1/d} log n) under the hypothesis f(n) \leq 2^{(1/4-\varepsilon)n^2}; the specific question of whether the intermediate speed regime f(n) < 2^{n^{1+\varepsilon}} forces a label size of O(n^{2/3} log n) appears unresolved in the indexed literature as of May 2026. A 2025 paper on implicit representations via the polynomial method (arXiv:2602.10922) addresses semialgebraic families but does not treat this speed regime or the n^{2/3} exponent.
Reviewer notes. No follow-up found that addresses this specific question. The paper arXiv:2602.10922 ('Implicit representations via the polynomial method', 2025) is thematically related but focuses on semialgebraic graphs and cites only Alon's main theorem (O(n^{1-1/d} log n)), not this open question. The source paper was published as Discrete Comput. Geom. (2024); the question about the n^{2/3} exponent for the intermediate speed range f(n) < 2^{n^{1+\varepsilon}} remains open with high confidence.
Context
This is posed as a follow-up to the $O(n^{1/2}\log n)$ question for the slower-speed regime. Theorem 1.1 guarantees only $O(n^{1-1/d}\log n)$ under the weaker bound $f(n) \leq 2^{(1/4-\varepsilon)n^2}$, and the question asks whether the intermediate speed range $f(n) < 2^{n^{1+\varepsilon}}$ forces a sub-polynomial improvement to $n^{2/3}$.
Notes. Posed as an explicit question in Section 3 but without a labelled theorem environment; PDF source.
Source paper
Implicit representation of sparse hereditary families
Noga Alon · 2022-01-02
https://arxiv.org/abs/2201.00328
PDF source