Tiling dense hypergraphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911732357660672 |
|---|---|
| author | Lang, Richard |
| author_facet | Lang, Richard |
| contents | The goal in the perfect tiling problem is to cover the vertices of a hypergraph $G$ with pairwise vertex-disjoint copies of a hypergraph $F$. Prior work has identified three necessary conditions for perfect tilings, which correspond to barriers in space, divisibility and covering. It is natural to ask for which families of hypergraphs these conditions are also asymptotically sufficient.
Our main result confirms this for all families that are approximately closed under subsampling. Among others, this includes families described by minimum degrees and uniform density, which have been studied extensively in this area. For instance, we characterise the minimum $d$-degree threshold for perfect $F$-tilings in terms of the thresholds to overcome the space, divisibility and covering barriers: \[δ_d(\mathsf{Til}_F) = \max \left\{ δ_d(\mathsf{Spa}_{F}),\, δ_d(\mathsf{Div}_F),\, δ_d(\mathsf{Cov}_F) \right\}.\] As an application, we recover and extend a series of well-known results for perfect tilings in hypergraphs and related settings involving vertex-orderings and transversal structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_12281 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Tiling dense hypergraphs Lang, Richard Combinatorics 05C35, 05C65, 05C70 G.2.2 The goal in the perfect tiling problem is to cover the vertices of a hypergraph $G$ with pairwise vertex-disjoint copies of a hypergraph $F$. Prior work has identified three necessary conditions for perfect tilings, which correspond to barriers in space, divisibility and covering. It is natural to ask for which families of hypergraphs these conditions are also asymptotically sufficient. Our main result confirms this for all families that are approximately closed under subsampling. Among others, this includes families described by minimum degrees and uniform density, which have been studied extensively in this area. For instance, we characterise the minimum $d$-degree threshold for perfect $F$-tilings in terms of the thresholds to overcome the space, divisibility and covering barriers: \[δ_d(\mathsf{Til}_F) = \max \left\{ δ_d(\mathsf{Spa}_{F}),\, δ_d(\mathsf{Div}_F),\, δ_d(\mathsf{Cov}_F) \right\}.\] As an application, we recover and extend a series of well-known results for perfect tilings in hypergraphs and related settings involving vertex-orderings and transversal structures. |
| title | Tiling dense hypergraphs |
| topic | Combinatorics 05C35, 05C65, 05C70 G.2.2 |
| url | https://arxiv.org/abs/2308.12281 |