Language evolution, coalescent processes, and the consensus problem on a social network

• We prove that agents arrive at a common lexicon in a new model of language evolution in a social network.
• The rate of convergence depends on the “spectral gap” of the graph.
• The proof hinges upon a novel relation to coalescent processes, usually seen in the context of population genetics.

In recent times, there has been an increased interest in theories of language evolution that have an applicability to the study of dialect formation, linguistic change, creolization, the origin of language, and animal and robot communication systems in general. One particular question that has attracted some interest has the following general form: how might a group of linguistic agents arrive at a shared communication system purely through local patterns of interaction and without any global agency enforcing uniformity? In this paper, we consider a natural model of language (or more precisely, word) evolution on a social network, prove several theoretical properties, and establish connections to related phenomena in biology, social sciences, and physics.