Mathematics – Combinatorics
Scientific paper
2010-03-25
Mathematics
Combinatorics
56 pages; 2 figures. Added references in this version
Scientific paper
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).
Pikhurko Oleg
Verbitsky Oleg
No associations
LandOfFree
Logical complexity of graphs: a survey does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Logical complexity of graphs: a survey, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logical complexity of graphs: a survey will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-556315