A blow-up lemma for approximate decompositions
A blow-up lemma for approximate decompositions
复制标题
近似分解的爆炸引理
DOI：
--
复制
发表时间：
2016
影响因子：
1.3
通讯作者：
Mykhaylo Tyomkyn
中科院分区：
文献类型：
--
作者：
Jaehoon Kim;D. Kuhn;Deryk Osthus;Mykhaylo Tyomkyn
<p>We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to long-standing decomposition problems. For instance, our results imply the following. Let <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G">
<mml:semantics>
<mml:mi>G</mml:mi>
<mml:annotation encoding="application/x-tex">G</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> be a quasi-random <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n">
<mml:semantics>
<mml:mi>n</mml:mi>
<mml:annotation encoding="application/x-tex">n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>-vertex graph and suppose <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H 1 comma ellipsis comma upper H Subscript s Baseline">
<mml:semantics>
<mml:mrow>
<mml:msub>
<mml:mi>H</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
<mml:mo>,</mml:mo>
<mml:mo>…<!-- … --></mml:mo>
<mml:mo>,</mml:mo>
<mml:msub>
<mml:mi>H</mml:mi>
<mml:mi>s</mml:mi>
</mml:msub>
</mml:mrow>
<mml:annotation encoding="application/x-tex">H_1,\dots ,H_s</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> are bounded degree <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n">
<mml:semantics>
<mml:mi>n</mml:mi>
<mml:annotation encoding="application/x-tex">n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>-vertex graphs with <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma-summation Underscript i equals 1 Overscript s Endscripts e left-parenthesis upper H Subscript i Baseline right-parenthesis less-than-or-equal-to left-parenthesis 1 minus o left-parenthesis 1 right-parenthesis right-parenthesis e left-parenthesis upper G right-parenthesis">
<mml:semantics>
<mml:mrow>
<mml:munderover>
<mml:mo>∑<!-- ∑ --></mml:mo>
<mml:mrow class="MJX-TeXAtom-ORD">
<mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow class="MJX-TeXAtom-ORD">
<mml:mi>s</mml:mi>
</mml:mrow>
</mml:munderover>
<mml:mi>e</mml:mi>
<mml:mo stretchy="false">(</mml:mo>
<mml:msub>
<mml:mi>H</mml:mi>
<mml:mi>i</mml:mi>
</mml:msub>
<mml:mo stretchy="false">)</mml:mo>
<mml:mo>≤<!-- ≤ --></mml:mo>
<mml:mo stretchy="false">(</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>−<!-- − --></mml:mo>
<mml:mi>o</mml:mi>
<mml:mo stretchy="false">(</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo stretchy="false">)</mml:mo>
<mml:mo stretchy="false">)</mml:mo>
<mml:mi>e</mml:mi>
<mml:mo stretchy="false">(</mml:mo>
<mml:mi>G</mml:mi>
<mml:mo stretchy="false">)</mml:mo>
</mml:mrow>
<mml:annotation encoding="application/x-tex">\sum _{i=1}^{s} e(H_i) \leq (1-o(1)) e(G)</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>. Then <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H 1 comma ellipsis comma upper H Subscript s Baseline">
<mml:semantics>
<mml:mrow>
<mml:msub>
<mml:mi>H</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
<mml:mo>,</mml:mo>
<mml:mo>…<!-- … --></mml:mo>
<mml:mo>,</mml:mo>
<mml:msub>
<mml:mi>H</mml:mi>
<mml:mi>s</mml:mi>
</mml:msub>
</mml:mrow>
<mml:annotation encoding="application/x-tex">H_1,\dots ,H_s</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> can be packed edge-disjointly into <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G">
<mml:semantics>
<mml:mi>G</mml:mi>
<mml:annotation encoding="application/x-tex">G</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>. The case when <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G">
<mml:semantics>
<mml:mi>G</mml:mi>
<mml:annotation encoding="application/x-tex">G</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> is the complete graph <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript n">
<mml:semantics>
<mml:msub>
<mml:mi>K</mml:mi>
<mml:mi>n</mml:mi>
</mml:msub>
<mml:annotation encoding="application/x-tex">K_n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> implies an approximate version of the tree packing conjecture of Gyárfás and Lehel for bounded degree trees, and of the Oberwolfach problem.</p>
<p>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édi’s regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Komlós, Sárkőzy, and Szemerédi to the setting of approximate decompositions.</p>
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus