<p>We consider the question of determining the probability of triangle count deviations in the Erdős-Rényi random graphs <i>G</i>(<i>n</i>,&#xa0;<i>m</i>) and <i>G</i>(<i>n</i>,&#xa0;<i>p</i>) with densities larger than <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1359_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="102" /> </InlineMediaObject> <EquationSource Format="TEX">\(n^{-1/2}(\log {n})^{1/2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. In particular, we determine the log probability <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1359_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="212" /> </InlineMediaObject> <EquationSource Format="TEX">\(\log \mathbb {P}\left( N_{\triangle }(G)\, &gt;\, (1+\delta )p^3n^3\right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>log</mo> <mi mathvariant="double-struck">P</mi> <mfenced close=")" open="("> <msub> <mi>N</mi> <mi>▵</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mspace width="0.166667em" /> <mo>&gt;</mo> <mspace width="0.166667em" /> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>δ</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>p</mi> <mn>3</mn> </msup> <msup> <mi>n</mi> <mn>3</mn> </msup> </mfenced> </mrow> </math></EquationSource> </InlineEquation> up to a constant factor across essentially the entire range of possible deviations, in both the <i>G</i>(<i>n</i>,&#xa0;<i>m</i>) and <i>G</i>(<i>n</i>,&#xa0;<i>p</i>) model. For the <i>G</i>(<i>n</i>,&#xa0;<i>p</i>) model, we also prove a stronger result, up to a <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="440_2025_1359_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">\((1+o(1))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> factor, in the non-localised regime. We also obtain some results for the lower tail and for counts of cherries (paths of length 2).</p>

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

Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(nm) and G(np)

  • José D. Alvarado,
  • Leonardo Gonçalves de Oliveira,
  • Simon Griffiths

摘要

We consider the question of determining the probability of triangle count deviations in the Erdős-Rényi random graphs G(nm) and G(np) with densities larger than \(n^{-1/2}(\log {n})^{1/2}\) n - 1 / 2 ( log n ) 1 / 2 . In particular, we determine the log probability \(\log \mathbb {P}\left( N_{\triangle }(G)\, >\, (1+\delta )p^3n^3\right) \) log P N ( G ) > ( 1 + δ ) p 3 n 3 up to a constant factor across essentially the entire range of possible deviations, in both the G(nm) and G(np) model. For the G(np) model, we also prove a stronger result, up to a \((1+o(1))\) ( 1 + o ( 1 ) ) factor, in the non-localised regime. We also obtain some results for the lower tail and for counts of cherries (paths of length 2).