Name
Abstract | ||
|---|---|---|
Let D(G) be the smallest quantifier depth of afirst-order formula which is true for a graph G but falsefor any other non-isomorphic graph. This can be viewed as a measurefor the descriptive complexity of G in first-orderlogic.We show that almost surely D(G)=θ(lnn / ln lnn), where G is a random tree of order n or thegiant component of a random graph G(n,c/n)with constant cD(T) for a tree T of order n andmaximum degree l, so we study this problem as well. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1017/S0963548306008376 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
constant cd,order n,ln lnn,random graph,afirst-order formula,sparse random graphs,order n andmaximum degree,graph g,non-isomorphic graph,first-order definability,descriptive complexity,random tree,maximum degree,first order,giant component | Random regular graph,Discrete mathematics,Combinatorics,Line graph,Random graph,Graph power,Cubic graph,Degree (graph theory),Graph bandwidth,Mathematics,Branch-decomposition | Journal |
Volume | Issue | ISSN |
16 | 3 | 0963-5483 |
Citations | PageRank | References |
2 | 0.39 | 9 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Tomasz Łuczak | 3 | 225 | 40.26 |
| Oleg Pikhurko | 4 | 318 | 47.03 |
| Clifford Smyth | 5 | 24 | 6.91 |
| JOEL SPENCER | 6 | 2 | 0.39 |
| Oleg Verbitsky | 7 | 191 | 27.50 |