text:
\begin{document}
\maketitle
\begin{abstract}
We introduce a new model of a preferential attachment based random graph which extends the family of models in which condensation phenomena can occur.  Each vertex in our model has an associated uniform random variable which we refer to as its location.  Our model evolves in discrete time by selecting $r$ vertices from the graph with replacement, with sampling probabilities proportional to their degrees plus a constant $\alpha$.  A new vertex joins the network and attaches to one of these $r$ vertices according to a given probability associated to the ranking of their locations.  Using stochastic approximation techniques we give conditions for the occurrence of condensation in this model, showing the existence of phase transitions in $\alpha$ below which condensation occurs.  The condensation in our model differs from that in preferential attachment models with fitness in that the condensation can occur at a random location, that it can (but not necessarily) be due to a persistent hub, and that there can be more than one point of condensation.

{\bf Keywords}: Preferential Attachment, Fitness, Location, Random Graphs, Phase Transition
\end{abstract}

\section{Introduction}\label{Chapter 3 Section 1}
Preferential attachment graphs were developed as an extension of Erd\H{o}s and R\'enyi's random graph model in order to model evolving networks that exhibited a power law in their degree distributions. The standard preferential attachment method discussed by Barab\'asi and Albert \cite{P.10} evolves from an initial graph $G_0$ with $n_0$ vertices $v_{1-n_0},\ldots,v_0$. For each $n\geq 0$ the graph $G_{n+1}$ is formed by a new vertex $v_{n+1}$ joining $G_n$ and attaching to an existing vertex $V\in\{v_{1-n_0},\dots,v_n\}$ according to
\begin{equation}\label{prefatt}
P(V=v_i)=\frac{\deg_{G_n}(v_i)+\alpha}{\sum_{j=-n_0}^n\left(\deg_{G_n}(v_j)+\alpha\right)},
\end{equation}
for some $\alpha>-1$.  Equation \eqref{prefatt} gives the form of preferential attachment developed by Dorogovtsev, Mendes and Samukhin in \cite{P.42} as a generalisation of the Barab\'asi and Albert model found in \cite{P.10}, and we shall use this more general form. However, several of the papers referred to in this section, including \cite{P.10}, only consider the case $\alpha=0$.

It is clear to see from (\ref{prefatt}) that vertices with a higher degree have a higher probability of attracting new edges. Some commonly mentioned applications of preferential attachment graphs include the number of links to a website and the growth of the number of connections on social networks.

It is observable in real world networks that the growth in influence of an individual vertex is affected by more factors than just its degree. How attractive the vertex is by itself or in comparison to the others also plays a large part. A model incorporating this notion was introduced by Bianconi and Barab\'{a}si in \cite{P.1}, where they gave each vertex a multiplicative fitness value in their version of \eqref{prefatt}. They did this in order to add an extra dimension to the competition between vertices that joined the vertex using a generalised preferential attachment mechanism. As a consequence, new, fitter, vertices can still compete against vertices which are well-established in the existing network.  A particularly interesting feature of preferential attachment with fitness is the so-called condensation phenomena, where at time $n$ a single vertex or a set of vertices of size $o(n)$ (which vertices can depend on time) can have a total degree of order $n$.  Condensation for preferential attachment with fitness is studied in detail by Borgs et al.\ \cite{P.2}, Dereich and Ortgiese \cite{P.4} and Dereich, Mailler and M\"{o}rters \cite{P.3}.

Another variant of preferential attachment is the choice model introduced by Malyshkin and Paquette in \cite{P.7,P.8} and Krapivsky and Redner in \cite{P.41}.  Here when a new vertex joins the network it first selects several candidate existing vertices at random using \eqref{prefatt}, then attaches to one of the candidates according to a deterministic rule, such as always attaching to the candidate of highest degree. In these papers, depending on the parameters, as the number of vertices increases linear or approximately linear growth can be observed in the degree of the largest vertex.  Preferential attachment with degree-based choice was further studied by Haslegrave and Jordan \cite{P.5},
who showed that condensation can also occur when choosing a lower-ranked vertex.

The choice model is combined with fitness in the model studied by Freeman and Jordan \cite{Sou.1} in which each vertex has its own fitness value; the new vertex joins the graph $G_n$ by using preferential attachment to select $r$ vertices from $G_n$. The new vertex forms an edge between itself and the vertex with the highest fitness of the $r$ selections.  It is shown in \cite{Sou.1} that again condensation can occur in this model.

In this paper we generalise the model of \cite{Sou.1} to allow for choices other than the largest or smallest, for example selecting the middle vertex of a selection of three.  Informally, an example of when the middle of three model might be appropriate is when voting for a political candidate; one might prefer to avoid voting for a candidate is too far left or right, and so decide to cast their vote in the middle.  We will also allow for randomised choice rules based on the ranking.  Because we are no longer selecting the largest value, we will use the term location rather than fitness.  In this paper the locations will be uniform random variables on $[0,1]$; note that as we are only using the order of locations, this is equivalent to any measure without atoms.

Using stochastic approximation techniques, we will show that the normalised empirical measure on the location space given by weighting the location of each vertex of the graph by its degree plus $\alpha$ converges almost surely to a limit.  In some cases, this limit is random and has an atom, the emergence of the atom corresponding to condensation occurring in the system.  We will show that the atom appears at a random location, as opposed to the results of \cite{P.2, Sou.1} where condensation can only occur at the supremum of the fitness distribution.  In addition we will show that condensation in our model can be due to a single vertex which acts as a persistent hub, which is not possible in fitness models.  In fact, for some choices of our parameters, condensation has probability 1, but persistent hub behaviour has probability strictly between 0 and 1, so condensation can occur in at least two different ways, each with positive probability.

The remainder of this article will start with a discussion of our model and a summary of the main results in Section \ref{Section 2}.  Our proofs are in Section \ref{Section 3}, and finally Section \ref{Section 4} includes some specific examples that highlight some of the important aspects of our main results.

\section{Our model and results}\label{Section 2}

\subsection{The model}

Fix a parameter $r\in \N$ with $r\geq 2$, a vector $\Xi\in \R^r$ such that  $\Xi_i\in[0,1]$ and $\sum^{r}_{i=1}\Xi_i=1$, and a real number $\alpha>-1$.

We start with a tree $G_{0}$ containing $n_0\geq 2$ vertices which we will denote by $V(G_0)=\{v_{0},v_{-1},\dots, v_{-(n_0-1)}\}$. Every vertex $v_i$ in $G_{0}$ has its own location $x_{i}$ in $(0,1)$; we will assume that these locations are distinct. Given $G_n$, at time $n+1$  we form $G_{n+1}$ by adding a new vertex $v_{n+1}$ to the network with a single edge.  This vertex has its own uniform random variable $x_{n+1}\sim\mbox{Uni}[0,1]$, which is independent of the other $x_i$, and chooses where to attach to at time $n+1$ by selecting a sample of $r$ pre-existing vertices in $G_n$ with replacement with probabilities proportional to their degrees plus $\alpha$ as given by equation \eqref{prefatt}.
While the requirement that $G_0$ is a tree is not necessary, and does not change the results, trees are the most natural starting graphs since the attachment process preserves the tree structure.  Provided $G_0$ is a tree we also have $\sum_{j=-n_0}^n\left(\deg_{G_n}(v_j)+\alpha\right)=2(n+n_0-1)+\alpha(n+n_0)=(n+n_0-1)(2+\alpha)+\alpha$.

Let the $r$ selected vertices at time $n+1$ be denoted by $\{V_1^{(n+1)},\dots,V_r^{(n+1)}\}$ with locations $x_{1}^{(n+1)},\allowbreak\dots,x_{r}^{(n+1)}$ respectively, and renumber if necessary so that the locations satisfy $x_{1}^{(n+1)}\leq x_{2}^{(n+1)}\leq\dots\leq x_{r}^{(n+1)}$. For definiteness we specify that if two or more vertices in the selection have the same location, we rank them in the order they were selected; note, however, that with probability $1$ the only way for this to occur is if the same vertex is selected more than once. The probability that $v_{n+1}$ attaches to vertex $V_i^{(n+1)}$ is then given by $\Xi_i$.

For example if $r=3$ and $\Xi=(0,1,0)$ then the new vertex selects a sample of size $3$, and connects to the selected vertex of median rank.  The model can be thought of as generalising the case of the model of \cite{Sou.1} with fixed sample size; that model is obtained by taking our model with $\Xi_r=1$ (or equivalently with $\Xi_1=1$).

\subsection{Results}

We define $\Psi_n(x)$ to be the probability that a vertex selected randomly from $G_n$ according to the law \eqref{prefatt} has location less than or equal to $x$, that is \[\Psi_n(x)=\frac{1}{(n+n_0-1)(2+\alpha)+\alpha}\sum_{v_i\in V(G_n):x_i\leq x}(\deg_{G_n}(v_i)+\alpha).\] Clearly $\Psi_n(0)=0$ and $\Psi_n(1)=1$.  We can think of $\Psi_n$ as being the distribution function of the normalised empirical measure on the location space given by weighting the location of each vertex of the graph by its degree plus $\alpha$; we will label this measure $\nu_n$.

