The Library
A bandwidth theorem for approximate decompositions
Tools
Condon, Padraig, Kim, Jaehoon, Kühn, Daniela and Osthus, Deryk (2019) A bandwidth theorem for approximate decompositions. Proceedings of the London Mathematical Society, 118 (6). pp. 1393-1449. doi:10.1112/plms.12218 ISSN 0024-6115.
|
PDF
WRAP-bandwidth-therorem-approximate-decompositions-Kim-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1233Kb) | Preview |
Official URL: https://doi.org/10.1112/plms.12218
Abstract
We provide a degree condition on a regular n ‐vertex graph G which ensures the existence of a near optimal packing of any family H of bounded degree n ‐vertex k ‐chromatic separable graphs into G . In general, this degree condition is best possible.
Here a graph is separable if it has a sublinear separator whose removal results in a set of components of sublinear size. Equivalently, the separability condition can be replaced by that of having small bandwidth. Thus our result can be viewed as a version of the bandwidth theorem of Böttcher, Schacht and Taraz in the setting of approximate decompositions.
More precisely, let δ k be the infimum over all δ ⩾ 1 / 2 ensuring an approximate K k ‐decomposition of any sufficiently large regular n ‐vertex graph G of degree at least δ n . Now suppose that G is an n ‐vertex graph which is close to r ‐regular for some r ⩾ ( δ k + o ( 1 ) ) n and suppose that H 1 , ⋯ , H t is a sequence of bounded degree n ‐vertex k ‐chromatic separable graphs with ∑ i e ( H i ) ⩽ ( 1 − o ( 1 ) ) e ( G ) . We show that there is an edge‐disjoint packing of H 1 , ⋯ , H t into G .
If the H i are bipartite, then r ⩾ ( 1 / 2 + o ( 1 ) ) n is sufficient. In particular, this yields an approximate version of the tree packing conjecture in the setting of regular host graphs G of high degree. Similarly, our result implies approximate versions of the Oberwolfach problem, the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree.
Item Type: | Journal Article | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Graph theory | ||||||||||||||||||
Journal or Publication Title: | Proceedings of the London Mathematical Society | ||||||||||||||||||
Publisher: | Cambridge University Press | ||||||||||||||||||
ISSN: | 0024-6115 | ||||||||||||||||||
Official Date: | June 2019 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Volume: | 118 | ||||||||||||||||||
Number: | 6 | ||||||||||||||||||
Page Range: | pp. 1393-1449 | ||||||||||||||||||
DOI: | 10.1112/plms.12218 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Reuse Statement (publisher, data, author rights): | “This is the accepted version of the following article:Condon, P. , Kim, J. , Kühn, D. and Osthus, D. (2018), A bandwidth theorem for approximate decompositions. Proc. London Math. Soc.. . doi:10.1112/plms.12218 which has been published in final form at https://doi.org/10.1112/plms.12218 | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 12 December 2018 | ||||||||||||||||||
Date of first compliant Open Access: | 12 December 2018 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year