<p>In a recent work, Allen, Böttcher, Hàn, Kohayakawa, and Person provided a first general analogue of the blow-up lemma applicable to sparse (pseudo)random graphs thus generalising the classic tool of Komlós, Sárközy, and Szemerédi. Roughly speaking, they showed that with high probability in the random graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="32" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_{n, p}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>p</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq2.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="133" /> </InlineMediaObject> <EquationSource Format="TEX">\(p \geqslant C(\log n/n)^{1/\Delta }\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>⩾</mo> <mi>C</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mi mathvariant="normal">Δ</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, sparse regular pairs behave similarly as complete bipartite graphs with respect to embedding a spanning graph <i>H</i> with <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta (H) \leqslant \Delta\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo>⩽</mo> <mi mathvariant="normal">Δ</mi> </mrow> </math></EquationSource> </InlineEquation>. However, this is typically only optimal when <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta \in \{2,3\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> and <i>H</i> either contains a triangle (<InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta = 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>) or many copies of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq7.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta = 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>). We go beyond this barrier for the first time and present a sparse blow-up lemma for cycles <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_{2k-1}, C_{2k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>C</mi> <mrow> <mn>2</mn> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>C</mi> <mrow> <mn>2</mn> <mi>k</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>, for all <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \geqslant 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>⩾</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, and densities <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_171_Article_IEq10.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="112" /> </InlineMediaObject> <EquationSource Format="TEX">\(p \geqslant Cn^{-(k-1)/k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>⩾</mo> <mi>C</mi> <msup> <mi>n</mi> <mrow> <mo>-</mo> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mi>k</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, which is in a way best possible. As an application of our blow-up lemma we fully resolve a question of Nenadov and Škorić regarding resilience of cycle factors in sparse random graphs.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Blow-up Lemma for Cycles in Sparse Random Graphs

  • Miloš Trujić

摘要

In a recent work, Allen, Böttcher, Hàn, Kohayakawa, and Person provided a first general analogue of the blow-up lemma applicable to sparse (pseudo)random graphs thus generalising the classic tool of Komlós, Sárközy, and Szemerédi. Roughly speaking, they showed that with high probability in the random graph \(G_{n, p}\) G n , p for \(p \geqslant C(\log n/n)^{1/\Delta }\) p C ( log n / n ) 1 / Δ , sparse regular pairs behave similarly as complete bipartite graphs with respect to embedding a spanning graph H with \(\Delta (H) \leqslant \Delta\) Δ ( H ) Δ . However, this is typically only optimal when \(\Delta \in \{2,3\}\) Δ { 2 , 3 } and H either contains a triangle ( \(\Delta = 2\) Δ = 2 ) or many copies of \(K_4\) K 4 ( \(\Delta = 3\) Δ = 3 ). We go beyond this barrier for the first time and present a sparse blow-up lemma for cycles \(C_{2k-1}, C_{2k}\) C 2 k - 1 , C 2 k , for all \(k \geqslant 2\) k 2 , and densities \(p \geqslant Cn^{-(k-1)/k}\) p C n - ( k - 1 ) / k , which is in a way best possible. As an application of our blow-up lemma we fully resolve a question of Nenadov and Škorić regarding resilience of cycle factors in sparse random graphs.