On winning strategies with unary quantifiers (Q2785670)

The author shows that connectivity of finite graphs cannot be expressed in monadic existential second-order logic with any set of unary generalized quantifiers. Moreover, he introduces the notion of a trivial graph and shows that for a finite set of non-trivial graphs \(\mathcal H\) the class \({\mathcal C}_{\mathcal H}\) of graphs having no graph in \(\mathcal H\) as a minor is not definable in first-order logic augmented with unary generalized quantifiers. On the other hand, if all graphs in \(\mathcal H\) are trivial then \({\mathcal C}_{\mathcal H}\) is first-order definable. The proofs use a combination of various extensions of the Ehrenfeucht-Fraïssé method.