Difference between revisions of "CATS-Oct-17-2014"
| (One intermediate revision by the same user not shown) | |||
| Line 7: | Line 7: | ||
== Abstract == | == Abstract == | ||
| − | I will talk about some of the statistical properties of the G(n,p) graph model, due to Erdos and Renyi. This model has two parameters: the number of vertices (n), and the edge probability (p). For each pair of vertices, u and v, p is the probability that the edge (u,v) is present, independent of all other edges. | + | I will talk about some of the statistical properties of the G(n,p) graph model, due to Erdos and Renyi.<br/> |
| + | This model has two parameters: the number of vertices (n), and the edge probability (p). For each pair of vertices, u and v, p is the probability that the edge (u,v) is present, independent of all other edges. | ||
We will show that such a random graph has many interesting global properties. Namely: | We will show that such a random graph has many interesting global properties. Namely: | ||
| − | (1) When p=d/n for some constant d, the number of triangles in G(n,p) is independent of n. | + | |
| − | (2) The property that G(n,p) has diameter two has a sharp threshold at p = \sqrt(\dfrac{2\ln n}{n}). | + | (1) When p=d/n for some constant d, the number of triangles in G(n,p) is independent of n.<br/> |
| − | (3) The disappearance of isolated vertices in G(n,p) has a sharp threshold at p = \dfrac{\ln n}{n}. | + | (2) The property that G(n,p) has diameter two has a sharp threshold at p = \sqrt(\dfrac{2\ln n}{n}).<br/> |
| + | (3) The disappearance of isolated vertices in G(n,p) has a sharp threshold at p = \dfrac{\ln n}{n}. <br/> | ||
(4) When p=d/n, d > 1, there is a giant component consisting of a constant fraction of the vertices. | (4) When p=d/n, d > 1, there is a giant component consisting of a constant fraction of the vertices. | ||
I will be covering material from the following book: http://www.cs.cornell.edu/jeh/book11April2014.pdf | I will be covering material from the following book: http://www.cs.cornell.edu/jeh/book11April2014.pdf | ||
Latest revision as of 18:21, 15 October 2014
Title[edit]
Random Graphs
Speaker[edit]
Amit Chavan
Abstract[edit]
I will talk about some of the statistical properties of the G(n,p) graph model, due to Erdos and Renyi.
This model has two parameters: the number of vertices (n), and the edge probability (p). For each pair of vertices, u and v, p is the probability that the edge (u,v) is present, independent of all other edges.
We will show that such a random graph has many interesting global properties. Namely:
(1) When p=d/n for some constant d, the number of triangles in G(n,p) is independent of n.
(2) The property that G(n,p) has diameter two has a sharp threshold at p = \sqrt(\dfrac{2\ln n}{n}).
(3) The disappearance of isolated vertices in G(n,p) has a sharp threshold at p = \dfrac{\ln n}{n}.
(4) When p=d/n, d > 1, there is a giant component consisting of a constant fraction of the vertices.
I will be covering material from the following book: http://www.cs.cornell.edu/jeh/book11April2014.pdf
