
%\usetikzlibrary{arrows}
%\usepackage{algorithmic}


\documentclass[10pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\usepackage{algorithm}
\usepackage{listings}
\usepackage{tikz}
%
%\usepackage{amsmath}
\usepackage[noend]{algpseudocode}
\usetikzlibrary{calc}
\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{4}{February 23, 2017}{Ronitt Rubinfeld}{Laura Gustafson}

\section*{Overview}
\begin{itemize}
  \item K-round Distributed Algorithms
  \item Parnas-Ron Framework
  \item Distributed Sub-Linear Time Vertex Cover
  \item Oracle Reduction Framework
  \item Sub-Linear Time Maximal Matching
\end{itemize}
\section{Relationship between Distributed and Sub-linear Algorithms}
We want to take advantage of the work done in distributed algorithms and apply it to sub-linear algorithms.  Why? We want to take advantage of the work we can do in a constant $k$ rounds.
\subsection{K-round Distributed Algorithms}
In distributed algorithms, there is no separate input network and distributing network. The network that you want to determine vertex cover on (for example) is the distributed network.
\subsection{Vertex Cover}
The goal for our algorithm is that after some constant $k$ rounds, every node will know whether or not it is a part of the vertex cover of the network. This algorithm will have $d^k$ query complexity where $d$ is the maximum degree. The first thing to consider is what would I send to my neighbors in 1 step (ie round 1). To determine this, I can look at my neighbors input and figure out what they would send. After two rounds, I could have received messages from my all of my neighbors and figured out how to combine what they sent me.  After a total of $k$ steps, I can only receive mail from within a $k$-ball (i.e. all nodes within a $k$-radius of me).  Any nodes outside of the $k$-ball do not influence me.  Therefore, we only need to look within the $k$-ball of a node for vertex cover. For vertex cover, we will make $d^k$ queries, and will have an oracle that will let us compute whether or not I am in the vertex cover.

\subsection{Parnas-Ron Framework}
This distributed algorithms framework has been used for multiple problems (maximum matching, coloring problems). The idea is shown in Algorithm 1.
\begin{algorithm}
\caption{Parnas-Ron Framework}\label{euclid}
\begin{algorithmic}[0]
\Procedure{ParnasRonFramework}{}
\State $\textit{sample nodes   } v_1 ... v_r $
\ForAll {$v_i$}
    \State $\textit{simulate distributed algorithm to see if } v_i \in VC$
\EndFor
\State $\textbf{Output: } \frac{\# v_i \in VC}{r} \cdot n $

\EndProcedure
\end{algorithmic}
\end{algorithm}

The run-time of this algorithm is $r\cdot d^{k+1}$. Using Chernoff bounds, we find that we will sample $r \approx O( \frac{1}{\epsilon^2})$.

\subsection{Distributed Algorithm for Vertex Cover}
\textit{Note}: This is not the best sub-linear time algorithm for vertex cover. Remember that vertex cover is a NP-hard problem.  This algorithm will not give us an optimal solution but instead a $2*log(d_{max})$ approximation. Remember that we can also do a 2-approximation for vertex cover in polynomial time. Suppose our graph looks like Figure 1.

\begin{figure}[H]
\begin{center}
\begin{tikzpicture}

  \node at (0,0) [draw] (1) {};
  \node at (0,2) [draw] (2) {};
  \node at (0,-2) [draw] (3) {};
  \node at (4,0) [draw] (4) {};
  \node at (-2,0) [draw] (5) {};
  \node at (1,1) [draw] (6) {};
  \node at (1,-1) [draw] (7) {};
  \node at (-1,1) [draw] (8) {};
  \node at (-1,-1) [draw] (9) {};
  
  \node at (1.5, 0.5) [draw] (10) {};
  \node at (1.5,-0.5) [draw] (11) {};
  \node at (-0.5,1.5) [draw] (12) {};
  \node at (0.5,1.5) [draw] (13) {};
  
  \node at (-1.5, 0.5) [draw] (14) {};
  \node at (-1.5,-0.5) [draw] (15) {};
  \node at (0.5,-1.5) [draw] (16) {};
  \node at (-0.5,-1.5) [draw] (17) {};
  \node at (4,-1) [draw] (18) {};
  \node at (3.5,-1) [draw] (19) {};
  \node at (4.5,-1) [draw] (20) {};
  \node at (4,-2) [draw] (21) {};
  \node at (4,-2.5) [draw] (22) {};
  \node at (4.5,1) [draw] (23) {};
  \node at (6,1) [draw] (24) {};
  
  \node at (7,1) [draw] (25) {};
  \node at (6,2) [draw] (26) {};
  \node at (6,0) [draw] (27) {};
  
  \node at (5.5,0.5) [draw] (28) {};
  \node at (5.5,1.5) [draw] (29) {};
  \node at (6.5,0.5) [draw] (30) {};
  \node at (6.5,1.5) [draw] (31) {};
  
  \path let \p1=(n1) in \pgfextra{\xdef\xNew{\x1}\xdef\yNew{\y1}}; % to get (n1) coordinates
  \foreach \i in {2,...,4} % compute xNew 
    \draw let \p1=(n\i) in \pgfextra{\pgfmathparse{max(\x1,\xNew)}\xdef\xNew{\pgfmathresult}};
   \path[every node/.style={font=\sffamily\large}]
    (1) edge node [left] {} (3)
        edge [right] node[left] {} (2)
        edge node [above left] {} (4)
        edge node [below] {} (5)
        edge node [above] {} (6)
        edge node [below right] {} (7)
        edge node [below right] {} (8)
        edge node [below right] {} (9)
        edge [right] node[left] {} (10)
        edge node [above left] {} (11)
        edge node [below] {} (12)
        edge node [above] {} (13)
        edge node [below right] {} (14)
        edge node [below right] {} (15)
        edge node [below right] {} (16)
        edge node [below right] {} (17)
    (4) edge node [left] {} (18)
        edge node [left] {} (19)
        edge node [left] {} (20)
        
    (21) edge node [left] {} (18)
        edge node [left] {} (19)
        edge node [left] {} (20)
        edge node [left] {} (22)
    (23) edge node [left] {} (4)
        edge node [left] {} (24)  
    (24) edge node [left] {} (25)
        edge node [left] {} (26)  
        edge node [left] {} (27)
        edge node [left] {} (28)
        edge node [left] {} (29)
        edge node [left] {} (30) 
        edge node [left] {} (31)
    
        
\end{tikzpicture}
\caption{Example graph for vertex cover.}
\end{center}
\end{figure}

Our algorithm is a $log(d_{max})$ round distributed algorithm for Vertex Cover. It gives us a $2*log(d_{max})$ approximation, where $d_{max}$ is the maximum degree of any node in the graph.

\begin{algorithm}
\caption{Distributed Vertex Cover}\label{euclid}
\begin{algorithmic}[0]
\Procedure{DistributedVertexCover}{}
\State $\textit{i} \gets 1$
\State $V^* \gets \{\}$
\While{$\textit{edges remain}$}
    \State $V^* \gets \textit{nodes with degree} > \frac{d}{2^i}$
    \State $\textit{Remove nodes with degree} > \frac{d}{2^i}$
    \State $i \gets i+1$
\EndWhile
\State$\textbf{Output: }V^*$
\EndProcedure
\end{algorithmic}
\end{algorithm}

In our example the max-degree is 16 (we can always assume it is an even power of 2).


\begin{figure}[H]
\begin{center}
\begin{tikzpicture}

  \node at (4,0) [draw] (4) {};
  
  
  \node at (4,-1) [draw] (18) {};
  \node at (3.5,-1) [draw] (19) {};
  \node at (4.5,-1) [draw] (20) {};
  \node at (4,-2) [draw] (21) {};
  \node at (4,-2.5) [draw] (22) {};
  \node at (4.5,1) [draw] (23) {};
  \node at (6,1) [draw] (40) {};
  
  \path let \p1=(n1) in \pgfextra{\xdef\xNew{\x1}\xdef\yNew{\y1}}; % to get (n1) coordinates
  \foreach \i in {2,...,4} % compute xNew 
    \draw let \p1=(n\i) in \pgfextra{\pgfmathparse{max(\x1,\xNew)}\xdef\xNew{\pgfmathresult}};
   \path[every node/.style={font=\sffamily\large}]
    (4) edge node [left] {} (18)
        edge node [left] {} (19)
        edge node [left] {} (20)
        
    (21) edge node [left] {} (18)
        edge node [left] {} (19)
        edge node [left] {} (20)
        edge node [left] {} (22)
    (23) edge node [left] {} (4)
        edge node [left] {} (24)  
    
        
\end{tikzpicture}
\caption{Graph after i=1 iteration.}
\end{center}
\end{figure}

After i=1, our graph will look like Figure 2. Because $\textit{maximum degree} = 16$, and $16/2^1 = 8$, we removed all nodes with degree $\geq 8$.

\begin{figure}[H]
\begin{center}
\begin{tikzpicture}

  \node at (4.5,1) [draw] (23) {};
  \node at (6,1) [draw] (40) {};
  
  \path let \p1=(n1) in \pgfextra{\xdef\xNew{\x1}\xdef\yNew{\y1}}; % to get (n1) coordinates
  \foreach \i in {2,...,4} % compute xNew 
    \draw let \p1=(n\i) in \pgfextra{\pgfmathparse{max(\x1,\xNew)}\xdef\xNew{\pgfmathresult}};
   \path[every node/.style={font=\sffamily\large}]
    (23)edge node [left] {} (24)  
    
        
\end{tikzpicture}
\caption{Graph after i=2 iteration.}
\end{center}
\end{figure}


After i = 2, our graph will look like Figure 4. We removed all nodes of degree $8\geq d \leq 16/2^2$. Since everything with degree $\geq 8$ was already removed, we will remove remaining nodes with degree $ \geq4$.

For i=3, $16/2^3 = 2$. There are no nodes in the remaining graph (Figure 3) that have degree $\geq2$, so we don't update the graph.

For i=4 $16/2^4 = 1$. The two remaining nodes have degree of 1, so we add both of them to the vertex cover.


Is the answer always a Vertex Cover? At the final time step, we are removing all nodes with degree $\geq 1$, so all edges are removed with at least one of their neighbors in the Vertex Cover. In the max degree = 1 case (ie the last time step), both nodes on one edge are added to the Vertex Cover as both have degree 1. So it IS a Vertex Cover.

Why is it a good Vertex Cover? We can prove that we remove a bound of \textit{wasteful} (not in the ideal Vertex Cover) nodes.

\begin{theorem}
$VC(G) \leq{|V^*|} \leq{2 \cdot \log(d) +1} \leq{VC(G)}$
\end{theorem}
\begin{proof}
$\theta$ = any minimum vertex cover such that $|\theta| = VC(G)$

\textbf{Claim:} in each iteration we add \textbf{at most} $2\cdot VC(G)$ nodes not in $\theta$.

\textbf{Implies:} at the end we removed $ \leq{|\theta| + \log(d)\cdot 2\cdot VC(G)}$ which is equivalent to saying $\leq{VC(G) + \log(d)\cdot 2VC(G)} $ as $|\theta| = VC(G)$. We possibly removed $VC(G)$ nodes in $\theta$, and also an additional \textit{extra} $2VC(G)$ nodes each round for $\log(d)$  rounds.

We at each time step, we can separate our nodes into two sets, nodes that we removed and nodes that we did not remove.  We know all nodes that we removed at time step i have $\frac{d}{2^{i-1}}> degree \geq
\frac{d}{2^i}$. We know all remaining nodes have $degree < \frac{2}{d^i}$. We also have $\theta$ and we want to figure out which nodes we removed that were not in $\theta$. We want to prove that the number of nodes not in $\theta$ is not that large.

If we have a node in our VC that is not in $\theta$, we know that it must point to something in $\theta$. We know that the item in $\theta$ has $degree < \frac{d}{2^i}$ (or else we would have removed it).

Let $X$ = nodes removed in round i that are not in $\theta$.
Number of edges from $X$ to $\theta$ is $\geq |x|\cdot \frac{d}{2^i}$. The number of edges touching $\theta < \frac{d}{2^i-1}|\theta|$ as $\frac{d}{2^i-1}$ is the maximum degree in the graph. Likewise the number of edges touching $X \geq |X| \cdot \frac{d}{2^i}$, as each node in $X$ has degree at least $\frac{d}{2^i}$. The number of edges touching $X$ must be a subset of the edges touching $\theta$, as all edges that touch $X$ must touch $\theta$. Putting these two inequalities together, we get $|X|\cdot \frac{d}{2^i} \leq \frac{d}{2^{i-1}} \cdot |\theta|$. From this we get $|X|\leq 2 \cdot |\theta|$. We are now done with the proof.
\end{proof}
\section{Maximal Matching}
We know that for a graph $VC \geq$ maximal matching. When we have a maximal matching all the nodes are disjoint.  We need at least one of the nodes in the VC, meaning we need at least maximal-matching nodes in our vertex cover. We also know that $VC \leq 2\cdot \textit{maximal matching}$, as if if we put all of the nodes touched by an edge in the maximal matching we by definition would have to have a vertex cover. If we do not, then we did not have a maximal matching.
\subsection{Maximal Matching on Graphs with Degree at Most d}
We know that for a graph $G$ with maximum degree $d$, the maximal matching $\geq \theta(\frac{n}{d})$. We know this as we can simply take out an edge and remove the 2 nodes adjacent to the edge and all edges adjacent to them until we are done.

This greedy algorithm is sequential and not sub-linear. 
\begin{algorithm}
\caption{Greedy Maximal Matching}\label{euclid}
\begin{algorithmic}[0]
\Procedure{GreedyMaximalMatching}{}
\State $M \gets \{\}$
\ForAll {$e \in (u, v) \in E$}

    \If {$\textit{neither u or v was previously matched} $} 
    \State $M \leftarrow e$    
    \EndIf
\EndFor
\hspace{\algorithmicindent}\State $\textbf{Output: } M$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The only thing this greedy algorithm depends on is the order of edges.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3cm,
                    thick,main node/.style={circle,draw}]

  \node[main node] (1) {};
  \node[main node] (2) [below left of=1] {};
  \node[main node] (3) [below right of=1] {};

  \path[every node/.style={font=\sffamily\large}]
    (1) edge node [left] {\textit{$e_1$}} (3)
        edge [right] node[left] {\textit{$e_2$}} (2)
    (2) edge node {\textit{$e_3$}} (3);
\end{tikzpicture}
\caption{Example graph.}
\end{center}
\end{figure}
As you can see in Figure 4, the edges that will be in the matching are dependant on the order the greedy algorithm iterates through them. For example if $e_1$ is chosen first, then it will be the maximal matching. If $e_2$ is chosen first, it will be the maximal matching. And if $e_3$ is chosen first, it will be the maximal matching. There are never any edges where both endpoints aren't in the maximal matching.

\subsection{Oracle Reduction Framework for Maximal Matching}
We now want to estimate the size of the matching. Suppose we have a deterministic ORACLE which in one step can tell us whether or not an edge is in the maximal matching.

\begin{algorithm}
\caption{Maximal Matching}\label{euclid}
\begin{algorithmic}[0]
\Procedure{OracleReductionMaximalMatching}{}
\State $S \leftarrow \frac{8}{\epsilon^2} \textit{ independently at random chosen nodes}$
\ForAll {$v \in \mathcal S$}

    \If {$ORACLE(v,w) == \textit{yes for any w} \in N(V)$} \State $x_v \gets 1$    \Else \State $x_v \gets 0$\EndIf
\EndFor
\State $\textbf{Output: }n\cdot \frac{1}{2}\cdot \frac{\sum_{v \in S}^{} (x_v)}{2 \cdot S} + \frac{\epsilon}{2}\cdot n $
\EndProcedure
\end{algorithmic}
\end{algorithm}

The reason that we add a factor of $\frac{\epsilon}{2}\cdot n$ to our answer is to make under counting unlikely.  The algorithm is outputting the fraction of samples matched. If we take enough samples, we know that it is a good estimate of the whole.  The reason for the factor of $\frac{1}{2}$ is that the size of the matching is one half the number of nodes (in order to get edges between two nodes in the matching). In this algorithm the ORACLE has a maximal matching $M$ in its head.

\textbf{Claim: } $E[ouptut] = |M| + \frac{\epsilon}{2}$ where $|M|$ is the size of the matching in the ORACLE's head.
\begin{proof}
$E[|output|] = E[\frac{n}{2\cdot S} \sum_{v \in S}^{} x_v] + \frac{\epsilon \cdot n}{2}$. This is equivalent to $\frac{n}{2 \cdot S}\sum_{v \in S}^{} x_v + \frac{\epsilon \cdot n}{2}$. We know that the $E[x_v] = \frac{2 \cdot |M|}{|V|}$ and that $|V| = n$. The $E[x_v]$ is the fraction of matched nodes. This gives us $E[|output|] =\frac{n}{2 \cdot S} \cdot S \cdot \frac{2 \cdot |M|}{n} + \frac{\epsilon \cdot n}{2}$, as expectation is linear. This reduces to $|M| + \frac{\epsilon \cdot n}{2}$. The probability $P(|\frac{n}{2\cdot S} \sum_{v \in S}^{} x_v] + \frac{\epsilon \cdot n}{2} - E[output]| \geq \frac{\epsilon \cdot n}{2})$ This is equivalent to $P(|\frac{n}{2\cdot S} \sum_{v \in S}^{} x_v] -|M|| \geq \frac{\epsilon \cdot n}{2})$. By additive Chernoff-Hoeffding bounds, we get $P \leq \frac{1}{3}.$
\end{proof}

