On Finite Rigid Structures

This is related to the problem of defining linear order on finite structures. If a linear order is definable on a finite structure A then A is rigid (which means that its only automorphism is the identity). There had been a suspicion that if K is the collection of all finite structures of a finitely axiomatizable class and if every K structure is rigid, then K permits a relatively simple uniform definition of linear order. That happens to be not the case. The main result of the paper is a probabilistic construction of finite rigid graphs. Using that construction, we exhibit a finitely axiomatizable class of finite rigid structures (called multipedes) such that no L^ω_{∞, ω} sentence φ with counting quantifiers defines a linear order in all the structures. Furthermore, φ does not distinguish between a sufficiently large multipede M and a multipede M’ obtained from M by moving a “shoe” to another foot of the same segment.