First order complexity of finite random structures

Danila Demin, Maksim Zhukovskii

For a sequence of random structures with $n$-element domains over a relational signature, we define its first order (FO) complexity as a certain subset in the Banach space $\ell^{\…