Name
Abstract | ||
|---|---|---|
We discuss the definability of finite graphs in first-order logic with two relation symbols for adjacency and equality of vertices. The logical depth D(G) of a graph G is equal to the minimum quantifier depth of a sentence defining G up to isomorphism. The logical width W(G) is the minimum number of variables occurring in such a sentence. The logical length L(G) is the length of a shortest defining sentence. We survey known estimates for these graph parameters and discuss their relations to other topics (such as the efficiency of the Weisfeiler-Lehman algorithm in isomorphism testing, the evolution of a random graph, quantitative characteristics of the zero-one law, or the contribution of Frank Ramsey to the research on Hilbert's Entscheidungsproblem). Also, we trace the behavior of the descriptive complexity of a graph as the logic becomes more restrictive (for example, only definitions with a bounded number of variables or quantifier alternations are allowed) or more expressible (after powering with counting quantifiers). |
Year | Venue | Keywords |
|---|---|---|
2010 | Contemporary Mathematics | first order logic,computational complexity,random graph |
Field | DocType | Volume |
Graph canonization,Discrete mathematics,Combinatorics,Line graph,Graph isomorphism,Graph property,Graph power,Graph homomorphism,Clique-width,Pathwidth,Mathematics | Journal | 558 |
ISSN | Citations | PageRank |
0271-4132 | 8 | 0.54 |
References | Authors | |
43 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| OLEG PIKHURKOAND | 1 | 8 | 0.54 |
| Oleg Verbitsky | 2 | 191 | 27.50 |