HW4 .pdf

File information

Original filename: HW4.pdf

This PDF 1.5 document has been generated by TeX / pdfTeX-1.40.14, and has been sent on pdf-archive.com on 03/06/2014 at 20:40, from IP address 89.98.x.x. The current document download page has been viewed 525 times.
File size: 124 KB (1 page).
Privacy: public file

Download original PDF file

HW4.pdf (PDF, 124 KB)

Share on social networks

Link to this file download page

Document preview

Toegepaste Stochastiek
Homework assignment 4
Hand in before lecture of 12 June

Problem 4.1 (8 points). Prove that for every fixed ε > 0, there is a fixed λ > 0 such that the
following holds a.a.s.: for any two disjoint subsets of Gn,λ/n with at least εn vertices, there must
be an edge between them.
Problem 4.2 (7 points). Use a Chernoff bound1 to prove that the minimum and maximum
degrees of dense Erd˝
os-R´enyi random graphs satisfy the following inequalities. Assuming np =
ω(log n), then for any fixed ε > 0 it holds a.a.s. that (1 − ε)np ≤ δ(Gn,p ) and ∆(Gn,p ) ≤ (1 + ε)np.
Problem 4.3 (15 points, a:8 b:7). Recall that at each step of the preferential attachment
process, a new vertex of degree m is added, with each of its incident edges joined to the existing
graph independently at random with probability proportional to the existing degree distribution.
(a) Show that the preferential attachment process with m = x is equivalent to running the
preferential attachment process with m = 1 and then merging successive blocks of exactly x
(b) Prove that the degree of the ith vertex added in the preferential attachment process tends
to infinity a.a.s. as t → ∞.
Problem 4.4 (5 points). Prove that the total number of configurations on [m] (m even) is
(m − 1) · (m − 3) · · · 3 · 1.

1 Say, if X has binomial distribution with parameters n and p, then for any 0 < ε ≤ 3/2, Pr(|X − E(X)| ≥
E(X)) ≤ 2 exp(−ε2 E(X)/3)

Document preview HW4.pdf - page 1/1

Related documents

onlineadversarialmodelingappendix 1
graph theory and applications rev4
adaptive percolation daniel burkhardt cerigo

Link to this page

Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Short link

Use the short link to share your document on Twitter or by text message (SMS)


Copy the following HTML code to share your document on a Website or Blog

QR Code

QR Code link to PDF file HW4.pdf