平均度为1的随机图的最大连通块大小

KeyTo9_Fans

在顶点数为$2n$的完全图中随机取$n$条边，得到的图记为$G$。

于是图$G$有$2n$个顶点，$n$条边，顶点的平均度为$1$。

设$G'$是$G$中最大的连通块（顶点数最多的连通子图）。

我们将$G'$的顶点个数的平均值记为$g$。

问题$1$：

给定$n=1,2,3,...$，求$g$的值。

问题$2$：

求证：$\lim_{n->\infty}ln(g)/ln(n)=2/3$

问题$3$：

求$\lim_{n->\infty}g^{1.5}/n$等于多少？

#####

当时论坛人少，现在人多了，我让我的朋友jsliyuan把这贴子重新顶起来，以获得更多坛友们的关注~

如果还是做不出来，我还可以去Math Overflow社区提问呀~

jsliyuan

顶一下

hujunhua

G有n条边是确定的，但咋肯定有2n个顶点呢

mathe

可以先看一看每个点上关联多少条边。
对于任意一条边，不使用某个指定的点的概率是${C_{2n-1}^2}/{C_{2n}^2}={n-1}/n$
所以对于一个指定的点，和其关联的边的数目为k的概率是$P(d(v)=k)=C_n^k ({n-1}/n)^{n-k}(1/n)^k$
然后采用极大似然估计，可以估算出关联边数最多的点关联的边的数目接近$\sqrt{2\ln(n)}$

kastin

这道题让我想到了那个连通图问题以及后面的渐近计数
https://bbs.emath.ac.cn/thread-9662-1-1.html

本质上要分析出2n个点中n条边构成的简单图中连通图的种类，以及非连通图中最大连通子图的顶点数分布。然后根据计数来计算平均值。
不过这种变递归长度的递归式如何对其结果渐近分析？