Premium
A bandwidth theorem for approximate decompositions
Author(s) -
Condon Padraig,
Kim Jaehoon,
Kühn Daniela,
Osthus Deryk
Publication year - 2019
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms.12218
Subject(s) - mathematics , combinatorics , sublinear function , bipartite graph , separable space , degree (music) , bounded function , vertex (graph theory) , discrete mathematics , conjecture , disjoint sets , graph , mathematical analysis , physics , acoustics
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 thatH 1 , ⋯ , H tis 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 ofH 1 , ⋯ , H tinto 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.