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<ε<1$ and $ ε^2pd\ge64(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 $ν_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.

Disclosure

“he gap in (20). In particular, determine whether the lower bound C∗ (A) = 2A + 2 is sharp, and classify the minimal parity-preclusion sets that determine the leading failure probability. Acknowledgement The authors acknowledge the use of AI tools during the exploratory stage of this project. All mathematical arguments and proofs in the final manuscript were checked and written by the authors. References [1] B. Bedert, N. Draganić, A. Müyesser, and M. Pavez-Signé, The Lovász”

PDF page 22

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-23T19:03:11.135434Z

Structural counts