Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\) (Q2254100)

Given a natural number \(k\) and a rational number \(\alpha=s/q\) with \(s<q\) and \(s\) and \(q\) coprime, we set \(n=n(k)=q^{2}k\), \(a=a(k)=sqk\) and \(c=c(k)=s^{2}k\) and consider the distance graph \(G_{k}\) whose vertex set is the set of \(n\)-vectors with all components 0 or 1, with \(a\) of the components being ones, two such vectors being adjacent if and only if their inner product is equal to \(c\). We then form a random distance graph \({\mathcal G}(G_{k},p)\) by retaining each edge of \(G_{k}\) with probability \(p\) independent of all other edges. Recall that a model of random graphs is said to satisfy the zero-one law if, as the number of vertices tends to infinity, for every first-order property \(L\). (i.e. property expressible by a first order sentence) the probability the random graph has \(L\) tends to either 0 or 1. For example, it is well-known that the usual Erdős-Rényi random graphs have this property. The paper under review considers the situation for random distance graphs. It is known by work of Zhukovskii that random distance graphs do not satisfy the zero-one law. However one can speak of the extended zero-one \(j\)-law holding if, for all first-order formulae with quantifier depth bounded by \(j\) we have all limits of subsequences of \(\mathbb{P}\) (\({\mathcal G}(G_{k},p)\in L\)) being 0 or 1, and of the extended zero-one law holding if for all first-order formulae, all limits of subsequences are 0 or 1. The paper states (but does not prove in detail) theorems which characterise the values of \(j\) and sequences \({\mathcal G}(G_{k_{i}},p)\) for which the extended zero-one law holds, the extended zero-one \(j\)-law holds but the extended zero-one law does not, and for which the extended zero-one \(j\)-law does not hold. By way of some flavour of the results, the extended zero-one 4-law always holds but when \(j\geq 6\) the situation is more complicated, with divisibility criteria on the numbers \(a(k)-c(k)\). The results are stated to depend, as so often in this area, on the Ehrenfeucht game; in particular, they use the notion of a special set of vertices.