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?
Progress made so far:
- 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?
In general are there other proofs of Zero-one laws that could be more useful here?
PS: I moved the question here from Mathstack, as I did not get any response there.
