  The method of hypergraph containers, introduced recently by Balogh, Morris,
and Samotij, and independently by Saxton and Thomason, has proved to be an
extremely useful tool in the study of various monotone graph properties. In
particular, a fairly straightforward application of this technique allows one
to locate, for each non-bipartite graph $H$, the threshold at which the
distribution of edges in a typical $H$-free graph with a given number of edges
undergoes a transition from 'random-like' to 'structured'. On the other hand,
for non-monotone hereditary graph properties the standard version of this
method does not allow one to establish even the existence of such a threshold.
  In this paper we introduce a refinement of the container method that takes
into account the asymmetry between edges and non-edges in a sparse member of a
hereditary graph property. As an application, we determine the approximate
structure of a typical graph with $n$ vertices, $m$ edges, and no induced copy
of the $4$-cycle, for each function $m = m(n)$ satisfying $n^{4/3} (\log n)^4
\leqslant m \ll n^2$. We show that almost all such graphs $G$ have the
following property: the vertex set of $G$ can be partitioned into an
'almost-independent' set (a set with $o(m)$ edges) and an 'almost-clique' (a
set inducing a subgraph with density $1-o(1)$). The lower bound on $m$ is
optimal up to a polylogarithmic factor, as standard arguments show that if $n
\ll m \ll n^{4/3}$, then almost all such graphs are 'random-like'. As a further
consequence, we deduce that the random graph $G(n,p)$ conditioned to contain no
induced $4$-cycles undergoes phase transitions at $p = n^{-2/3 + o(1)}$ and $p
= n^{-1/3 + o(1)}$.