\subsection{Maximal Matching Oracle}
The question is now how do we make the ORACLE? It is non-trivially difficult to simulate the greedy algorithm.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}

  \node at (0,0) [draw] (1) {};
  \node at (1,0) [draw] (2) {};
  \node at (2,0) [draw] (3) {};
  \node at (3,0) [draw] (4) {};
  \node at (4,0) [draw] (5) {};
  \path let \p1=(n1) in \pgfextra{\xdef\xNew{\x1}\xdef\yNew{\y1}}; % to get (n1) coordinates
  \foreach \i in {2,...,4} % compute xNew 
    \draw let \p1=(n\i) in \pgfextra{\pgfmathparse{max(\x1,\xNew)}\xdef\xNew{\pgfmathresult}};
   \path[every node/.style={font=\sffamily\small}]
    (1) edge node [above] {1} (2)
    (2) edge node [above] {2} (3)
    (3) edge node [above] {3} (4)
    (4) edge node [above] {4} (5);
    
        
\end{tikzpicture}
\caption{Graph where ordering is linear.}
\end{center}
\end{figure}
Take for example Figure 5.  What would the greedy algorithm do about edge 4? That would depend on what the algorithm did on edge 3. That result depends on what the greedy algorithm did on edge 2 and onwards. In order to determine what the greedy algorithm would do for one edge, we need to follow the dependence chain all the way back to the beginning. In cases like Figure 6, this dependence chain could be linear in length.

