2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes, by adaptation of the usual proof.

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – 123...
    Commented May 21, 2017 at 17:54
  • $\begingroup$ It seems to me that reasoning about probabilities in terms of the Ehrenfeucht–Fraïssé game is unnecessarily complicated, nevertheless the underlying combinatorial argument should ultimately be the same. $\endgroup$
    – Emil Jeřábek
    Commented May 21, 2017 at 18:08
  • $\begingroup$ You're assuming that p is constant here, the interesting case of the zero-one law is that it tends to zero, so that your axioms do not all hold with probability one (some will, depends on the order of magnitude of p). Still there is 'usually' a zero-one law, except if you deliberately choose p which is in the threshold window of an FO property (what's not trivial is to show that there are few such choices). $\endgroup$
    – user36212
    Commented May 21, 2017 at 20:00
  • 1
    $\begingroup$ @user36212 The question asks for $p$ constant. $\endgroup$
    – Emil Jeřábek
    Commented May 21, 2017 at 20:14
  • $\begingroup$ Sure, but in the question they mention that 0<p<1 constant gives a 0-1 law (as per your proof sketch) and p(n)=n^{-\alpha} with \alpha irrational also does. Though again I think the proof of this goes through easily for bipartite model. $\endgroup$
    – user36212
    Commented May 22, 2017 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .