\(\gamma\)-variable first-order logic of uniform attachment random graphs (Q2113354)

This paper examines the convergence of the probability that a first-order statement holds in a uniform attachment graph. To build such a random graph, we start from a complete graph of \(m\) vertices, and, at each step, we add a new vertex with \(m\) new edges, with the endpoints chosen uniformly at random from the already existing vertices, without replacement. The authors prove that if the number of different variables in a first-order sentence is at most \(m-2\), then the probability that the sentence is satisfied for this random graph with \(n\) vertices converges. It was already known that (contrary to many other random graph models, e.g. random regular graphs) the zero-one law is not true for this graph model for first-order sentences; the current paper shows that although the limit of the probabilities is not necessarily \(0\) or \(1\), it exists if the number of different variables is at most \(m-2\). As for the method of the proof, the authors rely on an already known connection between first-order logic statements and the winning strategy of a so-called pebble game, and certain local properties of uniform attachment graphs. Namely, in order to make use of this correspondence, the authors describe the typical position of cycles and paths of a given length in a uniform attachment graph.