Theoretical analysis demonstrates that hitting times for connectivity and perfect matchings coincide in Cartesian product random graphs, generalizing classical hypercube theorems.
For t ∈ N and every i∈[t], let Hᵢ be a dᵢ-regular connected graph, with 1<|V(Hᵢ)|≤ C for some integer C≥ 2. Let G=ᵢ₌₁ᵗHᵢ be the Cartesian product of H₁, …, Hₜ. We show that if t≥ 5Clog₂C then G contains a (nearly-)perfect matching. Then, considering the random graph process on G, we generalise the result of Bollob\'as on the binary hypercube Qᵗ, showing that with high probability, the hitting times for minimum degree one, connectivity, and the existence of a (nearly-)perfect matching in the G-random-process are the same. We develop several tools which may be of independent interest in a more general setting of the typical existence of a perfect matching under percolation.
No takes yet. Share an insight, caveat, or question.
Diskin et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: