论文标题
朋友和纠缠的新型号的连接图
Connectivity of Old and New Models of Friends-and-Strangers Graphs
论文作者
论文摘要
在本文中，我们研究了朋友和纠缠图的连接性，这些连通性是由Defant和Kravitz在2020年引入的。我们首先要考虑由两个随机图引起的朋友和纠缠者图，并考虑此类图形达到最大连接的阈值概率。我们稍微改善了阈值概率的下限，从而反驳了Alon，Defant和Kravitz的两个猜想。在随机两部分图的情况下，我们还改善了阈值概率上的上限，并获得一个紧密绑定到$ n^{o（1）} $的系数。此外，我们介绍了朋友和纠缠图的概念的概括，其中允许启动图的顶点具有多重性，并在这种新环境中获得威尔逊，Defant和Kravitz先前结果的概括。
In this paper, we investigate the connectivity of friends-and-strangers graphs, which were introduced by Defant and Kravitz in 2020. We begin by considering friends-and-strangers graphs arising from two random graphs and consider the threshold probability at which such graphs attain maximal connectivity. We slightly improve the lower bounds on the threshold probabilities, thus disproving two conjectures of Alon, Defant and Kravitz. We also improve the upper bound on the threshold probability in the case of random bipartite graphs, and obtain a tight bound up to a factor of $n^{o(1)}$. Further, we introduce a generalization of the notion of friends-and-strangers graphs in which vertices of the starting graphs are allowed to have multiplicities and obtain generalizations of previous results of Wilson and of Defant and Kravitz in this new setting.
