You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

随机图中独立数的渐近上界证明求助

随机图中独立数的渐近上界证明求助

最近我在学随机图的相关内容,卡在了一个据说很经典的结论上——翻了不少资料都没找到证明,自己推导也卡壳了,想请教下大家!

问题是这样的:
给定整数$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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.16 08:18:01