3
$\begingroup$

Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\square(G_n, G_m) < \epsilon$$

Moreover assume that $G_i$ is computable as a function of $i$ and $N$ is computable as a function of $\epsilon$.

Is there a computable function that, given a finite graph $H$, outputs a computable real number $p$ that is the probability of sampling $H$ from $\mathbb G(|H|, W)$ (where $W$ is the limit of $G$)? We are considering exact graph equality, not equality upto graph isomorphism.

$\endgroup$

0

You must log in to answer this question.