In order to determine whether and edge $e$ is in the matching, we only care about edges that come before it in the ordering. We need to need to know the decisions about the edges that come before in the ordering. We do \textbf{not} need to know anything about the edges that come after $e$ in the ordering.

In order to simulate a greedy algorithm, we will use a random ordering of the edges. Each edge will receive a random ranking.

\begin{figure}[H]
\begin{center}
\begin{tikzpicture}

  \node at (0,0) [draw] (1) {};
  \node at (1,0) [draw] (2) {};
  \node at (2,0) [draw] (3) {};
  \node at (3,0) [draw] (4) {};
  \node at (4,0) [draw] (5) {};
  \node at (5,0) [draw] (6) {};
  \node at (6,0) [draw] (7) {};
  \node at (4,0.5) [draw] (9) {};
  \path let \p1=(n1) in \pgfextra{\xdef\xNew{\x1}\xdef\yNew{\y1}}; % to get (n1) coordinates
  \foreach \i in {2,...,4} % compute xNew 
    \draw let \p1=(n\i) in \pgfextra{\pgfmathparse{max(\x1,\xNew)}\xdef\xNew{\pgfmathresult}};
   \path[every node/.style={font=\sffamily\small}]
    (1) edge node [above] {0.8} (2)
    (2) edge node [ above] {0.2} (3)
    (3) edge node [above] {0.4} (4)
    (4) edge node [below] {0.5} (5)
    (5) edge node [above] {0.3} (6)
    (6) edge node [above] {0.1} (7)
    (4) edge node [above] {0.7} (9);
    
