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

In article <see-A0418E.09461020092007@xxxxxxxxxxxxxxx>,
Barb Knox <see@xxxxxxxxx> wrote:

In article <1190217336.136399.45930@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Francois Delbot <francois.delbot@xxxxxxxxx> wrote:

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).

The error there is that it assumes the independence of each edge is a
probabilistically independent event. It isn't. For a blatant example,
when j = V + 1 (i.e. more than the maximum possible number of vertices)
then that formula still gives a probability > 0.


The probability that there are exactly k unused edges in the graph, for
k <= V*(V-1)/2, is
binomial(V*(V-1)/2, k) * (1-x)^k * x^(V*(V-1)/2 - k).
Call this P_unused(k).

For a given k, you have j*(j-1)/2 unordered edges, out of k possible
independent (i.e. unused) ones. So there are binomial(k, j*(j-1)/2)
different ways to assign them. There are a total of 2^(V*(V-1)/2)
possible unordered graphs with V vertices. So the independent ones
occur in that population with the probability
binomial(k, j*(j-1)/2) / 2^(V*(V-1)/2).
Call this P_ind(k).

Then the total probability over all k is the sum for k <= V*(V-1)/2 of
P_unused(k) * P_ind(k).


Oh bother, this analysis is incorrect. Spot the error.


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



--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
.

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: What is the probability that a random graph contains an independent set of size at least j ?
    ... i am looking for the probability that a graph has at least one ... The graph is a random graph: we have V vertexes and an edge ... The probability that there are exactly k unused edges in the graph, ... For a given k, you have j*/2 unordered edges, out of k possible ...
    (comp.theory)
  • 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)