Perfect Matching in Product Graphs and in their Random Subgraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909751914266624 |
|---|---|
| author | Diskin, Sahar Geisler, Anna |
| author_facet | Diskin, Sahar Geisler, Anna |
| contents | For $t \in \mathbb{N}$ and every $i\in[t]$, let $H_i$ be a $d_i$-regular connected graph, with $1<|V(H_i)|\le C$ for some integer $C\ge 2$. Let $G=\square_{i=1}^tH_i$ be the Cartesian product of $H_1, \ldots, H_t$. We show that if $t\ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14020 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Perfect Matching in Product Graphs and in their Random Subgraphs Diskin, Sahar Geisler, Anna Combinatorics Probability 05C80, 60K35 For $t \in \mathbb{N}$ and every $i\in[t]$, let $H_i$ be a $d_i$-regular connected graph, with $1<|V(H_i)|\le C$ for some integer $C\ge 2$. Let $G=\square_{i=1}^tH_i$ be the Cartesian product of $H_1, \ldots, H_t$. We show that if $t\ge 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. |
| title | Perfect Matching in Product Graphs and in their Random Subgraphs |
| topic | Combinatorics Probability 05C80, 60K35 |
| url | https://arxiv.org/abs/2404.14020 |