Matchings and Near-Optimal 2-Factor Packings in Percolated Vertex-Transitive Graphs

Abstract

Let $G$ be a connected simple vertex-transitive graph on $n$ vertices with degree $d$, and let $G_p$ be the random spanning subgraph obtained by retaining each edge of $G$ independently with probability $p$. Put $q:=1-p$. Motivated by a conjecture of Bedert, Draganić, Müyesser, and Pavez-Signé on Hamilton cycles in percolated Cayley graphs, we establish the corresponding matching and $2$-factor statements uniformly over the larger class of all connected vertex-transitive host graphs. For every $A>0$, if $q^d\le n^{-(5A+250)},$ then, with probability at least $1-n^{-A}$, the graph $G_p$ has a perfect matching when $n$ is even and is factor-critical when $n$ is odd. Separately, if $0<\hat{I}\mu <1$ and $\hat{I}{\mu }^{2}pd\ge 64(A+6)\log (2n),$ then, with probability at least $1-n^{-A}$, the graph $G_p$ contains at least \[ \left\lfloor\frac{(1-ε)pd}{2}\right\rfloor \] pairwise edge-disjoint spanning $2$-factors. Moreover, if $pd/\log n\to \infty$, then \[ ν_2(G_p)=(1+o(1))\frac{pd}{2} \] with high probability, which is asymptotically optimal, where $\hat{I}{½}_2(G)$ is the maximum number of pairwise edge-disjoint spanning 2-factors in $G$. Thus logarithmic-order percolation already forces these two factor-theoretic consequences of Hamiltonicity beyond the Cayley setting.