Author 
Topic: Triangles In Random Graphs (Read 6604 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Triangles In Random Graphs
« on: Oct 16^{th}, 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 16^{th}, 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: 13595


Re: Triangles In Random Graphs
« Reply #1 on: Oct 16^{th}, 2003, 3:02am » 
Quote Modify

if you take any three random nodes there's a p^{3} chance they form a triangle. So there's a (1p^{3}) they don't. The chance that there isn't any triangle would thus be (1p^{3})^{k}, where k is the number of sets of three nodes, which for n nodes is n*(n1)*(n2)/6 so the chance that there exists at least one triangle would be 1  (1p^{3})^{n*(n1)*(n2)/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 16^{th}, 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 16^{th}, 2003, 3:39am » 
Quote Modify

on Oct 16^{th}, 2003, 3:02am, towr wrote:if you take any three random nodes there's a p^{3} chance they form a triangle. So there's a (1p^{3}) they don't. The chance that there isn't any triangle would thus be (1p^{3})^{k}, where k is the number of sets of three nodes, which for n nodes is n*(n1)*(n2)/6 so the chance that there exists at least one triangle would be 1  (1p^{3})^{n*(n1)*(n2)/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 16^{th}, 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: 13595


Re: Triangles In Random Graphs
« Reply #3 on: Oct 16^{th}, 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 16^{th}, 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 16^{th}, 2003, 4:06am » 
Quote Modify

on Oct 16^{th}, 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 16^{th}, 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 16^{th}, 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 edgedictated 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^{2}, as opposed to p^{3}. Now consider a much arger graph of n nodes, and the dependencies between triplets becomes increasingly apparent and complicated.

« Last Edit: Oct 16^{th}, 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: 13595


Re: Triangles In Random Graphs
« Reply #6 on: Oct 16^{th}, 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 16^{th}, 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^(c^{3}/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 preprinted version.


IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Triangles In Random Graphs
« Reply #8 on: Oct 16^{th}, 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 closedform probabilities, as desired in this problem. If we only want asymptotic bounds, then assuming p=c/n, I can use Markov inequality and my "toberevealed" inequality to show that as n[to][infty], the Probability of a triangle is sandwiched respectively between c^{3}/6 and (c^{3}/6)/(1 + c^{3}/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 16^{th}, 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 2^{nd}, 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 "erdosrenyi random graph". one last comment. the number of triangles divided by n is called the connectivity constant (for any random graph, not just the erdosrenyi one described in the problem). it is studied when analyzing the sixdegrees of separation issue. if you want to pursue this search for the wattsstrogatz small world model.


IP Logged 



