Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 12 / 6 / Solution

There are genuine normalization inconsistencies in this PDF. In the standard linearized chord diagram model $G_n^{(1)}$, time $n$ gives $n$ edges and total vertex degree $2n$, with self-loops counted twice. The paper calls $2n$ the number of edges. Its right-endpoint hint also uses $\sqrt{i/(2n)}$ rather than $\sqrt{i/n}$. These cannot both describe the standard model; part (c)'s exponent is consequently inconsistent as well. We give the definition, prove the alternative construction and its limits, and explicitly identify the corrected conclusion rather than infer an invalid constant from the printed hint.

Start from the empty graph at time zero, or from one vertex with one self-loop at time one. To obtain $G_t$ from $G_{t-1}$, add vertex $t$ and an edge directed from $t$ to $I_t$, whereA self-choice creates a self-loop. The old vertex degrees sum to $2(t-1)$, so these probabilities sum to one. This is exact preferential attachment, including the outward half of the new edge as weight one for the new vertex; it is not a rule normalized by $2t$ or a process adding two edges at each step. The degree of a vertex here is its total incoming plus outgoing vertex degree. The construction in part (a) has exactly one chord per vertex and makes the edge-count discrepancy explicit.