# zero-one law in bipartite random model $G(n,n,p)$

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $$\lim\limits_{n \rightarrow \infty} Pr(G(n,p)\text{ has property }Q) \in \{ 0, 1 \}.$$ It has been proved that any fixed $p$, $0 < p < 1$ , and $P(n) = n^{-\alpha}$ where $\alpha$ is an irrational number satisfy in Zero-One law.

Now, Let $G(n, n, p)$ denote the random bipartite graph derived from the complete bipartite graph $K_{n,n}$ where each edge is included independently with probability $p$. Does the random graph $G(n, n, p)$, where here p is fixed number between 0 and 1, obeys $0-1$ law?

Let $L$ be the first-order language with a unary predicate $P(x)$ (denoting one of the partitions) and $E(x,y)$ (for edges of the graph, directed from $P$ to its complement). Let $T$ be the $L$-theory consisting of $\forall x,y\,(E(x,y)\to P(x)\land\neg P(y))$, and axioms expressing that for any pair of disjoint finite sets $U$ and $V$ in one partition, there is a node in the other partition connected to every node in $U$, and no node in $V$. Then a straightforward back-and-forth argument shows that $T$ is $\omega$-categorical, hence complete. Moreover, an easy computation shows that each axiom of $T$ holds in $G(n,n,p)$ with probability converging to $1$. Thus, any FO sentence holds with limit probability $1$ if provable in $T$, and limit probability $0$ otherwise.
• Unfortunately, I do not know a lot about Logic. As I know the proof for the Binomial model is based on a variant of the Ehrenfeucht Game. More precisely: A function p = p(n) satisfies the Zero-One Law if and only iffor every t, letting G(n,p(n)), H(m,p(m)) be independently chosen random graphs on disjoint vértex sets, $$\lim_{n,m\to\infty} Pr [Duplicator wins EHR{G(n,p(n)),H(m,p(m)), t]] = 1 .$$ Now, I am curious to know is there such approach exist for random bipartite graphs? thanks May 21, 2017 at 17:54
• @user36212 The question asks for $p$ constant. May 21, 2017 at 20:14