ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let K∩G(n;Θn)\mathbb{K \cap G}(n;\pmb{\Theta}_n) denote the intersection of an inhomogeneous random key graph and an Erdős–Rényi graph, with class probability distribution μ=(μ1,μ2,…,μr)\pmb{\mu}=(\mu_1,\mu_2,\ldots,\mu_r) satisfying μi>0\mu_i>0 for i=1,…,ri=1,\ldots,r, key-ring and key-pool scalings K1,…,Kr,P:N0→N0r+1K_1,\ldots,K_r,P:\mathbb{N}_0\to\mathbb{N}_0^{r+1}, and channel-probability scaling α:N0→(0,1)\alpha:\mathbb{N}_0\to(0,1). Let γ:N0→R\gamma:\mathbb{N}_0\to\mathbb{R} be defined by the paper's scaling condition, and suppose λ1(n)=o(1)\lambda_1(n)=o(1), possibly with additional conditions. The one-law for k-connectivity. One should have

lim⁡n→∞P[K∩G(n;Θn) is k-connected]={0,if lim⁡n→∞γn=−∞,1,if lim⁡n→∞γn=+∞.\lim_{n\to\infty}\mathbb{P}\left[\mathbb{K \cap G}(n;\pmb{\Theta}_n)\text{ is $k$-connected}\right]=\begin{cases}0,&\text{if }\lim_{n\to\infty}\gamma_n=-\infty,\\1,&\text{if }\lim_{n\to\infty}\gamma_n=+\infty. \end{cases}

The zero-law follows from the minimum-degree result, whereas simulations suggest that the one-law for kk-connectivity occurs under the same critical scaling as the one-law for minimum degree. Establishing the asserted one-law requires the additional conditions left unspecified in the conjecture.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.