First order complexity of finite random structures
<|reference_start|>First order complexity of finite random structures: 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^{\infty}/c_0$. The well-known FO zero-one law and FO convergence law correspond to FO complexities equal to $\{0,1\}$ and a subset of $\mathbb{R}$, respectively. We present a hierarchy of FO complexity classes, introduce a stochastic FO reduction that allows to transfer complexity results between different random structures, and deduce using this tool several new logical limit laws for binomial random structures. Finally, we introduce a conditional distribution on graphs, subject to a FO sentence $\varphi$, that generalises certain well-known random graph models, show instances of this distribution for every complexity class, and prove that the set of all $\varphi$ validating 0--1 law is not recursively enumerable.<|reference_end|>
@article{demin2024first,
    title={First order complexity of finite random structures},
    author={Danila Demin, Maksim Zhukovskii},
    journal={arXiv preprint arXiv:2402.02567},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.02567},
    primaryClass={cs.LO cs.DM math.CO math.LO math.PR}
}