• No extension will be provided, unless for serious documented reasons.
• Start early!
• Study the material taught in class, and feel free to do so in small groups, but the solutions should be a product of your own work.
• This is not a multiple choice homework; reasoning, and mathematical proofs are required before giving your final answer.
1 G(n,p) [50 points]
1. (5pts) In the limit as n goes to infinity, how does (1 behave?
2. (5pts) How many labeled graphs on n nodes have exactly m edges, where 0
3. (10pts) Consider a graph G sampled from the G(n,p) model. Prove that conditioned on G having m edges, it is equally likely among all graphs that have m edges.
4. (10pts) Suppose that where c is a constant. Prove that the number of vertices of degree k is asymptotically equal to for any fixed positive integer k.
5. (10pts) Consider generating the edges of a random graph by flipping two coins, one with probability p1 of heads and the other with probability p2 of heads. For each pair of nodes add an edge between them if either of the coins comes down heads. Show that this is equivalent to generating a graph G from G(n,p) for an appropriate value of p. What is this value p?
6. (10pts) Consider G sampled from G(n,0.1). How does the Central limit theorem apply to the degree of any node in G? Specifically, within what range will the degree of a node lie with probability at least 99%?
2 Coding [50 points]
Check the Jupyter notebook on our Git repo.
1 of 1
