A text I am reading is discussing ways to couple branching processes, and describes the following 2 pairings, the latter of which I am failing to understand. (I include the former for the sake of clarification.) We will use $T_{n,p}$ for the binomial branching process with parameters $n$ and $p$; we have a random graph $G_{n,p}$ in the Erdos-Renyi framework, and for a vertex $v$ of $G_{n,p}$, we write $T_v$ for the exploration tree of the component of $v$ obtained by a breadth-first search (the "obvious" way to obtain a tree starting at vertex $v$).

The text says there are 2 natural couplings of $T_v$ and $T_{n,p}$: firstly, we can couple them so that $T_v \subset T_{n,p}$: generate them together, and always add fictitious vertices to the vertex set of $G_{n,p}$ for the branching process to use. All descendants of fictitious vertices are fictitious.

Secondly (the coupling I don't understand), we can couple $T_v$ with $T_{n-k,p}$ such that one of two alternatives holds: either $T_v \supset T_{n-k,p}$ or both $T_v$ and $T_{n-k,p}$ have at least $k$ vertices. Indeed, grow $T_v$ (coupled with $T_{n-k,p}$) into (only) $n-k$ new vertices at each step, and stop when this is no longer possible.

Could anyone who understands the meaning of this latter coupling possibly try and explain it to me in different words? I'm not really following what the text is trying to say. I get the first coupling fine, but for this second one I can't figure out what's going on. Why, for example, would the 2 separate cases be $T_v \supset T_{n-k,p}$ or both $T_v$ and $T_{n-k,p}$ have at least $k$ vertices? Why does the latter possibility prevent the former? It seems to be saying that given $T_v$, at each stage pick at most $n-k$ vertices which are joined to vertices we picked in the previous stage, and if we have more vertices than that to pick from then ignore them until a later time.

So then do we choose which vertices to "ignore" at random? Do we choose which to ignore? If we pick a vertex $w$ and then in the next round we ignore some vertex which is adjacent only to $w$, is $w$ "lost forever"? And again, what's the issue with "both $T_v$ and $T_{n-k,p}$ have at least $k$ vertices"? I'm sure this is very simple once you understand it, but I'm not sure how standard it is (the book from which I take this passage is not yet published), so if I need to provide more details please just ask. Many thanks.


Your Answer

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

Browse other questions tagged or ask your own question.