  In this paper we explore maximal deviations of large random structures from
their typical behavior. We introduce a model for a high-dimensional random
graph process and ask analogous questions to those of Vapnik and Chervonenkis
for deviations of averages: how "rich" does the process have to be so that one
sees atypical behavior. In particular, we study a natural process of
Erd\H{o}s-R\'enyi random graphs indexed by unit vectors in $\mathbb{R}^d$. We
investigate the deviations of the process with respect to three fundamental
properties: clique number, chromatic number, and connectivity. In all cases we
establish upper and lower bounds for the minimal dimension $d$ that guarantees
the existence of "exceptional directions" in which the random graph behaves
atypically with respect to the property. For each of the three properties, four
theorems are established, to describe upper and lower bounds for the threshold
dimension in the subcritical and supercritical regimes.