Our first result is on the convergence of the measures $\nu_n$.  For a fixed $x$ and choice of $\Xi$, define \[F_1(y;x,\Xi)=x(\alpha+1)-(2+\alpha)y+\sum^{r}_{l=1}\Xi_l \sum^{r}_{i=l}\binom{r}{i}y^{i}(1-y)^{r-i},\] to be considered as a function of $y$ for $y\in[0,1]$.

We will say that $p\in (0,1)$ is a \emph{stable zero} of $F_1(y;x,\Xi)$ if $F_1(p;x,\Xi)=0$ where there exists an $\epsilon$ such that for $y\in (p-\epsilon,p)$ we have $F(y;x,\Xi)>0$ and for $y\in (p,p+\epsilon)$ we have $F(y;x,\Xi)<0$.  Similarly $p\in (0,1)$ is an \emph{unstable zero} if $F_1(p;x,\Xi)=0$ and there exists $\epsilon$ such that for $y\in (p-\epsilon,p)$ we have $F(y;x,\Xi)<0$ and for $y\in (p,p+\epsilon)$ we have $F(y;x,\Xi)>0$, and $p\in (0,1)$ is a \emph{touchpoint} if $F_1(p;x,\Xi)=0$ and there exists $\epsilon$ such that we have either $F(y;x,\Xi)<0$ for all $y\in (p-\epsilon,p+\epsilon)\setminus\{p\}$ or $F(y;x,\Xi)>0$ for all $y\in (p-\epsilon,p+\epsilon)\setminus\{p\}$.

\begin{rem}Since $F_1(y;x,\Xi)$ is a polynomial, every root in $(0,1)$ is either a stable zero, an unstable zero or a touchpoint. Also, for $x\in(0,1)$ we have $F_1(0;x,\Xi)>0>F_1(1;x,\Xi)$, so $0$ and $1$ are not roots.\end{rem}

\begin{thm}\label{main1}
As $n\to\infty$, the sequence of measures converges weakly, almost surely, to a (possibly random) probability measure on $[0,1]$, whose distribution function we will call $\Psi$.  Furthermore, for any given $x\in (0,1)$, \begin{enumerate}
\item Almost surely, $\Psi(x)$ is a zero of the function $F_1(y;x,\Xi)$.
\item For any stable zero or touchpoint $y$ of $F_1(y;x,\Xi)$, there is positive probability that $\Psi(x)=y$.
\item Any unstable zero $y$ of $F_1(y;x,\Xi)$ has probability zero that $\Psi(x)=y$.
\end{enumerate}
\end{thm}

Depending on the parameters of the model, the limit $\Psi$ may be continuous or discontinuous; for example in Section \ref{midofthreemodd} we will show that the model mentioned above where $r=3$ and $\Xi=(0,1,0)$ exhibits a phase transition where $\Psi$ is almost surely continuous for $\alpha\geq -\frac{1}{2}$ and almost surely has a discontinuity for $\alpha<-\frac{1}{2}$.

Discontinuity of $\Psi$ implies that $\Psi_n$ increases by $\Theta(1)$ on an interval
of length $o(1)$ as $n\to\infty$; this corresponds to a condensation phenomenon whereby a small number of vertices with locations in a range of size $o(1)$ have a
$\Theta(1)$ probability of being selected. A consequence of Theorem \ref{main1} is that where there is an interval of $x$ values for which $F_1(y;x,\Xi)$ has more than one stable root, the discontinuity occurs at a random location, as any stable root has positive probability of being the limit for each $x$ in the interval.

It does not immediately follow from discontinuity of $\Psi$ that a single vertex has linear degree; however, the next result shows that this occurs with positive probability.  Without loss of generality, we will focus on the vertex $v_0$, present in the graph from the start, and label its location as $z$.  We define
\begin{equation*}
D_n=\frac{\alpha+\deg_{G_n}(v_0)}{(n+n_0-1)(2+\alpha)+\alpha},
\end{equation*}
which would be the probability of selecting $v_0$ for attachment under the preferential attachment rule.

\begin{thm}\label{main2}Let $z$ be the the location of vertex $v_0$.
If $y_i\geq y_j$ are two stable fixed points of $F_1(y;z,\Xi)$, then there is positive probability that $(\Psi_n(z),D_n)\to (y_i,y_i-y_j)$ as $n\to\infty$.
\end{thm}

Theorem \ref{main2} shows that if there are two distinct stable fixed points of $F_1(y;z,\Xi)$ then condensation can occur at a persistent hub in the sense that a vertex of the initial graph with location $z$ has its degree growing linearly with $n$ with positive probability.  The condensation phenomenon that occurs in this case is thus different from that found for preferential attachment with multiplicative fitness, where Dereich, Mailler and M\"{o}rters \cite{P.3} show that the maximum degree divided by $n$ converges to zero in probability; it is also distinct from that found by Freeman and Jordan \cite{Sou.1} where, although the maximum degree is usually of linear order in $n$, any individual vertex only dominates for a finite time before being displaced by fitter vertices.

However, the next result shows that for some choices of our parameters there is also positive probability that the condensation phenomenon is not due to a persistent hub, as it implies there is positive probability of the condensation occurring at a specific location, where the probability of there being a vertex is zero.  This suggests that in this case the condensation phenomenon is more like one of those found in \cite{P.3} or \cite{Sou.1}, in that vertices whose location is close to the condensation location are replaced over time in the condensate by those which are even closer.

\begin{thm}\label{main3}
Let $x\in(0,1)$ and $\Xi$ be such that there exists $p\in (0,1)$ which is a touchpoint of $F_1(y;x,\Xi)$.  Then there is positive probability that condensation occurs at $p$ in the sense that $\Psi$ has a discontinuity at $p$.
\end{thm}

One natural question is whether it is possible to have more than one discontinuity in $\Psi$, implying more than one point of condensation.  The following result shows that this is not possible in the case where the same rank is always chosen; note that we write $\ekr$ to indicate $(0,0,\dots,1,\dots,0,0)$ where the $1$ is in the $k^{\text{th}}$ position.

\begin{thm}\label{highlander}
Whenever $\Xi=\ekr$ for some $k\in\{1,2,\dots,r\}$, it is impossible to have more than one point of condensation.
\end{thm}

An example of a choice of $\Xi$ for which more than one point of condensation is possible appears in section \ref{secondorsixth}.

\section{Proofs}\label{Section 3}

For the majority of this section we will restrict the model to the case where the choice between the $r$ selected vertices is deterministic, i.e.\ $v_{n+1}$ always attaches to the selected vertex with the $k^{\text{th}}$ highest location for some fixed $k$. In the formal notation given above this model can be written as $\Xi=(0,0,\dots,1,\dots,0,0)$ where the $1$ is in the $k^{\text{th}}$ position; we will write $\ekr$ instead of $\Xi$ in this case.  We will deal with the case with general $\Xi$ at the end of the section.

A key technique we use in our proofs is that of of stochastic approximation algorithms, originally developed by Robbins and Monro \cite{P.28}.  Stochastic approximation methods appear naturally in preferential attachment models, and have been used, for example, by Malyshkin and Paquette \cite{P.8} and Dereich and Ortgiese \cite{P.4}.  Stochastic approximation processes operate in discrete time with standard notation, based on Pemantle \cite{P.9},
\begin{equation*}
X_{n+1}-X_{n}=\gamma_n(F(X_n)+\xi_{n+1}+R_{n}),
\end{equation*}
where $\{X_n,n\geq n\}$ is a sequence of random variables on $\mathbb{R}^n$, $\gamma_n$ are step sizes satisfying $\sum_{n=1}^{\infty}\gamma_n=\infty$ and $\sum_{n=1}^{\infty}\gamma_n^2<\infty$  $F$ is a function from $\R^n$ to itself, $R_n$ are remainder terms which must tend to zero and satisfy $\sum_{n=1}^{\infty}n^{-1}|R_n|<\infty$, and $\xi_{n+1}$ are noise terms satisfying $\mathbb{E}(\xi_{n+1}|\mathcal{F}_{n})=0$ \cite{P.9}.

We will mainly use results found in Section 2 of \cite{P.9}, which show that under certain conditions the process will converge almost surely to an equilibrium of $F$, that stable equilibria have positive probability of being the limit and that unstable equilibria usually do not.

\subsection{Proofs of Theorems \ref{main1} to \ref{main3} when $\Xi=\ekr$}

Let $\mathcal{F}_{n}$ be the $\sigma$-algebra generated by the graphs $G_n$ and the locations of their vertices up until time $n$, i.e.\ $\mathcal{F}_{n}=\sigma(G_i,x_{i};i\leq n)$.
For $x\in [0,1]$, the probability of attaching a vertex with location less than or equal to $x$ at time $n+1$, conditional on $\mathcal F_n$, is given by
\begin{equation}\label{prob select vert leq x}
g(\Psi_n(x);\ekr)= \sum^{r}_{i=k}\binom ri\Psi_n(x)^{i}(1-\Psi_n(x))^{r-i}.
\end{equation}

