Bounding the strong chromatic index of dense random graphs (Q1827703)

For a finite simple graph \(G\), a strong edge colouring of \(G\) is an edge colouring in which every colour class is an induced matching. (Since each class is a matching, the colouring is proper.) The strong chromatic index of \(G\), \(\chi_{s}(G)\), is the smallest number of colours in a strong edge colouring of \(G\). The paper under review studies the strong chromatic index of random graphs \(G(n,p(n))\) where each edge arises with probability \(p(n)\) independently of all other edges. \textit{Z. Palka} [Australas. J. Comb. 18, 219-226 (1998; Zbl 0923.05042)] showed that if \(p(n)=\Theta(n^{-1})\), then \[ \lim_{n\rightarrow\infty}P\{\chi_{s}(G(n,p(n)))=O(\Delta(G(n,p(n))))\}=1 \] where, as usual, \(\Delta=\Delta(G)\) is the maximum degree of the graph. \textit{V. H. Vu} [Comb. Probab. Comput. 11, 103--111 (2002; Zbl 0991.05041)] used Rödl-nibble type arguments to show that if \(\log(n)^{1+\delta}/n\leq p(n)\leq n^{-\varepsilon}\) for any \(\varepsilon>0\) and \(\delta<1\), then \[ \lim_{n\rightarrow\infty}P\{\chi_{s}(G(n,p(n)))=O(\Delta^{2}/\log(\Delta))\}=1. \] These two papers between them cover most cases where \(p=o(1)\). (When \(p(n)=o(1/n)\) the random graph is usually a forest and the strong chromatic index of a tree is well understood: in particular, it is less than \(2\Delta\).) The aim of the paper under review is to study the case where \(p(n)>n^{-\varepsilon}\) for all \(\varepsilon>0\). The main result is that \[ \lim_{n\rightarrow\infty}P\{\frac{(1-o(1))p{n\choose 2}}{\log_{1/(1-p)}(n)}\leq \chi_{s}(G(n,p(n)))\leq \frac{(2+o(1))p{n\choose 2}}{\log_{1/(1-p)}(n)}\}=1. \] The lower bound is easy: a typical \(G(n,p)\) has about \(p{n\choose 2}\) edges and it is easy to see, using the first moment method, that the largest induced matching in \(G(n,p)\) has about \(\log_{1/(1-p)}(n)\) edges. More interesting part is the upper bound, derived from the result of \textit{B. Bollobás} [Combinatorica 8, 49--56 (1988; Zbl 0666.05033)] to the effect that the (ordinary) vertex chromatic number \(\chi(G(n,p))\) for \(0<p<1\) constant is usually about \(n/2\log_{1/(1-p)}(n)\). The link is made by observing that if \(M_{j}=\{e_{i}\}_{i=1}^{j}\) is a matching of \(G\), then a graph \(H_{M_{j}}(G)\) can be defined on vertex set \(M_{j}\), two vertices \(e_{j}\) and \(e_{k}\) in \(M_{j}\) being adjacent if and only if there is an edge \(e\) of \(G\) joining \(e_{j}\) and \(e_{k}\). Then a little thought shows that \(H_{M_{j}}(G(n,p))\) is a \(G(j,1-(1-p)^{4})\). Working out in detail the correspondence between independent sets in \(H_{M_{j}}(G)\) and induced matchings in \(G\) leads to the result. (Technical modifications are required if \(p(n)\) is not constant, but the same basic idea works.) The authors close by conjecturing that in fact \[ \lim_{n\rightarrow\infty}P\{\chi_{s}(G(n,p))=\frac{(1+o(1))p{n\choose 2}}{\log_{1/(1-p)}(n)}\}=1; \] that is, that the lower bound above is essentially the truth. Some progress towards this seems (subject, of course, to refereeing) to have been made in a recent preprint by A. Frieze, M. Krivelevich and B. Sudakov, available at http://www.math.cmu.edu/~af1p/strochrom.ps in which quite different techniques are used to show that \[ \lim_{n\rightarrow\infty}P\{\chi_{s}(G(n,p))\leq \frac{3}{2}\frac{(1+ o(1))p{n\choose 2}}{\log_{1/(1-p)}(n)}\}=1. \] However the preprint's authors remark that a substantial further idea seems to be required to prove the full conjecture. (The preprint also improves Palka's results in the sparse case.)