随机图中的完全子图

KeyTo9_Fans

图$G$是一个包含$N$个顶点的无向图。 对于任意一对顶点$(u,v)$，有边的概率是$50%$，且相互独立。 我们希望$G$中存在$K$个顶点的完全子图的概率至少为$50%$。 求顶点数$N$至少是多少。 例$1$：当$K=1$时，$N=1$，存在$1$个顶点的完全子图的概率为$100%$。 例$2$：当$K=2$时，$N=2$，存在$2$个顶点的完全子图的概率为$50%$。 当$K$比较大的时候，如何找最小的$N$，使得$G$中存在$K$个顶点的完全子图的概率至少为$50%$？

KeyTo9_Fans

写了一个生成随机图的程序和一个搜寻完全子图的程序，求得前面几项的结果如下。

  K   N   概率
  1   1    1
  2   2    0.5
  3   5    0.62109375
  4   9    0.6151...
  5  14   0.521...
  6  22   0.510...
  7  34   0.523...
  8  51   0.51...
  9  76   0.50...
10 113  0.50...
11 168  0.50...
12 250  0.51...
13 371  0.50...
14 553  0.50...

参考数列（第6、7、8、9项相同）：
http://oeis.org/search?q=22%2C34%2C51%2C76

本数列：
Minimum m such that the probability that there is a clique with size n in the Erdos-Renyi random graph with m vertices and parameter p=0.5 is at least 0.5
1, 2, 5, 9, 14, 22, 34, 51, 76, 113, 168, 250, 371, 553

数列的增长速度竟然是$\Theta(1.5^K)$，不是$\Theta(2^K)$，出乎意料

mathe

你可以使用GNU的igraph看看

KeyTo9_Fans

根据楼上的提示，安装了igraph，然后写了下面的代码：

1. #include <stdio.h>
   
2. #include "igraph.h"
   
3. 
   
4. int main()
   
5. {
   
6.         igraph_rng_seed(igraph_rng_default(), 42);
   
7.         while (1)
   
8.         {
   
9.                 igraph_integer_t cn;
   
10.                 igraph_t graph;
    
11.                 igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNP, 168, 0.5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
    
12.                 igraph_clique_number(&graph, &cn);
    
13.                 printf("%d ", (int)cn);
    
14.                 igraph_destroy(&graph);
    
15.         }
    
16.         return 0;
    
17. }

复制代码

代码虽短，但是运行效率堪忧呀~

当$N=168$时，我自己写的代码$0.9$秒就能跑$1$个图，上述代码要$2.0$秒才能跑$1$个图……

我自己写的代码如下：

1. #include<ctime>
   
2. #include<cstdio>
   
3. #include<cstdlib>
   
4. #include<cstring>
   
5. 
   
6. const int n=249,d=n+31>>5;
   
7. 
   
8. unsigned int a[n][d],todo[d],done[d];
   
9. unsigned __int64 g,h,p,q;
   
10. unsigned char i,j,s;
    
11. 
    
12. unsigned char rd()
    
13. {
    
14.         g=g*g/3+h+rand();
    
15.         return(g&32767)>>14;
    
16. }
    
17. 
    
18. void ad(unsigned char i,unsigned char j)
    
19. {
    
20.         a[i][j>>5]|=1<<(j&31);
    
21.         a[j][i>>5]|=1<<(i&31);       
    
22. }
    
23. 
    
24. unsigned char r(unsigned int p)
    
25. {
    
26.         for(unsigned char i=0;;i++)
    
27.                 if(p&1<<i)return i;
    
28. }
    
29. 
    
30. void mce(unsigned char c,unsigned int *todo,unsigned int *done)
    
31. {
    
32.         unsigned char i,j,k;
    
33.         unsigned int doing[d];
    
34.         for(i=0;i<d;i++)
    
35.                 if(todo[i]||done[i])
    
36.                 {
    
37.                         i=i<<5|r(todo[i]?todo[i]:done[i]);
    
38.                         for(j=0;j<d;j++)
    
39.                                 doing[j]=~a[i][j]&todo[j];
    
40.                         for(j=0;j<n;j++)
    
41.                         {
    
42.                                 unsigned char jh=j>>5;
    
43.                                 unsigned int jl=1<<(j&31);
    
44.                                 if(doing[jh]&jl)
    
45.                                 {
    
46.                                         todo[jh]&=~jl;
    
47.                                         unsigned int nt[d],nd[d];
    
48.                                         for(k=0;k<d;k++)
    
49.                                                 nt[k]=todo[k]&a[j][k],nd[k]=done[k]&a[j][k];
    
50.                                         mce(c+1,nt,nd);
    
51.                                         done[jh]|=jl;
    
52.                                 }
    
53.                         }
    
54.                         return;
    
55.                 }
    
56.         if(c>s)s=c;
    
57. }
    
58. 
    
59. int main()
    
60. {
    
61.         for(g=time(NULL),srand(g);;memset(a,0,sizeof(a)))
    
62.         {
    
63.                 for(i=0;i<n-1;i++)
    
64.                         for(j=i+1;j<n;j++)
    
65.                                 if(rd())ad(i,j);
    
66.                 for(i=0;i<n;i++)
    
67.                         todo[i>>5]|=1<<(i&31);
    
68.                 mce(0,todo,done);
    
69.                 p+=s>11,q++,s=0;
    
70.                 if(q%2<1)printf("%I64u %I64u %c",p,q,13),h+=time(NULL)+p;
    
71.         }
    
72.         return 0;
    
73. }

复制代码

mathe

$C_N^K \frac{1}{2^{C_K^2}} ~=1/2$
$C_N^K~=2^{C_K^2-1}$
$N~=\root{K}{2^{C_K^2-1}K!}~=K/e\sqrt{2}^{K+1}$
然后可以查看对于这种逼近，K+1个点完全图的概率大概为$C_N^{K+1}\frac{1}{2^{C_{K+1}^2}}~=N/{K2^K}C_N^K \frac{1}{2^{C_K^2}}~=N/{K2^{K+1}}~=1/{e\sqrt{2}^{K+1}}->0$
所以对于比较大的K,这个近似值应该是可以的

KeyTo9_Fans

虽然该数列的第$6$、$7$、$8$、$9$项与参考数列相同，

但是该数列从第$10$项起，增长速度比参考数列慢，而且与参考数列的差距越来越大，

说明用$\Theta(1.5^K)$来近似该数列，还是高估了它的增长速度。

用楼上分析得到的$\Theta(\sqrt{2}^K)$来近似该数列更靠谱。