Zero-one laws for random distance graphs with vertices in \0,1\^n
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.
- Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\)
- Zero-one law for random subgraphs of some distance graphs with vertices in Z^n
- The weak zero-one laws for the random distance graphs
- The weak zero-one law for the random distance graphs
- On a sequence of random distance graphs subject to the zero-one law
- A weak zero-one law for sequences of random distance graphs
- Zero-one laws for graphs with edge probabilities decaying with distance. Part I
- Zero-one laws for graphs with edge probabilities decaying with distance. Part II
- Zero-one laws for random \(k\)-partite graphs
- Zero-One Laws for Sparse Random Graphs
- A weak zero-one law for sequences of random distance graphs
- Coloring distance graphs and graphs of diameters
- On the rank of incidence matrices for points and lines of finite affine and projective geometries over a field of four elements
- Probabilities on finite models
- The probabilistic method
- The weak zero-one laws for the random distance graphs
- Zero-One Laws for Sparse Random Graphs
- MSO zero-one laws on random labelled acyclic graphs
- Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\)
- Zero-one law for random subgraphs of some distance graphs with vertices in Z^n
- Zero-One Laws for Connectivity in Inhomogeneous Random Key Graphs
- A weak zero-one law for sequences of random distance graphs
- Zero-one laws for graphs with edge probabilities decaying with distance. Part I
- Discrete metric spaces: structure, enumeration, and 0-1 laws
- Zero-one laws for random graphs with vertices in a Boolean cube
- Zero-one laws for graphs with edge probabilities decaying with distance. Part II
- The tenacity of zero-one laws
- The weak zero-one laws for the random distance graphs
This page was built for publication: Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2254100)
