For which densities are random triangle-free graphs almost surely bipartite? (Q1878594)

The authors settle a long standing problem of random graph theory. Let \({\mathcal T}(n,m)\) be the class of all triangle-free graphs on \(n\) vertices and \(m\) edges. It was known for a uniformly chosen \(T_{n,m} \in {\mathcal T}(n,m)\) that \(\text{Pr}(T_{n,m})\) goes to one if \(m=o(n)\) or \(m \geq c_1 n^{7/4}\log n\), and it goes to zero if \(c_2n \leq m c_3n^{3/2}\), see \textit{H. J. Prömel} and \textit{A. Steger} [J. Graph Theory 21, 137-151 (1996; Zbl 0856.05037)]. It was also known that there exists a constant \(C\) for each \(\delta >0\) so that almost all elements of \({\mathcal T}(n,m)\) can be made bipartite by deleting at most \(\delta m\) edges if \(m \geq Cn^{3/2}\), see \textit{T. Łuczak} [Random Struct. Algorithms 16, 260-276 (2000; Zbl 0947.05071)]. Main result of the paper is that \(\text{Pr}(T_{n,m})\) goes to zero if \(n/2 \leq m \leq (1-\varepsilon)t_3\), while it goes to one if \(m \geq (1+\varepsilon)t_3\), where \(t_3=(\sqrt{3}/4)n^{3/2}\sqrt{\log n}\), and \(\varepsilon >0\) arbitrary. There are some corresponding results on \(C_l\)-free random graphs (\(l\) is an odd natural number), too.