Rainbow \(k\)-connectivity of random bipartite graphs (Q2025233): Difference between revisions

There has been much recent interest in rainbow subgraphs of graphs whose edges have been (not necessarily properly) coloured, where a subgraph is rainbow if all its edges have different colours. The paper under review considers the question of how many colours are required to ensure that every pair of vertices are connected by at least \(k\) internally vertex-disjoint rainbow paths, a property which is called being rainbow \(k\)-connected due to the obvious analogy with Menger's theorem. Let \(\text{rc}_{k}(G)\) be this number, and consider the property that \(\text{rc}_{k}(G)\leq d\). This property is a monotone property so by the Bollobás-Thomason theorem has a threshold, which is sharp by the Friedgut-Kalai theorem. We aim to find this sharp threshold. The paper considers the random bipartite graph with \(n\) vertices in one class, \(m\) in the other, \(n\geq m\) and each of the \(nm\) possible edges present equiprobably with probability \(p\) independent of all other sets of edges, complementing recent work on Erdős-Rényi random graphs in [\textit{J. He} and \textit{H. Liang}, Inf. Process. Lett. 112, No. 10, 406--410 (2012; Zbl 1243.05218)] and work for random regular graphs in [\textit{A. Dudek} et al., SIAM J. Discrete Math. 29, No. 4, 2255--2266 (2015; Zbl 1325.05148); \textit{M. Molloy}, Electron. J. Comb. 24, No. 3, Research Paper P3.49, 3 p. (2017; Zbl 1369.05185); \textit{N. Kamčev} et al., J. Graph Theory 83, No. 4, 372--383 (2016; Zbl 1350.05078)]. The main result in the paper under review concerns \(G(n,m,p)\) with \(k=O(\log(n))\). In the case where \(d\) is odd we have that \((\log(mn))^{1/d}((mn)^{(d-1)/(2d)})\) is the sharp threshold for having \(\text{rc}_{k}G(n,m,p)\leq d+1\) provided \(pm\geq (\log^{n})^{4}\). For \(d\) even the corresponding sharp threshold is \(\log(n)^{1/d}/(m^{1/2}n^{(d-2)/(2d)})\) provided there is a small constant \(0<\epsilon <1\) such that \(pm^{1-\epsilon}\geq (\log(n))^{4}\). In particular, this gives the threshold for \(\text{rc}_{k}(G(n,n,p))\leq d+1\) to be \(\log(n)^{1/d}/n^{(d-1)/d}\) provided \(k=O(\log(n))\). The case \(d=2\) of this last statement was proved in [\textit{S. Fujita} et al., J. Comb. Math. Comb. Comput. 93, 33--52 (2015; Zbl 1320.05040)].