1
$\begingroup$

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the process, $0 \leq m \leq {n \choose 2}$, the fraction $\rho^n_k(m)$ of vertices in components with size $k$ is given by: $$\rho^n_k(m)= \sum_{v \in V(G_n)} \frac{1_{\{|\mathcal C_m(v)|=k\}}}{n}, k \in \{1, \ldots,n\},$$ with $|\mathcal C_m(v)|$the size of the component that contains the vertex $v \in V(G_n)$ at step $m$. As $n$ go to $\infty$, the (random) sequence of functions $(\rho^n(\lfloor t.n \rfloor ), t \geq 0)$ is known to converge to $(\rho(t), t \geq 0)$ the unique (deterministic) solution of the (discrete) Smoluchowski (coagulation) equation: $$\rho'_k(t)= k \bigg[ (\rho \star \rho)_k(t) - 2 \rho_k(t) \sum_{k \in \mathbb N} \rho_k(t) \bigg]$$ started at $\rho_k(0)=1_{\{k =1\}}$. I used $(\rho \star \rho)_k = \sum_{m+n=k} \rho_m \rho_n$ to denote the convolution. (The solution of this equation is explicit and involves the Borel Tanner distribution, that describes the size of a Poisson Galton Watson tree).

Question:

I now replace $G(n)$ by a sequence of (deterministic or random) graphs $H(n)$ with $n$ vertices. These $H(n)$ are supposed to have enough edges so that the problem is meaningful (that is $\omega(n)$ edges). Also, in case $H(n)$ is random, the alea should be independent of the construction of the process.

I wonder what are the relevant (geometric, probabilistic, ...) conditions on the sequence of graphs $H(n)$ that ensure the convergence of $(\rho^n(\lfloor t.n \rfloor), t \geq 0)$ to $(\rho(t), t \geq 0)$ the solution of the Smoluchowski equation?

Intuition:

An example where convergence does not hold is the discrete torus $H(n)=(\mathbb Z/m \mathbb Z)^d$, for fixed $d$, with $n= m^d$. If $d=d(n) \to \infty$ however this should work.

A condition like "all degrees in $H(n)$ are equal, and diverge with $n$" is relevant as a sufficient condition. It is however in no way a necessary condition. For instance we may take $H(n)=G(n,m)$ defined above, for $m=\omega(n)$.

All comments are welcomed!

$\endgroup$
1
$\begingroup$

just a comment: Looking up for conditions that would simply guarantee that the difference in, say, total variation between the distribution of the statistic you consider on $G(n)$ and the one on $H(n)$ goes to zero as $n$ goes to infinity at first instance, how does this relate to your question? Hope this is not too bad of a trade off to your question and might help you to find something relevant in the literature. Chau

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.