### Abstract

Let D(G) be the smallest quantifier depth of a first-order formula which is true for a graph G but false for any other non-isomorphic graph, This can be viewed as a measure for the descriptive complexity of G in first-order logic. We show that almost surely D(G) = ⊖(ln/ln ln n). where G is a random tree of order n or the giant component of a random graph script G sign(n, c/n) with constant c > 1. These results rely on computing the maximum of D(T) for a tree T of order n and maximum degree l, so we study this problem as well.

Original language | English (US) |
---|---|

Pages (from-to) | 375-400 |

Number of pages | 26 |

Journal | Combinatorics Probability and Computing |

Volume | 16 |

Issue number | 3 |

DOIs | |

State | Published - May 2007 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'First-order definability of trees and sparse random graphs'. Together they form a unique fingerprint.

## Cite this

Bohman, T., Frieze, A., ŁUczak, T., Pikhurko, O., Smyth, C., Spencer, J., & Verbitsky, O. (2007). First-order definability of trees and sparse random graphs.

*Combinatorics Probability and Computing*,*16*(3), 375-400. https://doi.org/10.1017/S0963548306008376