Search   Memberlist   Usergroups
 Page 1 of 1 [1 Post]
Author Message
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 k-set 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 k-sets in almost all graphs?

I'm having a problem with this in the following way: Let X(G) be the
number of k-bad sets in a graph G. I've found E(X):

E(X) = (n choose k) (1 - p^k)^{n-k}

(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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [1 Post]
 The time now is Sun Feb 17, 2019 1:42 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Question about Life. socratus Probability 0 Sun Jan 06, 2008 10:01 pm Probability Question dumont Probability 0 Mon Oct 23, 2006 3:38 pm Probabilistic Combinatorics Notes Help Sundus Math 0 Fri Jul 21, 2006 11:27 am Question about exponention WingDragon@gmail.com Math 2 Fri Jul 21, 2006 8:13 am question on solartron 1260 carrie_yao@hotmail.com Electrochem 0 Fri Jul 21, 2006 7:11 am