  Subgraph and homomorphism counting are fundamental algorithmic problems.
Given a constant-sized pattern graph $H$ and a large input graph $G$, we wish
to count the number of $H$-homomorphisms/subgraphs in $G$. Given the massive
sizes of real-world graphs and the practical importance of counting problems,
we focus on when (near) linear time algorithms are possible. The seminal work
of Chiba-Nishizeki (SICOMP 1985) shows that for bounded degeneracy graphs $G$,
clique and $4$-cycle counting can be done linear time. Recent works (Bera et
al, SODA 2021, JACM 2022) show a dichotomy theorem characterizing the patterns
$H$ for which $H$-homomorphism counting is possible in linear time, for bounded
degeneracy inputs $G$. At the other end, Ne\v{s}et\v{r}il and Ossona de Mendez
used their deep theory of "sparsity" to define bounded expansion graphs. They
prove that, for all $H$, $H$-homomorphism counting can be done in linear time
for bounded expansion inputs. What lies between? For a specific $H$, can we
characterize input classes where $H$-homomorphism counting is possible in
linear time?
  We discover a hierarchy of dichotomy theorems that precisely answer the above
questions. We show the existence of an infinite sequence of graph classes
$\mathcal{G}_0$ $\supseteq$ $\mathcal{G}_1$ $\supseteq$ ... $\supseteq$
$\mathcal{G}_\infty$ where $\mathcal{G}_0$ is the class of bounded degeneracy
graphs, and $\mathcal{G}_\infty$ is the class of bounded expansion graphs. Fix
any constant sized pattern graph $H$. Let $LICL(H)$ denote the length of the
longest induced cycle in $H$. We prove the following. If $LICL(H) < 3(r+2)$,
then $H$-homomorphisms can be counted in linear time for inputs in
$\mathcal{G}_r$. If $LICL(H) \geq 3(r+2)$, then $H$-homomorphism counting on
inputs from $\mathcal{G}_r$ takes $\Omega(m^{1+\gamma})$ time. We prove similar
dichotomy theorems for subgraph counting.
