Linear neighborhood-complexity conjecture for hereditary small classes

For a graph $G$, let $\mathcal{N}_G=\{N_G(v):v\in V(G)\}$ be its family of open neighborhoods, and let $\pi_{\mathcal{N}_G}(m)$ denote the maximum number of traces of these neighborhoods on an $m$-vertex subset. The neighborhood complexity of a graph class is the corresponding maximum trace count over its graphs.

Linear neighborhood-complexity conjecture. Every hereditary small class of graphs has neighborhood complexity $O(n)$.

The paper proves only the bound $O(n\log n)$ for hereditary small classes. Since all examples known to the authors have linear neighborhood complexity, improving this bound to $O(n)$ is left as an open question.