Rainbow \(k\)-connectivity of random bipartite graphs (Q2025233): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Xiao-Lin Chen / rank | |||
Property / author | |||
Property / author: Xue Liang Li / rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Property / author | |||
Property / author: Xiao-Lin Chen / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Xue Liang Li / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3117927275 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1212.6115 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Diameter of Random Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3682518 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Threshold functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On rainbow connection / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hardness and algorithms for rainbow connection / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rainbow connection in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The rainbow connectivity of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rainbow Connection of Random Regular Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Every monotone graph property has a sharp threshold / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2857372 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On rainbow-\(k\)-connectivity of random graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some remarks on rainbow connectivity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rainbow connections of graphs: a survey / rank | |||
Normal rank |
Latest revision as of 19:09, 25 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rainbow \(k\)-connectivity of random bipartite graphs |
scientific article |
Statements
Rainbow \(k\)-connectivity of random bipartite graphs (English)
0 references
11 May 2021
0 references
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)].
0 references
rainbow \(k\)-connectivity
0 references
sharp threshold function
0 references
random bipartite graph
0 references