\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}

\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black}\end{quote}
}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}(#1)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ba}{\backslash}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\diam}[1]{\Diam\left(#1\right)}

\begin{document}
\title{Math 301: Homework 9}
\author{Mary Radcliffe}
\date{due 9 Dec 2016}
\maketitle

Complete the following problems. Fully justify each response. Turn in ONLY problems 1, 2, and 3.

\begin{enumerate}

\item Complete problem 14 from \href{http://people.math.gatech.edu/~trotter/book.pdf}{Applied Combinatorics} on page 125 (figure 6.18 is on page 126).

\item Complete problem 3 from \href{https://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch21.pdf}{Networks Crowds and Markets} on page 687 (literally the last page of the book)

\item Consider the Erd\H{o}s-R\'{e}nyi graph $G_{n, p}$, in the regime that $np = C\log n$, for $C$ constant.
\begin{enumerate}
\item Arbitrarily root $G$ at some vertex $v=v_0$. Consider the Galton-Watson branching process from $v_0$, allowing repetition of vertices on multiple levels. Define \[L_i=\{v\in V(G)\ | \ v\hbox{ appears on the $i^{\textrm{th}}$ level of the GW process}\},\]
so $L_0=\{v_0\}$, $L_1 = N(v_0)$, $L_2 = \{\hbox{vertices that can be reached by a walk of length 2 from } v_0\}$, etc.

Show that for any vertex $v\in V(G)$, $\p{v\in L_k} \geq n^{k-1}p^k$.

\item Use the above analysis to show that if $k>\frac{\log n+\log(C-1)}{\log(C)}$, then $\diam{G} \leq 2k$ with probability $1-o(1)$.
\end{enumerate}


\item Let $w=(w_1, w_2, \dots, w_n)$ be a degree sequence, and let $G=G(w)$ be the corresponding Chung-Lu random graph. Prove that with probability $1-o(1)$, we have $\deg(v_i)=w_i(1+o(1))$ for every vertex $v_i\in V(G)$.

\item Suppose you wish to model a proximity network, in which people whose homes are in geographic proximity are more likely to come into contact with one another. Why might a RGG not quite fulfill your needs? What tweaks could you make to the model to improve its usefulness?

\item Define a random graph as follows.
\begin{itemize}
\item Begin with a fixed graph $G$, where $G$ is the $n\times n$ integer lattice having $(x, y)\sim (w, z)$ if and only if the Hamming distance between $(x, y)$ and $(w, z)$ is exactly 1. (In other words, draw the integer grid. Treat each intersection as a node, and lines as edges between nodes.)

\item Fix some $m$, and randomly choose $m$ pairs of vertices in $G$ to add edges.
\end{itemize}
This graph, a variant on the Kleinberg Small World model, was originally developed by Watts and Strogatz.

\begin{enumerate}
\item What is the diameter of the $n\times n$ integer lattice?
\item Determine a bound on the diameter of the random graph produced by the above process (which should depend somewhat on $m$). 
\end{enumerate}



\end{enumerate}

\end{document}