2026/07/22 by Mengyu Cao, Mei Lu, Xiamiao Zhao
#math.CO
Let G be a connected simple vertex-transitive graph on n vertices with degree d, and let Gp 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 qd≤ n-(5A+250), then, with probability at least 1-n-A, the graph Gp has a perfect matching when n is even and is factor-critical when n is odd. Separately, if 0<ε<1 and ε2pd≥64(A+6)log(2n), then, with probability at least 1-n-A, the graph Gp contains at least \lfloor((1-ε)pd)/(2)\rfloor pairwise edge-disjoint spanning 2-factors. Moreover, if pd/log n→∞, then ν2(Gp)=(1+o(1))(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.