×

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring. (English) Zbl 1087.05052

Mem. Am. Math. Soc. 845, 66 p. (2006).
The paper under review deals with random graphs \(G(n,p(n))\) where there are \(n\) labelled vertices and each potential edge arises with probability \(p(n)\), fails to arise with probability \(1-p(n)\) independently of all other edges. Recall that for an increasing graph property \(\wp\) (one for which, if a spanning subgraph has the property, then so does the whole graph) we say that a probability \(\hat{p}(n)\) is a threshold for \(\wp\) if (using whp to mean ‘with probability tending to 1 as \(n\rightarrow\infty\)’) we have \[ \lim_{n\rightarrow \infty}\frac{p(n)}{\hat{p}(n)}=0\Rightarrow G(n,p(n))\text{~has~}\wp\,\,\mathbf{whp} \] but \[ \lim_{n\rightarrow \infty}\frac{p(n)}{\hat{p}(n)}=1\Rightarrow G(n,p(n))\text{~does~not~have~}\wp\,\,\mathbf{whp}. \] An increasing property always has such a threshold. However there are different types of thresholds. For example, if \(\wp\) is ‘having a triangle’ then any function \(p(n)=c/n\) for any constant \(c>0\) is a threshold: but if \(\wp\) is ‘being connected’ then the threshold is sharper: it is \(\log(n)/n\) and at \((1+\epsilon)\log(n)/n\), the graph is already whp connected, whereas at \((1-\epsilon)\log(n)/n\) it is whp disconnected. The first kind is called a coarse threshold, the second a strong threshold. Recently, an explanation of this emerged; see [E. Friedgut, J. Am. Math. Soc. 12, 1017-1054 (1999; Zbl 0932.05084)]. Modulo (non-trivial) technicalities, it says that if a property \(\wp\) has a coarse threshold there is a pseudorandom graph \(G\) and a “balanced” graph \(M\) such that adding a copy of \(M\) to \(G\) often induces the property in question, but increasing the number of edges randomly by a constant proportion does not induce the property! This shows that the property is, in some sense, ‘local\'.
The substantial memoir under review proves the existence of a sharp threshold for the property \({\mathcal R}\) that every blue-red colouring of the edges of the graph has a monochromatic triangle. (Of course by undergraduate Ramsey theory this is heavily influenced by the question of whether the graph contains a \(K_{6}\), but it is not the same question, so there is a chance of a sharp threshold.) A large amount of hard earlier work by several authors, including the second and third authors of this paper, had established that there are constants \(0<c<C<\infty\) such that \(G(n,p(n))\) whp has \({\mathcal R}\) if \(p(n)>C/\sqrt{n}\) but whp \(G(n,p(n))\) does not have \({\mathcal R}\) if \(p(n)<c/\sqrt{n}\). Thus the contribution of the present paper is to confirm the sharp threshold by proving that there is a bounded function \(\hat{c}(n)\) such that for any \(\epsilon>0\) we have \(G((n,(1-\epsilon)\hat{c}(n)/n)\) whp does not have \({\mathcal R}\), but \(G((n,(1+\epsilon)\hat{c}(n)/n)\) has \({\mathcal R}\) whp. The authors observe that they cannot at present show that this function \(\hat{c}(n)\) actually tends to a limit.
Here is a necessarily very crude overview of the proof. By the earlier work we need only consider \(c/\sqrt{n}\leq \hat{p}\leq C/\sqrt{n}\): thus, using the idea in the first paragraph, we reduce to showing that for any balanced graph \(M\) with edge-to-vertex ratio 2 as in the first paragraph, there is a graph property \({\mathcal G}\) which \(G(n,p)\) has whp and an integer \(n_{1}\) such that for all graphs \(G\) with \({\mathcal G}\) but not \({\mathcal R}\), and with at least \(n_{1}\) vertices, we have that there is indeed a good chance that adding \(M\) to \(G\) gives, with a good probability, a graph with \({\mathcal R}\). This shows that no triangle-free (edge) colouring of \(G\) can be extended to \(G\cup M\) when \(M\) is placed in certain “bad” sets. Each such “bad” set is associated with certain edges in \(G\), a union of stars (a so-called special constellation). Fix a colouring of the special constellations such that every proper colouring of \(G\) must agree with every such coloured constellation on at least one edge: this is equivalent to a hypergraph problem, as the triangle-free colourings of \(G\) give so-called ‘hitting sets\' of the hyperedges of this hypergraph.
Next, it is shown that a hitting set may be associated with a large monochromatic set in \(G\) called a core. This step depends on inherent regular structure of the hypergraph, revealed through a form of the Szemerédi regularity lemma. Because the cores are large, use of the Janson concentration inequality and a lemma showing that there are many triangles (of a certain kind) in subgraphs of a \(G(n,p)\) with enough edges shows that we get a triangle both in \(G\) and in \(G(n,\xi p)\) with probability very close to 1. (Here \(G(n,\xi p)\) represents the extra edges added to \(G\) when the number of edges is increased randomly by a constant proportion: \(\xi\) is a constant.) Indeed it will be so close to 1 that the size of the family of cores times the error probability will go to zero, and these facts together complete the proof.
This is all even more complex than the above might sound! In particular, the regularity lemma used is a substantial extension of the usual regularity lemma (the ‘subgraph regularity lemma\') to the case where density is measured not just by number of edges, but also by number of copies of certain subgraphs: this is highly technical. The lemma guaranteeing that we can get our random graph to have many triangles in subgraphs with enough edges involves hard work with concentration inequalities.
There are many interesting follow-up questions, such as the extension to more than two colours, or the case of a graph other than a triangle as the forbidden subgraph, and one suspects there will be much interesting work in this area over the next few years, despite the considerable technical difficulties.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0932.05084
PDFBibTeX XMLCite
Full Text: DOI arXiv