Descriptive Complexity of Finite Structures: Saving the Quantifier Rank

Oleg Pikhurko, Oleg Verbitsky

Given a relational structure M on n elements, let D(M) be the minimum quantifier rank of a first order formula identifying M up to isomorphism in the class of n-element structures.…