Perfect Matching in Product Graphs and in their Random Subgraphs

2024/04/22 by Sahar Diskin, Diskin, Sahar, Anna Geisler +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2404.14020

Abstract

For t ∈ ℕ and every i∈[t], let H_i be a d_i-regular connected graph, with 1<|V(H_i)|≤ C for some integer C≥ 2. Let G=\square_i=1^tH_i be the Cartesian product of H₁, …, H_t. We show that if t≥ 5C then G contains a (nearly-)perfect matching. Then, considering the random graph process on G, we generalise the result of Bollobás on the binary hypercube Q^t, showing that with high probability, the hitting times for minimum degree one, connectivity, and the existence of a (nearly-)perfect matching in the random graph process on G are the same. As a byproduct, we develop several tools which may be of independent interest in a more general setting when one seeks to establish the typical existence of a perfect matching under percolation.

Related

• Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs
• Finding perfect matchings in random cubic graphs in linear time
• Perfect Matchings in Inhomogeneous Random Bipartite Graphs in Random Environment
• Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
• On the number of perfect matchings in random lifts