On the definability of properties of finite graphs (Q791548)

Let \({\mathcal D}\) be the class of second-order logical sentences whose variables range over first-order variables, unary relations and binary relations; the author shows that several properties of finite graphs can be defined in some special subclasses of \({\mathcal D}\). The set-theoretical relationship among those subclasses is presented in one of the main theorems (using analogues of the Fraïssé-Ehrenfeucht games and ultraproducts). The paper also obtains some upper and lower bounds on the number of quantifiers \((QN_ n)\) and on the quantifier rank \((QR_ n)\) of the formulas which define the above properties for the case of graphs with n vertices. The sequences of numbers \(QN_ n\) and \(QR_ n\) can be used to define a measure on the complexity of the definition of the properties he has characterized.