We can now formulate the first stochastic approximation equation associated to our model, which will allow us to show that as the network grows the total weight of vertices with location less than or equal to $x$ grows linearly.
\begin{lem}\label{first sae} For a fixed $x\in[0,1]$, we have the stochastic approximation equation
\begin{equation}\label{f1(y;x,ekr)}
\Psi_{n+1}(x)-\Psi_{n}(x)=\frac{F_1(\Psi_{n}(x);x,\ekr)+\xi_{n+1}}{(n+n_{0})(2+\alpha)+\alpha},
\end{equation}
where $F_1(y;x,\ekr)=g(y;\ekr)-(2+\alpha)y+x(1+\alpha)$. Here $g(y;\ekr)$ is given in equation (\ref{prob select vert leq x}) and $\xi_{n+1}$ is the noise generated by the process, satisfying $\mathop{\mathbb{E}}(\xi_{n+1}|\mathcal{F}_{n})=0$.
\end{lem}
\begin{proof}The vertex $v_{n+1}$ has fitness at most $x$ with probability $g(\Psi_{n}(x);\ekr)$ from equation \eqref{prob select vert leq x} as the probability of attaching to the vertex with rank $k$ of $r$ selections. We have that the expected addition to the system arising from the location of the new vertex is $x(1+\alpha)$. For a graph $G_0$ on $n_0$ vertices with $e_0$ edges we can deduce that $G_n$ has $n_0+n$ vertices and $e_0+n$ edges, this leads to the normalising constant $2(e_0+n)+\alpha(n_0+n)$. Here, as $G_n$ is a tree hence $e_0=n_0-1$ leads to the normalising constant $(n+n_0-1)(2+\alpha)+\alpha$. Therefore
\begin{align*}
\Psi_{n+1}(x)&=\frac{\Psi_{n}(x)\left( (n+n_{0})(2+\alpha)-2 \right)+x(1+\alpha)+g(\Psi_{n}(x);\ekr)+\xi_{n+1}}{(n+n_{0}+1)(2+\alpha)-2}\\
&=\Psi_{n}(x)+\frac{x(1+\alpha)-\left( \alpha+2 \right)\Psi_{n}(x)+g(\Psi_{n}(x);\ekr)+\xi_{n+1}}{(n+n_{0})(2+\alpha)+\alpha},
\end{align*}
and so
\begin{align*}
\Psi_{n+1}(x)-\Psi_{n}(x)&=\frac{g(\Psi_{n}(x);\ekr)-\left( \alpha+2 \right)\Psi_{n}(x)+x(1+\alpha)+\xi_{n+1}}{(n+n_{0})(2+\alpha)+\alpha}\\
&=\frac{F_1(\Psi_{n}(x);x,\ekr)+\xi_{n+1}}{(n+n_{0})(2+\alpha)+\alpha}.
\end{align*}
We define $\xi_{n+1}$ as
\begin{equation*}
\frac{\Psi_{n+1}(x)-\mathop{\mathbb{E}}(\Psi_{n+1}(x)|\mathcal{F}_{n})}{\gamma_{n+1}}
\end{equation*}
where $\gamma_{n+1}=(n+n_0)(2+\alpha)+\alpha$. It is clear that $\xi_{n+1}$ has conditional expectation zero.
\end{proof}
\begin{thm}\label{equstabroot}
Let $x\in(0,1)$.  The sequence of random variables $\Psi_n(x)$ converges almost surely to a zero $p$ of $F_1(y;x,\ekr)$.  Any stable zero in $[0,1]$ or touchpoint in $(0,1)$ has positive probability of being the limit, while any unstable zero has probability zero of being the limit.
\end{thm}

\begin{proof}
First we note that $F_1(0;x,\ekr)>0$ and $F_1(1;x,\ekr)<0$. Therefore there must be at least one zero of $F_1(y;x,\ekr)$ in the interval $[0,1]$.

The results for stable and unstable zeros follow from Corollary 2.7, Theorem 2.8 and Theorem 2.9 of Pemantle \cite{P.9}.  As we have that $F_1(y;x,\ekr)$ is continuous and $\gamma_n$ linear in $n$, to apply Corollary 2.7 and Theorem 2.8 we just need to check that there exists a value $C\in\mathbb{R^{+}}$ such that $\mathop{\mathbb{E}}(\xi_{n+1}^2|\mathcal{F}_{n})\leq C$.  For Theorem 2.9 we also need that the noise components $\mathop{\mathbb{E}}(\xi_{n+1}^{+}|\mathcal{F}_{n})$ and $\mathop{\mathbb{E}}(\xi_{n+1}^{-}|\mathcal{F}_{n})$ are bounded above and below by positive numbers.

We first bound the variance of the noise.  We have
\begin{equation*}
|\xi_{n+1}|\in[0,2],
\end{equation*}
and we can therefore see that $\mbox{Var}(\xi_{n+1}|\mathcal{F}_{n})\leq 4$ which also implies that $\mathop{\mathbb{E}}(\xi_{n+1}^{2}|\mathcal{F}_{n})\leq 4$.

We have shown that there exists a root $p$ in the interval $[0,1]$, we assume we have a root that satisfies $F_1(y;x,\ekr)>0$ on $(p-\epsilon,p)$ and $F_1(y;x,\ekr)<0$ on $(p,p+\epsilon)$ for some $\epsilon>0$. Therefore Theorem 2.8 from \cite{P.9} holds true, we can conclude there is a positive probability of convergence to this root.

We now verify the conditions on $\xi_{n+1}^{+}$ and $\xi_{n+1}^{-}$. For some member of the zero set $p\in(0,1)$ we have that the sign of $F_1(\Psi_n(x);x,\ekr)$ is the same as the sign of $\Psi_n(x)-p$. We know that $|\xi_{n}|=\xi_{n}^{+}+\xi_{n}^{-}\leq\xi_{n}^{2}$ which implies both $\xi_{n}^{+}\leq\xi_{n}^{2}$ and $\xi_{n}^{-}\leq\xi_{n}^{2}$. Because of this we can use the variance bound above to conclude that both $\mathop{\mathbb{E}}(\xi_{n}^{+}|\mathcal{F}_{n})\leq C$ and $\mathop{\mathbb{E}}(\xi_{n}^{-}|\mathcal{F}_{n})\leq C$ hold true for the same $C\in\mathbb{R^{+}}$. Let $\Phi_{n+1}$ be the number of edges added to the graph adjacent to a vertex with location at most $x$. The random variable $\Phi_{n+1}$ takes the values $\{0,1,2\}$ where $P(\Phi_{n+1}=0)=0>c_1$ and $P(\Phi_{n+1}=2)=c_2>0$.
\begin{equation}\label{last one}
2(1-c_1)=2(1-P(\Phi_{n+1}=0|\mathcal{F}_{n}))\geq\mathop{\mathbb{E}}(\Phi_{n+1}|\mathcal{F}_{n})\geq2P(\Phi_{n+1}=2|\mathcal{F}_{n})=c_2
\end{equation}
Using equation (\ref{last one}) we can see that $P(\xi^{+}_{n+1}\geq2-2(1-c_1)|\mathcal{F}_{n})\geq c_2$ implies $\mathop{\mathbb{E}}(\xi_{n+1}^{+}|\mathcal{F}_{n})=2c_1c_2$. We can also see from $P(\xi^{+}_{n+1}\leq2-2c_2|\mathcal{F}_{n})\leq 1-c_1\leftrightarrow c_1\leq P(\xi^{-}_{n+1}\geq2-2c_2|\mathcal{F}_{n})$ that $\mathop{\mathbb{E}}(\xi_{n+1}^{-}|\mathcal{F}_{n})=2c_1(1-c_2)$. From these two results we can see that both $\mathop{\mathbb{E}}(\xi_{n+1}^{+}|\mathcal{F}_{n})$ and $\mathop{\mathbb{E}}(\xi_{n+1}^{-}|\mathcal{F}_{n})$ are bounded away from zero therefore we can conclude that both $\mathop{\mathbb{E}}(\xi_{n+1}^{+}|\mathcal{F}_{n})$ and $\mathop{\mathbb{E}}(\xi_{n+1}^{-}|\mathcal{F}_{n})$ are bounded above and below by positive values. Hence we can apply Theorem 2.9 of \cite{P.9} to show non-convergence to an unstable root.

In the case where $p$ is a touchpoint, we can apply the result stated as Theorem 2.5 in Antunovi\'{c}, Mossel and R\'{a}cz \cite{P.43} based on work by Pemantle in \cite{P.44}; the bounds given above on our noise immediately imply that the conditions needed are met, and so convergence to the touchpoint happens with positive probability.
\end{proof}

The following result completes the proof of Theorem \ref{main1} in the case $\Xi=\ekr$.
\begin{cor}\label{limpsi}The sequence of measures defined by $\Psi_n$ converges weakly, almost surely, to a limit defined by a (possibly random) distribution function $\Psi:[0,1]\to[0,1]$.
\end{cor}
\begin{proof}By definition, we have that for each $n$ $\Psi_n$ is a non-decreasing cadlag function with $\Psi_n(1)=1$ and, almost surely, $\Psi_n(0)=0$.  We apply Theorem \ref{equstabroot} to a countable dense set of $x\in(0,1)$ and for $x$ in this set we define $\Psi(x)=\lim_{n\to\infty}\Psi_n(x)$.  We complete the definition of $\Psi$ by defining $\Psi(0)=0$ and $\Psi(1)=1$ and defining $\Psi$ elsewhere to ensure that it is cadlag.\end{proof}

