Author |
Topic: Triangles In Random Graphs (Read 7839 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Triangles In Random Graphs
« on: Oct 16th, 2003, 12:00am » |
 Quote  Modify
|
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.
|
| « Last Edit: Oct 16th, 2003, 4:46am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangles In Random Graphs
« Reply #1 on: Oct 16th, 2003, 3:02am » |
Quote Modify
|
if you take any three random nodes there's a p3 chance they form a triangle. So there's a (1-p3) they don't. The chance that there isn't any triangle would thus be (1-p3)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-p3)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..
|
| « Last Edit: Oct 16th, 2003, 3:04am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Triangles In Random Graphs
« Reply #2 on: Oct 16th, 2003, 3:39am » |
Quote Modify
|
on Oct 16th, 2003, 3:02am, towr wrote:if you take any three random nodes there's a p3 chance they form a triangle. So there's a (1-p3) they don't. The chance that there isn't any triangle would thus be (1-p3)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-p3)n*(n-1)*(n-2)/6 |
|
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".
|
| « Last Edit: Oct 16th, 2003, 3:39am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangles In Random Graphs
« Reply #3 on: Oct 16th, 2003, 3:55am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 16th, 2003, 3:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Triangles In Random Graphs
« Reply #4 on: Oct 16th, 2003, 4:06am » |
Quote Modify
|
on Oct 16th, 2003, 3:55am, 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.
|
| « Last Edit: Oct 16th, 2003, 4:07am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Triangles In Random Graphs
« Reply #5 on: Oct 16th, 2003, 4:45am » |
Quote Modify
|
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 p2, as opposed to p3. Now consider a much arger graph of n nodes, and the dependencies between triplets becomes increasingly apparent and complicated.
|
| « Last Edit: Oct 16th, 2003, 4:54am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Triangles In Random Graphs
« Reply #6 on: Oct 16th, 2003, 8:21am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Triangles In Random Graphs
« Reply #7 on: Oct 16th, 2003, 10:59am » |
Quote Modify
|
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^(-c3/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.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Triangles In Random Graphs
« Reply #8 on: Oct 16th, 2003, 11:39am » |
Quote Modify
|
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 c3/6 and (c3/6)/(1 + c3/6). This is news to me if this sort of analysis also falls under the umbrella of techniques known as "the probabilistic method."
|
| « Last Edit: Oct 16th, 2003, 11:43am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
pjay
Newbie
Gender:
Posts: 30
|
|
Re: Triangles In Random Graphs
« Reply #9 on: Dec 2nd, 2003, 10:01am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print