Determining Factorial Speed Fast

Abstract

The speed of a graph class $\mathcal{G}$ measures how many labeled graphs on $n$ vertices one can find in $\mathcal{G}$. This graph class complexity function is explicitly provided on graphclasses.org. However, for many graph classes, their speed status is classified as \emph{unknown}. In this paper, w}\shortversion{W}e show that any graph class representable by a finite binary language has at most factorial speed, meaning that its speed function behaves like $2^{\hat{I}˜(n\log n)}$, and we use this criterion to classify many graph classes whose speed was previously unknown as factorial. As a consequence, inclusions between several graph classes can now be seen to be proper. We also prove that $k$-letter graphs have exponential speed, i.e., the speed function lies in $2^{\hat{I}˜(n)}$.