We now move towards proving Theorem \ref{main2} in the case $\Xi=\ekr$.  To do this, we consider a two dimensional stochastic approximation for $(\Psi_n(z),D_n)$.  Let $\chi$ be the location of a selected vertex under preferential attachment from $G_n$.  Assuming that $v_0$ is the only vertex at location $z$, which occurs almost surely, we have
\begin{align*}
P(\chi_n =z|\mathcal{F}_{n})=&D_{n}\label{option1},\\
P(\chi_n <z|\mathcal{F}_{n})=&\Psi_{n}(z)-D_{n},\\
P(\chi_n >z|\mathcal{F}_{n})=&1-\Psi_{n}(z).
\end{align*}
The probability of the $k^{\text{th}}$ ranked location being $z$, and hence of selecting vertex $v_0$ for $v_{n+1}$ to attach to is given by
\begin{equation}\label{equ of select vert v1}
h(\Psi_n(z),D_n;\ekr)=\sum^{k-1}_{j=0}\sum^{r}_{i=k}\binom{r}{i}\binom{i}{j}(\Psi_n(z)-D_n)^jD_n^{i-j}(1-\Psi_n(z))^{r-i}.
\end{equation}
We can now form our two dimensional stochastic approximation.
\begin{lem}\label{second sae}
We have
\begin{equation*}
D_{n+1}-D_{n}=\frac{F_{2}(\Psi_{n}(z),D_{n};\ekr)+\zeta_{n+1}}{(n+n_{0})(2+\alpha)+\alpha},
\end{equation*}
where $F_{2}(y,d;\ekr)=h(y,d;\ekr)-(2+\alpha)d$ and $\zeta_{n+1}$ is the noise incurred with $D_{n}$ such that $\mathop{\mathbb{E}}(\zeta_{n+1}|\mathcal{F}_{n})=0$.
\end{lem}
\begin{proof}
Similarly to how we found equation \eqref{f1(y;x,ekr)} we use \eqref{equ of select vert v1} to obtain
\begin{equation*}
\begin{aligned}
\mathop{\mathbb{E}}(D_{n+1}|\mathcal{F}_{n})={}&\frac{D_{n}\left( (n+n_{0})(2+\alpha)-2 \right)+h(\Psi_{n}(z),D_{n};\ekr)}{(n+n_{0}+1)(2+\alpha)-2}\\
&+\frac{D_{n}(2+\alpha)-D_{n}(2+\alpha)}{(n+n_{0}+1)(2+\alpha)-2}\\
\mathop{\mathbb{E}}(D_{n+1}|\mathcal{F}_{n})={}&D_{n}+\frac{-D_{n}(2+\alpha)+h(\Psi_{n}(z),D_{n};\ekr)}{(n+n_{0})(2+\alpha)+\alpha}\\
\mathop{\mathbb{E}}(D_{n+1}|\mathcal{F}_{n})-D_{n}={}&\frac{F_{2}(\Psi_{n}(z),D_{n};\ekr)}{(n+n_{0})(2+\alpha)+\alpha}
\end{aligned}
\end{equation*}
We therefore have the stochastic approximation equation for $D_{n}$ in the form
\begin{equation*}
D_{n+1}-D_{n}=\frac{F_{2}(\Psi_{n}(z),D_{n};\ekr)+\zeta_{n+1}}{(n+n_{0})(2+\alpha)+\alpha},
\end{equation*}
where we define $\zeta_{n+1}$ as
\begin{equation*}
\zeta_{n+1}=\frac{D_{n+1}-\mathop{\mathbb{E}}(D_{n+1}|\mathcal{F}_{n})}{(n+n_0)(2+\alpha)+\alpha}
\end{equation*}
which has expectation zero.
\end{proof}
We have now formed a two dimensional system of stochastic approximation equations represented by
\begin{equation*}
\begin{pmatrix}
    \Psi_{n+1}(z) \\
    D_{n+1}
\end{pmatrix}
=\frac{1}{\gamma_{n+1}}
\begin{pmatrix}
    F_{1}(\Psi_{n}(z);z,\ekr) \\
    F_{2}(\Psi_{n}(z),D_{n};\ekr)
\end{pmatrix}
+
\frac{1}{\gamma_{n+1}}
\begin{pmatrix}
    \xi_{n+1} \\
    \zeta_{n+1}
\end{pmatrix}.
\end{equation*}

The following relationship between $F_1$ and $F_2$ will be useful for identifying stationary points of the vector field associated to our two dimensional stochastic approximation.
\begin{thm}\label{relationship theorem}
We have that
\begin{equation}\label{relationship equation}
F_1(y-d;x,\ekr)=F_1(y;z,\ekr)-F_2(y,d;\ekr).
\end{equation}
\end{thm}
\begin{proof}
We use induction on $k$.  For $k=1$,
\begin{align*}
F_1(y-d;x,\basisvector{1}{r})={}&1-(1-y+d)^r -(2+\alpha)(y-d)+x(\alpha+1)\\
&-\left(-(2+\alpha)d+\sum^{r}_{i=1}\binom{r}{i}d^{i}(1-y)^{r-i}\right)\\
={}&-(2+\alpha)(y) + x(\alpha+1) + \sum^{r}_{i=1}\binom{r}{i}y^{i}(1-y)^{r-i} \\
={}&F_1(y;x,\basisvector{1}{r})-F_2(y,d;\basisvector{1}{r})
\end{align*}
Assuming (\ref{relationship equation}) holds for $k$,
\begin{align*}
&F_1(y-d;x,\basisvector{k+1}{r})\\
={}&\sum^{r}_{i=k+1}\binom{r}{i}(y-d)^{i}(1-y+d)^{r-i}-(2+\alpha)(y-d)+x(\alpha+1)\\
={}&F_1(y-d;x,\ekr)-\binom{r}{k}(y-d)^{k}(1-y+d)^{r-k}\\
={}&F_1(y;z,\ekr)-F_2(y,d;\ekr)-\binom{r}{k}(y-d)^{k}(1-y+d)^{r-k}\mbox{, by the induction}\\
&\mbox{hypothesis,}\\
={}&F_1(y;x,\basisvector{k+1}{r})-F_2(y,d;\ekr)-\binom{r}{k}(y-d)^k(1-y+d)^{r-k}+\binom{r}{k}y^k(1-y)^{r-k}\\
={}&F_1(y;x,\basisvector{k+1}{r})-\sum^{k-1}_{j=0}\sum^{r}_{i=k}\binom{r}{i}\binom{i}{j}(y-d)^jd^{i-j}(1-y)^{r-i}\\
&-\sum^{r}_{i=k}\binom{r}{i}\binom{i}{k}(y-d)^kd^{i-k}(1-y)^{r-i} \\
&+\sum^{k}_{j=0}\binom{r}{k}\binom{k}{j}(y-d)^jd^{k-j}(1-y)^{r-k}-(2+\alpha)d\\
={}&F_1(y;x,\basisvector{k+1}{r})-\sum^{k-1}_{j=0}\sum^{r}_{i=k}\binom{r}{i}\binom{i}{j}(y-d)^jd^{i-j}(1-y)^{r-i}\\
&-\sum^{k}_{j=k}\sum^{r}_{i=k}\binom{r}{i}\binom{i}{j}(y-d)^jd^{i-j}(1-y)^{r-i} \\
&+\sum^{k}_{j=0}\sum^{k}_{i=k}\binom{r}{i}\binom{i}{j}(y-d)^jd^{i-j}(1-y)^{r-i}-(2+\alpha)d\\
={}&F_1(y;x,\basisvector{k+1}{r})-\left(\sum^{k}_{j=0}\sum^{r}_{i=k+1}\binom{r}{i}\binom{i}{j}(y-d)^jd^{i-j}(1-y)^{r-i}+(2+\alpha)d \right)\\
={}&F_1(y;x,\basisvector{k+1}{r})-F_2(y,d;\basisvector{k+1}{r}),
\end{align*}
completing the proof.
\end{proof}

It follows from Theorem \ref{relationship theorem} that if $F_1(y_i;x,\ekr)=F_1(y_j;x,\ekr)=0$ then $F_2(y_i,y_i-y_j;x,\ekr)=0$ and that the solutions to $F_1(y;z,\ekr)=F_2(y,d;\ekr)=0$ all take the form $(y,d)=(y_i,y_i-y_j)$ where $i,j\in\{1,2,\dots,r\}$.

To investigate the stability of the stationary points, we will now calculate the Jacobian $M$ of the two dimensional system.  We can observe that $M$ is an upper triangular matrix because $F_1(y;z,\ekr)$ does not depend on $D_n$ so $\frac{\partial F_1}{\partial d}=0$. Therefore we have that the eigenvalues of our system are
\begin{align*}
\lambda_1(y;\ekr)&=\sum^{r}_{i=k}\binom{r}{i}y^{i-1}(1-y)^{r-i-1}(i-ry)-(2+\alpha),\\
\lambda_2(y,d;\ekr)&=\sum^{k-1}_{j=0}\sum^{r}_{i=k}\binom{r}{i}\binom{i}{j}Q(r,i,j,y,d)(y-d)^{j-1}d^{i-j-1}(1-y)^{r-i-1}
-(2+\alpha),
\end{align*}
where $Q(r,i,j,y,d)=(y-d)(i-iy+rd-id)+j(1-y)(2d-y)$.

