How Complex are Random Graphs in First Order Logic?
| dc.creator | Kim, Jeong Han | |
| dc.creator | Pikhurko, Oleg | |
| dc.creator | Spencer, Joel | |
| dc.creator | Verbitsky, Oleg | |
| dc.date | 2004-01-20 | |
| dc.date.accessioned | 2026-07-07T05:04:41Z | |
| dc.date.available | 2026-07-07T05:04:41Z | |
| dc.description | It is not hard to write a first order formula which is true for a given graph G but is false for any graph not isomorphic to G. The smallest number $(G) of nested quantifiers in a such formula can serve as a measure for the ``first order complexity'' of G. Here, this parameter is studied for random graphs. We determine it asymptotically when the edge probability p is constant; in fact, D(G) is of order log n then. For very sparse graphs its magnitude is Θ(n). On the other hand, for certain (carefully chosen) values of p the parameter D(G) can drop down to the very slow growing function log^* n, the inverse of the tower-function. The general picture, however, is still a mystery. | |
| dc.description | 27 pages | |
| dc.identifier | https://arxiv.org/abs/math/0401247 | |
| dc.identifier | http://arxiv.org/abs/math/0401247 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69901 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80 | |
| dc.title | How Complex are Random Graphs in First Order Logic? | |
| dc.type | text |