Liczba klik na losowych wykresach

11

Istnieje rodzina losowych wykresów G(n,p) z węzłami n ( ze względu na Gilberta ). Każda możliwa krawędź jest niezależnie wstawiana do G(n,p) z prawdopodobieństwem p . Niech Xk będzie liczbą klik o rozmiarze k w G(n,p) .

Wiem, że , ale jak to udowodnić?E(Xk)=(nk)p(k2)

Jak pokazać, że E(Xlog2n)1 dla n ? I jak pokazać, że E(Xclog2n)0 dla n i stałej, arbitralnej stałej c>1 ?

użytkownik1374864
źródło

Odpowiedzi:

9

Zasadniczo wiążą się z tym trzy pytania.


Wiem, że E(Xk)=(nk)p(k2) , ale jak to udowodnić?

Korzystasz z liniowości oczekiwań i sprytnego przepisywania. Przede wszystkim zwróć uwagę, że Teraz, biorąc pod uwagę oczekiwanie na , można po prostu wyciągnąć sumę (z powodu liniowości) i uzyskać Wyciągając sumę, wyeliminowaliśmy wszystkie możliwe zależności między podzbiorami węzłów. Jakie jest zatem prawdopodobieństwo, że jest kliką? Cóż, bez względu na to, z czego składa się , wszystkie prawdopodobieństwa krawędzi są równe. DlategoXkE(Xk)=T V ,

Xk=TV,|T|=k1[T is clique].
XkTTPr[T to klika]=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), ponieważ wszystkie krawędzie tego podgrafu muszą być obecne. I wtedy wewnętrzny warunek sumy nie zależy już od , pozostawiając nam .TE(Xk)=p(k2)TV,|T|=k1=(nk)p(k2)

Jak to pokazać dla :E ( X log 2 n ) 1nE(Xlog2n)1

Nie jestem do końca pewien, czy jest to w ogóle poprawne. Stosując ograniczenie do współczynnika dwumianowego, otrzymujemy

E(Xlogn)=(nlogn)p(logn2)(nep(logn)4logn)logn=(nen(logp)/4logn)logn.
(Zauważ, że z grubsza górną granicę przez .) Jednak teraz można wybrać i uzyskać to , co powoduje, że cały termin przechodzi do dla dużej . Czy może brakuje Ci niektórych założeń dotyczących ?p1+logn2plogn4p=0.001log20.0019.960np
HdM
źródło
Czy to prawda? . Czy to nie musi być ale teraz nie wiem, jak to kontynuowaćE(XlogE(Xlogn)=(nlogn)p(logn2)(nep(logn)4logn)logn
E(Xlogn)=(nlog2n)p(log2n2)(nelog2n)lognp(log2(n)e)24
użytkownik1374864
Zastosowałem wspomniane ograniczenie tylko w . W przypadku można zauważyć, że . Teraz od chcemy zmniejszyć jego wykładnik (przekonaj się dlaczego). Dla rozsądnie dużego mamy to . Dlatego powyższe obliczenia powinny być poprawne ...p(nlogn)ps1n(logn)(logn-1)/2>(logn)2/4(logn2)=(logn)(logn1)/2p1n(logn)(logn1)/2>(logn)2/4
HdM
Co jest z trzecim pytaniem?
Kolejka
Ma ten sam problem, co drugie pytanie. Przepraszam, powinienem to wyjaśnić.
HdM