\begin{thm}\label{only one eig needed}
For any $y\in\{y_i,y_j\}$ such that $F_1(y;z,\ekr)=0$, $y_i-y_j\geq0$ and when
\begin{equation*}
\frac{\partial}{\partial y}F_1(y;z,\ekr)=\lambda_1(y;\ekr)<0
\end{equation*}
is satisfied for both $y_i,y_j\in\{y_1,y_2,\dots y_r\}$ we have that $(y_i,y_i-y_j)$ is a stable equilibrium of the vector field $(F_1(y;z,\ekr),F_2(y,d;\ekr))$.
\end{thm}

\begin{proof} By rearranging equation (\ref{relationship equation}) we can see that
\[
F_2(y,d;\ekr)=F_1(y;z,\ekr)-F_1(y-d;x,\ekr)
\]
and can deduce that
\[\lambda_2(y,d;\ekr)=\frac{\partial}{\partial d}\left(F_1(y;z,\ekr)-F_1(y-d;x,\ekr)\right).\]
Here $F_1(y;z,\ekr)$ does not depend on $d$ therefore $F_1'(y;z,\ekr)=0$. It is observable that $\lambda_2(y,d;\ekr)=-\frac{\partial}{\partial d}F_1(y-d;x,\ekr)=\lambda_1(y-d;\ekr)$. All roots of $F_1(y;z,\ekr)=F_2(y,d;\ekr)=0$ are of the form $(y_i,y_i-y_j)$. If we evaluate our eigenvalue at this point we get $\lambda_1(y_i;\ekr)$ and $\lambda_2(y_i,d_i;x,\ekr)=\lambda_1(y_j;\ekr)$, which, referring to our initial conditions, are both negative. Therefore the pair $y_i$ and $y_j$ form the possible limit $(y_i,y_i-y_j)$.
\end{proof}

\begin{cor}\label{2dlimits}If $y_i\geq y_j$ are two stable fixed points of $F_1(y;z,\ekr)$, then there is positive probability of $(\Psi_n(z),D_n)\to (y_i,y_i-y_j)$ as $n\to\infty$.\end{cor}
\begin{proof} Theorem \ref{only one eig needed} shows that $(y_i,y_i-y_j)$ is a stable stationary point of the vector field $(F_1(y;z,\ekr),F_2(y,d;\ekr))$.  The conclusion then follows from Theorem 2.16 of Pemantle \cite{P.9}.\end{proof}
This completes the proof of Theorem \ref{main2} in the case $\Xi=\ekr$.

To prove Theorem \ref{main3}, we first note that where $p$ is a touchpoint of $F_1(y;x,\ekr)$ with $F_1(y;x,\ekr)$ non-positive in a neighbourhood of $p$ there will be a neighbourhood of $p$ which contains no zeros of $F_1(y;x-u,\Xi)$ for positive $u$.  Hence the probability of $\Psi(x-u)$ being in this neighbourhood of $p$ is zero, but we know from Theorem \ref{equstabroot} that there is positive probability that $\lim_{n\to\infty} \Psi_n(x)=p$.  Hence there is positive probability of a discontinuity at $x$.  The same applies if $F_1(y;x,\ekr)$ is non-negative in a neighbourhood of $p$ with $x-u$ replaced by $x+u$.

\subsection{Proofs of Theorems \ref{main1} to \ref{main3} in the general case}

We now extend the proofs of Theorems \ref{main1} to \ref{main3} in the case where $\Xi$ is not necessarily equal to $\ekr$.  We can derive
\begin{align*}
F_1(y;x,\Xi)&=\sum^r_{l=1}\Xi_l F_1(y;x,\elr)\\
&=z(\alpha+1)-(2+\alpha)y+\sum^{r}_{l=1}\Xi_l \sum^{r}_{i=l}\binom{r}{i}y^{i}(1-y)^{r-i}
\end{align*}
and extend the definition of $F_2$ from Lemma \ref{second sae} as
\begin{align*}
F_2(y,d;\Xi)&=\sum^r_{l=1}\Xi_l F_2(y,d;\elr)\\
&=\left( \sum^{r}_{l=1}\Xi_l \sum^{l-1}_{j=0}\sum^{r}_{i=l}\binom{r}{i}\binom{i}{j}(y-d)^j d^{i-j}(1-y)^{r-i} \right)-(2+\alpha)d.
\end{align*}
We can see that Lemmas \ref{first sae} and \ref{second sae} still hold, and the arguments for Theorem \ref{equstabroot} and Corollary \ref{limpsi} work in the same way as for the case $\Xi=\ekr$, completing the proof of Theorem \ref{main1}.

By considering the sums we can see that Theorem \ref{relationship theorem} still holds, so if we let $y\in\{y_1,y_2,\dots,y_r\}$ be the set of zeros of $F_1(y;x,\Xi)$, the stationary points are still of the form $(y_i,y_i-y_j)$.  It is easy to see that the eigenvalues of the Jacobian are now
\begin{align*}
\lambda_1(y;\Xi)&=-(2+\alpha)+\sum^r_{l=1}\Xi_l \frac{\partial}{\partial y}F_1(y;x,\elr)\\
&=-(2+\alpha)+\sum^r_{l=1}\Xi_l \lambda_1(y;\elr);\\
\lambda_2(y,d;\Xi)&=-(2+\alpha)+\sum^r_{l=1}\Xi_l \frac{\partial}{\partial d}F_2(y,d;\elr)\\
&=-(2+\alpha)+\sum^r_{l=1}\Xi_l \lambda_1(y-d;\elr).
\end{align*}
As a result we can see that Theorem \ref{only one eig needed} can be extended to this case: if we have two roots of $F_1(y;x,\Xi)$, namely $y_i,y_j$, that satisfy $\lambda_1(y_i;\Xi)<0$ and $\lambda_1(y_j;\Xi)<0$ then $(y_i,y_i-y_j)$ is a stable equilibrium of the vector field given by $F_1(y;z,\Xi)$ and $F_2(y,d;\Xi)$.  This completes the proof of Theorem \ref{main2}.

Finally, the proof of Theorem \ref{main3} is the same as for the case $\Xi=\ekr$.

\subsection{Proof of Theorem \ref{highlander}}

\begin{proof}
By differentiating $F_1(y;x,\ekr)$ we show that for every $x$ there are at most two values of $\Psi(x)$ which occur with positive probability, and where there are two such values that they occur in two disjoint intervals which do not depend on $x$. Thus a point of condensation must almost surely involve a jump between these regions. Since $\Psi(x)$ is increasing by definition, this can happen at most once.

We have
\begin{align*}
\frac{\partial g(y;\ekr)}{\partial y}&=\frac{\partial}{\partial y}\sum_{i=k}^{r}\binom{r}{i}y^{i}(1-y)^{r-i}\\
&=\sum_{i=k}^{r}i\binom{r}{i}y^{i-1}(1-y)^{r-i}-\sum_{i=k}^{r-1}(r-i)\binom{r}{i}y^{i}(1-y)^{r-i-1} \\
&=\sum_{i=k}^{r}r\binom{r-1}{i-1}y^{i-1}(1-y)^{r-i}-\sum_{i=k}^{r-1}r\binom{r-1}{i}y^{i}(1-y)^{r-i-1} \\
&=r\binom{r-1}{k-1}y^{k-1}(1-y)^{r-k},
\end{align*}
because all other terms cancel. So
\[\frac{\partial F_1(y;x,\ekr)}{\partial y}=r\binom{r-1}{k-1}y^{k-1}(1-y)^{r-k}-(2+\alpha)\,;\]
note that this does not depend on $x$.

If $k=r$ then $\frac{\partial^{2}F_1(y;x,\ekr)}{\partial y^2}$ is positive on $(0,1)$, and if $k=1$ then it is negative on $(0,1)$. Otherwise,
\begin{align*}
\frac{\partial^2 F_1(y;x,\ekr)}{\partial y^2}&=r\binom{r-1}{k-1}\bigl((k-1)(1-y)-(r-k)y\bigr)y^{k-2}(1-y)^{r-k-1}\\
&=r\binom{r-1}{k-1}y^{k-2}(1-y)^{r-k-1}\bigl((k-1)-(r-1)y\bigr),
\end{align*}
which is positive for $y\in(0,\frac{k-1}{r-1})$ and negative for $y\in(\frac{k-1}{r-1},1)$. It follows that, for any choice of $k$, the equation
\begin{equation}r\binom{r-1}{k-1}y^{k-1}(1-y)^{r-k}-(2+\alpha)=0\label{turning}\end{equation}
has at most two roots in $(0,1)$, and that if it has exactly two such roots $z_1<z_2$ then the left-hand side is positive for $y\in(z_1,z_2)$.

