Re: probability of connected graph

On Jan 4, 8:35 am, Allan Adler <a...@xxxxxxxxxxxxxxxxxxxx> wrote:
Let n be a positive integer. Let E be a set of 2-element subsets of an
n-element set S such that the union of E is S. We can regard (E,S) as a
a graph G with n vertices. What is the probability that G is connected,
as a function of n, given that the union of E is S?

I don't know whether that is known or not. But in any case, maybe one
can prove that the probability converges to 1 at a certain rate as n
goes to infinity. Is there anything known along those lines?

You have to make precise in what sense you are taking
probabilities, but for the standard model in which you
pick 0 < p < 1 and each edge is in the graph with
probability p, independently of the other edges, one
can show without much work that almost all graphs are
connected (even k-connected, for fixed k): that is, if
P(n) is the probability that a n-vertex random graph
(selected from the above distribution) is connected,
then lim P(n) = 1. See, e.g., corollary 11.3.3 in
R. Diestel's `Graph Theory.'

One can be precise about rates of convergence, different
probability models and so on, You should consult a text
on graph theory: any modern text should have at least a
chapter on `random graphs'.

HTH,

-- m
.

Relevant Pages

  • Re: probability of connected graph
    ... a graph G with n vertices. ... What is the probability that G is connected, ... given that the union of E is S? ... If one starts out by with a finite set by connecting edges ...
    (sci.math)
  • 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: probability of connected graph
    ... a graph G with n vertices. ... What is the probability that G is connected, ... given that the union of E is S? ...
    (sci.math)
  • 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)