\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}

\begin{document}
\noindent
%
%
{\bf Vadim V. Lozin, Colin Mayhill and Victor Zamaraev}
%
%

\medskip
\noindent
%
%
{\bf A Note on the Speed of Hereditary Graph Properties}
%
%

\vskip 5mm
\noindent
%
%
%
%
For a graph property $X$, let $X_n$ be the number of graphs with vertex set $\{1,\ldots,n\}$ 
having property $X$, also known as the speed of $X$. A property $X$ is called factorial if $X$ is 
hereditary (i.e. closed under taking induced subgraphs) and $n^{c_1n}\le X_n\le n^{c_2n}$ for some 
positive constants $c_1$ and $c_2$. Hereditary properties with the speed slower than factorial are 
surprisingly well structured.
The situation with factorial properties is more complicated and less explored, although 
this family includes many properties of theoretical or practical importance,
such as planar graphs or graphs of bounded vertex degree.
To simplify the study of factorial properties, we propose the following conjecture:
the speed of a hereditary property $X$ is factorial if and only if the fastest of 
the following three properties is factorial: bipartite graphs in $X$, co-bipartite graphs 
in $X$ and split graphs in $X$. In this note, we verify the conjecture for hereditary properties defined 
by forbidden induced subgraphs with at most 4 vertices.  

\end{document}

.
