14
$\begingroup$

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the sentence tends to either 0 or 1 as $n$ goes to infinity. It is known that testing, for a given sentence, whether the limit is 0 or whether it is 1 is PSPACE-complete (Grandjean, "Complexity of the first-order theory of almost all finite structures", Information and Control 1983). One possible approach to performing this sort of test would be to sample random graphs of sufficiently large size and test whether they model the sentence; but this would be limited both by the difficulty of testing whether a graph models a given sentence and also by the convergence rate of the 0-1 law, as that would control the size of the graphs needed in this sampling scheme.

What if anything is known and published about more explicit upper or lower bounds on the convergence rate of $P_S$, for the worst-case sentence $S$ of a given length, as a function of $S$? Or to put it another way, if one wishes to get the correct limit with probability bounded away from $1/2$, how large a graph should one sample?

One simple example of a sentence that converges slowly is given by the Ramsey property: does this graph contain either a clique of size $k$ or an independent set of size $k$? The sentence for this has length $O(k^2)$ but one needs to sample graphs of size at least exponential in $k$ to discover that the limit probability is one. But maybe there are other sentences that converge even more slowly?

$\endgroup$
9
$\begingroup$

For definiteness, I will consider undirected graphs without self-loops, or equivalently, structures with a symmetric irreflexive binary predicate $E(x,y)$. These choices do not really matter.

The question mentions an exponential lower bound. It can be optimized as follows: $$\phi=\forall x_0\dots\forall x_{k-1}\,\exists x_k\,\bigwedge_{i<k}(x_k\ne x_i\land E(x_k,x_i))$$ is a sentence of length $O(k)$ that holds in sufficiently large random graphs, but as it implies the existence of cliques of size $k+1$, it needs graphs of size $2^{\Omega(k)}=2^{\Omega(|\phi|)}$ to hold with probability above $1/2$.

Conversely, I will show an exponential upper bound, using a more generous measure: the number of distinct variables in the formula. Note that the number of variables is bounded by the length of the formula, but may be substantially smaller (as modal logicians know, already the $2$-variable fragment of first-order logic is quite rich, albeit in a different language).

Let me say that an extension axiom of rank $k$ is a sentence of the form $$\forall x_0\dots\forall x_{k-1}\,\Bigl[\bigwedge_{i<j<k}x_i\ne x_j\to\exists x_k\,\Bigl(\bigwedge_{i<k}(x_k\ne x_i\land E(x_k,x_i)^{e_i})\Bigr)\Bigr],$$ where $e_0,\dots,e_{k-1}\in\{0,1\}$, and we use the notation $\phi^1=\phi$, $\phi^0=\neg\phi$. Let $E_k$ denote the conjunction of all $2^k$ extension axioms of rank $k$, together with the axiom stating that the universe has size at least $k$.

Observation: If $k\le l$, then $E_l$ implies $E_k$.

As is well known, $\def\rg{\mathit{RG}}\rg=\{E_k:k\in\mathbb N\}$ is an axiomatization of the complete theory of random graphs, which describes the sentences with limit probability $1$. Now, one easy way of showing the completeness of $\rg$ is to prove that if $A,B\models\rg$, then Duplicator has a winning strategy in the $n$-round Ehrenfeucht–Fraïssé game on $A,B$ for every $n$: indeed, whatever Spoiler plays in one of the models, Duplicator can match in the other one just by applying the relevant extension axiom.

In fact, if there are $k$ pebbles on each of the models, and Spoiler is placing a $(k+1)$th, then Duplicator can find a matching move by applying $E_k$. Thus, if we assume only that $A,B$ are models of $E_k$, then Duplicator can still win the $(k+1)$-round EF game, or even the $(k+1)$-pebble game. Consequently,

Proposition: Any two models of $E_k$ satisfy the same sentences using at most $k+1$ distinct variables.

In particular, if $\phi$ is a sentence using $k+1$ distinct variables, then $\phi$ or $\neg\phi$ follows from $E_k$.

On the other hand, if $n>k$, then a simple union bound shows that a random $n$-vertex graph fails to satisfy $E_k$ with probability at most $$2^k\binom nk(1-2^{-k})^{n-k}\le n^k(1-2^{-k})^n\le\exp(k\log n-n2^{-k}).$$

Corollary: If $\phi$ is a sentence using $k+1$ distinct variables with limit probability $p\in\{0,1\}$, and $n>k$, then $$|\Pr_G(G\models\phi)-p|\le\exp(k\log n-n2^{-k}),$$ where the probability is over random graphs with $n$ vertices. In particular, the probability is close to $p$ for $n$ larger than roughly $2^kk^2\log2$.

$\endgroup$
  • $\begingroup$ Thanks, this is just what I was looking for. Do you happen to know whether anything like this can be found in published sources?(In one place, that is; I'm pretty sure that the parts about extension axioms implying all k-variable properties and large-enough graphs obeying all extension axioms can be found easily enough in the literature.) $\endgroup$ – David Eppstein Dec 1 '15 at 22:39
  • $\begingroup$ I'm afraid I don't. The FO 0-1 law for random graphs is treated in many places, and the arguments I gave are pretty straightforward, hence there is a good chance such a source exists, but I can't give you a reference offhand. $\endgroup$ – Emil Jeřábek Dec 2 '15 at 11:26

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.