Re: combinatorics/graph theory problem for set partitions

From: Rob Pratt (Rob.Pratt_at_sas.com)
Date: 08/11/04 

Date: Wed, 11 Aug 2004 13:19:29 -0400

"Faheem Mitha" <faheem@email.unc.edu> wrote in message
news:slrnchiff8.rsk.faheem@Chrestomanci.home.earth...
> Dear People,
>
> I have a question which is both combinatorial and (possibly)
> graph-theoretical, which arises from a modelling problem.
>
> Consider n vertices. Then there are $\binom{n}{2} = \frac{n(n-1)}{2}$
> edges that can connect these n vertices.
>
> Suppose I construct a random graph by choosing k edges in such a way
> that each edge is chosen independently with probability p, where p is
> small.
>
> Then I consider the set partition defined by this graph such that two
> vertices i and j are in the same partition iff they are connected by
> some sequence of edges.
>
> The motivation for this is to get a probability distribution on set
> partitions of sets of a fixed size. It is clear that the above recipe
> defines one. However, it is less clear for a given model M how to
> compute its probability P(M). This seems to involve adding up the
> probabilities over all graphs that give rise to a particular M, which
> might be a hard problem. Does anyone know if there is a known answer
> for this? I don't need a closed form solution. A recursive algorithm
> would work fine.
>
> I'd be interested to hear of other probability distributions on set
> partitions. The reason for this particular construction is to find a
> distribution which makes larger subsets less likely, and does so in a
> way that seems reasonable in the context. In this case, the partitions
> correspond to sets of correlated variables.
>
> I did a Google search along those lines, but could not find much.
>
> Faheem.

Greetings from a former classmate!

I haven't thought too much about your problem, but you will have better luck
in your search if you use the phrases "random graph" and "connected
components" (your set partitions).

Also, it turns out that "almost all" graphs have diameter two and hence are
connected (have one connected component).

Rob Pratt

Relevant Pages

  • combinatorics/graph theory problem for set partitions
    ... which arises from a modelling problem. ... The motivation for this is to get a probability distribution on set ... partitions of sets of a fixed size. ...
    (sci.stat.math)
  • combinatorics/graph theory problem for set partitions
    ... which arises from a modelling problem. ... The motivation for this is to get a probability distribution on set ... partitions of sets of a fixed size. ...
    (sci.math.research)
  • combinatorics/graph theory problem for set partitions
    ... which arises from a modelling problem. ... The motivation for this is to get a probability distribution on set ... partitions of sets of a fixed size. ...
    (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: 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)