论文标题
$ d $ - 连接的随机图和预算限制
$d$-connectivity of the random graph with restricted budget
论文作者
论文摘要
在简短的说明中，我们考虑了Frieze，Krivelevich和Michaeli最近引入的图表过程。在他们的模型中，完整图$ k_n $的边缘是均匀订购的，然后连续透露给一个名为Builder的播放器。在每一轮比赛中，建筑商都必须决定他们是否接受本轮提出的边缘。我们证明，对于$（1+o（1））n \ log n/2 $ rounds的$ d $ d $连接的图形，建筑商可以通过接受$（1+o（1+o（1））dn/2 $ edges构建一个跨度$ d $连接的图形，而概率为1 $ n \ to \ n \ iffty $。这解决了Frieze，Krivelevich和Michaeli的猜想。
In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph $K_n$ are ordered uniformly at random and are then revealed consecutively to a player called Builder. At every round, Builder must decide if they accept the edge proposed at this round or not. We prove that, for every $d\ge 2$, Builder can construct a spanning $d$-connected graph after $(1+o(1))n\log n/2$ rounds by accepting $(1+o(1))dn/2$ edges with probability converging to 1 as $n\to \infty$. This settles a conjecture of Frieze, Krivelevich and Michaeli.
