FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Probabilistic Method Question (Palmer: Graphical Evolution)
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
Author Message
Rob
science forum beginner


Joined: 20 Jun 2005
Posts: 44

PostPosted: Mon Nov 21, 2005 9:31 pm    Post subject: Probabilistic Method Question (Palmer: Graphical Evolution) Reply with quote

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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [1 Post] View previous topic :: View next topic
The time now is Mon Jun 26, 2017 3:38 am | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0272s ][ Queries: 16 (0.0109s) ][ GZIP on - Debug on ]