The first order convergence law fails for random perfect graphsMüller, T. & Noy, M., Dec-2018, In : Random structures & algorithms. 53, 4, p. 717-727 11 p.
Research output: Contribution to journal › Article › Academic › peer-review
We consider first order expressible properties of random perfect graphs. That is, we pick a graph G(n) uniformly at random from all (labeled) perfect graphs on n vertices and consider the probability that it satisfies some graph property that can be expressed in the first order language of graphs. We show that there exists such a first order expressible property for which the probability that G(n) satisfies it does not converge as n -> infinity.
|Number of pages||11|
|Journal||Random structures & algorithms|
|Publication status||Published - Dec-2018|
|Event||18th International Conference on Random Structures and Algorithms - Gniezno, Poland|
Duration: 7-Aug-2017 → 11-Aug-2017
18th International Conference on Random Structures and Algorithms
07/08/2017 → 11/08/2017Gniezno, Poland
- logical limit laws, random perfect graphs