Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erd o s and R 'enyi, and the family of @math -free graphs, that is, graphs which do not contain a subgraph isomorphic to a given (usually small) graph @math . A widely studied problem that lies at the interface of these two areas is that of determining how the structure of a typical @math -free graph with @math vertices and @math edges changes as @math grows from @math to @math . In this paper, we resolve this problem in the case when @math is a clique, extending a classical result of Kolaitis, Pr "omel, and Rothschild. In particular, we prove that for every @math , there is an explicit constant @math such that, letting @math , the following holds for every positive constant @math . If @math , then almost all @math -free @math -vertex graphs with @math edges are @math -partite, whereas if @math , then almost all of them are not @math -partite.
Let us remark here that a statement that is even stronger than Conjecture was proved by Osthus, Pr "o mel, and Taraz @cite_3 in the case when @math is a cycle of odd length. More precisely, the following was shown in @cite_3 . Let @math be an integer, let @math be an arbitrary positive constant, and let [ t_ = t_ (n) = ( -1 ( n 2 )^ n )^ 1 -1 . ] If @math , then almost all graphs in @math are not bipartite and if @math , then almost all of them are bipartite.
@cite_3
2023104754
Denote by @math the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix e > 0 and let @math . If n 2 ≤ m ≤ (1 − e) t3, then almost all graphs in @math are not bipartite, whereas if m ≥ (1 + e)t3, then almost all of them are bipartite. For m ≥ (1 + e)t3, this allows us to determine asymptotically the number of graphs in @math . We also obtain corresponding results for Cl-free graphs, for any cycle Cl of fixed odd length.