Non-convergence of proportions of types in a preferential attachment graph with three co-existing types (2018)

Abstract: We consider the preferential attachment model with multiple vertex types introduced by Antunović, Mossel and Rácz. We give an example with three types, based on the game of rock-paper-scissors, where the proportions of vertices of the different types almost surely do not converge to a limit, giving a counterexample to a conjecture of Antunović Mossel and Rácz. We also consider another family of examples where we show that the conjecture does hold.

The picture (due to John Haslegrave) below shows a simulation of the rock-paper-scissors example, with the proportions of the three types over time, showing the cycling pattern. The grey line shows 27 times the product of the three proportions.