Suppose \eqref{turning} has two roots $z_1<z_2$. Then for any $x$ we have that $F_1(y;x,\ekr)$ is strictly decreasing on the intervals $[0,z_1)$ and $(z_2,1]$, but strictly increasing on $(z_1,z_2)$. Consequently, $F_1(y;x,\ekr)=0$ has at most one root $y_1(x)\in[0,z_1]$, at most one root $y_2(x)\in(z_1,z_2)$ (which, if it exists, is an unstable zero), and at most one root $y_3(x)\in[z_2,1]$. Further, for each $i$, $y_i(x)$ is continuous on the range of $x$ for which it exists. Note that $F_1(0;0,\ekr)=F_1(1;1,\ekr)=0$ and so $y_1(0)=0=\Psi(0)$ and $y_3(1)=1=\Psi(1)$. By Theorem \ref{main1}, almost surely for almost all $x$ we have $\Psi(x)\in\{y_1(x),y_3(x)\}$. Let $x^*=\sup\{x\in[0,1]:\Psi(x)=y_1(x)\}$; since $\Psi$ is increasing and $y_1(x)$ and $y_3(x)$ are continuous we have $\Psi(x)=y_1(x)$ for all $x\in[0,x^*)$ and $\Psi(x)=y_3(x)$ for all $x\in(x^*,1]$. It follows that $\Psi$ is continuous everywhere except possibly at $x^*$, as required.

If \eqref{turning} has exactly one root, $z$, in $(0,1)$, then the equation $F_1(y;x,\ekr)=0$ has at most one root $y_1(x)\in[0,z]$ and at most one root $y_2(x)\in(z,1]$ for every $x\in [0,1]$; again we must have $y_1(0)=0=\Psi(0)$ and $y_2(1)=1=\Psi(1)$. Defining $x^*$ as above, almost surely $\Psi(x)=y_1(x)$ for all $x\in[0,x^*)$ and $\Psi(x)=y_2(x)$ for all $x\in(x^*,1]$, so again $\Psi$ is continuous except possibly at $x^*$. Finally, if \eqref{turning} has no roots in $[0,1]$, then the equation $F_1(y;x,\ekr)=0$ has exactly one root $y_1(x)\in[0,1]$ for every $x\in[0,1]$ and we must have $y_1(0)=0=\Psi(0)$ and $y_1(1)=1=\Psi(1)$. Thus we almost surely have $\Psi(x)\equiv y_1(x)$, and there are no points of condensation.
\end{proof}

\section{Examples}\label{Section 4}
In this section we consider some examples of choices of $\Xi$ which illustrate how the results of Theorems \ref{main1} and \ref{main2} can apply to different cases.

\subsection{Middle of three}\label{midofthreemodd}

As $r=1$ gives standard preferential attachment, and the cases with $r=2$ and either $\Xi=(0,1)$ or $\Xi=(1,0)$ are equivalent to cases of the choice-fitness model of \cite{Sou.1}, which has rather different behaviour, the simplest case which illustrates our results is the ``middle of three'' model given by $r=3$ and $\Xi=(0,1,0)$.

We can express our functions $F_1(y;x,\ekr)$ and $F_2(y,d;\ekr)$ as \[F_1(y;x,\midthree)=-2y^3+3y^2-(2+\alpha)y+x(\alpha+1)\] and \[F_2(y,d;\midthree)=-2d^{3}+6d^{2}y-3d^{2}-6dy^{2}+6dy-d(2+\alpha).\]

For $x\in(0,1)$, define $\{\psi_1(x),\psi_2(x),\psi_3(x)\}$ such that $\psi_1(x)\leq\psi_2(x)\leq\psi_3(x)$ as the three real roots of $F_1(y;z,\midthree)=0$ when three exist and $\psi(x)$ as the single root when only one exists.  We have $F_1'(y;x,\midthree)=-6y^3+6y^2-(2+\alpha)$, and so $F_1(y;x,\midthree)$ is decreasing in $y$ whenever $\alpha\geq-\frac12$, but has turning points at $y=\frac12\pm\sqrt{-(1+2\alpha)/12}$ for $\alpha\in(-1,-\frac12)$. At $x=\frac12$ we have $F_1(y;x,\midthree)=(\frac12-y)(F_1'(y;x,\midthree)+1+2\alpha)/3$. Consequently the values of $F_1(y;\frac12,\midthree)$ at the turning points are $\mp\sqrt{-(1+2\alpha)^3/108}$, and the corresponding values of $F_1(y;\frac12,\midthree)$ are given by $(1+\alpha)(x-\frac12)\mp\sqrt{-(1+2\alpha)^3/108}$. It follows that there are multiple roots if and only if $\lvert x-\frac12\rvert\leq\sqrt{\frac{-(1+2\alpha)^3}{108(1+\alpha)}}$; write $s=s(\alpha)$ for this quantity. Note that $s<\frac12$ if and only if $\alpha>-\frac78$.

\begin{figure}[!htb]
\begin{tikzpicture}
\begin{axis}[
width=.95\textwidth,
height=6cm,
axis lines = left,
ymin=-0.15,ymax=0.2,
xlabel = $y$,
ylabel = {$F_1(y;x,\midthree)$},
]

\addplot [
domain=0:1,
samples=100,
color=black,
dotted,
thick,
]
{-2*x^3+3*x^2-1.25*x+0.159};
\addlegendentry{$x=\frac{9+\sqrt{6}}{18}$}

\addplot [
domain=0:1,
samples=100,
color=black,
dashed,
thick,
]
{-2*x^3+3*x^2-1.25*x+0.091};
\addlegendentry{$x=\frac{9-\sqrt{6}}{18}$}

\addplot [
domain=0:1,
samples=100,
color=black,
]
{0};
\end{axis}
\end{tikzpicture}
\caption{$F_1(y;x,\midthree)$ for $\alpha=-0.75$ and $x=\frac12\pm s$.}\label{Fig_2}
\end{figure}

Figure \ref{Fig_2} plots $F_1(y;x,\midthree)$ against $y\in[0,1]$ for the value $\alpha=-\frac{3}{4}$ and $x=\frac12\pm s$, and Figure \ref{Fig_4} plots the roots of $F_1(y;x,\midthree)$ against $x\in[0,1]$. There is exactly one real root when $x\in\{[0,\frac{9+\sqrt{6}}{18})\cup(\frac{9-\sqrt{6}}{18},1]\}$ and three real roots when $x\in[\frac{9-\sqrt{6}}{18},\frac{9+\sqrt{6}}{18}]$.

\begin{figure}[!htb]
\centering
\includegraphics[width=\textwidth]{middle-roots}
\caption{The roots of $F_1(y;x,\midthree)$ for $x\in[0,1]$ and $\alpha=-0.75$.}\label{Fig_4}
\end{figure}

In this setting, Theorem \ref{main1} becomes the following.
\begin{thm}\label{mid of 3 phase trans}
For a fixed location $x\in(0,1)$, the random variable $\Psi_n(x)$ converges pointwise as $n\to\infty$ almost surely to the following limits.
\begin{equation*}
\lim_{n\to\infty}\Psi_n(x)=
\begin{cases}
\psi(x) ,& \text{if } \alpha\geq-\frac{1}{2}\\
\psi(x) ,& \text{if } \alpha\in(-\frac{7}{8},-\frac{1}{2}) \text{ and }x\not\in\left[\frac{1}{2}-s,\frac{1}{2}+s\right]\\
\psi_{1}(x)\text{ or }\psi_{3}(x),& \text{if } \alpha\in(-\frac{7}{8},-\frac{1}{2})\text{ and } x\in\left[\frac{1}{2}-s,\frac{1}{2}+s\right]\\
\psi_{1}(x)\text{ or }\psi_{3}(x),& \text{if } \alpha\leq-\frac{7}{8}.
\end{cases}
\end{equation*}
\end{thm}
We can see there is a phase transition at $\alpha=-\frac{1}{2}$:
when $\alpha\geq-\frac{1}{2}$, $\Psi$ is almost surely continuous, whereas when $\alpha<-\frac{1}{2}$, $\Psi$ follows the lower root $\psi_1(x)$
until a random point in $[\frac{1}{2}-s,\frac{1}{2}+s]$ at which it jumps to the upper root $\psi_3(x)$, giving a point of condensation.

\begin{figure}[!htb]
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{middle-persistent}
\end{minipage}
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{middle-non-persistent}
\end{minipage}
\caption{Results from simulations for $\alpha=-0.75$}\label{mid-sims}
\end{figure}

If $-\frac{7}{8}<\alpha<\frac{1}{2}$, Theorem \ref{main2} implies that this point of condensation is with positive probability caused by a persistent hub
occurring at a random location which has full support on $(\frac{1}{2}-s,\frac{1}{2}+s)$. However, Theorem \ref{main3} implies that the point of condensation
also has positive probability of occurring at each of the endpoints $\frac{1}{2}-s$ and $\frac{1}{2}+s$; since almost surely these values are not fitnesses
of any vertex, it follows that there is also a positive probability that there is no persistent hub. Figure \ref{mid-sims} shows the results of two simulations
for $\alpha=-0.75$ with different behaviour: in the first simulation there is rapid convergence of $\Psi_n$ to a limit with condensation occurring via a
persistent hub, whereas in the second $\Psi_n$ shows much slower convergence, apparently towards condensation at $\frac12+s$.
If $\alpha\leq-\frac{7}{8}$, Theorem \ref{main2} implies that the location of the jump has full support on $(0,1)$.

