solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2043次
A blow-up lemma for approximate decompositions. (arXiv:1604.07282v3 [math.CO] UPDATED)
来源于:arXiv
We develop a new method for constructing approximate decompositions of dense
graphs into sparse graphs and apply it to longstanding decomposition problems.
For instance, our results imply the following. Let $G$ be a quasi-random
$n$-vertex graph and suppose $H_1,\dots,H_s$ are bounded degree $n$-vertex
graphs with $\sum_{i=1}^{s} e(H_i) \leq (1-o(1)) e(G)$. Then $H_1,\dots,H_s$
can be packed edge-disjointly into $G$. The case when $G$ is the complete graph
$K_n$ implies an approximate version of the tree packing conjecture of
Gy\'arf\'as and Lehel for bounded degree trees, and of the Oberwolfach problem.
We provide a more general version of the above approximate decomposition
result which can be applied to super-regular graphs and thus can be combined
with Szemer\'edi's regularity lemma. In particular our result can be viewed as
an extension of the classical blow-up lemma of Koml\'os, S\'ark\H{o}zy and
Szemer\'edi to the setting of approximate decompositions. 查看全文>>