Trouble in understanding a proof in a Random graph paper

83 Views Asked by At

I am reading a paper on Random graphs (Asymptotic properties of a random graph with duplications, Backhausz and Mori). In that, I am having some trouble understanding a part of the proof. It's not a mathematical step but an idea of how the proof is started.

In the paper, two models for duplication of graphs are proposed:

Model $1$: In a given graph, we choose (not necessarily different) old vertices independently, uniformly at random. Then the new vertex is added to the graph. We connect it to the first vertex and to all its neighbors. After that, we delete all edges emanating from the second old vertex we have selected, with the possible exception that edges of the new vertex cannot be deleted.

Model $2$: We choose two (not necessarily different) old vertices independently, uniformly at random. The new vertex is connected to the first one and to its neighbors. Then we delete all edges of the second vertex without any exceptions.

After this a theorem is proposed whose statement isn't of much relevance. The proof starts as following:

Both in model 1 and 2 two old vertices are selected with replacement, independently, uniformly at random. Thus we can couple the models such that the selected vertices are the same in all steps. The duplication part is the same in the two versions. The difference is in the deletion: in model 1, the edges of the new vertex cannot be deleted. So in version 1, we do the following. In the deletion part, we colour an edge red if it is saved in model 2. That is, if it connects the new vertex with the old vertex to be deleted.

I am having trouble understanding this colouration part. Isn't the last two statements contradictory? If it connects the new vertex with the old vertex to be deleted, then we colour the edge red. But then how can it be saved it model 2?

Any help?

Here is the paper, in case anyone wants to read it: https://arxiv.org/pdf/1308.1506.pdf

1

There are 1 best solutions below

0
On BEST ANSWER

The phrase "we colour an edge red if it is saved in model 2" is almost certainly a mistake in the paper. See the next paragraph:

The colouring is defined in such a way that the graph sequence of the black edges is a realization of version 2. Indeed, edges turning red are deleted and hence the copies of them does not appear in this model, but all other edges are black.

So my understanding is that the phrase should have said "we colour an edge red if it is saved in model 1, but not in model 2". That is, in full detail, the coupled model is generated as follows:

  1. Two vertices $v_1$ and $v_2$ of the graph are selected, with replacement.
  2. A new vertex $x$ is created.
  3. A black edge is drawn from $x$ to $v_1$.
  4. For every vertex $w$ with the edge $v_1w$, a corresponding edge $xw$ is drawn, in the same color as $v_1w$.
  5. For every vertex $w \ne x$ with the edge $v_2w$, that edge is deleted.
  6. If the edge $v_2x$ is present, it is not deleted, but it is colored red.

As a result, the distribution of the graph of all edges follows Model 1; the distribution of the graph of only black edges follows Model 2.