On the Evolution of Triangle-Free Graphs
The paper under review deals with the structure of \({\mathcal T}(n,m)\), the class of all triangle-free graphs on \(n\) labelled vertices which have \(m\) edges. An obvious subclass of \({\mathcal T}(n,m)\) is \({\mathcal S}(n,m)\), the class of all bipartite graphs on \(n\) (in total) labelled vertices with \(m\) edges. Whilst there clearly are triangle-free graphs which are not bipartite, there often do not seem to be very many. This raises the question: For which values of \(m=m(n)\) does \[ \lim_{n\rightarrow\infty}\frac{| {\mathcal S}(n,m)|}{| {\mathcal T}(n,m)|}=1? \] In alternative language: for which \(m(n)\) is it true that (letting \(T_{n,m}\) be a member of \({\mathcal T}(n,m)\) selected uniformly at random) \[ \lim_{n\rightarrow\infty}P(T_{n,m}\text{~is~bipartite})=1?\tag{*} \] A pretty precise answer to this question has been worked out over the years, based on work of (amongst others) the author, Prömel, Osthus and Taraz [see \textit{D. Osthus, H. J. Prömel} and \textit{A. Taraz}, Combinatorica 23, 105--150 (2003; Zbl 1047.05040)]. Cutting a long story short, the limiting probability in equation (*) is 1 if \(m=o(n)\), or if (for \(\varepsilon>0\)) \(m(n)\geq (1+\varepsilon)\tfrac{\sqrt{3}}{4}n^{3/2}\sqrt{\log_{2}(n)}\), but is zero if \(n/2\leq m(n)\leq (1-\varepsilon)\tfrac{\sqrt{3}}{4}n^{3/2}\sqrt{\log_{2}(n)}\). (Note there is still a slightly grey area for \(m(n)=cn\) with \(0<c<1/2\) constant.) By far the hardest part of this proof is the statement that the limiting probability is 1 if \(m(n)\geq (1+\varepsilon)\tfrac{\sqrt{3}}{4}n^{3/2}\sqrt{\log_{2}(n)}\). This relies on a result of \textit{T. Łuczak} [Random Struct. Algorithms 16, 260--276 (2000; Zbl 0947.05071)], showing that if \(m(n)\geq Cn^{3/2}\) then all triangle-free graphs are \` close\'\, to being bipartite in an appropriate sense. Łuczak's result in turn depends on a hard result -- a sparse form of the Szemerédi regularity lemma. In the paper under review, the author provides a much simplified proof of this step (not involving the regularity lemma), by showing directly that there is a constant \(C>0\) such that \[ m(n)\geq Cn^{3/2}\sqrt{\log_{2}(n)}\Rightarrow \lim_{n\rightarrow\infty}P(T_{n,m}\text{~is~bipartite})=1. \] Her proof does not at present appear to yield the exact value of \(C\) in the previous paragraph. It would be of some interest to get this by a direct method, but it is not obvious whether the current proof can be upgraded to such a result. The essential idea of the proof is to define six \` bad\'\, classes of triangle-free graphs, each of which has some \` bad\'\, property which one would not expect a random bipartite graph to have. Examples of these \` bad\'\, properties include having a vertex of implausibly high or low degree, or a set of vertices whose number of neighbours is not close to its expected value. The first key observation (Lemma 2.3) is that a triangle-free graph with \(m(n)\geq bn^{3/2}\sqrt{\log_{2}(n)}\) edges, for \(b\geq 1\), which is not in any of these six bad classes, really is bipartite. Now it suffices to show that each of the six bad classes is small relative to \({\mathcal S}(n,m)\). This result (Theorem 2.4) uses bounds on the sizes of \({\mathcal S}(n,m)\) and \({\mathcal T}(n,m)\) proved in \textit{H. J. Prömel} and \textit{A. Steger} [J. Graph Theory 21, 137--151 (1996; Zbl 0856.05037)], descriptions of how the graphs in the six bad classes can be constructed, and standard estimates of binomial coefficients. To deal with the last of the six classes, a result from \textit{S. Janson, T. Łuczak} and \textit{A. Ruciński} in [Random graphs '87 (Wiley, Chichester) (1990; Zbl 0733.05073)], giving an exponential bound on the probability of non-existence of a specified subgraph in a random graph, is also used.
This page was built for publication: On the Evolution of Triangle-Free Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4660565)