On the performance of percolation graph matching

The original version of the paper had a mistake in the proof of Lemma 2 in the appendix, which we correct in the revised version. The corrected proof has two parts. In the first part, we show that early in the matching process, no wrong pair $[i,j]$ receives $r$ marks or more, i.e., no wrong pairs are matched (w.h.p.) In the second part, we show that late in the matching process, if a wrong pair $[i,j]$ reaches $r$ marks, then either $[i,i]$ or $[j,j]$ lready received $r$ marks before (w.h.p.), and as a consequence $[i,j]$ does not get matched. Together, this establishes a sufficient condition for no matching error to occur. However, as a consequence of this correction, the condition on the parameter $r$ in Lemma 2 (threshold for number of marks until a node pair gets matched) is now $r >= 4$, as opposed to $r>=2$. This is reflected in the discussion of the result below Lemma 2. The main findings and conclusions of the paper are otherwise unchanged.