随机图中独立数的渐近上界证明求助
随机图中独立数的渐近上界证明求助
最近我在学随机图的相关内容,卡在了一个据说很经典的结论上——翻了不少资料都没找到证明,自己推导也卡壳了,想请教下大家!
问题是这样的:
给定整数$n$,$0\le d \le n$,考虑$n$个顶点的随机图$G$:每条边以概率$d/n$独立存在。当$d = \omega(1)$(也就是$d$随$n$增长趋于无穷)时,图$G$满足
$$\alpha(G) \le (1 + o(1)) \frac{2n \ln d}{d} =: b$$
的概率是$1 - o(1)$。
我自己想了个比较朴素的思路:定义随机变量$X$来计数$G$中大小为$b+1$的独立集的数量,本来打算用马尔可夫不等式或者切尔诺夫界这类工具来估计,但推到一半就卡住了,不知道接下来该怎么处理这个随机变量的期望和概率上界。
有没有大佬能给我讲讲这个结论的证明思路,或者指点下我这个方法该怎么往下走呀?
备注:内容来源于stack exchange,提问作者Immanuel
相关产品推荐
相关产品推荐