\end{tikzpicture}
\caption{Example graph for maximal matching.}
\end{center}
\end{figure}

Suppose we are now looking at the edge with weight 0.5 in Figure 6.  We take the following steps to determine if 0.5 is in the matching:
\begin{itemize}
  
\item In order to determine if it is in the matching, we first look at its neighbors. Two of its neighbors, 0.3 and 0.4, appear first in the ordering. We must first determine if either of those edges are in the matching. If they are, then 0.5 is not in the matching. If neither of 0.3 or 0.4 is in the matching, though, then 0.5 is in the matching.

\item Now we will look at edge 0.3. Is it in the matching? To determine this, we must look at edge 0.1.
\begin{itemize}

    \item Looking at edge 0.1, it has no neighbors with rank less than it, so edge 0.1 \textbf{is} in the matching.

    \item Going back to edge 0.3, we now know that 0.1 is in the matching, so edge 0.3 \textbf{is not} in the matching.
\end{itemize}

\item Now we look at 0.5's other neighbor, 0.4. In order to determine if 0.4 is in the matching, we must know if 0.2 is in the matching.
\begin{itemize}


    \item Looking at 0.2, its only other neighbor, 0.8, has rank greater than it, so 0.2 \textbf{is} in the matching.
    
    \item Since 0.2 is in the matching, 0.4 \textbf{is not} in the matching.
