标题： 随机s-交集图中的阈值函数 显示英文标题

标题： Threshold Functions in Random s-Intersection Graphs

摘要： 随机$s$-交图最近在广泛的应用领域中受到了相当多的关注。 在这样的图中，每个顶点以某种随机方式配备一组物品，当且仅当它们至少有$s$个共同物品时，任意两个顶点之间建立一条无向边。 特别是，在均匀随机$s$-交图中，每个顶点独立地从一个共同的物品池中均匀随机选择固定数量的物品，而在二项随机$s$-交图中，某个物品池中的每个物品独立地以相同的概率附加到每个顶点上。 对于二项/均匀随机$s$-交图，我们建立了完美匹配包含、哈密顿环包含和$k$-鲁棒性的阈值函数，其中$k$-鲁棒性是指 Zhang 和 Sundaram 的定义 [IEEE 控制与决策会议 '12]。 我们证明这些阈值函数类似于经典 Erdős-Rényi 图的阈值函数，其中每对顶点以相同的概率独立地具有无向边。 显示英文摘要

摘要： Random $s$-intersection graphs have recently received considerable attention in a wide range of application areas. In such a graph, each vertex is equipped with a set of items in some random manner, and any two vertices establish an undirected edge in between if and only if they have at least $s$ common items. In particular, in a uniform random $s$-intersection graph, each vertex independently selects a fixed number of items uniformly at random from a common item pool, while in a binomial random $s$-intersection graph, each item in some item pool is independently attached to each vertex with the same probability. For binomial/uniform random $s$-intersection graphs, we establish threshold functions for perfect matching containment, Hamilton cycle containment, and $k$-robustness, where $k$-robustness is in the sense of Zhang and Sundaram [IEEE Conf. on Decision & Control '12]. We show that these threshold functions resemble those of classical Erd\H{o}s-R\'{e}nyi graphs, where each pair of vertices has an undirected edge independently with the same probability.