Weights and degrees in a random graph model based on 3-interactions (Q396992): Difference between revisions

The paper under review studies a model of random graphs with interactions between sets of three vertices. In detail, initially probabilities \(p\), \(q\), \(r\) are given and we start with a triangle with all edges and vertices having weight 1. Then, at each stage, with probability \(p\) a new vertex is introduced and interacts with two old vertices: with probability \(r\) the two old vertices are the ends of an edge, each edge chosen with probability proportional to the edge weights, otherwise the two old vertices are chosen uniformly at random from all pairs of old vertices. Then, any absent edges between these three vertices are inserted and the weights of each edge in this triangle are increased by 1. Otherwise with probability \(1-p\) three old vertices are chosen to interact: with probability \(q\) a triangle of old vertices is chosen with probability proportional to the edge weights, and with probability \(1-q\), three vertices are chosen uniformly at random from the old vertices, any absent edges between these three vertices are inserted and again the triangle has all its edge weights increased by 1. The weight of a vertex is the sum of the weights of the triangles that vertex is in. The paper under review, extending earlier work by the authors, shows almost sure convergence of the proportion of vertices of degree \(d\) and weight \(w\) to a limit \(X_{d,w}\), which is described through a recurrence equation. Martingale techniques are amongst those used in this argument. This asymptotic joint distribution of weights and degrees is constructed in a different way in Section 4. This allows one to recover the asymptotic weight distribution. Finally, asymptotics of the maximum degree and maximum weight are discussed.