Minimal H-factors and covers
(2023)- Abstract
- Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G.
If G is the complete graph Kn 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 e.g. H=K2.
We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/26b4da5f-977f-4ace-8a76-bfa21a755588
- author
- Federico, Lorenzo
and Danielsson, Joel
LU
- organization
- publishing date
- 2023-02-23
- type
- Working paper/Preprint
- publication status
- published
- subject
- keywords
- Random graphs, Graph tiling, factor, cover, sharp concentration
- pages
- 20 pages
- publisher
- arXiv.org
- DOI
- 10.48550/arXiv.2302.12184
- language
- English
- LU publication?
- yes
- id
- 26b4da5f-977f-4ace-8a76-bfa21a755588
- date added to LUP
- 2023-03-02 14:42:08
- date last changed
- 2023-03-03 09:07:18
@misc{26b4da5f-977f-4ace-8a76-bfa21a755588, abstract = {{Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. <br/>If G is the complete graph Kn 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 e.g. H=K2. <br/>We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(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.}}, author = {{Federico, Lorenzo and Danielsson, Joel}}, keywords = {{Random graphs; Graph tiling; factor; cover; sharp concentration}}, language = {{eng}}, month = {{02}}, note = {{Preprint}}, publisher = {{arXiv.org}}, title = {{Minimal H-factors and covers}}, url = {{http://dx.doi.org/10.48550/arXiv.2302.12184}}, doi = {{10.48550/arXiv.2302.12184}}, year = {{2023}}, }