\(\gamma\)-variable first-order logic of uniform attachment random graphs (Q2113354)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(\gamma\)-variable first-order logic of uniform attachment random graphs |
scientific article |
Statements
\(\gamma\)-variable first-order logic of uniform attachment random graphs (English)
0 references
14 March 2022
0 references
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.
0 references
uniform attachment graph
0 references
first-order logic
0 references
pebble game
0 references