Probability Seminar: Moumanti Podder

The first order language on graphs consists of sentences, or graph properties, that are expressible using the relations of vertex equality (x = y) and vertex adjacency (x \sim y). In their 1988 paper, Shelah and Spencer showed that when 0 < \alpha < 1 is an irrational number, the Erdös-Rényi random graph G(n, n^{-\alpha}) satisfies the zero-one law for the first order language on graphs, i.e. for any first order sentence A, the limit \lim_{n \rightarrow \infty} \mathbb{P}\left[G(n, n^{-\alpha}) \text{ satisfies } A\right] exists and equals either 0 or 1.

It has been a long-standing question in mathematical logic as to whether the existential fragment of a given logic is less expressive compared to the full logic. In particular, one may consider whether, for certain edge probability functions, the random graph G(n, p(n)) satisfies the zero-one law for the existential fragment but not for the entire logic. In his 2012 paper, Zhukovskii showed that the minimum 0 < \alpha  < 1 such that G(n, n^{-\alpha}) satisfies the zero-one law for all first order sentences of quantifier depth at most k, is \frac{1}{k-2}. At first glance, it seems that this bound can be moved significantly for existential first order sentences of quantifier depth at most k, but this is not true, since we show that the minimum positive \alpha such that the zero-one law fails for the existential fragment is \frac{1}{k - 2 - O(k^{-2})}.
 

Joint with Maksim Zhukovskii, Department of Discrete Mathematics, Moscow Institute of Physics and Technology.