As we can now implement conditions on $F_1(y,x;\ekr)$ using $x$ and $\alpha$ to control whether we have one or three real roots we can solve
\begin{equation*}
F_1(y,x;\ekr)=F_2(y,d,x;\ekr)=0
\end{equation*}
by assuming $F_1(y,x;\ekr)=0$ has three real roots $\{\psi_1(x),\psi_2(x),\psi_3(x)\}$. We therefore can solve $F_2(y,d,x;\ekr)=0$ to get $\delta_1=0$ and $\delta_2$ and $\delta_3$ given by $\frac{3}{4}(2\psi_i(x)-1)\pm\frac{1}{4}\sqrt{-12\psi_i(x)^2+12\psi_i(x)-7-8\alpha}$.

\begin{figure}[!htb]
\begin{tikzpicture}
\begin{axis}[
width=\textwidth,
height=8cm,
axis lines = left,
ymin=-0.75,ymax=0.5,
xlabel = $y$,

xmin=0, xmax=1,

]

\addplot [
domain=0.0917517:0.908248,
samples=300,
color=black,
thick,
dash dot,
]
{-6*x^2+6*x-1.25};

\addplot [
domain=0.0917517:0.908248,
samples=1000,
color=black,
dashed,
thick,
]
{-0.25*((-12*x^2 + 12*x -7 +6)^0.5)*(6*x-3+(-12*x^2 + 12*x -7 +6)^0.5)};

\addplot [
domain=0.0917517:0.908248,
samples=1000,
color=black,
dotted,
thick,
]
{-0.25*((-12*x^2 + 12*x -7 +6)^0.5)*(3-6*x+(-12*x^2 + 12*x -7 +6)^0.5)};

\addplot [
domain=0:1,
samples=300,
color=black,
]
{-2*x^3 + 3*x^2 - 1.25*x + 0.25*(0.5-(6^0.5)/18)};

\addplot [
domain=0:1,
samples=300,
color=black,
]
{-2*x^3 + 3*x^2 - 1.25*x + 0.25*(0.5+(6^0.5)/18)};

\addplot [
domain=0:1,
samples=100,
color=black,
]
{0};
\end{axis}
\end{tikzpicture}
\caption{Plot of eigenvalues of the Jacobian when $\alpha=-0.75$}\label{Fig_5}
\end{figure}

Figure \ref{Fig_5} illustrates Theorem \ref{only one eig needed} in this case, showing the eigenvalues of the Jacobian at the stationary points.
The solid curves show $F_1(y;x,\midthree)$ for $y\in[0,1]$ at $x=\frac{1}{2}\pm s$, the upper and lower limits of the region of $x$ where there are three real roots. In this same region are plotted $\lambda_1(y;\midthree)$ (the parabola), $\lambda_2(y,\delta_2;\midthree)$ and $\lambda_2(y,\delta_3;\midthree)$ (dashed and dotted lines respectively). The two regions where the eigenvalues are both negative overlap with where the roots of $F_1(y;x,\ekr)$ would be as $x$ increases from the lower limit to the upper limit.

\subsection{Second or sixth of seven}\label{secondorsixth}
The second example we will discuss makes use of the vector notation introduced in Section \ref{Section 2}. The ``middle of three'' model of Section \ref{midofthreemodd} is an example of selecting the $k^{\text{th}}$ highest location from $r$ selections, and demonstrates a phase transition below which condensation must occur at a single point. By Theorem \ref{highlander}, no such model can have condensation occurring simultaneously at more than one point. We now consider whether models in which more than one rank has positive probability of being selected can demonstrate multiple points of condensation. If there are three (or more) stable roots of $F_1(y;x,\Xi)$ for some range of $x$ then by Theorem \ref{main2} there is a positive probability of a jump from the first to the second in that range, and in this case since there are still higher stable roots, another jump must occur. If there are two disjoint ranges with two or more stable roots, separated by a range in which there is only one, then at least one jump must occur in each of these ranges. In this section we give an example which (for different values of $\alpha$) demonstrates that both of these can occur, even for models where only two ranks have positive probability. A real-life example of when two points of condensation might be expected is that of a bipartisan election, where two candidates from different regions of the location parameter (which might represent political position) may both attract a given proportion of the votes.

The distribution we shall use is $\Xi=(0,\frac{1}{2},0,0,0,\frac{1}{2},0)$, that is, each new vertex is equally likely to connect to the second or sixth rank of seven candidates; this was the simplest example we could find which allowed for two points of condensation. In this setting, \eqref{prob select vert leq x} gives the following expression for $F_1(y;x,\Xi)$:
\begin{align*}
F_1(y;x,\Xi)&=\frac{1}{2}F_1(y;x,\basisvector 27)+\frac{1}{2}F_1(y;x,\basisvector 67)\\
&=\frac{1}{2}\left(\sum^{7}_{i=2}\binom{7}{i}y^{i}\left( 1-y \right)^{7-i}\right)+\frac{1}{2}\left(\sum^{7}_{i=6}\binom{7}{i}y^{i}\left( 1-y \right)^{7-i}\right)\\
&\phantom{=}-(2+\alpha)y+x(\alpha+1)\\
&=-6y^7+21y^6-42y^5+\frac{105}{2}y^4-35y^3+\frac{21}{2}y^2-(2+\alpha)y +x(\alpha+1).
\end{align*}

The middle of three model features two phase transitions, at $\alpha=-\frac{1}{2}$ and $\alpha=-\frac{7}{8}$. To discuss phase transitions in this model, we note that the derivative (with respect to $y$) $F_1'(y;x,\Xi)$ does not depend on $x$ and is decreasing in $\alpha$ for fixed $y$; we also note that the symmetry in the system means that $F_1'(y;x,\Xi)=F_1'(1-y;x,\Xi)$.  We can thus define
\[\alpha_1=\inf\{\alpha: F_1'(y;x,\Xi)\leq 0\; \forall\; \alpha\in (0,1)\};\]
for $\alpha\geq \alpha_1$, $F_1(y;x,\Xi)$ is a decreasing function of $y$ and so for all $x\in (0,1)$ there is a unique root of $F_1(y;x,\Xi)=0$
in $(0,1)$, whereas for $\alpha<\alpha_1$ there is at least one interval of values of $x$ which have at least three roots of $F_1(y;x,\Xi)=0$ in
$(0,1)$.  Hence our results show that condensation occurs almost surely if and only if $\alpha<\alpha_1$. We can calculate $\alpha_1$ explicitly,
since
\[F_1''(y;x,\Xi)=-\tfrac72(2x-1)(6x^2-6x+4-\sqrt{10})(6x^2-6x+4+\sqrt{10})\]
does not depend on $\alpha$. It is easy to verify that $F_1'(y;x,\Xi)$ is maximised at $y=\frac12\pm\frac16\sqrt{6\sqrt{10}-15}$,
and the maximum value is positive if and only if $\alpha<\frac{35\sqrt{10}-116}{9}$.

For $\alpha\in(-1,\alpha_1)$ $F_1(y;x,\Xi)$ has, in $(0,1)$, two local minima at $\eta_1(\alpha)$ and $\eta_3(\alpha)$ and two local maxima at $\eta_2(\alpha)$ and $\eta_4(\alpha)$, where $\eta_1(\alpha)<\eta_2(\alpha)<\eta_3(\alpha)<\eta_4(\alpha)$; these values depend on $\alpha$ but not on $x$.  Set $\alpha_2=\sup\{\alpha: F_1(\eta_2(\alpha);x,\Xi)\geq F_1(0;x,\Xi)\}$; then the set of values of $x$ which have at least three roots includes $0$ and $1$ if and only if $\alpha\leq \alpha_2$.  Next, set $\alpha_3=\sup\{\alpha: F_1(\eta_4(\alpha);x,\Xi)\geq F_1(\eta_1(\alpha);x,\Xi)\}$; then for $\alpha<\alpha_3$ there is a range of values of $x$ such that there are five roots of $F_1(y;x,\Xi)=0$ in $(0,1)$, whereas for $\alpha>\alpha_3$ there are always at most three, and there are two disjoint intervals of $x$ where there are three.  Hence for $\alpha\in (\alpha_3,\alpha_1)$ there will almost surely be two points of condensation, whereas for $\alpha<\alpha_3$ there will be positive probability of there being a single point of condensation.

Finally, set $\alpha_4=\sup\{\alpha: F_1(\eta_4(\alpha);x,\Xi)\geq F_1(0;x,\Xi)\}$; then there are five roots of $F_1(y;x,\Xi)=0$ in $(0,1)$ for all $x\in (0,1)$ if
and only if $\alpha\leq \alpha_4$, and hence for this range of $\alpha$ a single point of condensation can occur at a location which is fully supported on $(0,1)$.

\begin{figure}[!htb]
\begin{subfigure}{.45\linewidth}
\begin{tikzpicture}[scale=1]

\begin{axis}[
width=\textwidth,
height=6cm,
axis lines = left,
ymin=-0.6,ymax=0.7,
xlabel = $y$,

xmin=0, xmax=1,
ymin=-0.15, ymax=0.15,
]

\addplot [
domain=0:1,
samples=300,
color=black,
dotted,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.59114)*x+0.5*(-0.59114+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
dashed,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.59114)*x+1*(-0.59114+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.59114)*x+0*(-0.59114+1)};

\addplot [
domain=0:1,
samples=100,
color=black,
]
{0};
\end{axis}

\end{tikzpicture}
\caption{$\alpha=\alpha_1$} \label{fig:topleftgrid4}
\end{subfigure}

\begin{subfigure}{.45\linewidth}
\centering
\begin{tikzpicture}[scale=1]
\begin{axis}[
width=\textwidth,
height=6cm,
axis lines = left,
ymin=-0.6,ymax=0.7,
xlabel = $y$,

xmin=0, xmax=1,
ymin=-0.15, ymax=0.15,
]

\addplot [
domain=0:1,
samples=300,
color=black,
dotted,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.87562)*x+0.5*(-0.87562+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
dashed,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.87562)*x+1*(-0.87562+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.87562)*x+0*(-0.87562+1)};

