Número de clique em gráficos aleatórios

11

Existe uma família de gráficos aleatórios G(n,p) com n nós ( devido a Gilbert ). Cada aresta possível é inserida independentemente em G(n,p) com probabilidade p . Seja Xk o número de cliques de tamanho k em G(n,p) .

Eu sei que , mas como faço para provar isso?E(Xk)=(nk)p(k2)

Como mostrar que para ? E como mostrar que para e uma constante fixa e arbitrária ?n E ( X c log 2 n ) 0 n c > 1E(Xlog2n)1nE(Xclog2n)0nc>1

user1374864
fonte

Respostas:

9

Então, basicamente, há três perguntas envolvidas.


Eu sei que , mas como faço para provar isso?E(Xk)=(nk)p(k2)

Você usa a linearidade da expectativa e algumas reescrições inteligentes. Primeiramente, observe que Agora, ao considerar a expectativa de , pode-se simplesmente extrair a soma (devido à linearidade) e obter Ao desenhar a soma, eliminamos todas as dependências possíveis entre subconjuntos de nós. Portanto, qual é a probabilidade de ser uma camarilha? Bem, não importa em que consiste, todas as probabilidades de ponta são iguais. Portanto,XkE(Xk)=T V ,

Xk=TV,|T|=k1[T is clique].
XkTTPr[T é clique]=p ( k
E(Xk)=TV,|T|=kE(1[T is clique])=TV,|T|=kPr[T is clique]
TT TE(Xk)=p ( kPr[T is clique]=p(k2), uma vez que todas as arestas deste subgráfico devem estar presentes. E então, o termo interno da soma não depende mais de , deixando-nos com .TE(Xk)=p(k2)TV,|T|=k1=(nk)p(k2)

Como mostrar isso para :E ( X log 2 n ) 1nE(Xlog2n)1

Não tenho muita certeza se isso está correto. Aplicando um limite no coeficiente binomial, obtemos

p-1+logn

E(Xlogn)=(nlogn)p(logn2)(nep(logn)4logn)logn=(nen(logp)/4logn)logn.
(Observe que limitei aproximadamente por .) No entanto, agora é possível escolher e obter essa , o que faz com que todo o termo vá para para grande . Talvez você esteja perdendo algumas suposições sobre ? plognp1+logn2plogn4p=0.001log20.0019.960np
HdM
fonte
Isso está certo? . Não precisa ser mas agora não sei como continuarE(Xlogn)=(nlogn)p(logn2)(nep(logn)4logn)logn
E(Xlogn)=(nlog2n)p(log2n2)(nelog2n)lognp(log2(n)e)24
user1374864
Apliquei o referido limite apenas em . Para , você pode observar que . Agora, desde , queremos reduzir seu expoente (convencer-se do porquê). Para razoavelmente grande , temos que . Portanto, o cálculo acima deve estar correto ...(nlogn)pp1N(registon)(logn-1)/2>(logn)2/4(logn2)=(logn)(logn1)/2p1n(logn)(logn1)/2>(logn)2/4
HdM
O que há com a terceira pergunta?
Fila
Sofre o mesmo problema que a segunda questão. Desculpe, eu deveria ter esclarecido isso.
HdM 28/05