Name
Abstract | ||
|---|---|---|
Let D(G) be the minimum quantifier depth of a first order sentence @F that defines a graph G up to isomorphism. Let D"0(G) be the version of D(G) where we do not allow quantifier alternations in @F. Define q"0(n) to be the minimum of D"0(G) over all graphs G of order n. We prove that for all n we have log^*n-log^*log^*n-2@?q"0(n)@?log^*n+22, where log^*n is equal to the minimum number of iterations of the binary logarithm needed to bring n to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ejc.2007.04.016 | European Journal of Combinatorics |
Keywords | Field | DocType |
binary logarithm,order n,f. define q,small depth,graph decompositions,graphs g,ehrenfeucht game on graphs,order sentence,graph g,minimum quantifier depth,decomposable graph,minimum number,quantifier alternation,first order logic,descriptive complexity of graphs | Adjacency list,Discrete mathematics,Graph,Binary logarithm,Combinatorics,Vertex (geometry),First order,Upper and lower bounds,Isomorphism,Mathematics,Alternation (linguistics) | Journal |
Volume | Issue | ISSN |
28 | 8 | 0195-6698 |
Citations | PageRank | References |
3 | 0.41 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Pikhurko | 1 | 318 | 47.03 |
| Joel Spencer | 2 | 3 | 0.41 |
| Oleg Verbitsky | 3 | 191 | 27.50 |