First Order Definability of Trees and Sparse Random Graphs

Simple item page
dc.creatorBohman, Tom
dc.creatorFrieze, Alan
dc.creatorLuczak, Tomasz
dc.creatorPikhurko, Oleg
dc.creatorSmyth, Clifford
dc.creatorSpencer, Joel
dc.creatorVerbitsky, Oleg
dc.date2005-06-15
dc.date.accessioned2026-07-07T05:20:46Z
dc.date.available2026-07-07T05:20:46Z
dc.descriptionLet 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 first order descriptive complexity of G. We will show that almost surely D(G)=Θ(\ln n/\ln\ln n), where G is a random tree of order n or the giant component of a random graph G(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.
dc.description28 pages
dc.identifierhttps://arxiv.org/abs/math/0506288
dc.identifierhttp://arxiv.org/abs/math/0506288
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75498
dc.subjectCombinatorics
dc.subject05C80
dc.titleFirst Order Definability of Trees and Sparse Random Graphs
dc.typetext

Files

Collections

arXiv