wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Triangles In Random Graphs
        
(Message started by: william wu on Oct 16^th, 2003, 12:00am)

Title: Triangles In Random Graphs
Post by william wu on Oct 16^th, 2003, 12:00am

Imagine a graph of n nodes whose edges are randomly generated as follows: for every two nodes, the probability there exists an edge connecting those two nodes is p.

What is the probability that there exists a triangle of edges in the graph? (A "triangle" is strictly a set of three edges whose endpoints form the corners of the same triangle.)

Disclaimer: I only know how to get a "dumb" upper bound, and a nice lower bound. The lower bound uses a relatively unknown idea, not taught in most probability courses; I'll be happy to present it later if someone doesn't anticipate it.

Edit: 4:46 AM 10/16/2003 Clarified what a triangle is.

Title: Re: Triangles In Random Graphs
Post by towr on Oct 16^th, 2003, 3:02am

if you take any three random nodes there's a p³ chance they form a triangle. So there's a (1-p³) they don't. The chance that there isn't any triangle would thus be (1-p³)^k, where k is the number of sets of three nodes, which for n nodes is n*(n-1)*(n-2)/6
so the chance that there exists at least one triangle would be 1 - (1-p³)^{n*(n-1)*(n-2)/6}

Assuming I didn't make a mistake this is the right answer. If however I did make a mistake, it might still be the right answer, but it wouldn't be justified, and probably it'd be just wrong..

Title: Re: Triangles In Random Graphs
Post by wowbagger on Oct 16^th, 2003, 3:39am

on 10/16/03 at 03:02:29, towr wrote:

There could still be a triangle you missed. Namely, one that uses four or more edges, some of which are connected forming a straight line.
Maybe William would call your solution "dumb".

Title: Re: Triangles In Random Graphs
Post by towr on Oct 16^th, 2003, 3:55am

I wouldn't call that a triangle..
Besides the probability of three nodes lying on a line is zero except for very specific pdf's for the distribution of the nodes over the (unspecified) space they lie in.

Title: Re: Triangles In Random Graphs
Post by wowbagger on Oct 16^th, 2003, 4:06am

on 10/16/03 at 03:55:11, towr wrote:

I wouldn't call that a triangle..

Guess I would. It has three (straight) sides touching in three vertices, thus forming three angles. That's what I call a triangle.
You're right about the probability of something like this occuring, though.

Title: Re: Triangles In Random Graphs
Post by william wu on Oct 16^th, 2003, 4:45am

wowbagger: We tend to think of our graphs not as diagrams pressed onto a 2d space, but more of an abstract, flexible wireframe that can be twisted about in any manner while still preserving the edge-dictated relationships between certain nodes. That is, the important aspect of a graph representation is simply how nodes are connected. So a "triangle" is strictly a set of three edges whose endpoints form the corners of the same triangle.

I'm afraid towr's solution doesn't work because it assumes that the probability of one triplet of nodes forming a triangle is independent of some other triplet of nodes forming a triangle. Consider a graph with four nodes: call them a b c and d. Now suppose you know that a b and c form the corners of a triangle. This knowledge affects the probability that the bcd triplet forms a triangle -- in fact it increases the probability. Since b and c already have an edge between them, you just need the edges (b,d) and (c,d) to complete the bcd triangle. So the conditional probability is p², as opposed to p³. Now consider a much arger graph of n nodes, and the dependencies between triplets becomes increasingly apparent and complicated.

Title: Re: Triangles In Random Graphs
Post by towr on Oct 16^th, 2003, 8:21am

hmm.. yes dependence.. I thought that might be a problem, but it's so much easier when you just ignore it ;)

so far, for n=3,4,5 , I have:
p^3
3·p^6 - 6·p^5 + 4·p^3
- 4·p^10 + 30·p^9 - 75·p^8 + 70·p^7 - 30·p^5 + 10·p^3

but I haven't really found an easy pattern.. the number of possibilities with increasing n is rather larger..

Title: Re: Triangles In Random Graphs
Post by Barukh on Oct 16^th, 2003, 10:59am

The so called Probabilistic Method deals with problems like this. This method is relative new, it was originated by Paul Erdos, and may be used to find many elegant solutions for combinatorial problems.

I've got a copy of a book "The Probabilistic Method" by Noga Alon and Joel H. Spencer. It's not an easy reading; but the section 10.1 addresses the discussed problem. If my understanding is correct, the approach is as follows: let c = p/n. For a fixed c, the probability that there are no triangles in a graph asymptotically (when n tends to [infty]) approaches the probability of no triangles assuming the independence of the triplets, that is towr's formula. The latter, as n->[infty], is e^(-c³/6).

But probably all this is not relevant or bad understanding.

If somebody is interested in the aforementioned book, let me know; I'll try to locate the softcopy of pre-printed version.

Title: Re: Triangles In Random Graphs
Post by william wu on Oct 16^th, 2003, 11:39am

When I was lectured on the probabilistic method, we only used it in existence proofs. If I show the probability of a certain desired object is greater than 0, I know that object exists. Alternatively, if I show that the expectation of a random variable X is equal to a certain desired threshold value K, then I have demonstrated there exist outcomes [omega] in the event space such that X([omega]) either meets or exceeds the threshold, and this could be great to know in the context of K being some specification in a design problem. (As a famous example, Shannon used such arguments to promise the existence of block codes that allow information transmission at rates below channel capacity with an arbitrarily small probability of error, if the block length is large enough.)

Outside of existence proofs, I'm not sure how the probabilistic method applies to actually computing closed-form probabilities, as desired in this problem. If we only want asymptotic bounds, then assuming p=c/n, I can use Markov inequality and my "to-be-revealed" inequality to show that as n[to][infty], the Probability of a triangle is sandwiched respectively between c³/6 and (c³/6)/(1 + c³/6). This is news to me if this sort of analysis also falls under the umbrella of techniques known as "the probabilistic method."

Title: Re: Triangles In Random Graphs
Post by pjay on Dec 2^nd, 2003, 10:01am

this seems like a very hard problem- in fact a research level problem. If someone gets a full answer to this it can almost surely be pulished. I have a feeling this or something close to it has probably been answered in the mathematics literature since it is very closely related to something called connectivity of graphs. The best place to look is a book by bollobas. I think it's called graph theory- it's in the springer series. Another option is to search the mathsci net for "erdos-renyi random graph". one last comment. the number of triangles divided by n is called the connectivity constant (for any random graph, not just the erdos-renyi one described in the problem). it is studied when analyzing the six-degrees of separation issue. if you want to pursue this search for the watts-strogatz small world model.