Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T04:19:21.519Z Has data issue: false hasContentIssue false
  • English
  • Français

First-Order Definability of Trees and Sparse Random Graphs

Published online by Cambridge University Press:  01 May 2007

TOM BOHMAN ,
ALAN FRIEZE ,
TOMASZ ŁUCZAK ,
OLEG PIKHURKO ,
CLIFFORD SMYTH ,
JOEL SPENCER  and
OLEG VERBITSKY
TOM BOHMAN
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: tbohman@moser.math.cmu.edu, alan@random.math.cmu.edu, pikhurko@cmu.edu)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: tbohman@moser.math.cmu.edu, alan@random.math.cmu.edu, pikhurko@cmu.edu)
TOMASZ ŁUCZAK
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznań 61-614, Poland (e-mail: tomasz@amu.edu.pl)
OLEG PIKHURKO
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: tbohman@moser.math.cmu.edu, alan@random.math.cmu.edu, pikhurko@cmu.edu)
CLIFFORD SMYTH
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail: csmyth@math.mit.edu)
JOEL SPENCER
Affiliation:
Courant Institute, New York University, New York, NY 10012, USA (e-mail: spencer@cims.nyu.edu)
OLEG VERBITSKY
Affiliation:
Institut für Informatik, Humboldt Universität Berlin, D-10099 Berlin, Germany (e-mail: verbitsk@informatik.hu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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)=\Theta(\frac{\ln n}{\ln\ln n})$, where G is a random tree of order n or the giant component of a random graph $\C G(n,\frac cn)$ 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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 3 , May 2007 , pp. 375 - 400
Copyright
Copyright © Cambridge University Press 2007

References

[1]Barbour, A. D. (1982) Poisson convergence and random graphs. Math. Proc. Camb. Phil. Soc. 92 349–359.CrossRefGoogle Scholar
[2]Bollobás, B. (2001) Random Graphs, 2ndedn, Cambridge University Press.CrossRefGoogle Scholar
[3]Chung, F. and Lu, L. (2001) The diameter of sparse random graphs. Adv. Appl. Math. 26 257–279.CrossRefGoogle Scholar
[4]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley–Interscience.CrossRefGoogle Scholar
[5]Kim, J. H., Pikhurko, O., Spencer, J. and Verbitsky, O. (2005) How complex are random graphs in first order logic? Random Struct. Alg. 26 119–145.CrossRefGoogle Scholar
[6]Moon, J. W. (1968) On the maximum degree in a random tree. Michigan Math. J. 15 429–432.CrossRefGoogle Scholar
[7]Ore, O. (1962) Theory of Graphs, AMS, Providence, RI.CrossRefGoogle Scholar
[8]Pikhurko, O., Spencer, J. and Verbitsky, O. (2005) Decomposable graphs and definitions with no quantifier alternation. To appear in Europ. J. Combin. The conference version (EuroComb'05) appeared in Discrete Math. & Theoretical Comput. Sci., Vol. AE, pp. 25–30.CrossRefGoogle Scholar
[9]Pikhurko, O., Spencer, J. and Verbitsky, O. (2006) Succinct definitions in the first order graph theory. Annals Pure Appl. Logic 139 74–109.CrossRefGoogle Scholar
[10]Pikhurko, O., Veith, H. and Verbitsky, O. (2006) The first order definability of graphs: Upper bounds for quantifier rank. Discrete Appl. Math. 154 2511–2529.CrossRefGoogle Scholar
[11]Pikhurko, O. and Verbitsky, O. (2005) Descriptive complexity of finite structures: Saving the quantifier rank. J. Symb. Logic 70 419–450.CrossRefGoogle Scholar
[12]Spencer, J. (2001) The Strange Logic of Random Graphs, Springer.CrossRefGoogle Scholar
[13]Stanley, R. P. (1997) Enumerative Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[14]Verbitsky, O. (2005) The first order definability of graphs with separators via the Ehrenfeucht game. Theoret. Comp. Sci. 343 158–176.CrossRefGoogle Scholar