# Do Fagin's zero-one laws hold on stochastic block model?

Let $$n$$ be a positive integer (the number of vertices), $$k$$ be a positive integer (the number of communities), $$p = (p_1, . . . , p_k)$$ be a probability vector on $$[k] := \{1, . . . , k\}$$ (the prior on the $$k$$ communities) and $$W$$ be a $$k \times k$$ symmetric matrix with entries in $$[0, 1]$$ (the connectivity probabilities). The pair $$(X, G)$$ is drawn under $$SBM(n,p,W)$$ if $$X$$ is an $$n$$- dimensional random vector with i.i.d. components distributed under $$p$$, and $$G$$ is an $$n$$-vertex simple graph where vertices $$i$$ and $$j$$ are connected with probability $$W(X_i,X_j)$$ , independently of other pairs of vertices.

Now, Fagin's zero-one laws say that for a Erdos-Reyni random graph $$G(n,p)$$, then for any first order logic formula $$\Phi$$ in the language of graphs the following holds:

$$\lim_{n \rightarrow \infty} \mathbb{P}_{g \sim G(n,p)}[g \models \Phi] \text{ is either } 0 \text{ or } 1$$

My question is does the same hold for Stochastic Block Model?

• If you force $$W(X_i,X_j) \in (0,1)$$ then fagin's argument of extension axioms goes through, and you have a rado graph in the limit and hence the 0-1 laws hold.
• If for some $$j$$, we have that $$\forall i: (i \neq j). W(X_i,X_j) = 0$$, then you cannot create extensions (as used in fagin's proof) for a set of nodes in the community $$j$$ plus some other nodes. Basically the community $$j$$ will form a seperate connected component. In this case do zero-one laws hold?