\end{itemize}

\item Since 0.5 has rank lower than 0.7, and neither 0.3 or 0.4 are in the matching, we know know that 0.5 \textbf{is} in the matching.
\end{itemize}

The question now is: \textit{Is randomness really going to help us?}

\begin{algorithm}
\caption{Maximal Matching Oralce}\label{euclid}
\begin{algorithmic}[0]
\Procedure{MaximalMatchingOracle}{$e$}
\ForAll{$e' \in neighbors(e)$}
    \If{$rank_e' < rank_e$}
        \If{$e' \in M$}
            \State$\textbf{Output: }\lq e \notin M \rq$
        \EndIf
    \EndIf
\EndFor
\State$\textbf{Output: } \lq e \in M \rq$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The correctness of Algorithm 5 follows from the correctness of the greedy algorithm. The $E[\#\textit{oracle calls}] = 2^d$. 

\textbf{Claim }$E[\#\textit{queries/oracle call}] = 2^{O(d)}$

\begin{proof}
When determining if a node $e$ is in the matching, we can explore the sub-tree of a $d$-ary tree of the neighbors of each edge.
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}

  \node at (0,0) [draw] (1) {};
  \node at (0,-1) [draw] (2) {};
  \node at (2,-1) [draw] (3) {};
  \node at (-2,-1) [draw] (4) {};
  
  \node at (0,-2) [draw] (5) {};
  \node at (-0.5,-2) [draw] (6) {};
  \node at (0.5,-2) [draw] (7) {};
  
  \node at (2,-2) [draw] (8) {};
  \node at (1.5,-2) [draw] (9) {};
  \node at (2.5,-2) [draw] (10) {};
  
  \node at (-2,-2) [draw] (11) {};
  \node at (-1.5,-2) [draw] (12) {};
  \node at (-2.5,-2) [draw] (13) {};
  
  \path let \p1=(n1) in \pgfextra{\xdef\xNew{\x1}\xdef\yNew{\y1}}; % to get (n1) coordinates
  \foreach \i in {2,...,4} % compute xNew 
    \draw let \p1=(n\i) in \pgfextra{\pgfmathparse{max(\x1,\xNew)}\xdef\xNew{\pgfmathresult}};
   \path[every node/.style={font=\sffamily\large}]
    (1) edge node [center] {$e_1$} (2)
    (1) edge node [ right] {$e_2$} (3)
    (1) edge node [left] {$e_3$} (4)
    
    (2) edge node [left] {} (5)
    (2) edge node [left] {} (6)
    (2) edge node [left] {} (7)
        
    (3) edge node [left] {} (8)
    (3) edge node [left] {} (9)
    (3) edge node [left] {} (10)
        
    (4) edge node [left] {} (11)
    (4) edge node [left] {} (12)
    (4) edge node [left] {} (13)
    
    
\end{tikzpicture}
\caption{d-ary tree of $e$'s neighbors.}
\end{center}
\end{figure}
Figure 7 is an example neighbor tree for a node $e_0$ where the maximum degree, $d$, is 3. The number of nodes in the tree, is $d^k$ where $k$ is the height of the tree. The number of nodes in the tree is the number of edges we will have to explore to determine if $e_0$ is in the matching.

Now we want to bound the size of the tree. We know that we will only keep paths that are monotonically decreasing in rank, as once a edge has no neighbors with rank less than itself, we can determine whether or not it is in the matching. The probability of a path explored (monotonically decreasing) is  $P(\textit{any path P of length k is explored} = \frac{1}{(k+1)!}$.  There are at most $d^k$ paths of length $k$. In order to get the total expected number of edges explored, we must sum  over all $k$. Therefore, $E[\textit{total \# of edges explored}] = \sum_{k=0}^{\infty} \frac{d^k}{(k+1)!} \leq \frac{e^d}{d}$. 
\end{proof}

\end{document}