\addplot [
domain=0:1,
samples=100,
color=black,
]
{0};
\end{axis}

\end{tikzpicture}
\caption{$\alpha=\alpha_2$} \label{fig:toprightgrid4}
\end{subfigure}

\\
\begin{subfigure}{.45\linewidth}
\centering
\begin{tikzpicture}[scale=1]

\begin{axis}[
width=\textwidth,
height=6cm,
axis lines = left,
ymin=-0.6,ymax=0.7,
xlabel = $y$,

xmin=0, xmax=1,
ymin=-0.15, ymax=0.15,
]

\addplot [
domain=0:1,
samples=300,
color=black,
dotted,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.93144)*x+0.5*(-0.93144+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
dashed,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.93144)*x+1*(-0.93144+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.93144)*x+0*(-0.93144+1)};

\addplot [
domain=0:1,
samples=100,
color=black,
]
{0};
\end{axis}
\end{tikzpicture}
\caption{$\alpha=\alpha_3$} \label{fig:bottomleftgrid4}
\end{subfigure}

\begin{subfigure}{.45\linewidth}
\centering
\begin{tikzpicture}[scale=1]
\begin{axis}[
width=\textwidth,
height=6cm,
axis lines = left,
ymin=-0.6,ymax=0.7,
xlabel = $y$,

xmin=0, xmax=1,
ymin=-0.15, ymax=0.15,
]

\addplot [
domain=0:1,
samples=300,
color=black,
dotted,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.96842)*x+0.5*(-0.96842+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
dashed,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.96842)*x+1*(-0.96842+1)};

\addplot [
domain=0:1,
samples=300,
color=black,
]
{-6*x^7+21*x^6-42*x^5+52.5*x^4-35*x^3+10.5*x^2-(2-0.96842)*x+0*(-0.96842+1)};

\addplot [
domain=0:1,
samples=100,
color=black,
]
{0};
\end{axis}
\end{tikzpicture}
\caption{$\alpha=\alpha_4$} \label{fig:bottomrightgrid4}
\end{subfigure}

\caption{$F_1(y;x,\Xi)$ evaluated at four different values of $\alpha$ corresponding to the phase transitions that appear for this choice of $\Xi$, and at three different values of $x$: from top to bottom, $x=1$, $x=\frac{1}{2}$ and $x=0$.}\label{Fig_9}
\end{figure}

The four transition points satisfy $\alpha_{1}=\frac{35\sqrt{10}-116}{9}\approx-0.59114$,
$\alpha_{2}\approx-0.87562$, $\alpha_{3}\approx-0.93144$ and $\alpha_{4}\approx-0.96842$. Plots of $F_1(y;x,\Xi)$ for each of the transition points $\alpha_1$, $\alpha_2$, $\alpha_3$ and $\alpha_4$ are shown in Figure \ref{Fig_9}, and plots showing the roots of $F_1(y;x,\Xi)=0$ for two specific values of $\alpha$ ($\alpha=-0.85\in (\alpha_2,\alpha_1)$ and $\alpha=-0.95\in (\alpha_4,\alpha_3)$) appear in Figure \ref{sec-six-roots}.

\begin{figure}[!htb]
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{sec-six-roots-85}
\end{minipage}
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{sec-six-roots-95}
\end{minipage}
\caption{The roots of $F_1(y;x,\Xi)$ for $\alpha=-0.85$ (left) and $\alpha=-0.95$ (right).}\label{sec-six-roots}
\end{figure}

For $\alpha=-0.85$ the stable roots and touchpoints are given by three continuous partial functions of $x$: $\psi_1$ defined on $(0,\beta_2]$,
$\psi_3$ defined on $[\beta_1,1-\beta_1]$, and $\psi_5$ defined on $[1-\beta_2,1)$, where $0<\beta_1<\beta_2<1/2$. (In fact we have $\beta_1\approx 0.0492$ and $\beta_2\approx 0.2721$.) Each function gives a stable root on the interior of its domain and a touchpoint on the boundary. Consequently, by Theorem \ref{main1}, almost surely $\Psi(x)$ takes the value $\psi_1(x)$ on some interval containing $(0,\beta_1)$, the value $\psi_3(x)$ on some interval containing $(\beta_2,1-\beta_2)$, and the value $\psi_5(x)$ on some interval containing $(1-\beta_1,1)$. Thus there are almost surely two points of condensation. By Theorem \ref{main2}, each of these points of condensation is caused by a persistent hub with positive probability. However, Theorem \ref{main3} implies there is also a positive probability of condensation occurring without a persistent hub at $\beta_1$, $\beta_2$, $1-\beta_2$ or $1-\beta_1$. Figure \ref{85sims} shows the results of two simulations: in the first simulation, both points of condensation arise from persistent local hubs, but in the second the upper part of $\Psi_n$ shows much slower convergence, apparently towards condensation at $1-\beta_2$. Our results do not give any bounds on the relative likelihoods of these types of behaviour; however, simulations suggest that it is relatively uncommon to have early hubs forming in both the feasible regions $(\beta_1,\beta_2)$ and $(1-\beta_2,1-\beta_1)$.

\begin{figure}[!htb]
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{85-persistent}
\end{minipage}
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{85-non-persistent}
\end{minipage}
\caption{Results from simulations for $\alpha=-0.85$}\label{85sims}
\end{figure}

For $\alpha=-0.95$ the corresponding partial functions of $x$ are $\psi_1$ defined on $(0,1-\beta]$,
$\psi_3$ defined on $(0,1)$, and $\psi_5$ defined on $[1-\beta,1)$, where $\beta\approx0.3420$. In this case Theorem \ref{main1} implies that there are nontrivial regions on which $\Psi(x)$ takes the values $\psi_1(x)$ and $\psi_5(x)$, but there need not be any $x$ for which $\Psi(x)=\psi_3(x)$, since that is never the only stable root. Consequently there may be two points of condensation if such an $x$ exists, and one point of condensation corresponding to a jump from $\psi_1$ to $\psi_5$ otherwise. Theorem \ref{main2} implies that each of these types of behaviour has positive probability, and Figure \ref{95sims} shows the results of two simulations exhibiting the two types of behaviour. As before, Theorem \ref{main3} implies that there is a positive probability of non-persistent condensation occuring at $\beta$ or $1-\beta$.

\begin{figure}[!htb]
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{95-one-jump}
\end{minipage}
\begin{minipage}[b]{.5\textwidth}\vspace{0pt}
\centering\includegraphics[width=\textwidth]{95-two-jumps}
\end{minipage}
\caption{Results from simulations for $\alpha=-0.95$}\label{95sims}
\end{figure}

\section{Acknowledgments}
The third author acknowledges support from the University of Sheffield for funding their research in the form of a graduate teaching assistant studentship, and would also like to thank Dr Nic Freeman for all of his feedback during the writing of this paper.

The first author acknowledges support from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 639046).

\bibliographystyle{abbrv}
\bibliography{references}
\end{document}


TITLE: $(A\times B)\cap {(C\times D)}=(A\cap C)\times(B\cap D)$ Analogy in Group Theory
QUESTION [3 upvotes]: In set theory we have $(A\times B)\cap {(C\times D)}=(A\cap C)\times(B\cap D)$, is this true in group theory if we replace the $\times$ by products of subgroups i.e.
$$(AB)\cap (CD)=(A\cap C)(B\cap D)$$
I know that $(A\cap C)(B\cap D)$ is contained in $AB\cap CD$ but I could not prove the other inclusion.

REPLY [0 votes]: I don't think (AB)∩(CD)=(A∩C)(B∩D) is true.Consider dihedral group D12 generated by a and t such that a^6=1, t^2=1, atat=1. The subgroups A,B,C,D of D12, in which A={1,t},B={1,ta^5},C={1,a^2,a^4},,D={1,a^3}, contradict to (AB)∩(CD)=(A∩C)(B∩D), because (AB)∩(CD)={1,a^5} and (A∩C)(B∩D)={1}.