A bandwidth theorem for approximate decompositions

DOI10.1112/PLMS.12218zbMATH Open1415.05145arXiv1712.04562OpenAlexW2964248410WikidataQ128870056 ScholiaQ128870056MaRDI QIDQ4967769FDOQ4967769

Authors: Padraig Condon, Daniela Kühn, Deryk Osthus, Jaehoon Kim 

Publication date: 10 July 2019

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

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 $mathcalH$ 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"ottcher, Schacht and Taraz in the setting of approximate decompositions. More precisely, let $delt{a}_k$ be the infimum over all $deltage1/2$ ensuring an approximate $K_k$-decomposition of any sufficiently large regular $n$-vertex graph $G$ of degree at least $deltan$. Now suppose that $G$ is an $n$-vertex graph which is close to $r$-regular for some $rge(delt{a}_k+o(1))n$ and suppose that $H_1,dots,H_t$ is a sequence of bounded degree $n$-vertex $k$-chromatic separable graphs with $su{m}_{i}e(H_i)le(1-o(1))e(G)$. We show that there is an edge-disjoint packing of $H_1,dots,H_t$ into $G$. If the $H_i$ are bipartite, then $rgeq(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.

Full work available at URL: https://arxiv.org/abs/1712.04562

Recommendations

• A blow-up lemma for approximate decompositions
• Optimal packings of bounded degree trees
• Packing spanning graphs from separable families
• Tree decompositions of graphs without large bipartite holes
• Packings in Dense Regular Graphs

zbMATH Keywords

near optimal packing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (14)

• Tree decompositions of graphs without large bipartite holes
• A blow-up lemma for approximate decompositions
• The bandwidth theorem for locally dense graphs
• Progress towards Nash-Williams' conjecture on triangle decompositions
• Decomposing hypergraphs into cycle factors
• Graph and hypergraph packing
• A greedy algorithm for the social golfer and the Oberwolfach problem
• Optimal packings of bounded degree trees
• Pseudorandom hypergraph matchings
• Resolution of the Oberwolfach problem
• Resolution of the Oberwolfach problem
• On the relation of separability, bandwidth and embedding
• A Short proof of the blow-up lemma for approximate decompositions
• On sufficient conditions for spanning structures in dense graphs

This page was built for publication: A bandwidth theorem for approximate decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4967769)