Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 717-727 |
| Number of pages | 11 |
| Journal | Random structures & algorithms |
| Volume | 53 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - Dec-2018 |
| Event | 18th International Conference on Random Structures and Algorithms - Gniezno, Poland Duration: 7-Aug-2017 → 11-Aug-2017 |
Keywords
- logical limit laws
- random perfect graphs