Rob science forum beginner
Joined: 20 Jun 2005
Posts: 44

Posted: Mon Nov 21, 2005 9:31 pm Post subject:
Probabilistic Method Question (Palmer: Graphical Evolution)



E. Palmer: Graphical Evolution (1985(?)) (< are there solutions
available to this anywhere?)
2.3.5: A kset S of vertices is bad if no other vertex is adjacent to
each vertex of S. In Model A (G(n,p)) with p fixed, how fast can k
grow so that we still have no bad ksets in almost all graphs?
I'm having a problem with this in the following way: Let X(G) be the
number of kbad sets in a graph G. I've found E(X):
E(X) = (n choose k) (1  p^k)^{nk}
(and E(X) > 0 for k fixed). But, what I can't figure out is the
remaining part: how fast can k grow so that E(X) still goes to 0? I
plugged the think into maple, and tried a bunch of functions for k. It
looks like polynomials wont do it, and it looks like k(n) = ln n works
(E(X) still goes to 0 as n goes to infinity), but even with this
knowledge, I cant prove that E(X) goes to 0 with k(n) = ln n.
I'm not looking for an answer...just a hint if anyone could suggest
one. There should be a way to take E(X), and, assuming it goes to 0,
prove that k must be o(g(n)), or O(g(n)) or something like that.
Rob 
