A very sharp threshold for first order logic distinguishability of random graphs

arXiv2207.11593MaRDI QIDQ6405833FDOQ6405833

Authors: Itai Benjamini, M. E. Zhukovskii 

Publication date: 23 July 2022

Abstract: In this paper we find an integer $h=h(n)$ such that the minimum number of variables of a first order sentence that distinguishes between two independent uniformly distributed random graphs of size $n$ with the asymptotically largest possible probability $frac14-o(1)$ belongs to $h,h+1,h+2,h+3$. We also prove that the minimum (random) $k$ such that two independent random graphs are distinguishable by a first order sentence with $k$ variables belongs to $h,h+1,h+2$ with probability $1-o(1)$.

This page was built for publication: A very sharp threshold for first order logic distinguishability of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405833)