Name
Abstract | ||
|---|---|---|
We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifier rank) of such a sentence. We define the succinctness function s(n) (resp. its variant q(n)) to be the minimum L(G) (resp. D(G)) over all graphs on n vertices. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.apal.2005.04.003 | Annals of Pure and Applied Logic |
Keywords | Field | DocType |
Definability,Finite graphs,First order logic,Turing machine simulation | Integer,Binary logarithm,Discrete mathematics,Graph,Combinatorics,First order theory,Vertex (geometry),Upper and lower bounds,First order,Recursive functions,Mathematics | Journal |
Volume | Issue | ISSN |
139 | 1 | 0168-0072 |
Citations | PageRank | References |
9 | 1.12 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Pikhurko | 1 | 318 | 47.03 |
| Joel Spencer | 2 | 41 | 4.73 |
| Oleg Verbitsky | 3 | 191 | 27.50 |