<p>Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$G_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>, ..., <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">$G_m$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> be independentBernoulli random subgraphs of the complete graph <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal{K}_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> havingrandom sizes <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="195" /> </InlineMediaObject> <EquationSource Format="TEX">$X_1,\dots, X_m\in \{0,1,2,\dots\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>X</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>X</mi> <mi>m</mi> </msub> <mo>∈</mo> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>⋯</mo> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and edge densities <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq5.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$Q_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>, ..., <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$Q_m\in [0,1]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mi>m</mi> </msub> <mo>∈</mo> <mrow> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Letting <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="92" /> </InlineMediaObject> <EquationSource Format="TEX">$n,m\to+\infty$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>,</mo> <mi>m</mi> <mo stretchy="false">→</mo> <mo>+</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation> we establish the connectivity threshold for the union <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$ \bigcup_{i=1}^mG_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mo>⋃</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </msubsup> <msub> <mi>G</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> defined on the vertex set of <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal{K}_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>. We show that <Equation ID="Equ1"> <MediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_Equ1.gif" Format="GIF" Height="48" Rendition="HTML" Resolution="72" Type="Linedraw" Width="294" /> </MediaObject> <EquationSource Format="TEX">$ \textbf{P} \bigl \{ \bigcup_{i=1}^m G_i \ \hbox{is connected}\ \bigr \}= e^{-e^{\lambda^_{n,m}}}+o(1) , $</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="bold">P</mi> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">{</mo> </mrow> <munderover> <mo>⋃</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </munderover> <msub> <mi>G</mi> <mi>i</mi> </msub> <mspace width="4pt" /> <mtext>is connected</mtext> <mspace width="4pt" /> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">}</mo> </mrow> <mo>=</mo> <msup> <mi>e</mi> <mrow> <mo>-</mo> <msup> <mi>e</mi> <msubsup> <mi>λ</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>m</mi> </mrow> <mo>∗</mo> </msubsup> </msup> </mrow> </msup> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> </mrow> </math></EquationSource> </Equation> where <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2025_1518_Article_IEq10.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="321" /> </InlineMediaObject> <EquationSource Format="TEX">$\lambda^{}_{n,m}= \ln n - \frac{1}{n} \sum\nolimits_{i=1}^{m} \textbf{E} X_{i}(1-(1-Q_i)^{|X_i-1|})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mmultiscripts> <mi>λ</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>m</mi> </mrow> <mrow> <mrow /> <mo>∗</mo> </mrow> </mmultiscripts> <mo>=</mo> <mo>ln</mo> <mi>n</mi> <mo>-</mo> <mfrac> <mn>1</mn> <mi>n</mi> </mfrac> <msubsup> <mo>∑</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>m</mi> </msubsup> <mi mathvariant="bold">E</mi> <msub> <mi>X</mi> <mi>i</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <msub> <mi>Q</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msub> <mi>X</mi> <mi>i</mi> </msub> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">|</mo> </mrow> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>.</p>

Connectivity threshold for superpositions of Bernoulli random graphs. II

期刊论文
发表日期：

2025年4月22日

查看全文

M. Bloznelis,
D. Marma,
R. Vaicekauskas

摘要

Let $G_1$ $G_{1}$ , ..., $G_m$ $G_{m}$ be independentBernoulli random subgraphs of the complete graph $\mathcal{K}_n$ $K_{n}$ havingrandom sizes $X_1,\dots, X_m\in \{0,1,2,\dots\}$ $X_{1}, \dots, X_{m} \in {0, 1, 2, \dots}$ and edge densities $Q_1$ $Q_{1}$ , ..., $Q_m\in [0,1]$ $Q_{m} \in [0, 1]$ . Letting $n,m\to+\infty$ $n, m \to + \infty$ we establish the connectivity threshold for the union $ \bigcup_{i=1}^mG_i$ $⋃_{i = 1}^{m} G_{i}$ defined on the vertex set of $\mathcal{K}_n$ $K_{n}$ . We show that $ \textbf{P} \bigl \{ \bigcup_{i=1}^m G_i \ \hbox{is connected}\ \bigr \}= e^{-e^{\lambda^*_{n,m}}}+o(1) , $ $P {⋃_{i = 1}^{m} G_{i} is connected} = e^{- e^{λ_{n, m}^{*}}} + o (1),$ where $\lambda^{*}_{n,m}= \ln n - \frac{1}{n} \sum\nolimits_{i=1}^{m} \textbf{E} X_{i}(1-(1-Q_i)^{|X_i-1|})$ $λ_{n, m}^{*} = ln n - \frac{1}{n} \sum_{i = 1}^{m} E X_{i} (1 - {(1 - Q_{i})}^{| X_{i} - 1 |})$ .