Critical mean out-degrees of directed, undirected and bidirectional lattice neighbour graphs

In lattice neighbour graphs on ℤd every vertex independently chooses a random set of nearest neighbours whose mean size β ∈ [0, 2d] varies continuously. From these choices one obtains a directed graph and two undirected graphs, in which an edge is open if one, respectively both, of its endpoints choose it. We study the three critical mean out-degrees βcU(d) ≤ βcD(d) ≤ βcB(d). Simulations in dimensions 2 ≤ d ≤ 10 show that they behave very differently: βcB(d) grows like √(2d), βcD(d) decreases like 1 + 1/(2d), and βcU(d) approaches one like 1 + 1/(8d2). We prove that βcB(d) = √(2d) + 1/2 + O(d−1/2) and βcD(d) = 1 + 1/(2d) + O(d−2), and that 1 + (1 + o(1))/(8d2) ≤ βcU(d) ≤ 1 + 1/(2d) + O(d−2). The lower bound βcB(d) ≥ √(2d) + 1/2 holds in every dimension d ≥ 2. In addition, we give explicit two-sided bounds in all dimensions, which for d ≥ 11 determine βcB(d) up to about 0.03, and we prove βcB(2) < 3. A column projection gives upper bounds on βcD(d) for all d ≥ 3 and shows βcD(d) < βcD(2) for d ≥ 8. The main tool is a sharp local comparison between the mixture of uniform k- and (k + 1)-subsets and a product law, which holds for both undirected rules.