1 results
Minimal H-factors and covers
- Part of
-
- Journal:
- Journal of Applied Probability / Volume 62 / Issue 1 / March 2025
- Published online by Cambridge University Press:
- 14 February 2025, pp. 136-152
- Print publication:
- March 2025
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs
$H'\subset G$, each isomorphic to H, that cover the vertices of G. If G is the complete graph 
$K_n$ equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for 
$H=K_2$, for example. We show that if H contains a cycle, then the minimum weight is sharply concentrated around some 
$L_n = \Theta(n^{1-1/d^*})$ (where 
$d^*$ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.
