A bandwidth theorem for approximate decompositions

DOI10.1112/PLMS.12218MaRDI QIDQ4967769zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1712.04562, http://pure-oai.bham.ac.uk/ws/files/55049439/SeparableGraphPacking_2Oct.pdf

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)

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.

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

Cited in

(16)

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

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)