2026/07/30 by Jie Han, Bin Wang, Jingwen Zhao
Mathematics · #math.CO
20 pages
arxiv created 2026/07/30 · arxiv updated 2026/07/31
Let F be an r-vertex graph. In this paper, we study the F-factor problem in random induced subgraphs of dense graphs. We show that for any r-vertex graph F and γ>0, if H is an n-vertex graph with minimum degree at least (1-1/χcr(F)+γ)n, then for every fixed p ∈ (0,1), the random induced subgraph H[p] contains an F-factor with probability at least 1/(rq)-on(1), where q∈ ℕ is the order of certain coset group defined from H. The probability is asymptotically best possible for infinitely many F and H and yields that a 1/(rq)-on(1) proportion of the subsets of H induce F-factors, interestingly, regardless of whether H itself admits an F-factor. Similar results are obtained for perfect matchings in hypergraphs under minimum degree conditions. Our proof combines concentration inequalities, lattice point counting in ℤd and structural theorems for F-factors in dense (hyper)graphs.