标题： 单调递增属性及其在均匀随机交集图中的相变 显示英文标题

标题： Monotone Increasing Properties and Their Phase Transitions in Uniform Random Intersection Graphs

摘要： 均匀随机交集图已经引起了很大的兴趣，并被应用于各种领域。 具有$n$个节点的均匀随机交集图是这样构造的：每个节点从包含$P_n$个不同项目的同一池中统一随机选择一组$K_n$个项目，如果两个节点共享至少一个项目，则在它们之间建立一条无向边。 对于这样的图$G(n, K_n, P_n)$，我们在本文中提出了以下结果。 首先，在$P_n = \omega\big(n (\ln n)^5\big)$的条件下（所有渐近符号均理解为$n \to \infty$），我们分别对$G(n, K_n, P_n)$具有完美匹配和具有哈密顿环的概率进行了精确分析。 分析表明，与先前工作中显示的（$k$-）连通性类似，对于完美匹配包含性和哈密顿环包含性这两种性质，$G(n, K_n, P_n)$也表现出相变现象：对于上述每种性质，随着$K_n$的增加，$G(n, K_n, P_n)$具有该性质的概率的极限从$0$增加到$1$。 其次，我们分别计算了$G(n, K_n, P_n)$在$k$连通性（KC）、完美匹配包含（PMC）和哈密顿环包含（HCC）的相变宽度。 对于图性质$R$和正常数$a < \frac{1}{2}$，相变宽度$d_n(R, a)$定义为确保$G(n, K_n, P_n)$以至少$1-a$或$a$的概率具有性质$R$的最小$K_n$的差值，我们证明对于任何正数$a<\frac{1}{2}$和$k$：(i) 如果$P_n=\Omega(n)$和$P_n=o(n\ln n)$，则对于每个足够大的$n$，$d_n(KC, a)$要么是$0$，要么是$1$。 (ii) 如果$P_n=\Theta(n\ln n)$，则$d_n(KC, a)=\Theta(1)$。 (iii) 如果$P_n=\omega(n\ln n)$，则$d_n(KC, a)=\omega(1)$。 (iv) 如果 $P_n=\omega\big(n (\ln n)^5\big)$，$d_n(PMC, a)$和$d_n(HCC, a)$都是$\omega(1)$。 显示英文摘要

摘要： Uniform random intersection graphs have received much interest and been used in diverse applications. A uniform random intersection graph with $n$ nodes is constructed as follows: each node selects a set of $K_n$ different items uniformly at random from the same pool of $P_n$ distinct items, and two nodes establish an undirected edge in between if and only if they share at least one item. For such graph denoted by $G(n, K_n, P_n)$, we present the following results in this paper. First, we provide an exact analysis on the probabilities of $G(n, K_n, P_n)$ having a perfect matching and having a Hamilton cycle respectively, under $P_n = \omega\big(n (\ln n)^5\big)$ (all asymptotic notation are understood with $n \to \infty$). The analysis reveals that just like ($k$-)connectivity shown in prior work, for both properties of perfect matching containment and Hamilton cycle containment, $G(n, K_n, P_n)$ also exhibits phase transitions: for each property above, as $K_n$ increases, the limit of the probability that $G(n, K_n, P_n)$ has the property increases from $0$ to $1$. Second, we compute the phase transition widths of $G(n, K_n, P_n)$ for $k$-connectivity (KC), perfect matching containment (PMC), and Hamilton cycle containment (HCC), respectively. For a graph property $R$ and a positive constant $a < \frac{1}{2}$, with the phase transition width $d_n(R, a)$ defined as the difference between the minimal $K_n$ ensuring $G(n, K_n, P_n)$ having property $R$ with probability at least $1-a$ or $a$, we show for any positive constants $a<\frac{1}{2}$ and $k$: (i) If $P_n=\Omega(n)$ and $P_n=o(n\ln n)$, then $d_n(KC, a)$ is either $0$ or $1$ for each $n$ sufficiently large. (ii) If $P_n=\Theta(n\ln n)$, then $d_n(KC, a)=\Theta(1)$. (iii) If $P_n=\omega(n\ln n)$, then $d_n(KC, a)=\omega(1)$. (iv) If $P_n=\omega\big(n (\ln n)^5\big)$, $d_n(PMC, a)$ and $d_n(HCC, a)$ are both $\omega(1)$.