What is the probability that a random graph contains an independent set of size at least j ?

Dear all,

i am looking for the probability that a graph has at least one
independent set of size j.

The graph is a random graph: we have V vertexes and an edge (i,k)
exist with probability x.

if i have a set of j vertexes, i can said that this set is an
independent set with probability (1-x)^(j*(j-1)/2).

so, i enumerate the number of sets of size j in my graph, and i
multiply by the probability that a set is an independent set:

binomial(V, j)*(1-x)^((1/2)*j*(j-1))

but, for exemple, when V=10, and x=0.2, i obtained 36.0.

Clearly, it cannot be a probability. I dont understand how i can
calculate the probability that a graph G(V,x) contains an independent
set.

Can you help me please?

thank you very much

Francois Delbot

.

Relevant Pages

  • Percolation theory
    ... I am a mathematician and don't know a whole lot about biology. ... This gives us an infinite graph, which we shall also call Z^n. ... with probability 1-p we delete the edge. ... probability that one genotype will produce a viable organism, ...
    (sci.bio.evolution)
  • Re: Fault-tolerant telephone trees
    ... > telephone (less than half the members have email). ... Random graph theory, specifically the problem where you have a graph ... where every edge uv has a probability of being in the ...
    (sci.math)
  • Re: Looking for feedback on two algorithm monographs
    ... You don't label the graph axes ... but each does half the work and the recursion ... Consider calling this algorithm on an array of two elements, ... What's the probability that 31 passes will be needed? ...
    (comp.programming)
  • Re: probability of connected graph
    ... What is the probability that G is connected, ... given that the union of E is S? ... Pis the probability that a n-vertex random graph ...
    (sci.math)
  • Re: combinatorics/graph theory problem for set partitions
    ... > that each edge is chosen independently with probability p, ... > Then I consider the set partition defined by this graph such that two ... > The motivation for this is to get a probability distribution on set ... > partitions of sets of a fixed size. ...
    (sci.math)