# The $K$-distribution of random graph $\mathrm{C}^{*}$-algebras

Bhishan Jacelon  Institute of Mathematics of the Czech Academy of Sciences
Žitná 25
115 67 Prague 1
Czech Republic<EMAIL_ADDRESS>and  Igor Khavkine  Institute of
Mathematics of the Czech Academy of Sciences
Žitná 25
115 67 Prague 1
Czech Republic  Charles University, Faculty of Mathematics and Physics
Sokolovská 83
186 75 Prague 8
Czech Republic<EMAIL_ADDRESS>
###### Abstract.

We appeal to results from combinatorial random matrix theory to deduce that
various random graph $\mathrm{C}^{*}$-algebras are asymptotically almost
surely Kirchberg algebras with trivial $K_{1}$. This in particular implies
that, with high probability, the stable isomorphism classes of such algebras
are exhausted by variations of Cuntz algebras that we term _Cuntz polygons_.
These probabilistically generic algebras can be assembled into a _Fraïssé
class_ whose limit structure $\mathbb{G}$ is consequently relevant to any
$K$-theoretic analysis of finite graph $\mathrm{C}^{*}$-algebras. We also use
computer simulations to experimentally verify the behaviour predicted by
theory and to estimate the asymptotic probabilities of obtaining stable
isomorphism classes represented by actual Cuntz algebras. These probabilities
depend on the frequencies with which the Sylow $p$-subgroups of $K_{0}$ are
cyclic and in some cases can be computed from existing theory. For random
symmetric $r$-regular multigraphs, current theory can describe these
frequencies for finite sets of odd primes $p$ not dividing $r-1$. A novel
aspect of the collected data is the observation of new heuristics outside of
this case, leading to a conjecture for the asymptotic probability of these
graphs yielding $\mathrm{C}^{*}$-algebras stably isomorphic to Cuntz algebras.
For other models of random multigraphs including Bernoulli (di)graphs, the
data also allow us to estimate and heuristically explain the (surprisingly
high) asymptotic probabilities of _exact_ isomorphism to a Cuntz algebra.
Recognising the role played by Cuntz–Krieger algebras in the theory of
symbolic dynamics, we also collect supplemental data to estimate (and in some
cases, actually compute) the asymptotic probability of a random subshift of
finite type being flow equivalent to a full shift.

###### Key words and phrases:

Random graphs, $\mathrm{C}^{*}$-algebras, symbolic dynamics, Cuntz–Krieger
algebras, $K$-theory, Fraïssé theory.

###### 2020 Mathematics Subject Classification:

46L35, 46L80, 15B52 , 60B20, 37B10

##  1\. Introduction

This article is a continuation of [20], which initiated the study of random
constructions of several classes of $\mathrm{C}^{*}$-algebras of interest to
the Elliott classification programme. Here, we focus on the
$\mathrm{C}^{*}$-algebras associated to directed multigraphs that are created
by randomly adding edges to a large number of vertices (see Section 3). With
high probability, the graphs (or rather, directed multigraphs) we consider are
strongly connected and consequently describe purely infinite simple
$\mathrm{C}^{*}$-algebras. This means that our graph algebras fall under the
remit of the Kirchberg–Phillips classification theorem [33, Theorem 4.2.1],
that is, their (stable) isomorphism classes are determined by $K$-theory.
Here, _stable isomorphism_ means isomorphism up to tensoring with the
$\mathrm{C}^{*}$-algebra of compact operators on a separable, infinite-
dimensional Hilbert space, and actually, our algebras are specifically
Cuntz–Krieger algebras (see Section 2), so we could alternatively appeal to
Rørdam’s earlier classification [36, Theorem 6.5].

In [20, §6], it was explained how some of the powerful machinery developed by
Wood [42] could be adapted to the setting of graph $\mathrm{C}^{*}$-algebras.
We considered multigraphs $E$ built from unions of perfect matchings, and
observed that the distributions of Sylow subgroups of random cokernels
established in [29] were also present for $K_{0}(\mathrm{C}^{*}(E))$, which
happens to be given by the cokernel of the transpose of the multigraph’s
adjacency matrix shifted by the identity. The original motivation for the
current work was to experimentally verify the $K_{0}$-behaviour predicted by
this theory. We were indeed able to do this (see Section 4), but what
immediately became apparent from the data was something overlooked in [20],
namely, asymptotically almost-sure triviality of the $K_{1}$-group, which
happens to be given by the kernel of the shifted, transposed adjacency matrix.

The singularity problem for random matrices has a storied history in
combinatorics (see the discussion and references in [29]). It posits that
sufficiently random square matrices are nonsingular with probability
approaching $1$ as the matrix size grows to infinity. Our working hypothesis
is that this should be applicable not just to the adjacency matrices $A_{E}$
of appropriate random graphs $E$, but equally well to $M_{E}=A_{E}^{t}-I$. As
alluded to earlier, this matrix determines
$K_{0}(\mathrm{C}^{*}(E))=\operatorname{\mathrm{coker}}M_{E}$ and
$K_{1}(\mathrm{C}^{*}(E))=\ker M_{E}$ (see the discussion surrounding (2.3)),
and its nonsingularity exactly means triviality of $K_{1}$. We will see in
Section 3 that this applies to _Bernoulli digraphs_ $\mathbb{D}_{n,q}$ in
which each possible edge (allowing loops but not multiple edges) occurs
independently with fixed probability $q$, and also to random $r$-regular
multigraphs $\widehat{\mathbb{G}}_{n,r}$ built from perfect matchings.

Because of this $K_{1}$-triviality, and in light of $K$-theoretic
classification, the stable isomorphism classes of our random graph algebras
(and, given the scope of the singularity problem, likely more generally) can
with high probability be described by rather simple directed multigraphs.
These representatives, which we call _Cuntz polygons_ (see Figure 1), are
generalisations of Cuntz algebras in the sense that $K_{0}$ need not be cyclic
but can be any finite abelian group. Stable isomorphism to an actual Cuntz
algebra is detected by cyclicity of $K_{0}$. As it turns out, for large
Bernoulli digraphs this happens about $85\%$ of the time, a probability which
can be computed asymptotically from existing theory (see Theorem 3.2) and
which is supported by the data (Table 1). For random $r$-regular multigraphs,
there are currently three obstacles to computing the asymptotic probability of
the graph algebra being stably isomorphic to a Cuntz algebra. They all stem
from the fact that cyclicity of $K_{0}$ is equivalent to cyclicity of the
Sylow $p$-subgroups of $K_{0}$ for all primes $p$. Firstly and secondly,
although the probability of cyclicity of Sylow $p$-subgroups is known for odd
primes $p$ that do not divide $r-1$, it is unknown for $p=2$ or $p\mid r-1$.
Thirdly, the known theory covers the case of only _finitely many_ primes, not
all primes simultaneously. See the discussion around Theorem 3.4, which is
adapted from [29, Theorem 1.6].

However, we conjecture from the data that the asymptotic probability of the
graph algebra being stably isomorphic to a Cuntz algebra still converges to
the product over all primes $p$ of the asymptotic probability of cyclicity of
the Sylow $p$-subgroup of $K_{0}$ (see Table 8). When the regularity degree is
one more than a power of two, we estimate this product to be about $40\%$ (see
Table 10). As for cyclicity of the Sylow $p$-subgroup of
$K_{0}(\widehat{\mathbb{G}}_{n,r})$ for large $n$ when $p\mid 2(r-1)$ (that
is, $p=2$ or $p$ is an odd prime dividing $r-1$), the data reveal new
heuristics (see Table 8, Table 9 and Conjecture 4.1).

On the other hand, the _symmetric_ versions $\mathbb{E}_{n,q}$ of
$\mathbb{D}_{n,q}$ (that is, _Erdős–Rényi graphs_ allowing loops) lead to
$\mathrm{C}^{*}$-algebras $\mathrm{C}^{*}(\mathbb{E}_{n,q})$ for which _all_
Sylow $p$-subgroups of $K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n,q}))$, including
$p=2$, follow the limiting behaviour (3.7), (3.8) and (3.10). This is proved
in Theorem 3.12 of Wood’s article [44], where it is also stated that
forthcoming work will extend this result to infinitely many primes. Moreover,
asymptotic triviality of $K_{1}$ also holds for these algebras, for the same
reason as for the algebras $\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$
(namely, [29, Corollary 4.2]). One would therefore expect about $79\%$ of the
algebras $\mathrm{C}^{*}(\mathbb{E}_{n,q})$ for large $n$ to be stably
isomorphic to Cuntz algebras.

Cuntz–Krieger algebras are intimately connected to the theory of symbolic
dynamics. If the (directed multi-) graph $E$ is strongly connected and does
not consist of a single cycle (equivalently, if the adjacency matrix is
irreducible and is not a permutation matrix), then the stable isomorphism
class of the graph algebra $\mathrm{C}^{*}(E)$ (which is a Cuntz–Krieger
algebra) is an invariant for the flow equivalence class of the associated edge
shift $\sigma\colon\Sigma_{E}\to\Sigma_{E}$. Here, $\Sigma_{E}$ is the two-
sided infinite path space

$\Sigma_{E}=\left\\{(e_{i})_{i\in\mathbb{Z}}\in(E^{1})^{\mathbb{Z}}\mid
s(e_{i+1})=r(e_{i})\text{ for every }i\in\mathbb{Z}\right\\}$ (1.1)

(see Section 2 for notation) and $\sigma$ is the shift map that sends
$(e_{i})_{i\in\mathbb{Z}}$ to $(e_{i+1})_{i\in\mathbb{Z}}$. _Flow equivalence_
between topological dynamical systems $(\Sigma_{E},\sigma_{E})$ and
$(\Sigma_{F},\sigma_{F})$ is a weakening of conjugacy that refers to
equivalence of their suspension flows (see, for example, [25, §13.6]). In our
setting, flow equivalence can be characterised by certain graph _moves_ (see
[39, 5]) and implies the existence of a _diagonal-preserving_ stable
isomorphism between the graph algebras (see [9, §4] and [5]). Mere stable
isomorphism of the associated graph algebras (or in other words, isomorphism
of their $K_{0}$ groups) is strictly weaker than flow equivalence. By [17],
the necessary and sufficient additional data is the sign of the determinant of
$I-A_{E}$, which when combined with the $K_{0}$ group yields the _signed
Bowen–Franks group_

$\mathrm{BF}_{+}(E)=\operatorname{\mathrm{sgn}}(\det(I-A_{E}))\operatorname{\mathrm{coker}}(I-A_{E}),$
(1.2)

where we notationally attach the sign label ‘$+$’ to the group
$\operatorname{\mathrm{coker}}(I-A_{E})$ if $\det(I-A_{E})>0$, or ‘$-$’ if
$\det(I-A_{E})<0$. For the graph $E$ with one vertex and $n$ loops (whose
shift space $\Sigma_{E}$ is the full shift on an alphabet of $n$ symbols and
whose graph algebra is the Cuntz algebra $\mathcal{O}_{n}$),
$\mathrm{BF}_{+}(E)=-\mathbb{Z}/(n-1)\mathbb{Z}$. Collecting this sign data in
conjunction with a tally of cyclicity therefore allows us to estimate the
asymptotic probabilities of a random subshift of finite type (that is, the
edge shift associated to a random graph) being flow equivalent to a full
shift. For Bernoulli digraphs $\mathbb{D}_{n,q}$, the percentage probability
appears to be about $42$ (see Conjecture 3.9 and Table 2). In certain special
cases (Theorem 3.8), we can prove that this is indeed the right number (thus
providing a question to an answer of D. Adams). The asymptotic behaviour of
the determinant for $\mathbb{E}_{n,q}$ and $\widehat{\mathbb{G}}_{n,r}$, about
which we have formulated and left open Question 3.10, is less clear. However,
the full-shift probability for large graphs is still nontrivial (see Tables 6,
11).

As for the property of being _exactly_ (rather than stably) isomorphic to a
Cuntz algebra, the asymptotic probability of this event does not appear to be
readily deducible from existing random matrix theory. (There is also no
available dynamical interpretation of the corresponding equivalence relation
for the associated edge shifts, although there is a geometric description via
graph moves; see [1].) Nonetheless, by keeping track of the class of the unit
we are able to provide estimates (together with heuristic explanations; see
Conjecture 3.11, Table 2 and Table 6). The surprising conclusions are that, if
$n$ is large, then $\mathrm{C}^{*}(\mathbb{D}_{n,q})$ is about $51\%$ likely
to be isomorphic to a Cuntz polygon and is about $44\%$ likely to be
isomorphic to an actual Cuntz algebra. For $\mathrm{C}^{*}(\mathbb{E}_{n,q})$,
these numbers are $61\%$ and $48\%$, respectively. In short, it’s about a coin
toss whether a chance encounter with a large graph $\mathrm{C}^{*}$-algebra is
in fact a meeting with a Cuntz algebra.

How should this (and our other probabilistic observations) be interpreted? The
first thing we can say is that theorems about Cuntz polygons become
asymptotically almost-sure theorems about the stable isomorphism classes of
random graph $\mathrm{C}^{*}$-algebras. For example, in Section 2.5 we make
the observation that Cuntz polygons $\mathcal{P}_{\bar{m}}$ form a _Fraïssé
class_. The Fraïssé limit $\mathbb{G}$ of this class (which by [40] is the
graph algebra of an infinite, strongly connected graph) is then a structure
that is asymptotically almost surely universal and homogeneous for
sufficiently random unital graph algebras. See Theorem 2.6 and also Section
3.6, in which we emphasise the point that, while we have opted to work with
distributions amenable to calculations of probability, similar conclusions
should hold for any distribution that shares the same asymptotically almost-
sure events (so-called _contiguous_ distributions). When applied to Bernoulli
digraphs as in Theorem 3.15, this general slogan materialises into the
concrete observation that _most_ of the $\mathrm{C}^{*}$-algebras associated
to finite digraphs on large vertex sets with suitably many edges are stably
isomorphic to Cuntz polygons. The other message is that complex structures are
rare, or put another way, the objects that we tend to encounter are the ones
with minimal symmetry. On the flip side, when there is imposed extra structure
(such as graph regularity), it seems that we tend to see more complicated
automorphism groups with greater frequency. (It is also interesting that
$\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$ being isomorphic to a Cuntz
polygon is a very rare event (see Table 11). Question 3.13, whether this
probability asymptotes to zero, is left open.) The central point of the
present work is that for graph $\mathrm{C}^{*}$-algebras these various
statements can be made quantifiably precise.

We have gathered the data reported in Section 4 by running computer
simulations. Our code generates samples of random graphs
$\widehat{\mathbb{G}}_{n,r}$, $\mathbb{D}_{n,q}$ or $\mathbb{E}_{n,q}$ (our
typical sample size being $m=10^{5}$) and collects $K$-theoretic data. The
primary tool for computing cokernels of integer matrices, and hence the
$K$-theory of graph algebras, is the Smith normal form (SNF) algorithm. It has
been used extensively in the literature (see, for example, [36, 6, 15]) and is
an integral piece of our analysis of the graphs. The SNF algorithm provides,
for a given $M_{E}\in M_{n}(\mathbb{Z})$, a diagonalisation
$UM_{E}V=D=\operatorname{\mathrm{diag}}(d_{1},\dots,d_{n})$, where
$U,V\in\operatorname{\mathrm{GL}_{n}}(\mathbb{Z})$ and the $d_{i}$ are
integers with $d_{i}|d_{i+1}$ for $1\leq i\leq n-1$. Then,

$\operatorname{\mathrm{coker}}M_{E}\cong\operatorname{\mathrm{coker}}D\cong\mathbb{Z}/d_{1}\mathbb{Z}\oplus\dots\oplus\mathbb{Z}/d_{n}\mathbb{Z}.$
(1.3)

From this, we can also determine the structure of the $p$-Sylow subgroup of
$\operatorname{\mathrm{coker}}M_{E}\cong K_{0}(\mathrm{C}^{*}(E))$ for any
prime $p$. We also record:

  * •

whether or not each graph is strongly connected;

  * •

whether $K_{0}$ is cyclic, by removing any $0$ entries from the list
$L=[d_{1},\dots,d_{n}]$ (storing these as $K_{1}$), and also any $1$s (as
these do not contribute to the cokernel), then checking whether there remains
at most one entry in $L$;

  * •

the rank of $K_{1}$ (in other words, the number of $0$ entries removed from
$L$);

  * •

tallies of cyclicity of Sylow $p$-subgroups for specified primes $p$, as well
as instances where these subgroups are of the form
$\mathbb{Z}/(p^{N}\mathbb{Z})$ or $(\mathbb{Z}/p\mathbb{Z})^{N}$, for integers
$N$ that are small enough for these events to be statistically observable (see
(3.7) and (3.8));

  * •

whether or not the class of the unit in $K_{0}$ is in the same automorphism
orbit as the ‘canonical’ class, which in instances of trivial $K_{1}$ means
that we have exact rather than stable isomorphism between $\mathrm{C}^{*}(E)$
and the corresponding Cuntz polygon (see Section 2.4);

  * •

the sign of the determinant of $I-A_{E}=-M^{t}_{E}$ (and hence, if $K_{0}$ is
also cyclic, whether or not the corresponding edge shift is flow equivalent to
a full shift);

  * •

$99\%$ confidence intervals for the various proportions above, using the
normal approximation to the binomial distribution.

The simulation and analysis code is written in Python. For efficiency reasons,
the SNF is computed by calling the PARI library [32], which is written in C.
Both the code and experimental data are available on
GitHub.111https://github.com/bjacelon/random-graph-k-theory There are three
reasons for our decision to include a substantial offering of empirical data.
First, we are demonstrating the reliability of our experimental process by
comparing with behaviour predicted by theory, whenever the appropriate theory
is available. Next, in situations where there is as yet no theoretical
prediction, the estimates that we extract from the data can then be expected
to carry some weight. Last, but not least, we wish to document the present
mathematical endeavour as the conversation between theory, practice and
scientific discovery that it truly was.

We have organised the article as follows. Section 2 provides some background
on the $\mathrm{C}^{*}$-algebras associated to finite graphs, as well as their
$K$-theoretic classification, and introduces Cuntz polygons. Section 3
describes the relevant random graph models and some asymptotic behaviour
guaranteed by random matrix theory. Finally, Section 4 contains empirical data
that either experimentally verify the theory or provide estimates for
probabilities that are not yet theoretically computable.

### Acknowledgements

BJ is supported by the GAČR project 22-07833K and partially supported by the
Simons Foundation Award No 663281 granted to the Institute of Mathematics of
the Polish Academy of Sciences for the years 2021–2023. He is grateful to the
organisers of the stimulating ‘Graph Algebras’ and ‘Generic Structures’
conferences held at the Bedlewo Centre in 2023. IK is partially supported by
the Praemium Academiae of M. Markl and by Czech science foundation (GAČR)
under the grant GA22-00091S. This collaboration would not have been possible
without the excellent working environment at the Institute of Mathematics of
the Czech Academy of Sciences (RVO: 67985840). The computer code was written
with some facilitation by ChatGPT [31]. Both authors are indebted to Søren
Eilers and the anonymous referee of an earlier version of this article for
pointing out the connections to symbolic dynamics and for encouraging a deeper
dive into the question of exact vs stable isomorphism between random graph
algebras and Cuntz polygons.

##  2\. Graph $\mathrm{C}^{*}$-algebras

###  2.1. Graph algebras

The ‘graph’ in ‘graph $\mathrm{C}^{*}$-algebra’ might in other contexts be
called a directed (multi)graph. For clarity, we begin by specifying the kinds
of graphs that are amenable to our analysis and explain how
$\mathrm{C}^{*}$-algebras are attached to them.

A _directed graph_ $E$ consists of a vertex set $E^{0}$, an edge set $E^{1}$,
and range and source maps $r,s\colon E^{1}\to E^{0}$. A _path_ in $E$ is a
(possibly finite) sequence of edges $(\alpha_{i})_{i\geq 1}$ such that
$r(\alpha_{i})=s(\alpha_{i+1})$ for every $i$, and a _cycle_ is a finite path
$(\alpha_{i})_{i=1}^{n}$ whose initial and final vertices coincide and with no
other repeated vertices. A vertex $v\in E^{0}$ is called a _sink_ if
$s^{-1}(v)=\emptyset$. Every graph considered in this article will be finite
and (except for some of the graphs mentioned in Remark 3.3 and Table 4) will
with high probability have no sinks.

We recall the definition of the graph algebra associated to $E$. (Note that a
different convention is used in [34]. What follows is the definition that
appears, for example, in [3].) A _Cuntz–Krieger $E$-family_ associated to a
directed graph $E=(E^{0},E^{1},s,r)$ is a set

$\\{p_{v}\mid v\in E^{0}\\}\cup\\{s_{e}\mid e\in E^{1}\\},$ (2.1)

where the $p_{v}$ are mutually orthogonal projections and the $s_{e}$ are
partial isometries satisfying:

$\displaystyle s_{e}^{*}s_{f}$ $\displaystyle=0$ $\displaystyle\forall\>e,f\in
E^{1}\text{ with }e\neq f$ $\displaystyle s_{e}^{*}s_{e}$
$\displaystyle=p_{r(e)}$ $\displaystyle\forall\>e\in E^{1}$ $\displaystyle
s_{e}s_{e}^{*}$ $\displaystyle\leq p_{s(e)}$ $\displaystyle\forall\>e\in
E^{1}$ $\displaystyle p_{v}$ $\displaystyle=\sum\limits_{e\in
s^{-1}(v)}s_{e}s_{e}^{*}$ $\displaystyle\forall\>v\in E^{0}\>\text{that is not
a sink}.$ (2.2)

The _graph algebra_ $\mathrm{C}^{*}(E)$ is the universal
$\mathrm{C}^{*}$-algebra with generators (2.1) satisfying the relations (2.1).
Every graph algebra $\mathrm{C}^{*}(E)$ is separable, nuclear and satisfies
the universal coefficient theorem (UCT) (see, for example, [34, Remark 4.3]
and [35, Lemma 3.1]), and $\mathrm{C}^{*}(E)$ is unital if and only if $E^{0}$
is finite, in which case $1_{\mathrm{C}^{*}(E)}=\sum\limits_{v\in
E^{0}}p_{v}$.

###  2.2. Cuntz–Krieger algebras

By a _Cuntz–Krieger algebra_ we mean the graph $\mathrm{C}^{*}$-algebra of a
finite graph without sinks. This is not the original definition that appears
in [9], but is equivalent to it (see [2, Definition 2.3] and the ensuing
discussion, and also [2, Theorem 3.12]).

If $E$ is such a graph, and $A_{E}$ is its adjacency matrix

$A_{E}(v,w)=|\\{e\in E^{1}\mid s(e)=v,r(e)=w\\}|,$

then the $K$-theory of $\mathrm{C}^{*}(E)$ can be computed as follows. From
the proof of [35, Theorem 3.2], the map $\mathbb{Z}^{E^{0}}\to
K_{0}(\mathrm{C}^{*}(E))$ that sends the standard basis vector $e_{v}$ to
$[p_{v}]$ is surjective with kernel isomorphic to
$(A_{E}^{t}-I)\mathbb{Z}^{E^{0}}$. In particular,

$(K_{0}(\mathrm{C}^{*}(E)),[1_{\mathrm{C}^{*}(E)}]_{0},K_{1}(\mathrm{C}^{*}(E)))\cong(\operatorname{\mathrm{coker}}(A_{E}^{t}-I),[(1,\dots,1)],\ker(A_{E}^{t}-I)).$
(2.3)

A _UCT Kirchberg algebra_ is by definition a purely infinite, simple, nuclear,
separable $\mathrm{C}^{*}$-algebra that satisfies the universal coefficient
theorem. By the Kirchberg–Phillips theorem (see [33, Theorem 4.2.1], and also
[23] and [37, Chapter 8]), these algebras are classified up to stable
isomorphism by $K$-theory. Further, specifying the class $[1]_{0}$ of the unit
determines the isomorphism class of the algebra (see [33, Theorem 4.2.4]).

The following is a consequence of [3, Propositions 5.1 and 5.3].

######  Proposition 2.1.

If $E$ is strongly connected and does not consist of a single cycle (so in
particular, every cycle has an exit), then the Cuntz–Krieger algebra
$\mathrm{C}^{*}(E)$ is purely infinite and simple, so is a UCT Kirchberg
algebra.

######  Remark 2.2.

  1. 1.

We do not actually need the full strength of the Kirchberg–Phillips theorem in
this article, and could instead appeal to Rørdam’s earlier classification [36,
Theorem 6.5] of simple Cuntz–Krieger algebras.

  2. 2.

While the graph algebras of primary interest to us will be covered by
Proposition 2.1, it should be noted that the full class of unital graph
algebras is classifiable by an invariant called ordered reduced filtered
$K$-theory that accounts for the ideal structure of the algebras (see [15]).

###  2.3. Cuntz polygons

######  Definition 2.3.

For $n\in\mathbb{N}$ and $\bar{m}=(m_{1},\dots,m_{n})\in\mathbb{N}^{n}$, let
$E_{\bar{m}}$ be the graph with vertices

$E_{\bar{m}}^{0}=\\{v_{1},\dots,v_{n}\\}$

and edges

$E_{\bar{m}}^{1}=\\{e_{i,j}\mid 1\leq i\leq n,1\leq j\leq
m_{i}\\}\cup\\{l_{1},\dots,l_{n}\\}$

where, for $1\leq i\leq n$ and $1\leq j\leq m_{i}$,

$r(l_{i})=s(l_{i})=v_{i},\>r(e_{i,j})=v_{i},\>s(e_{i,j})=v_{i-1}\>(\operatorname{\mathrm{mod}}n).$

We call the graph algebra $\mathcal{P}_{\bar{m}}:=\mathrm{C}^{*}(E_{\bar{m}})$
a _Cuntz $n$-gon_. A _Cuntz polygon_ is a Cuntz $n$-gon for some $n$.

$m_{2}$$m_{3}$$m_{4}$$m_{5}$$m_{1}$ Figure 1. The graph
$E_{(m_{1},m_{2},m_{3},m_{4},m_{5})}$ of the Cuntz pentagon
$\mathcal{P}_{(m_{1},m_{2},m_{3},m_{4},m_{5})}$.

The reason for the terminology, apart from the shapes of their associated
graphs (see Figure 1), is that Cuntz polygons are generalisations of Cuntz
algebras. Note indeed that a Cuntz $1$-gon $\mathcal{P}_{(m)}$ is isomorphic
to $\mathcal{O}_{m+1}$. Moreover, we have the following.

######  Proposition 2.4.

  1. 1.

If $A$ is a Cuntz polygon $\mathrm{C}^{*}(E_{\bar{m}})$, then $A$ is a UCT
Kirchberg algebra with

$(K_{0}(A),[1_{A}]_{0},K_{1}(A))\cong\left(\bigoplus_{i=1}^{n}\mathbb{Z}/m_{i}\mathbb{Z},(1,\dots,1),0\right).$
(2.4)

  2. 2.

A Cuntz polygon $\mathcal{P}_{\bar{m}}$ is stably isomorphic to a Cuntz
algebra if and only if $K_{0}(\mathcal{P}_{\bar{m}})$ is cyclic, which happens
if and only if the components $m_{1},\dots,m_{n}$ of $\bar{m}$ are pairwise
coprime.

  3. 3.

If $E$ is a strongly connected finite graph whose adjacency matrix $A_{E}$ is
not a permutation matrix and is such that $A_{E}^{t}-I$ is nonsingular, then
$\mathrm{C}^{*}(E)$ is stably isomorphic to $\mathcal{P}_{\bar{m}}$ for some
$\bar{m}$.

###### Proof.

  1. 1.

Since $E_{\bar{m}}$ is strongly connected and does not consist of a single
cycle, $A$ is a UCT Kirchberg algebra by Proposition 2.1. The adjacency matrix
of $E_{\bar{m}}$ is $A_{E_{\bar{m}}}=I+PD$, where $D$ is the diagonal matrix
$\operatorname{\mathrm{diag}}(m_{1},\dots,m_{n})$ and $P$ is the permutation
matrix whose action on the standard basis of $\mathbb{Z}^{E^{0}}$ is given by
$Pe_{v_{i}}=e_{v_{i-1}}$ (mod $n$). So, $A^{t}_{E_{\bar{m}}}-I=DP^{t}$, which
implies that $\ker(A^{t}_{E_{\bar{m}}}-I)=0$ and
$\operatorname{\mathrm{coker}}(A^{t}_{E_{\bar{m}}}-I)=\operatorname{\mathrm{coker}}D\cong\bigoplus_{i=1}^{n}\mathbb{Z}/m_{i}\mathbb{Z}$.
Therefore, (2.4) follows from (2.3).

  2. 2.

The second assertion follows from the Kirchberg–Phillips (or Rørdam)
classification theorem together with the fact that the Cuntz algebra
$\mathcal{O}_{n}$ is a UCT Kirchberg algebra with $K$-theory

$(K_{0}(\mathcal{O}_{n}),[1_{\mathcal{O}_{n}}]_{0},K_{1}(\mathcal{O}_{n})]\cong(\mathbb{Z}/(n-1)\mathbb{Z},1,0)$

(see [7] and [8]). Note also that
$\bigoplus_{i=1}^{n}\mathbb{Z}/m_{i}\mathbb{Z}$ is cyclic if and only if the
$m_{i}$ are pairwise coprime, and in this case, $\mathcal{P}_{\bar{m}}$ is in
fact isomorphic to $\mathcal{O}_{1+\prod_{i=1}^{n}m_{i}}$.

  3. 3.

Finally, if $A_{E}$ is not a permutation matrix, then $E$ does not consist of
a single cycle. By Proposition 2.1, $\mathrm{C}^{*}(E)$ is therefore a UCT
Kirchberg algebra. By (2.3) and (2.4), there exists some Cuntz polygon that
has the same $K$-theory as $\mathrm{C}^{*}(E)$, which is then in the same
stable isomorphism class by the Kirchberg–Phillips (or Rørdam) classification
theorem. ∎

###  2.4. Exact vs stable isomorphism

While Cuntz polygons cover all _stable_ isomorphism classes of purely infinite
simple Cuntz–Krieger algebras with trivial $K_{1}$, they are far from being
able to capture all _isomorphism_ classes. The reason of course is the
position of the unit in $K_{0}$, information which is encoded by the
potentially complicated structure of the graph. In fact, the class of the unit
can be arbitrary: by [14, Proposition 3.9], for any finitely generated abelian
group $G$, distinguished element $g\in G$ and free abelian group $F$ with
$\operatorname{\mathrm{rank}}F=\operatorname{\mathrm{rank}}G$ (for example,
$F=0$ and $G$ any finite abelian group), there exists a finite graph $E$ such
that $\mathrm{C}^{*}(E)$ is a Kirchberg algebra with

$\left(K_{0}(\mathrm{C}^{*}(E)),[1_{\mathrm{C}^{*}(E)}]_{0},K_{1}(\mathrm{C}^{*}(E))\right)\cong(G,g,F).$

But actually, we can keep track of the class of the unit via the matrix $U$
that appears in the SNF decomposition $UM_{E}V=D$ of $M_{E}=A_{E}^{t}-I$. More
precisely, and elaborating on (1.3), the map
$\mathbb{Z}^{n}\to\mathbb{Z}^{n}/D\mathbb{Z}^{n}=\operatorname{\mathrm{coker}}(D)$,
$x\mapsto[Ux]$ is surjective with kernel $M_{E}\mathbb{Z}^{n}$, so gives an
isomorphism between $\operatorname{\mathrm{coker}}(M_{E})$ and
$\operatorname{\mathrm{coker}}(D)\cong\mathbb{Z}/d_{1}\mathbb{Z}\oplus\dots\oplus\mathbb{Z}/d_{n}\mathbb{Z}$.
In light of (2.3), the class of the unit under this isomorphism is
$\left[U\left(\begin{smallmatrix}1\\\ \vdots\\\ \\\
1\end{smallmatrix}\right)\right]$.

Suppose now that $E$ satisfies the hypotheses of Proposition 2.4.3, so that
$\mathrm{C}^{*}(E)$ is stably isomorphic to the corresponding Cuntz polygon
$\mathcal{P}_{\bar{d}}:=\mathcal{P}_{(d_{1},\dots,d_{n})}$. By Proposition
2.4.1, the class of the unit for $\mathcal{P}_{\bar{d}}$ is
$\left[\left(\begin{smallmatrix}1\\\ \vdots\\\ \\\
1\end{smallmatrix}\right)\right]$. Comparing the automorphism orbits of these
two vectors (by incorporating the description presented in [12, 38] into our
computer code), we can therefore decide whether or not there exists an
isomorphism between $(K_{0}(\mathrm{C}^{*}(E)),[1_{\mathrm{C}^{*}(E)}])$ and
$(K_{0}(\mathcal{P}_{\bar{d}}),[1_{\mathcal{P}_{\bar{d}}}])$, giving an
isomorphism between $\mathrm{C}^{*}(E)$ and $\mathcal{P}_{\bar{d}}$. In
Section 3.5, we present a heuristic analysis of the asymptotic probability of
this event for Bernoulli digraphs $\mathbb{D}_{n,q}$ and their symmetric
cousins $\mathbb{E}_{n,q}$. Section 4 contains experimental confirmation of
the formulas displayed in Conjecture 3.11.

###  2.5. The Fraïssé theory of Cuntz polygons

The category whose objects are finite abelian groups and whose morphisms are
injective group homomorphisms forms a _Fraïssé class_ (see, for example, the
discussion and references in [24, §2]). The content of this assertion, given
the more immediately obvious properties of separability (that is, countably
many isomorphism classes of objects), heredity (closure under substructures)
and joint embedding (any two objects can both be embedded into a third), is
the ability to amalgamate, that is, to complete commutative diagrams of the
form

${H_{1}}$${G_{1}}$${G_{2}}$${H_{2}}$

Attached to any Fraïssé class $\mathcal{L}$ is its _Fraïssé limit_
$\mathbb{F}$, the unique structure whose _age_ (the collection of its finite
substructures) is $\mathcal{L}$, and which is _homogeneous_ , meaning that any
two embeddings of an object of $\mathcal{L}$ into $\mathbb{F}$ must lie in the
same automorphism orbit (where $\operatorname{\mathrm{Aut}}(\mathbb{F})$ acts
on embeddings by post-composition). For the class of finite abelian groups,
this limit is the group
$\mathbb{A}=\bigoplus\limits_{i<\omega}\mathbb{Q}/\mathbb{Z}$ (see [24,
Proposition 6]).

######  Definition 2.5.

Let $\mathbb{G}$ be the stable UCT Kirchberg algebra with
$(K_{0}(\mathbb{G}),K_{1}(\mathbb{G}))=(\mathbb{A},0)$.

Now let us consider the category $\mathcal{P}$ whose objects are stabilised
Cuntz polygons (that is, $\mathrm{C}^{*}$-algebras of the form
$\mathcal{P}_{\bar{m}}\otimes\mathbb{K}$ for some $\bar{m}$, where
$\mathbb{K}$ is the $\mathrm{C}^{*}$-algebra of compact operators on a
separable, infinite-dimensional Hilbert space) and whose morphisms are
approximate unitary equivalence classes of _$K$ -embeddings_, by which we mean
∗-homomorphisms that are embeddings at the level of $K$-theory. Note that,
since the objects in $\mathcal{P}$ are simple, $K$-embeddings are embeddings.
By Kirchberg’s classification theorem (see [37, Theorem 8.3.3]), this is also
a Fraïssé class in the suitable $\mathrm{C}^{*}$-algebraic sense (see [13, 27,
21]). The $\mathrm{C}^{*}$-algebra $\mathbb{G}$ defined above is the
$\mathrm{C}^{*}$-algebraic Fraïssé limit of this class. $\mathbb{G}$ is:

  * •

(by [40]) the graph $\mathrm{C}^{*}$-algebra of an infinite (but row-finite)
strongly connected graph;

  * •

_universal_ , by which we mean that it can be built as an inductive limit of
objects in $\mathcal{P}$ in such a way that every object in $\mathcal{P}$ can
be embedded into some finite stage of the inductive sequence (a fact which
follows from Kirchberg’s classification theorem since the corresponding
statement is true of $\mathbb{A}$);

  * •

_homogeneous_ , meaning that for every object $B$ in $\mathcal{P}$,
$\operatorname{\mathrm{Aut}}(\mathbb{G})$ acts transitively on the space of
embeddings of $B$ into $\mathbb{G}$.

In summary, we have the following.

######  Theorem 2.6.

Let $B$ be a UCT Kirchberg algebra with $K_{1}(B)=0$ and $K_{0}(B)$ finite (in
other words, $B$ is stably isomorphic to a Cuntz polygon). Then, there is an
embedding $\varphi\colon B\to\mathbb{G}$ such that $K_{0}(\varphi)$ is
injective. Moreover, if $\psi\colon B\to\mathbb{G}$ is another such embedding
then there exists an automorphism $\alpha$ of $\mathbb{G}$ such that $\psi$ is
approximately unitarily equivalent to $\alpha\circ\varphi$.

######  Remark 2.7.

In contrast to the Fraïssé limits described in [13, 27, 21], the
$\mathrm{C}^{*}$-algebra $\mathbb{G}$ is purely infinite rather than stably
finite. In the stably finite setting, it is an open problem to decide whether
the automorphism group of the $\mathrm{C}^{*}$-algebraic limit structure is
_extremely amenable_ (under the topology of pointwise convergence), meaning
that every continuous action of the group on a nonempty compact space should
admit a fixed point. This property is indeed a feature of
$\operatorname{\mathrm{Aut}}(A)$ when $A$ is a uniformly hyperfinite (UHF)
$\mathrm{C}^{*}$-algebra (see [13, §5]), but it is unclear whether it holds
when $A$ is the Jiang–Su algebra $\mathcal{Z}$ or any of the stably
projectionless algebras considered in [21]. For $A=\mathbb{G}$, the following
argument shows that $\operatorname{\mathrm{Aut}}(\mathbb{G})$ is _not_
extremely amenable. By [10] (a reference for which we thank Vadim Alekseev),
the class of finite abelian groups does not have the Ramsey property, so by
the KPT correspondence [22],
$\operatorname{\mathrm{Aut}}(K_{0}(\mathbb{G}))\cong\operatorname{\mathrm{Aut}}(\mathbb{A})$
is not extremely amenable when equipped with the pointwise-convergence
topology. By [37, Corollary 8.4.10],
$\operatorname{\mathrm{Aut}}(K_{0}(\mathbb{G}))$ is isomorphic to the quotient
of $\operatorname{\mathrm{Aut}}(\mathbb{G})$ by the closed subgroup of
approximately inner automorphisms. (Note that [37, Corollary 8.4.10] provides
an isomorphism of _topological_ groups as the homomorphisms in the short exact
sequence are continuous and open onto their images.) Since extreme amenability
passes to quotients, we conclude that
$\operatorname{\mathrm{Aut}}(\mathbb{G})$ is not extremely amenable.

######  Remark 2.8.

Let $\mathcal{P}_{\mathbb{G}}$ denote the set of approximate unitary
equivalence classes of the $\mathrm{C}^{*}$-subalgebras of $\mathbb{G}$ that
are stably isomorphic to $\mathcal{P}_{\bar{m}}$ for some $\bar{m}$. More
precisely, we consider subalgebras $C,D\subseteq\mathbb{G}$ to be equivalent
if there exists an isomorphism $\alpha\colon C\to D$ (which, by homogeneity,
can be extended to $\alpha\in\operatorname{\mathrm{Aut}}(\mathbb{G})$) such
that $\alpha|_{C}$ is approximately unitarily equivalent to the inclusion
$C\hookrightarrow\mathbb{G}$ . Note that every $\mathrm{C}^{*}$-algebra
representing an equivalence class in $\mathcal{P}_{\mathbb{G}}$ is a UCT
Kirchberg algebra, so is either stable or unital. Let us correspondingly
separate
$\mathcal{P}_{\mathbb{G}}=\mathcal{P}^{0}_{\mathbb{G}}\sqcup\mathcal{P}^{1}_{\mathbb{G}}$
into the classes of stable algebras and the classes of unital ones. Fix a set
$\mathcal{C}_{\mathbb{G}}\subseteq\mathcal{P}^{1}_{\mathbb{G}}$ of
representatives of isomorphism classes, one for each Cuntz polygon, so that
their stabilisations
$\mathcal{C}_{\mathbb{G}}\otimes\mathbb{K}\subseteq\mathbb{G}\otimes\mathbb{K}\cong\mathbb{G}$
are representatives of isomorphism classes in $\mathcal{P}^{0}_{\mathbb{G}}$.
By homogeneity, that is, because partial automorphisms can be extended to full
automorphisms, we can completely describe the
$\operatorname{\mathrm{Aut}}(\mathbb{G})$-orbit of
$\mathcal{C}_{\mathbb{G}}\otimes\mathbb{K}$: the orbit of
$[C]\in\mathcal{C}_{\mathbb{G}}\otimes\mathbb{K}$ is
$\\{[D]\in\mathcal{P}^{0}_{\mathbb{G}}\mid K_{0}(D)\cong K_{0}(C)\\}$, and the
orbit of the whole set is all of $\mathcal{P}^{0}_{\mathbb{G}}$. Now we ask
about the unital component of $\mathcal{P}_{\mathbb{G}}$: what is the
$\operatorname{\mathrm{Aut}}(\mathbb{G})$-orbit
$\operatorname{\mathrm{Aut}}(\mathbb{G})_{\mathcal{P}_{\mathbb{G}}}(\mathcal{C}_{\mathbb{G}})$
of $\mathcal{C}_{\mathbb{G}}$ in
$\mathcal{P}^{1}_{\mathbb{G}}\subseteq\mathcal{P}_{\mathbb{G}}$? Again by
homogeneity, this is really the same question that was addressed in Section
2.4, and the description of
$\operatorname{\mathrm{Aut}}(\mathbb{G})_{\mathcal{P}_{\mathbb{G}}}(\mathcal{C}_{\mathbb{G}})$
supported by the present article is probabilistic. For an idea of the
probability that a suitably large randomly chosen element of
$\mathcal{P}^{1}_{\mathbb{G}}$ lies in
$\operatorname{\mathrm{Aut}}(\mathbb{G})_{\mathcal{P}_{\mathbb{G}}}(\mathcal{C}_{\mathbb{G}})$,
see Conjecture 3.11.

##  3\. Random graph models

We will consider three methods of constructing directed multigraphs on $n$
labelled vertices by randomly adding edges. Equivalently, we create adjacency
matrices $A(n)$ whose entries are random variables taking values in the
nonnegative integers.

  1. 1.

First, we insist that these entries be independent, leading in particular to
_Bernoulli digraphs_ $\mathbb{D}_{n,q}$ in which each possible edge (allowing
loops but not multiple edges) occurs independently with fixed probability $q$.
That is, each entry of $A(n)$ is either $1$ (with probability $q$) or $0$
(with probability $1-q$).

  2. 2.

By contrast, there are two sources of dependence among the entries of our
second model of random adjacency matrix, which is now required to be symmetric
with each row summing to a fixed integer $r\geq 3$. That is, we build _random
$r$-regular undirected multigraphs_ and convert them into directed ones by
replacing each edge (between given vertices $i,j$) by two (one from $i$ to $j$
and one from $j$ to $i$). Specifically, we use the _perfect matchings model_

$\widehat{\mathbb{G}}_{n,r}=\underbrace{\widehat{\mathbb{G}}_{n,1}+\dots+\widehat{\mathbb{G}}_{n,1}}_{r},$

that is, the union of $r$ independent, uniformly random perfect matchings on
the $n\in 2\mathbb{N}$ vertices.

  3. 3.

The third model $\mathbb{E}_{n,q}$ is in a sense intermediate between the
first two. These _Erdős–Rényi graphs_ are constructed in the same manner as
$\mathbb{D}_{n,q}$, but symmetrically. They exhibit a pattern of asymptotic
connectivity similar to $\mathbb{D}_{n,q}$, and asymptotic $K$-theoretic
behaviour similar to $\widehat{\mathbb{G}}_{n,r}$.

In each case, we make statements about the asymptotic probabilities of:

  * •

strong connectedness of the graph (entailing simplicity and pure infiniteness
of the graph algebra);

  * •

nonsingularity of $M(n)=A(n)^{t}-I$ (leading to $K_{1}=0$ for the graph
algebra);

  * •

occurrences of specific Sylow $p$-subgroups of the $K_{0}$-group of the graph
algebra, for fixed primes $p$;

  * •

cyclicity of (Sylow subgroups of) the $K_{0}$-group (allowing us to compute or
estimate the probability that the graph algebra is stably isomorphic to a
Cuntz algebra).

We also discuss situations in which we can compute or estimate the asymptotic
probabilities of the associated edge shift being flow equivalent to a full
shift (Section 3.4) or the graph $\mathrm{C}^{*}$-algebra being _exactly_
isomorphic to a Cuntz polygon or Cuntz algebra (Section 3.5), and investigate
the scope for analysing related distributions (Section 3.6).

######  Notation and terminology 3.1.

If $G$ is a finite group and $p$ a prime, then $G_{p}$ denotes the Sylow
$p$-subgroup of $G$. If $P$ is a finite set of primes, then a _$P$ -group_ is
a group whose order is a product of powers of primes in $P$, and we write
$G_{P}$ for $\bigoplus\limits_{p\in P}G_{p}$. We use the symbol $\mathbb{P}$
for probabilities. A sequence of events $\mathscr{E}_{n}$, $n\in\mathbb{N}$,
is said to occur _asymptotically almost surely_ , or _with high probability_ ,
if $\lim\limits_{n\to\infty}\mathbb{P}(\mathscr{E}_{n})=1$.

###  3.1. Bernoulli digraphs

The following in particular applies to Bernoulli digraphs $\mathbb{D}_{n,q}$.
Note that, since the entries of the adjacency matrices of these graphs are all
either $0$ or $1$, if $q\in(0,1)$ then the condition (3.1) holds for all
primes $p$.

######  Theorem 3.2.

Fix a constant $\varepsilon\in(0,1)$ and a finite set $S$ of nonnegative
integers. For each $n\in\mathbb{N}$, let $A(n)$ be an $n\times n$ matrix with
independent random entries taking values in $S$ such that, for every
$i,j\in\\{1,\dots,n\\}$ and every prime $p$,

$\max_{s\in S}\mathbb{P}\left(A(n)_{ij}\equiv s\mod p\right)\leq
1-\varepsilon.$ (3.1)

Then:

  1. 1.

the graph $\mathbb{H}_{n}$ associated with $A(n)$ is asymptotically almost
surely strongly connected;

  2. 2.

$M(n)=A(n)^{t}-I$ is asymptotically almost surely nonsingular (and so is
$A(n)$ itself);

  3. 3.

$\mathrm{C}^{*}(\mathbb{H}_{n})$ is asymptotically almost surely stably
isomorphic to a Cuntz polygon;

  4. 4.

for any finite set $P$ of primes and any finite abelian $P$-group $G$,

$\lim_{n\to\infty}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))_{P}\cong
G\right)=\frac{1}{|\operatorname{\mathrm{Aut}}(G)|}\prod_{p\in
P}\prod_{k=1}^{\infty}\left(1-p^{-k}\right);$ (3.2)

  5. 5.

assuming that the entries of $A(n)$ are identically distributed, the
probability $c_{n}$ that $\mathrm{C}^{*}(\mathbb{H}_{n})$ is stably isomorphic
to a Cuntz algebra satisfies

$\lim\limits_{n\to\infty}c_{n}=\prod_{p\text{
prime}}\left(1+\frac{1}{p^{2}-p}\right)\prod_{k=2}^{\infty}\zeta(k)^{-1}\approx
0.84694,$ (3.3)

where $\zeta$ is the Riemann zeta function.

###### Proof.

  1. 1.

For the first assertion, see [18, Theorem13.9]. While this theorem is
specifically about loopless Bernoulli digraphs, adding loops or multiple edges
does not affect connectivity.

  2. 2.

The second assertion is a consequence of [4, Corollary 3.3]; there, $S$ can be
any finite set of complex numbers (with (3.1) replaced by $\max_{s\in
S}\mathbb{P}\left(A(n)_{ij}=s\right)\leq 1-\varepsilon$), so in particular,
the entries of $M(n)$ also satisfy the necessary hypotheses. (In fact, it is
shown there that the asymptotic probability of singularity is
$(\sqrt{1-\varepsilon}+o(1))^{n}$.)

  3. 3.

Since $A(n)$ with high probability is not a permutation matrix, and we have
just established strong connectivity of $\mathbb{H}_{n}$ and nonsingularity of
$M(n)$, the third claim follows from Proposition 2.4.3.

  4. 4.

For the computation of the distribution of Sylow $p$-subgroups, see [43,
Corollary 3.4].

  5. 5.

For the final equation, note that by definition and Theorem 2.4.2, and in
light of Theorem 3.2.3, $c_{n}$ is asymptotically equal to the probability
that $\operatorname{\mathrm{coker}}M(n)\cong
K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))$ is cyclic. Lest the appearance of the
zeta function in the limiting value of $c_{n}$ seem overly mysterious,
consider the following derivation, which is heuristic only in skipping the
justification of exchanging the limits $n\to\infty$ and $|P|\to\infty$. Let us
define the related quantity

$c^{P}_{n}=\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))_{P}\text{ is
cyclic}\right),$

so that
$\lim_{n\to\infty}c_{n}=\lim_{n\to\infty}\lim_{|P|\to\infty}c^{P}_{n}$. If we
could exchange the two limits, then we could compute this by taking the
$|P|\to\infty$ limit of (3.2). First, recall that for any prime $p$ and any
integer $N\geq 1$

$|\operatorname{\mathrm{Aut}}(\mathbb{Z}/p^{N}\mathbb{Z})|=p^{N}(1-p^{-1}),$

as well as $|\operatorname{\mathrm{Aut}}(G_{1}\oplus
G_{2})|=|\operatorname{\mathrm{Aut}}(G_{1})|\cdot|\operatorname{\mathrm{Aut}}(G_{2})|$
when $|G_{1}|$ and $|G_{2}|$ are coprime. Let $N_{P}=(N_{p})_{p\in P}$ denote
a sequence of non-negative integers, and recall also that a cyclic group of
order divisible only by some power of $p\in P$ must be of the form
$\bigoplus_{p\in P}\mathbb{Z}/p^{N_{p}}\mathbb{Z}$, so that

$\displaystyle\lim_{n\to\infty}c_{n}^{P}$
$\displaystyle=\lim_{n\to\infty}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))_{P}\text{
is cyclic}\right)$
$\displaystyle=\lim_{n\to\infty}\sum_{N_{P}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))_{P}\cong\bigoplus_{p\in
P}\mathbb{Z}/p^{N_{p}}\mathbb{Z}\right)$
$\displaystyle\text{``=''}\sum_{N_{P}}\lim_{n\to\infty}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))_{P}\cong\bigoplus_{p\in
P}\mathbb{Z}/p^{N_{p}}\mathbb{Z}\right)$
$\displaystyle=\sum_{N_{P}}\frac{1}{|\operatorname{\mathrm{Aut}}\left(\bigoplus_{p\in
P}\mathbb{Z}/p^{N_{p}}\mathbb{Z}\right)|}\prod_{p\in
P}\prod_{k=1}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\sum_{N_{P}}\prod_{p\in
P}\frac{1}{|\operatorname{\mathrm{Aut}}\left(\mathbb{Z}/p^{N_{p}}\mathbb{Z}\right)|}\prod_{k=1}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\prod_{p\in
P}\left(1+\sum_{N=1}^{\infty}\frac{p^{-N}}{(1-p^{-1})}\right)\prod_{k=1}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\prod_{p\in
P}\left(1-\frac{1}{p}+\frac{1}{p-1}\right)\prod_{k=2}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\left[\prod_{p\in
P}\left(1+\frac{1}{p^{2}-p}\right)\right]\left[\prod_{k=2}^{\infty}\prod_{p\in
P}\left(1-p^{-k}\right)\right].$

By taking the limit $|P|\to\infty$ and using Euler’s product formula

$\zeta(k)^{-1}=\prod_{p\text{ prime}}\left(1-p^{-k}\right),$

we recover (3.3). Of course, in this heuristic derivation we have not
justified the exchanges of the sum over $N_{P}$ and the $n\to\infty$,
$|P|\to\infty$ limits and that is part of what is accomplished in [30, Theorem
1.2] (with $u=0$ and $\alpha_{n}=\varepsilon$). On the other hand, while this
theorem essentially does establish (3.3), we cannot apply it automatically
because the entries of $M(n)=A(n)^{t}-I$ are not identically distributed (the
probability distribution for the diagonal entries has been shifted by $1$).
However, a close inspection of its proof reveals that the conclusion remains
valid. We now offer a brief justification of this claim.

One must show that, for every prime $p$,
$\operatorname{\mathrm{rank}}(M(n)\text{ mod }p)\geq n-1$. ‘Small’, ‘medium’
and ‘large’ primes are considered separately. The case of small primes [30,
Proposition 2.1] is already observed for random matrices whose entries are not
necessarily identical. The medium primes case [30, Proposition 2.2] depends on
Odlyzko’s lemma [30, Lemma 3.1] and its ‘union bound’ corollary [30, Corollary
3.2] (whose proofs are easily seen to cover random vectors with non-identical
entries that share the same bound, which is certainly the case for us), [30,
Theorem 5.3] (which does not assume identical distributions), and [30, Theorem
5.2] (the $u=0$ case of which is [28, Theorem A.1], discussed below). The
large primes case [30, Proposition 2.3], our use of which falls under [30,
§6.1], depends on the Erdős–Littlewood–Offord result [30, Theorem 6.3] (which
by convexity, that is, conditioning over the possible values taken by the
first entry of the random vector $X$ and using the triangle inequality,
implies the version in which this entry is not identical to the others), [30,
Lemma 6.4] (which follows from Odlyzko’s lemma), [30, Lemma 6.5] (which is
deterministic) and [30, Lemma 6.2] (which follows from the previous three
results).

It remains to carefully inspect the proof of [28, Theorem A.1], which is split
into many lemmas, propositions and theorems. The key ones for us to examine
are [28, Theorem A.15] (which is the aforementioned Erdős–Littlewood–Offord
result), [28, Lemma A.9], [28, Proposition A.18] and [28, Lemma A.11]. The
other results are either deterministic or are proved from these key ones
(together with Odlyzko’s lemma) without further appeal to the assumption of
identically distributed entries.

For each of these key results, the only change is that instead of one measure
$\mu$ specifying the distribution of the entries of the random vector $X$,
there are two, $\mu$ and $\mu_{1}$ say (to account for the shifted first
entry), and products of the form $\prod\limits_{l=1}^{n}\widehat{\mu}(t_{l})$
should be replaced by
$\widehat{\mu}_{1}(t_{1})\prod\limits_{l=2}^{n}\widehat{\mu}(t_{l})$. Here,
$\widehat{\mu}$ denotes the Fourier transform defined on [28, p. 287], the
absolute value of which is not affected by the shift $\mu_{1}(t)=\mu(t+1)$.
So, the proof of [28, Lemma A.9] carries over unchanged. For [28, Proposition
A.18] (which is used to prove [28, Lemma A.11]), the measure $\nu_{1}$
associated to $\mu_{1}$ (obtained from [26, Proposition 3.6]) has the same
Fourier transform as $\nu$ associated to $\mu$ (since by construction,
$\widehat{\nu}(\xi)=1-\gamma+\gamma|\widehat{\mu}(\xi)|^{2}$ for a suitable
$\gamma\in(0,1)$), so again the same proof works (in fact with $\nu_{1}=\nu$).
The rest of the proof of [28, Lemma A.11] also needs no change. ∎

######  Remark 3.3.

Apart from expanding the analysis from finitely many primes to all primes
simultaneously, a substantial portion of Nguyen and Wood’s work in [30] goes
towards proving that, for random matrices with identically distributed
entries, the probability bound $1-\varepsilon$ can be weakened to
$1-\alpha_{n}$ with $\alpha_{n}\geq n^{-1+\varepsilon}$. The argument we have
described in the proof of Theorem 3.2 works for $\alpha_{n}\geq
n^{-1/6+\varepsilon}$ (which is the case considered in [30, §6.1]), but a
great deal more care is needed to extend to the general case. On the other
hand, as pointed out in [30], the bound $\alpha_{n}\geq n^{-1+\varepsilon}$ is
asymptotically best possible: if the matrix entries can take the value $0$
with probability at least $1-\log n/n$, then with nonzero probability the
matrix has a row of zeros, so is singular and in particular has infinite
cokernel. The statistics of these sparser graphs are thus rather different, a
fact that is supported by the data (see Table 4).

###  3.2. Random regular multigraphs

For a finite abelian group $G$, a symmetric, $\mathbb{Z}$-bilinear map
$\varphi\colon G\times G\to\mathbb{C}^{*}$ is a _perfect pairing_ if the only
$g\in G$ with $\varphi(g,G)=1$ is $g=0$. (Equivalently, $\varphi$ induces an
isomorphism $G\to\widehat{G}=\operatorname{\mathrm{Hom}}(G,\mathbb{C}^{*})$
via $g\mapsto\varphi(g,\cdot)$.) We define

$N(G)=\frac{|\\{\text{symmetric, bilinear, perfect }\varphi\colon G\times
G\to\mathbb{C}^{*}\\}|}{|G|\cdot|\operatorname{\mathrm{Aut}}(G)|}.$ (3.4)

If $G$ is a finite abelian $p$-group

$G=\bigoplus_{i=1}^{M}\mathbb{Z}/p^{\lambda_{i}}\mathbb{Z}$

with $\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{M}$, then

$N(G)=p^{-\sum_{i}\frac{\mu_{i}(\mu_{i}+1)}{2}}\prod_{i=1}^{\lambda_{1}}\prod_{j=1}^{\lfloor\frac{\mu_{i}-\mu_{i+1}}{2}\rfloor}(1-p^{-2j})^{-1},$
(3.5)

where $\mu_{i}=|\\{j\mid\lambda_{j}\geq i\\}|$ (see [42, §1]). It is worth
noticing that, if the $\lambda_{i}$ are interpreted as the lengths of the rows
of a Young diagram, the $\mu_{j}$ are the lengths of its columns.

The expression (3.6) makes use of the following observation. If $G_{1}$ is a
finite abelian $p_{1}$-group and $G_{2}$ is a finite abelian $p_{2}$-group
with $p_{2}\neq p_{1}$, then $N(G)=N(G_{1})\cdot N(G_{2})$ for $G=G_{1}\oplus
G_{2}$. After all, if we count the perfect pairings in the definition (3.4) of
$N(G)$ as group homomorphisms $G\to\widehat{G}$, any such homomorphism comes
from an independent pair of homomorphisms $G_{1}\to\widehat{G}_{1}$ and
$G_{2}\to\widehat{G}_{2}$, which are themselves perfect pairings. The
factorisation of $N(G)$ then follows by noting also the obvious factorisations
$|G|=|G_{1}|\cdot|G_{2}|$ and
$|\operatorname{\mathrm{Aut}}(G)|=|\operatorname{\mathrm{Aut}}(G_{1})|\cdot|\operatorname{\mathrm{Aut}}(G_{2})|$.

The following adaptation of [29] was mostly observed in [20].

######  Theorem 3.4.

Let $n\in 2\mathbb{N}$ and $3\leq r\in\mathbb{N}$, and recall that
$\widehat{\mathbb{G}}_{n,r}$ denotes a random $r$-regular multigraph on $n$
vertices. Then:

  1. 1.

$\widehat{\mathbb{G}}_{n,r}$ is asymptotically almost surely strongly
connected;

  2. 2.

$M(n)=A(n)^{t}-I$ is asymptotically almost surely nonsingular (and so is
$A(n)$);

  3. 3.

$\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$ is asymptotically almost surely
stably isomorphic to a Cuntz polygon;

  4. 4.

for any finite set $P$ of odd primes not dividing $r-1$, and any finite
abelian $P$-group $G$,

$\lim_{n\in
2\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{P}\cong
G\right)=\prod_{p\in P}N(G_{p})\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right).$
(3.6)

###### Proof.

The first and last assertions appear in [20, Theorem 6.3]. The second then
follows from [29, Corollary 4.2] (see also the rest of the proof of [29,
Theorem 1.6]), and the third then follows from Proposition 2.4.3, since $A(n)$
is not a permutation matrix (because each of its rows sums to $r$) and we have
already established asymptotic strong connectivity of $E$ as well as
asymptotic nonsingularity of $A(n)^{t}-I$. ∎

In particular, for any odd prime $p$ coprime to $r-1$ and any integer $N\geq
0$,

$\displaystyle\lim_{n\in
2\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}\cong\mathbb{Z}/p^{N}\mathbb{Z}\right)$
$\displaystyle=p^{-N}\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$ (3.7)
$\displaystyle\approx p^{-N},$

while

$\displaystyle\lim_{n\in
2\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}\cong(\mathbb{Z}/p\mathbb{Z})^{N}\right)$
$\displaystyle=p^{-\frac{N(N+1)}{2}}\prod_{j=1}^{\lfloor
N/2\rfloor}(1-p^{-2j})^{-1}\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$ (3.8)
$\displaystyle\approx p^{-\frac{N(N+1)}{2}},$

the approximations holding for sufficiently large primes $p$.

Using (3.6) and (3.7), we can compute the asymptotic probability that
$(K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{P}$ is cyclic, for any
_finite_ set $P$ of odd primes not dividing $r-1$. The following also applies
to Erdős–Rényi graphs $\mathbb{E}_{n,q}$ for $P=\\{p\\}$, where $p$ can be any
prime (see Theorem 3.7).

######  Proposition 3.5.

Let $(\mathbb{E}_{n})_{n\in\mathbb{N}}$ be a family of random graphs and $P$ a
finite set of primes such that

$\lim_{n\in\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{P}\cong
G\right)=\prod_{p\in P}N(G_{p})\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$
(3.9)

for every finite abelian $P$-group $G$. Then,

$\lim_{n\in\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{P}\text{
is cyclic}\right)=\prod_{p\in P}\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right).$
(3.10)

###### Proof.

As in the proof of Theorem 3.2, let us write
$c_{n}^{P}:=\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{P}\text{ is
cyclic}\right)$, and for $N_{P}=(N_{p})_{p\in P}$ let
$c_{n}^{N_{P}}=\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{P}\cong\bigoplus_{p\in
P}\mathbb{Z}/p^{N_{p}}\mathbb{Z}\right)$, so that
$c_{n}^{P}=\sum_{N_{P}}c_{n}^{N_{P}}$. To show the equality (3.10) we
essentially want to interchange the limit with the summation to get

$\lim_{n\in\mathbb{N}}c_{n}^{P}=\lim_{n\in\mathbb{N}}\sum_{N_{p}}c_{n}^{N_{P}}=\sum_{N_{P}}\lim_{n\in\mathbb{N}}c_{n}^{N_{P}}$
(3.11)

and sum the right-hand side, where by hypothesis (3.9) and (3.7) we have

$\displaystyle\sum_{N_{P}}\lim_{n\in\mathbb{N}}c_{n}^{N_{P}}$
$\displaystyle=\sum_{N_{P}}\prod_{p\in
P}p^{-N_{p}}\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$
$\displaystyle=\prod_{p\in
P}\sum_{N_{p}=0}^{\infty}p^{-N_{p}}\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$
$\displaystyle=\prod_{p\in P}\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right).$

The interchange in (3.11) is justified by the Vitali convergence theorem [11,
Theorem III.6.15], which in general applies to the interchange of a limit with
integration of absolutely summable functions over a measure space. In our
case, with the pointwise convergence of $c_{n}^{N_{P}}$ over the discrete
measure space of all $N_{P}$’s, the remaining hypothesis to check is
_equismallness at infinity_ (a.k.a  _equisummability at infinity_ ; for series
this is spelled out in [41, Theorem 44.2]). Namely, for every $\varepsilon>0$
we need to find a finite set $X_{\varepsilon}$ such that for all $n$

$\sum_{N_{P}\not\in X_{\varepsilon}}c_{n}^{N_{P}}<\varepsilon.$

By virtue of being probability distributions (hence absolutely summable, with
no need to take absolute values because of pointwise positivity) there exist
finite sets $Z_{\varepsilon}$ and $Z_{n,\varepsilon}$ of abelian $P$-groups
such that

$\sum_{G\not\in
Z_{\varepsilon}}\lim_{m\in\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{m}))_{P}\cong
G\right)<\frac{\varepsilon}{2}\quad\text{and}\quad\sum_{G\not\in
Z_{n,\varepsilon}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{P}\cong
G\right)<\varepsilon.$

By pointwise convergence of the probability distributions in (3.9), there also
exists an $M\in\mathbb{N}$ such that for all $n\geq M$ and $G\in
Z_{\varepsilon}$

$\left|\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{P}\cong
G\right)-\lim_{m\in\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{m}))_{P}\cong
G\right)\right|<\frac{\varepsilon}{2|Z_{\varepsilon}|}.$

Hence, we can set $Z_{n,\varepsilon}=Z_{\varepsilon}$ for all $n\geq M$.
Noting that $c^{N_{P}}$ and $c_{n}^{N_{P}}$ are restrictions of the above
probability distributions to cyclic groups and setting $X_{\varepsilon}$ to be
the intersection of the set
$Z_{\varepsilon}\cup\bigcup_{n<M}Z_{n,\varepsilon}$ with cyclic groups shows
that $c_{n}^{N_{P}}$ is equismall at infinity, allowing us to apply Vitali’s
convergence theorem in (3.11). ∎

######  Remark 3.6.

If $r=2^{j}+1$ for some $j$, then (3.7), (3.8) and (3.10) hold for
$\widehat{\mathbb{G}}_{n,r}$ for any finite set $P$ of odd primes (as all odd
primes are coprime to $r-1=2^{j}$). This is why we we pay special attention to
these values of $r$ in Section 4. But we do not have any theoretical
distribution for $p=2$. In addition, because of the subtleties arising from
the two limits, $n\to\infty$ and enlarging $P$ to the set of all primes, one
cannot immediately extend (3.10) to infinitely many primes. For Bernoulli
digraphs, this more delicate analysis is carried out in [30], but there is as
yet no such result for $r$-regular multigraphs. These are exactly the
obstacles to computing the asymptotic probability that
$\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$ is stably isomorphic to a Cuntz
algebra, which we mentioned in the Introduction.

###  3.3. Erdős–Rényi graphs

The following in particular applies to Erdős–Rényi graphs $\mathbb{E}_{n,q}$,
the symmetric versions of $\mathbb{D}_{n,q}$, provided that $q\in(0,1)$.

######  Theorem 3.7.

Fix a constant $\varepsilon\in(0,1)$ and a finite set $S$ of nonnegative
integers. For each $n\in\mathbb{N}$, let $A(n)$ be a symmetric $n\times n$
matrix such that, for every $i\leq j\in\\{1,\dots,n\\}$, the entries
$A(n)_{ij}$ are independent random variables taking values in $S$ that satisfy

$\max_{s\in S}\mathbb{P}\left(A(n)_{ij}\equiv s\mod p\right)\leq
1-\varepsilon$ (3.12)

for every prime $p$. Then:

  1. 1.

the graph $\mathbb{E}_{n}$ associated with $A(n)$ is asymptotically almost
surely strongly connected;

  2. 2.

$M(n)=A(n)^{t}-I$ is asymptotically almost surely nonsingular (and so is
$A(n)$ itself);

  3. 3.

$\mathrm{C}^{*}(\mathbb{E}_{n})$ is asymptotically almost surely stably
isomorphic to a Cuntz polygon;

  4. 4.

for any prime $p$ and any finite abelian $p$-group $G$,

$\lim_{n\in\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n}))_{p}\cong
G\right)=N(G)\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right),$ (3.13)

where $N(G)$ is as in (3.4), (3.5).

###### Proof.

The first assertion follows from [16] (see [18, Theorem 4.1]) and the last
from [44, Theorem 3.12]. The second then follows from [29, Corollary 4.2], and
the third then follows from Proposition 2.4, exactly as in the proof of
Theorem 3.2.3. ∎

By Theorem 3.7.4, _all_ Sylow $p$-subgroups of
$K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n,q}))$, including $p=2$, follow the
limiting behaviour (3.7), (3.8) and (3.10) with $P=\\{p\\}$. The data we have
collected for these graphs are consistent with this (see Figure 5 and Table
5).

###  3.4. The signed Bowen–Franks group

As discussed in the Introduction, every (directed multi-) graph $E$ has an
associated edge shift $\sigma\colon\Sigma_{E}\to\Sigma_{E}$, whose flow
equivalence class is determined by the signed Bowen–Franks group
$\mathrm{BF}_{+}(E)=\operatorname{\mathrm{sgn}}(\det(I-A_{E}))\operatorname{\mathrm{coker}}(I-A_{E})$
(assuming that $E$ is strongly connected and does not consist of a single
cycle). For the random graph models discussed above, we are interested in the
asymptotic probability of flow equivalence to a full shift (whose Bowen–Frank
invariant is $-\mathbb{Z}/k\mathbb{Z}$ for some $k$). If we make the heuristic
assumption that positivity of the determinant is asymptotically independent of
cyclicity of the cokernel (a not unreasonable notion given the data; see
Tables 2, 3, 6, 11), then we are left with the question: what is the shape of
the distribution of $\det(I-A(n))$?

There is one situation in which symmetry is immediately apparent, namely, when
the entries of $A(n)-I$ are identically distributed, simply because in this
case swapping rows preserves the distribution. Moreover, our careful
adaptation of [30, Theorem 1.2] in the proof of Theorem 3.2.5 is now no longer
necessary. A direct application this theorem tells us that the asymptotic
probability of cyclicity is once again given by (3.3).

In summary of the above discussion, we have the following. Recall that $\zeta$
denotes the Riemann zeta function.

######  Theorem 3.8.

Fix a constant $\varepsilon\in(0,1)$ and a finite set $S$ of nonnegative
integers. For each $n\in\mathbb{N}$, let $B(n)$ be an $n\times n$ matrix with
independent random entries taking values in $S$ such that, for every
$i,j\in\\{1,\dots,n\\}$ and every prime $p$,

$\max_{s\in S}\mathbb{P}\left(B(n)_{ij}\equiv s\mod p\right)\leq
1-\varepsilon.$

Suppose further that there are two rows (or columns) of $B(n)$ whose vector
distributions are identical. Let $\mathbb{H}_{n}$ be the graph whose adjacency
matrix is $A(n)=B(n)+I$. Then, the asymptotic probability that the edge shift
$\sigma\colon\Sigma_{\mathbb{H}_{n}}\to\Sigma_{\mathbb{H}_{n}}$ is flow
equivalent to a full shift is

$\frac{1}{2}\prod_{p\text{
prime}}\left(1+\frac{1}{p^{2}-p}\right)\prod_{k=2}^{\infty}\zeta(k)^{-1}$
(3.14)

which, as a percentage, is about $42$.

Just as Theorem 3.2 in particular applies to Bernoulli digraphs
$\mathbb{D}_{n,q}$, Theorem 3.8 applies to _shifted_ Bernoulli digraphs
$\mathbb{D}_{n,q}+I$ (see Table 3). These graphs have either one loop (with
probability $1-q$) or two (with probability $q$) at every vertex, with other
edges distributed in the same way as for $\mathbb{D}_{n,q}$. With randomness
specified in this manner, the pithy interpretation of (3.14) is that this is
the asymptotic probability that a random subshift of finite type is flow
equivalent to a full shift. Of course, it might be reasonable to expect that,
asymptotically, shifting by the identity matrix should not have any effect on
the distribution of the determinant. The data do support this expectation (see
Table 2), and we conjecture it to be true.

######  Conjecture 3.9.

For $q\in(0,1)$,

$\lim_{n\to\infty}\mathbb{P}\left(\sigma\colon\Sigma_{\mathbb{D}_{n,q}}\to\Sigma_{\mathbb{D}_{n,q}}\text{
is flow equivalent to a full shift}\right)\\\ =\frac{1}{2}\prod_{p\text{
prime}}\left(1+\frac{1}{p^{2}-p}\right)\prod_{k=2}^{\infty}\zeta(k)^{-1}\approx
0.42347.$

For the symmetric graphs $\mathbb{E}_{n,q}$, it is expected but not yet proved
(though supported by the data; see Table 5), that Proposition 3.5 should hold
when $P$ is enlarged to the set of all primes. In other words, we expect that

$\lim_{n\to\infty}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n,q}))\text{
is cyclic}\right)=\prod_{p\text{
prime}}\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right)\approx 0.79352.$ (3.15)

It seems however that for $\mathbb{E}_{n,q}$ (and also
$\widehat{\mathbb{G}}_{n,r}$), the determinant may not be symmetrically
distributed about the origin and its asymptotic behaviour is a little harder
to predict (see Tables 6, 11). This means that we cannot simply bisect (3.15)
(or for $\widehat{\mathbb{G}}_{n,r}$, (4.2)) and conjecture that value as the
asymptotic full-shift probability.

######  Question 3.10.

What is the asymptotic distribution of the signs of of $\det(I-A(n))$ when
$A(n)$ is the adjacency matrix of $\mathbb{E}_{n,q}$ or
$\widehat{\mathbb{G}}_{n,r}$? Is it still the case that negativity of the
determinant and cyclicity are asymptotically independent events? Namely, do
the probabilities

$\displaystyle\delta_{n,q}$
$\displaystyle:=\mathbb{P}\left(\det(I-A(n))<0\right)$ (3.16)
$\displaystyle\sigma_{n,q}$
$\displaystyle:=\mathbb{P}\left(\det(I-A(n))<0\wedge\operatorname{\mathrm{coker}}(I-A(n))\text{
cyclic}\right)$

for $\mathbb{E}_{n,q}$ ($q\in(0,1)$) and the probabilities

$\displaystyle\varepsilon_{n,r}$
$\displaystyle:=\mathbb{P}\left(\det(I-A(n))<0\right)$ (3.17)
$\displaystyle\tau_{n,r}$
$\displaystyle:=\mathbb{P}\left(\det(I-A(n))<0\wedge\operatorname{\mathrm{coker}}(I-A(n))\text{
cyclic}\right)$

for $\widehat{\mathbb{G}}_{n,r}$ ($r\geq 3$) converge, and if so, what are
their limits $\delta_{q}$, $\sigma_{q}$, $\varepsilon_{r}$, $\tau_{r}$?

###  3.5. Exact isomorphism

We described in Section 3.5 how, practically speaking, we can check whether a
graph algebra is exactly (rather than stably) isomorphic to a Cuntz polygon
(or Cuntz algebra). In Section 4, we provide estimates of the asymptotic
probabilities of these events for $\mathbb{D}_{n,q}$ and $\mathbb{E}_{n,q}$
(see Tables 2, 6). Here, we offer an explanation of the numbers that we see
there.

######  Conjecture 3.11.

For $q\in(0,1)$,

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{D}_{n,q})\text{
is isomorphic to a Cuntz algebra}\right)$
$\displaystyle=\prod_{k=2}^{\infty}\zeta(k)^{-1}$ $\displaystyle\approx
0.43576,$ (3.18)
$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{E}_{n,q})\text{
is isomorphic to a Cuntz algebra}\right)$ $\displaystyle=\prod_{p\text{
prime}}\left(1-\frac{1}{p^{2}}\right)\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right)$
$\displaystyle\approx 0.51451,$ (3.19)
$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{D}_{n,q})\text{
is isomorphic to a Cuntz polygon}\right)$ $\displaystyle=\prod_{p\text{
prime}}\left(1+\frac{1}{p^{2}-p}\right)^{-1}$ $\displaystyle\approx 0.48240,$
(3.20)
$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{E}_{n,q})\text{
is isomorphic to a Cuntz polygon}\right)$ $\displaystyle=\prod_{p\text{
prime}}\left(1-\frac{1}{p^{2}}\right)$ $\displaystyle\approx 0.60793.$ (3.21)

###### Heuristic ‘proof’.

The derivation is easy if we are willing to freely and recklessly use the
heuristic principles of _independence_ (I) and _uniformity_ (U). More
precisely, let us assume that if $\mathbb{H}_{n}$ is a suitably random family
of graphs, then the following hold asymptotically.

  1. (I)

The events $\mathscr{C}_{n}$: ‘$K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))$ is
cyclic’ and $\mathscr{U}_{n}$: ‘$[1_{\mathrm{C}^{*}(\mathbb{H}_{n})}]$ is in
the same automorphism orbit in $K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))$ as the
unit of the corresponding Cuntz polygon’ are independent.

  2. (U)

Conditioned on $\mathscr{C}_{n}$, $[1_{\mathrm{C}^{*}(\mathbb{H}_{n})}]$ is
uniformly distributed in $K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))$.

Suppose that $K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))\cong\bigoplus\limits_{p\in
P}\mathbb{Z}/p^{N_{p}}\mathbb{Z}=:G_{N_{P}}$ for some finite set $P$ of
primes. The class of the unit of the corresponding Cuntz algebra is a
generator of the cyclic group $G_{N_{P}}$. Its automorphism orbit is the set
of elements of full order, of which there are $\prod\limits_{p\in
P}p^{N_{p}}(1-p^{-1})=|\operatorname{\mathrm{Aut}}(G_{N_{P}})|$ many. Applying
(U) in this case, the conditional probability that
$\mathrm{C}^{*}(\mathbb{H}_{n})$ is isomorphic to
$\mathcal{O}_{1+|G_{N_{P}}|}$ is

$\frac{|\operatorname{\mathrm{Aut}}(G_{N_{P}})|}{|G_{N_{P}}|}=\prod_{p\in
P}(1-p^{-1}).$

Then, proceeding as in the heuristic argument presented in the proof Theorem
3.2.5 and making no attempt to justify any rearrangement of limits,

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{H}_{n})\cong\mathcal{O}_{k}\text{
for some }k\right)$
$\displaystyle=\lim_{n\to\infty}\mathbb{P}(\mathscr{C}_{n}\cap\mathscr{U}_{n})$
$\displaystyle=\lim_{n\to\infty}\sum_{N}\frac{|\operatorname{\mathrm{Aut}}(G_{N_{P}})|}{|G_{N_{P}}|}\mathbb{P}(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))\cong
G_{N_{P}})$ $\displaystyle=\prod_{p\text{
prime}}\sum_{N}\frac{|\operatorname{\mathrm{Aut}}(\mathbb{Z}/p^{N}\mathbb{Z})|}{|\mathbb{Z}/p^{N}\mathbb{Z}|}\lim_{n\to\infty}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\mathbb{H}_{n}))_{p}\cong\mathbb{Z}/p^{N}\mathbb{Z}\right).$

Applying (3.2) in the case $\mathbb{H}_{n}=\mathbb{D}_{n,q}$, we get

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{D}_{n,q})\cong\mathcal{O}_{k}\text{
for some }k\right)$ $\displaystyle=\prod_{p\text{
prime}}\sum_{N}\frac{|\operatorname{\mathrm{Aut}}(\mathbb{Z}/p^{N}\mathbb{Z})|}{|\mathbb{Z}/p^{N}\mathbb{Z}|}\cdot\frac{1}{|\operatorname{\mathrm{Aut}}(\mathbb{Z}/p^{N}\mathbb{Z})|}\prod_{k=1}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\prod_{p\text{
prime}}\sum_{N}p^{-N}\prod_{k=1}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\prod_{p\text{
prime}}\prod_{k=2}^{\infty}\left(1-p^{-k}\right)$
$\displaystyle=\prod_{k=2}^{\infty}\zeta(k)^{-1}.$

From this we deduce that

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{D}_{n,q})\cong\mathcal{P}_{\bar{m}}\text{
for some }\bar{m}\right)$
$\displaystyle=\lim_{n\to\infty}\mathbb{P}(\mathscr{U}_{n})$
$\displaystyle=\lim_{n\to\infty}\frac{\mathbb{P}(\mathscr{C}_{n}\cap\mathscr{U}_{n})}{\mathbb{P}(\mathscr{C}_{n})}$
(appealing to (I)) $\displaystyle=\prod_{p\text{
prime}}\left(1+\frac{1}{p^{2}-p}\right)^{-1}$ $\displaystyle\text{(by
\eqref{eqn:dcuntz} and \eqref{eqn:ercuntz})}.$

For $\mathbb{H}_{n}=\mathbb{E}_{n,q}$, recall that the normalisation factor
$N(G_{P})$ defined in (3.5) and appearing in (3.13) simplifies to
$N(\mathbb{Z}/p^{N}\mathbb{Z})=\prod\limits_{p\text{
prime}}p^{-N}=|G_{P}|^{-1}$ for the cyclic group $G_{P}$ (as in (3.7)).
Assuming that (3.13) behaves well when passing to the set of all primes, we
have

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{E}_{n,q})\cong\mathcal{O}_{k}\text{
for some }k\right)$ $\displaystyle=\prod_{p\text{
prime}}\sum_{N}\frac{|\operatorname{\mathrm{Aut}}(\mathbb{Z}/p^{N}\mathbb{Z})|}{|\mathbb{Z}/p^{N}\mathbb{Z}|^{2}}\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$
$\displaystyle=\prod_{p\text{
prime}}\left(1+\sum_{N=1}^{\infty}\frac{p^{N}(1-p^{-1})}{p^{2N}}\right)\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$
$\displaystyle=\prod_{p\text{
prime}}\left(1+\frac{1}{p}\right)\prod_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$
$\displaystyle=\prod_{p\text{
prime}}\left(1-\frac{1}{p^{2}}\right)\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right).$

By the same token, assuming (3.15) as in the discussion following Conjecture
3.9, we have

$\lim_{n\to\infty}\mathbb{P}(\mathscr{C}_{n})=\prod_{p\text{
prime}}\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right)$ (3.22)

and then

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\mathbb{E}_{n,q})\cong\mathcal{P}_{\bar{m}}\text{
for some }\bar{m}\right)$
$\displaystyle=\lim_{n\to\infty}\frac{\mathbb{P}(\mathscr{C}_{n}\cap\mathscr{U}_{n})}{\mathbb{P}(\mathscr{C}_{n})}$
(by (I)) $\displaystyle=\prod_{p\text{ prime}}\left(1-\frac{1}{p^{2}}\right)$
$\displaystyle\text{(by \eqref{eqn:ecuntz} and \eqref{eqn:ecn})}.\qed$

By contrast, it appears to be _very_ rare for
$\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$ to be isomorphic to a Cuntz
polygon. Indeed, for the values of $n$ and $r$ for which we collected data,
this event essentially never happened (see Table 11). But it is not an
impossibility. The following example was generated by our computer code.

######  Example 3.12.

Let $E$ be the $8$-regular graph on $6$ vertices whose adjacency matrix is

$A=\begin{pmatrix}0&3&3&1&0&1\\\ 3&0&0&2&3&0\\\ 3&0&0&2&1&2\\\ 1&2&2&0&1&2\\\
0&3&1&1&0&3\\\ 1&0&2&2&3&0\end{pmatrix}.$

Since $A-I$ is not a permuted diagonal matrix, its underlying graph is
obviously not that of a Cuntz polygon itself. The SNF factorisation $UMV=D$ of
$M=A-I$ is

$\left(\begin{smallmatrix}1&-6&-6&-6&-6&-6\\\ 0&1&0&0&0&0\\\ 0&0&1&0&0&0\\\
0&0&0&1&0&0\\\ 0&0&0&0&1&0\\\
0&0&0&0&0&1\end{smallmatrix}\right)\left(\begin{smallmatrix}-1&3&3&1&0&1\\\
3&-1&0&2&3&0\\\ 3&0&-1&2&1&2\\\ 1&2&2&-1&1&2\\\ 0&3&1&1&-1&3\\\
1&0&2&2&3&-1\end{smallmatrix}\right)\left(\begin{smallmatrix}13&13&11&11&10&9\\\
13&19&6&10&13&6\\\ -1&-6&3&0&-3&2\\\ -1&-2&0&-1&-1&0\\\ -8&-5&-9&-7&-5&-7\\\
-15&-18&-10&-12&-13&-9\end{smallmatrix}\right)=\left(\begin{smallmatrix}7&0&0&0&0&0\\\
0&1&0&0&0&0\\\ 0&0&1&0&0&0\\\ 0&0&0&1&0&0\\\ 0&0&0&0&1&0\\\
0&0&0&0&0&1\end{smallmatrix}\right),$

from which we can deduce that

$(K_{0}(\mathrm{C}^{*}(E),[1_{\mathrm{C}^{*}(E)}],K_{1}(\mathrm{C}^{*}(E)))\cong(\mathbb{Z}/7\mathbb{Z},-29,0)\cong(\mathbb{Z}/7\mathbb{Z},1,0),$

since $29$ and $7$ are coprime. The conclusion is that $\mathrm{C}^{*}(E)$ is
isomorphic to $\mathcal{O}_{8}$.

######  Question 3.13.

Is it true that, for $r\geq 3$,
$\lim\limits_{n\to\infty}\mathbb{P}\left(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})\cong\mathcal{P}_{\bar{m}}\text{
for some }\bar{m}\right)=0$?

###  3.6. Contiguity

By definition, events that occur asymptotically almost surely according to one
random graph model also occur asymptotically almost surely for any
_contiguous_ model. For example, the perfect matchings model
$\widehat{\mathbb{G}}_{n,r}$ analysed in Section 3.2 is contiguous to the
_uniform model_ $\mathbb{G}^{\prime}_{n,r}$, that is, a random element of the
set of $r$-regular multigraphs with the uniform distribution, conditioned on
there being no loops (see the discussion and references in [18, Chapter 21]).
Had we adopted this model instead, the resultant graph algebras would
therefore still be stably isomorphic to Cuntz polygons with high probability
(see Theorem 3.4). As for the ‘Erdős–Rényi’ graphs $\mathbb{E}_{n,q}$ of
Section 3.3, a better name for them might have been ‘Gilbert’ after his
analysis of this model in [19]. Moreover, the model $\mathbb{E}_{n,m}$
actually employed in [16] is a different one, specifically the uniform
distribution on the set of undirected graphs with $m$ edges on $n$ labelled
vertices (where $n\in\mathbb{N}$ and $0\leq m\leq\binom{n}{2}$). To borrow a
phrase from [18], these two models $\mathbb{E}_{n,q}$ and $\mathbb{E}_{n,m}$
are ‘almost contiguous’ in a quantifiably precise sense. This principle, when
adapted for digraphs and combined with the asymptotic probabilities of
singularity and strong connectedness in this setting, leads to the observation
(Theorem 3.15) that _most_ of the $\mathrm{C}^{*}$-algebras associated to
digraphs on large vertex sets with suitably many edges are stably isomorphic
to Cuntz polygons.

######  Definition 3.14.

For integers $m_{1},m_{2},n$ with $n\geq 1$ and $0\leq
m_{1},m_{2}\leq\binom{n}{2}$, let $\mathcal{G}_{n,m_{1},m_{2}}$ denote the set
of directed graphs on $n$ labelled vertices with $m_{1}$ ‘forward’ edges (that
is, edges $e$ with $s(e)<r(e)$, corresponding to above-diagonal entries of the
adjacency matrix) and $m_{2}$ ‘backward’ ones (edges $e$ with $s(e)>r(e)$, or
below-diagonal entries of the adjacency matrix). Loops ($s(e)=r(e)$) are
allowed, but not multiple edges. We let $\mathbb{U}_{n,m_{1},m_{2}}$ denote an
element of $\mathcal{G}_{n,m_{1},m_{2}}$ chosen randomly according to the
uniform distribution, that is,

$\mathbb{P}(\mathbb{U}_{n,m_{1},m_{2}}=E)=\frac{1}{2^{n}\binom{n}{m_{1}}\binom{n}{m_{2}}}$
(3.23)

for every $E\in\mathcal{G}_{n,m_{1},m_{2}}$ (the factor of $2^{n}$ accounting
for loops).

It is sometimes useful to think of a directed graph $E$ on vertices
$\\{1,\dots,n\\}$ as being obtained by overlaying three undirected ones
($E_{0}$ described by the diagonal entries of the adjacency matrix, $E_{1}$
the above-diagonal entries the and $E_{2}$ the below-diagonal ones). For
example, if $E_{1}$ and $E_{2}$ are both connected, then $E$ is strongly
connected. We take up this point of view in the proof of the following.

######  Theorem 3.15.

If $m_{1}=m_{1}(n)$ and $m_{2}=m_{2}(n)$ satisfy $0\leq
m_{1},m_{2}\leq\binom{n}{2}$ and

$\lim\limits_{n\to\infty}\frac{m_{i}}{\binom{n}{2}}=:\widehat{q}_{i}\in(0,1),\quad
i=1,2,$ (3.24)

then $\mathrm{C}^{*}(\mathbb{U}_{n,m_{1},m_{2}})$ is asymptotically almost
surely stably isomorphic to a Cuntz polygon.

###### Proof.

We adapt the proof of [18, Lemma 1.2], which addresses undirected graphs. Let
$\mathscr{P}=\mathscr{P}_{n,m_{1},m_{2}}\subseteq\mathcal{G}_{n,m_{1},m_{2}}$
be a graph property. Write $N=\binom{n}{2}=\frac{n(n-1)}{2}$ and
$q_{i}=\frac{m_{i}}{N}\approx\frac{2m_{i}}{n^{2}}$, $i=1,2$. Let $A(n)$ be the
$n\times n$ matrix whose entries are independent Bernoulli random variables
with success probability either $q_{1}$ (above the diagonal) or $q_{2}$ (below
the diagonal) or $\frac{1}{2}$ (on the diagonal), and let us write
$\mathbb{H}_{n}$ for the corresponding random graph. We adopt the notational
convention suggested after Definition 3.14 and write $\mathbb{H}_{n,i}$,
$i=0,1,2$, for the graphs corresponding to entries on, above or below the
diagonal of $A(n)$.

For integers $k_{i}\geq 0$, $i=0,1,2$, with $k_{0}\leq n$ and $k_{1},k_{2}\leq
N$, the conditional probability that $\mathbb{H}_{n}$ has the graph property
$\mathscr{P}$, given that $\mathbb{H}_{n,i}$ has $k_{i}$ edges for $i=0,1,2$,
is

$\displaystyle\mathbb{P}(\mathbb{H}_{n}\in\mathscr{P}\mid|\mathbb{H}_{n,i}^{1}|$
$\displaystyle=k_{i},\,i=0,1,2)$
$\displaystyle=\frac{\mathbb{P}(\mathbb{H}_{n}\in\mathscr{P}\wedge|\mathbb{H}_{n,i}^{1}|=k_{i},\,i=0,1,2)}{\prod\limits_{i=0}^{2}\mathbb{P}(|\mathbb{H}_{n,i}^{1}|=k_{i})}$
$\displaystyle=\sum_{\begin{subarray}{c}E\in\mathscr{P}\\\
|E_{i}^{1}|=k_{i}\>\forall
i\end{subarray}}\frac{(\frac{1}{2})^{k_{0}}(\frac{1}{2})^{n-k_{0}}}{\binom{n}{k_{0}}(\frac{1}{2})^{k_{0}}(\frac{1}{2})^{n-k_{0}}}\cdot\frac{q_{1}^{k_{1}}(1-q_{1})^{N-k_{1}}}{\binom{N}{k_{1}}q_{1}^{k_{1}}(1-q_{1})^{N-k_{1}}}\cdot\frac{q_{2}^{k_{2}}(1-q_{2})^{N-k_{2}}}{\binom{N}{k_{2}}q_{2}^{k_{2}}(1-q_{2})^{N-k_{2}}}$
$\displaystyle=\sum_{\begin{subarray}{c}E\in\mathscr{P}\\\
|E_{i}^{1}|=k_{i}\>\forall
i\end{subarray}}\frac{1}{\binom{n}{k_{0}}\binom{N}{k_{1}}\binom{N}{k_{2}}}$
$\displaystyle=\frac{2^{n}}{\binom{n}{k_{0}}}\cdot\mathbb{P}(\mathbb{U}_{n,k_{1},k_{2}}\in\mathscr{P})\quad\text{(by
definition \eqref{eqn:uniform})}.$

Therefore, by the law of total probability,

$\displaystyle\mathbb{P}(\mathbb{H}_{n}\in\mathscr{P})$
$\displaystyle=\sum_{k_{0}=0}^{n}\sum_{k_{1},k_{2}=0}^{N}\mathbb{P}(\mathbb{H}_{n}\in\mathscr{P}\mid|\mathbb{H}_{n,i}^{1}|=k_{i},\,i=0,1,2)\cdot\mathbb{P}(|\mathbb{H}_{n,i}^{1}|=k_{i},\,i=0,1,2)$
$\displaystyle=\sum_{k_{0}=0}^{n}\sum_{k_{1},k_{2}=0}^{N}\frac{2^{n}}{\binom{n}{k_{0}}}\cdot\mathbb{P}(\mathbb{U}_{n,k_{1},k_{2}}\in\mathscr{P})\cdot\mathbb{P}(|\mathbb{H}_{n,i}^{1}|=k_{i},\,i=0,1,2)$
$\displaystyle=\sum_{k_{0}=0}^{n}\sum_{k_{1},k_{2}=0}^{N}\mathbb{P}(\mathbb{U}_{n,k_{1},k_{2}}\in\mathscr{P})\cdot\mathbb{P}(|\mathbb{H}_{n,1}^{1}|=k_{1})\cdot\mathbb{P}(|\mathbb{H}_{n,2}^{1}|=k_{2})$
$\displaystyle\geq\mathbb{P}(\mathbb{U}_{n,m_{1},m_{2}}\in\mathscr{P})\cdot\mathbb{P}(|\mathbb{H}_{n,1}^{1}|=m_{1})\cdot\mathbb{P}(|\mathbb{H}_{n,2}^{1}|=m_{2})$
$\displaystyle\geq\frac{1}{100\sqrt{m_{1}m_{2}}}\mathbb{P}(\mathbb{U}_{n,m_{1},m_{2}}\in\mathscr{P})\quad\text{for
sufficiently large $n$},$

the latter estimate obtained from Stirling’s formula applied to the binomial
probabilities

$\mathbb{P}(|\mathbb{H}_{n,i}^{1}|=m_{i})=\binom{N}{m_{i}}q_{i}^{m_{i}}(1-q_{i})^{N-m_{i}}=\frac{N!}{m_{i}!(N-m_{i})!}q_{i}^{m_{i}}(1-q_{i})^{N-m_{i}},\,i=1,2,$

as in the proof of [18, Lemma 1.2]. Note that (3.24) justifies this use of
Stirling’s formula, as it ensures that the numbers $m_{1}$, $m_{2}$, $N-m_{1}$
and $N-m_{2}$ are all large when $n$ is. What we have now shown is that

$\mathbb{P}(\mathbb{U}_{n,m_{1},m_{2}}\in\mathscr{P})\leq
100\sqrt{m_{1}m_{2}}\cdot\mathbb{P}(\mathbb{H}_{n,m_{1},m_{2}}\in\mathscr{P})\quad\text{for
all large $n$}.$ (3.25)

By assumption (3.24), $M(n)=A(n)^{t}-I$ (for that matter, $A(n)$ itself)
satisfies the requirement (3.1) of Theorem 3.2 for a suitable
$\varepsilon<\min\left\\{\widehat{q}_{1},\widehat{q}_{2},1-\widehat{q}_{1},1-\widehat{q}_{2}\right\\}$.
As mentioned in the proof of Theorem 3.2, the asymptotic probability that
$M(n)$ is singular (which is the relevant graph property $\mathscr{P}$) is
$(\sqrt{1-\varepsilon}+o(1))^{n}$. By (3.25), the corresponding asymptotic
probability for $\mathbb{U}_{n,m_{1},m_{2}}$ is at most
$100\sqrt{m_{1}m_{2}}(\sqrt{1-\varepsilon}+o(1))^{n}$, which converges to $0$
as $n\to\infty$. We also know that, with high probability, the undirected
graphs $(\mathbb{U}_{n,m_{1},m_{2}})_{1}$ and
$(\mathbb{U}_{n,m_{1},m_{2}})_{2}$ are connected (see [18, Theorem 4.1]), so
$\mathbb{U}_{n,m_{1},m_{2}}$ is strongly connected (and does not consist of a
single cycle). The theorem now follows from Proposition 2.4.3. ∎

##  4\. Empirical $K$-data

In this section, we present some of the data produced by our computer code. We
generated samples of size $m=10^{5}$ for various random Bernoulli digraphs
$\mathbb{D}_{n,q}$, Erdős–Rényi graphs $\mathbb{E}_{n,q}$ and regular
multigraphs $\widehat{\mathbb{G}}_{n,r}$, and collected the $K$-theoretic data
outlined in Section 1 for several small primes (up to $p=37$) and a couple
larger ones ($p=137$ and $p=277$). We also collected the supplemental data
outlined in Sections 2.4, 3.4, 3.5 needed to tally flow equivalence to a full
shift or exact isomorphism to a Cuntz algebra or Cuntz polygon. Typical
sampled graphs are illustrated in Figure 2 and Figure 3.

All collected data were consistent with available theory, as long as the
number of vertices was sufficiently large. In practice, $n=50$ vertices seemed
to be large enough to produce expected results (see Table 7), though most of
the time we opted for $n=100$. Note that, since our sample sizes are very
large, the margin of error for the data is small. Using the normal
approximation to the binomial distribution, at the $99\%$ level of confidence
this margin is at most

$z_{0.005}\left.\sqrt{\frac{x(1-x)}{n}}\right|_{x=1/2}\approx\frac{2.576}{2\sqrt{10^{5}}}\approx
0.004$

for any of our proportions of interest. This means that if our sampling
procedure were to be repeated many times, and $\widehat{\gamma}$ denotes our
empirical estimate of some true probability $\gamma$, then the interval
$[\widehat{\gamma}-0.004,\widehat{\gamma}+0.004]$ should contain $\gamma$
approximately 99% of the time. In practice, the margin of error depends on the
variability of the data characteristic being measured, possibly resulting in a
narrower confidence interval. See, for example, Table 7, and notice also that
the error bars in graphs such as Figure 4 vary from bar to bar.

###  4.1. Bernoulli graphs $\mathbb{D}_{n,q}$

Here, our emphasis was on (3.3) for small primes $p$ and (3.2) for small
$p$-groups $G=\mathbb{Z}/(p^{N}\mathbb{Z})$ and
$G=(\mathbb{Z}/p\mathbb{Z})^{N}$. See Figure 4 and Table 1, respectively.
Conjecture 3.9 and Conjecture 3.11 are supported by the data in Table 2 (see
also Table 3).

As discussed in Remark 3.3, sparser Bernoulli digraphs (those for which
$q=\log n/n$) exhibit rather different statistics. This expectation was
consistent with the data, some of which is presented in Table 4. As for
connectivity, note that if $q=(\log n+\omega)/n$ for some function
$\omega=\omega(n)$, then

$\lim_{n\to\infty}\mathbb{P}\left(\mathbb{D}_{n,q}\text{ is strongly
connected}\right)=\begin{cases}0&\text{ if }\>\omega\to-\infty\\\
e^{-2e^{-c}}&\text{ if }\>\omega\to c\text{ constant}\\\ 1&\text{ if
}\>\omega\to\infty\end{cases}$

(see [18, Theorem 13.9], which is derived from the similar behaviour [18,
Theorem 4.1] exhibited by the symmetric versions $\mathbb{E}_{n,q}$). If $n$
is large enough and $q=\log n/n$ (that is, $\omega=0$), we would expect strong
connectivity about $e^{-2}\approx 13.5\%$ of the time. Our observation of
$15.6\%$ for $n=100$ (see Table 4) is not inconsistent with this.

###  4.2. Erdős–Rényi graphs $\mathbb{E}_{n,q}$

From (3.7) and (3.10), we can compute the asymptotic cyclicity probabilities
for $K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n,q}))_{p}$, for any prime $p$. The
recorded data closely agree with these probabilities (see Figure 5). As
mentioned in Section 3.5, it is expected, though not yet proved, that the
asymptotic probability that $K_{0}(\mathrm{C}^{*}(\mathbb{E}_{n,q}))$ is
cyclic is equal to the product of the respective probabilities over all primes
$p$, that is, to

$\prod_{p\text{ prime}}\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right)\approx
0.79352.$

The data in Table 5 and Table 6 are in accordance with this expectation. Table
6 also contains data for the open Question 3.10 and data in support of
Conjecture 3.11.

###  4.3. Regular multigraphs $\widehat{\mathbb{G}}_{n,r}$

The graph algebras $\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$ are almost
never exactly isomorphic to Cuntz polygons (see Question 3.13 and Table 11).
The asymptotic behaviour of the determinant is also somewhat opaque (see Table
11 again), so we refrain from conjecturing the asymptotic probability of flow
equivalence to a full shift for these graphs, leaving open Question 3.10.

On the other hand, the purely $K$-theoretic data are easier to understand.
With $n=100$, the data collected for
$K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}$ for all primes $p$
between $3$ and $37$ (and also $p=137$ and $p=277$) were remarkably in line
with the limiting distributions (3.7) and (3.8) provided that $p\nmid r-1$.
See, for example, Table 7, Figure 6 and Figure 7.

For $p=2$, the event “$K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{2}$
is cyclic” tended to be concentrated on a single outcome
$K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{2}=\mathbb{Z}/2^{N}\mathbb{Z}$,
with $N=0$ if $2\nmid r-1$. (On the other hand, note that, in general,
$K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}$ cannot be trivial if
$p\mid r-1$.) We did however observe some interesting deviations from this
pattern (see Figure 8 and Figure 9), including variable behaviour for a fixed
value of $r$ and different $n$ (compare Figure 10 with Figure 11).

In Table 8, $\widehat{\gamma}_{n,r}$ and $\widehat{\pi}_{p,r}$ denote our
estimators of the probabilities

$\gamma_{n,r}:=\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))\text{
is cyclic}\right)$

and

$\pi_{p,r}:=\lim_{n\in
2\mathbb{N}}\mathbb{P}\left(K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}\text{
is cyclic}\right).$

While we are somewhat begging the question here, as the definition of
$\pi_{p,r}$ does assume that the limit exists, note that, from Proposition
3.5,

$\pi_{p,r}=\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right)$ (4.1)

if $p\nmid 2(r-1)$. Convergence outside of this setting, that is, for $p=2$ or
$p\mid r-1$, does seem to be supported by the data. In fact, if we rely on the
heuristic principle that $n=100$ is large enough to indicate asymptotic
behaviour, then from Table 8 we see that $\pi_{2,r}$ is consistently about
$0.42$, independently of $r$. As for the provenance of this number, we suspect
it to be (4.1) adjusted to also include the $k=1$ term. Fascinatingly, this
adjustment also appears to govern the asymptotic probability of cyclicity of
$K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}$ for primes $p$
dividing $r-1$ (see Table 9). Arguing heuristically as in the proof of Theorem
3.2.5, we would also expect $\gamma_{n,r}$ to converge as $n\to\infty$ to
$\prod\limits_{p\text{ prime}}\pi_{p,r}=:\gamma_{r}$. This expectation is
indeed supported by the data (see Table 8 and Table 10). Putting this
together, we are led to make the following.

######  Conjecture 4.1.

For an integer $r$ and prime $p$, let $\pi_{p,r}:=\lim\limits_{n\in
2\mathbb{N}}\mathbb{P}\left((K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r}))_{p}\text{
is cyclic}\right)$. Then, for any $r\geq 3$:

  1. 1.

$\pi_{p,r}=\prod\limits_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$ if $p=2$ (in
which case, $\pi_{p,r}\approx 0.419$) or if $p$ is odd and $p\mid r-1$;

  2. 2.

the asymptotic probability that $\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,r})$
is stably isomorphic to a Cuntz algebra is

$\gamma_{r}:=\prod_{p\text{ prime}}\pi_{p,r}=\prod_{\begin{subarray}{c}p\text{
prime}\\\ p\mid 2(r-1)\end{subarray}}\left(1-p^{-1}\right)\prod_{p\text{
prime}}\prod_{k=2}^{\infty}\left(1-p^{-2k+1}\right)\>(\approx 0.397\text{ if
$r=2^{j}+1$}).$ (4.2)

Figure 2. Sample generated graph $\widehat{\mathbb{G}}_{20,3}$ Figure 3. Sample generated graph $\mathbb{D}_{11,1/2}$ Figure 4. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\mathbb{D}_{100,1/4}))_{2}$ $(n,q)$ | $\mathbb{D}_{n,q}$ connected | $K_{1}\neq 0$ |  $(\operatorname{\mathrm{Tor}}(K_{0}))_{p}$ cyclic
---|---|---|---
all $p$ | $p=2$ | $p=3$ | $p=5$ | $p=7$
$(50,1/2)$ | 100000 | 0 | 84881 | 86769 | 98104 | 99788 | 99954
$(100,1/2)$ | 100000 | 0 | 85098 | 86928 | 98086 | 99819 | 99961
$(50,1/3)$ | 100000 | 0 | 84597 | 86598 | 97975 | 99784 | 99950
$(100,1/3)$ | 100000 | 0 | 84727 | 86676 | 98003 | 99801 | 99952
$(50,1/4)$ | 99994 | 0 | 84756 | 86679 | 98057 | 99793 | 99955
$(100,1/4)$ | 100000 | 0 | 84586 | 86570 | 97982 | 99805 | 99958
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $10^{5}\left(\frac{1}{\sqrt{2}}+o(1)\right)^{n}$ | $84694$ | $86636$ | 98022 | 99794 | 99951
Table 1. Selected totals for $10^{5}$ observations of $\mathrm{C}^{*}(\mathbb{D}_{n,1/k})$, $n=50,100$, $k=2,3,4$ $(n,q)$ | Connected | $K_{1}\neq 0$ |  $K_{0}$ cyclic | $\mathrm{Det}<0$ | Full shift | $\mathcal{P}_{\bar{m}}$ | $\mathcal{O}_{m}$
---|---|---|---|---|---|---|---
$(50,1/2)$ | 100000 | 0 | 84377 | 49887 | 42186 | 50880 | 43518
$(100,1/2)$ | 100000 | 0 | 84525 | 49963 | 42190 | 50640 | 43481
$(50,1/3)$ | 100000 | 0 | 84825 | 50036 | 42381 | 50695 | 43503
$(100,1/3)$ | 100000 | 0 | 84736 | 50044 | 42410 | 50736 | 43635
$(50,1/4)$ | 99989 | 1 | 84610 | 49966 | 42225 | 50739 | 43581
$(100,1/4)$ | 100000 | 0 | 84636 | 49831 | 42260 | 50764 | 43582
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $10^{5}\left(\frac{1}{\sqrt{2}}+o(1)\right)^{n}$ | $84694$ | 50000 | 42347 | 51451 | 43576
Table 2. Selected totals for $10^{5}$ observations of $\mathrm{C}^{*}(\mathbb{D}_{n,1/k})$, $n=50,100$, $k=2,3,4$. Numbers marked in purple support Conjecture 3.11 and those marked in teal support Conjecture 3.9. $(n,q)$ | Connected | $K_{1}\neq 0$ |  $K_{0}$ cyclic | $\mathrm{Det}<0$ | Full shift | $\mathcal{P}_{\bar{m}}$ | $\mathcal{O}_{m}$
---|---|---|---|---|---|---|---
$(50,1/2)$ | 100000 | 0 | 84794 | 50112 | 42478 | 50588 | 43616
$(100,1/2)$ | 100000 | 0 | 84524 | 49976 | 42302 | 50429 | 43337
$(50,1/3)$ | 100000 | 0 | 84726 | 49632 | 42065 | 50709 | 43535
$(100,1/3)$ | 100000 | 0 | 84669 | 49989 | 42394 | 50498 | 43421
$(50,1/4)$ | 99992 | 5 | 84631 | 49833 | 42205 | 50742 | 43553
$(100,1/4)$ | 100000 | 0 | 84706 | 50051 | 42377 | 50437 | 43309
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $10^{5}\left(\frac{1}{\sqrt{2}}+o(1)\right)^{n}$ | $84694$ | 50000 | 42347 | 51451 | 43576
Table 3. Selected totals for $10^{5}$ observations of shifted Bernoulli digraph algebras $\mathrm{C}^{*}(\mathbb{D}_{n,1/k}+I)$, $n=50,100$, $k=2,3,4$. Numbers marked in purple are relevant to Conjecture 3.11 and those marked in teal support Theorem 3.8. $q$ ($n=100$) | $\mathbb{D}_{100,q}$ connected | $K_{1}\neq 0$ |  $(\operatorname{\mathrm{Tor}}(\operatorname{\mathrm{coker}}(A^{t}-I)))_{p}$ cyclic∗
---|---|---|---
all $p$ | $p=2$ | $p=3$ | $p=5$ | $p=7$
$3\log n/n$ | 99993 | 3 | 84617 | 86586 | 97990 | 99781 | 99958
$2\log n/n$ | 98606 | 114 | 84880 | 86786 | 98062 | 99805 | 99952
$\log n/n$ | 15623 | 8829 | 85713 | 87481 | 98183 | 99801 | 99941
$\log n/2n$ | 0 | 51702 | 87968 | 89172 | 98776 | 99866 | 99978
Table 4. $10^{5}$ observations of $\mathrm{C}^{*}(\mathbb{D}_{n,k\log n/n})$, $n=100$, $k=3,2,1,0.5$. ∗We may no longer have $K_{0}\cong\operatorname{\mathrm{coker}}(A^{t}-I)$ as sinks now occur with nonzero probability so would have to be taken into account as in [35, Theorem 3.2]. $(n,q)$ | $\mathbb{E}_{n,q}$ connected | $K_{1}\neq 0$ |  $(\operatorname{\mathrm{Tor}}(K_{0}))_{p}$ cyclic
---|---|---|---
all $p$ | $p=2$ | $p=3$ | $p=5$ | $p=7$
$(50,1/2)$ | 100000 | 0 | 79239 | 83805 | 95846 | 99169 | 99696
$(100,1/2)$ | 100000 | 0 | 79325 | 83786 | 95889 | 99125 | 99707
$(50,1/3)$ | 100000 | 0 | 79235 | 83784 | 95854 | 99157 | 99703
$(100,1/3)$ | 100000 | 0 | 79206 | 83797 | 95883 | 99139 | 99694
$(50,1/4)$ | 99997 | 3 | 79306 | 83833 | 95898 | 99150 | 99687
$(100,1/4)$ | 100000 | 0 | 79331 | 83822 | 95839 | 99169 | 99697
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $o(1)$ | 79352 | 83884 | 95851 | 99167 | 99702
Table 5. Selected totals for $10^{5}$ observations of $\mathrm{C}^{*}(\mathbb{E}_{n,1/k})$, $n=50,100$, $k=2,3,4$ $(n,q)$ | Connected | $K_{1}\neq 0$ |  $K_{0}$ cyclic | $\mathrm{Det}<0$ | Full shift | $\mathcal{P}_{\bar{m}}$ | $\mathcal{O}_{m}$
---|---|---|---|---|---|---|---
$(50,1/2)$ | 100000 | 0 | 79379 | 56708 | 45005 | 59431 | 48330
$(75,1/2)$ | 100000 | 0 | 79325 | 50912 | 40336 | 59051 | 48073
$(100,1/2)$ | 100000 | 0 | 79416 | 45762 | 36274 | 59317 | 48281
$(50,1/3)$ | 100000 | 0 | 79286 | 55144 | 43670 | 59335 | 48317
$(75,1/3)$ | 100000 | 0 | 79400 | 45625 | 36269 | 59195 | 48253
$(100,1/3)$ | 100000 | 0 | 79371 | 46400 | 36794 | 59121 | 48224
$(50,1/4)$ | 99999 | 1 | 79526 | 46138 | 36771 | 59643 | 48634
$(75,1/4)$ | 100000 | 0 | 79296 | 47678 | 37797 | 59246 | 48315
$(100,1/4)$ | 100000 | 0 | 79322 | 54237 | 42983 | 59275 | 48218
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $o(1)$ | 79352 | $10^{5}\delta_{n,q}$ | $10^{5}\sigma_{n,q}$ | 60793 | 48240
Table 6. Selected totals for $10^{5}$ observations of $\mathrm{C}^{*}(\mathbb{E}_{n,1/k})$, $n=50,100$, $k=2,3,4$. Numbers marked in purple support Conjecture 3.11. Numbers marked in teal provide empirical data for the open Question 3.10. In particular, using the definitions (3.16), the values $\delta_{n,q}$ and $\sigma_{n,q}$ in the data table obey the relationship $\sigma_{n,q}\approx 0.79352\cdot\delta_{n,q}$, supporting statistical independence of determinant negativity and cyclicity (cf. (3.15)).  Figure 5. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\mathbb{E}_{100,1/2}))_{2}$ $n$ | $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,3}))_{13}$
---|---
$0$ | $\mathbb{Z}/13\mathbb{Z}$ | $\mathbb{Z}/13^{2}\mathbb{Z}$ | $(\mathbb{Z}/13\mathbb{Z})^{2}$ | $\mathbb{Z}/13^{3}\mathbb{Z}$
$n\to\infty$ | 0.92265 | 0.07097 | 0.00546 | 0.00042 | 0.00042
200 | $[0.9223,0.9266]$ | $[0.0672,0.0713]$ | $[0.0048,0.0060]$ | $[0.0002,0.0006]$ | $[0.0002,0.0006]$
100 | $[0.9192,0.9236]$ | $[0.0700,0.0742]$ | $[0.0049,0.0061]$ | $[0.0004,0.0007]$ | $[0.0002,0.0005]$
60 | $[0.9215,0.9258]$ | $[0.0677,0.0718]$ | $[0.0053,0.0066]$ | $[0.0002,0.0005]$ | $[0.0002,0.0005]$
50 | $[0.9225,0.9268]$ | $[0.0672,0.0713]$ | $[0.0048,0.0060]$ | $[0.0003,0.0006]$ | $[0.0001,0.0004]$
20 | $[0.9583,0.9615]$ | $[0.0360,0.0391]$ | $[0.0021,0.0029]$ | $[0.0000,0.0002]$ | $[0.0000,0.0000]$
10 | $[1.0000,1.0000]$ | $[0.0000,0.0000]$ | $[0.0000,0.0000]$ | $[0.0000,0.0000]$ | $[0.0000,0.0000]$
Table 7. $99\%$ CIs for Sylow 13-subgroups of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{n,3}))$, various $n$ Figure 6. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{200,3}))_{5}$ Figure 7. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,11}))_{11}$ Figure 8. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,5}))_{2}$ in support of Conjecture 4.1 Figure 9. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,13}))_{2}$ in support of Conjecture 4.1 Figure 10. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,9}))_{2}$ in support of Conjecture 4.1 Figure 11. Frequency distribution for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{200,9}))_{2}$ $r$ | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 17
---|---|---|---|---|---|---|---|---|---|---
$\widehat{\pi}_{2,r}$ | 0.416 | 0.418 | 0.419 | 0.415 | 0.416 | 0.420 | 0.420 | 0.420 | 0.418 | 0.419
$\prod\limits_{\stackrel{{\scriptstyle p\text{ prime}}}{{p\leq 37}}}\widehat{\pi}_{p,r}$ | 0.264 | 0.395 | 0.317 | 0.262 | 0.338 | 0.396 | 0.265 | 0.318 | 0.359 | 0.397
$\widehat{\gamma}_{100,r}$ | 0.265 | 0.395 | 0.316 | 0.261 | 0.338 | 0.396 | 0.264 | 0.317 | 0.360 | 0.397
Table 8. Cyclicity frequencies for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,r}))$, various $r$. Marked in bold are empirical estimates supporting Conjecture 4.1. $r$ | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 20
---|---|---|---|---|---|---|---|---|---
$p\mid r-1$ | 5 | 3 | 7 | 3 | 5 | 11 | 3 | 13 | 19
$\widehat{\pi}_{p,r}$ | 0.794 | 0.639 | 0.856 | 0.639 | 0.794 | 0.908 | 0.638 | 0.922 | 0.947
$\prod\limits_{k=1}^{\infty}\left(1-p^{-2k+1}\right)$ | 0.793 | 0.639 | 0.855 | 0.639 | 0.793 | 0.908 | 0.639 | 0.923 | 0.947
Table 9. Cyclicity frequencies for $10^{5}$ observations of $K_{0}(\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,r}))_{p}$, $p\mid r-1$. Marked in bold are empirical estimates supporting Conjecture 4.1. $r=2^{j}+1$ | $\widehat{\mathbb{G}}_{100,r}$ connected | $K_{1}\neq 0$ |  $(\operatorname{\mathrm{Tor}}(K_{0}))_{p}$ cyclic
---|---|---|---
all $p$ | $p=2$ | $p=3$ | $p=5$ | $p=7$
$3$ | 99519 | 57 | 38494 | 40599 | 95942 | 99198 | 99686
$5$ | 100000 | 0 | 39460 | 41781 | 95779 | 99152 | 99713
$9$ | 100000 | 0 | 39600 | 41978 | 95679 | 99221 | 99655
$17$ | 100000 | 0 | 39655 | 41903 | 95910 | 99212 | 99676
$33$ | 100000 | 0 | 39879 | 42133 | 95934 | 99121 | 99724
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $o(1)$ | $10^{5}\gamma_{2^{j}+1}$ | $10^{5}\pi_{2,2^{j}+1}$ | 95851 | 99167 | 99702
Table 10. Selected totals for $10^{5}$ observations of $\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,2^{j}+1})$, $1\leq j\leq 5$. Marked in bold are empirical estimates supporting Conjecture 4.1. $r$ | Connected | $K_{1}\neq 0$ |  $K_{0}$ cyclic | $\mathrm{Det}<0$ | Full shift | $\mathcal{P}_{\bar{m}}$ | $\mathcal{O}_{m}$
---|---|---|---|---|---|---|---
$3$ | 99495 | 65 | 38335 | 55987 | 21448 | 0 | 0
$4$ | 99989 | 0 | 26361 | 41056 | 10832 | 0 | 0
$5$ | 100000 | 0 | 39611 | 58341 | 23108 | 0 | 0
$6$ | 100000 | 0 | 31373 | 41669 | 13153 | 0 | 0
$7$ | 100000 | 0 | 26325 | 52379 | 13864 | 0 | 0
$8$ | 100000 | 0 | 34067 | 57153 | 19529 | 0 | 0
$9$ | 100000 | 0 | 39401 | 47150 | 18616 | 0 | 0
$n\to\infty$ | $10^{5}-O\left(\frac{1}{n}\right)$ | $o(1)$ | $10^{5}\cdot\gamma_{r}$ | ${\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}10^{5}\varepsilon_{n,r}}$ | ${\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}10^{5}\tau_{n,r}}$ | 0 | 0
Table 11. Selected totals for $10^{5}$ observations of
$\mathrm{C}^{*}(\widehat{\mathbb{G}}_{100,r})$, various $r$. Numbers in purple
provide empirical data for the open Question 3.13. Numbers marked in teal
provide empirical data for the open Question 3.10. In particular, using the
definitions (3.17), the values $\varepsilon_{n,r}$ and $\tau_{n,r}$ in the
data table obey the relationship
$\tau_{n,r}\approx\gamma_{r}\cdot\varepsilon_{n,r}$, supporting statistical
independence of determinant negativity and cyclicity (cf. (4.2)).

## References

  * [1] S. E. Arklint, S. Eilers, and E. Ruiz.  Geometric classification of isomorphism of unital graph $\mathrm{C}^{*}$-algebras.  New York J. Math., 28:927–957, 2022.
  * [2] S. E. Arklint and E. Ruiz.  Corners of Cuntz-Krieger algebras.  Trans. Amer. Math. Soc., 367(11):7595–7612, 2015.
  * [3] T. Bates, D. Pask, I. Raeburn, and W. Szymański.  The $\mathrm{C}^{*}$-algebras of row-finite graphs.  New York J. Math., 6:307–324 (electronic), 2000.
  * [4] J. Bourgain, V. H. Vu, and P. M. Wood.  On the singularity probability of discrete random matrices.  J. Funct. Anal., 258(2):559–603, 2010.
  * [5] T. M. Carlsen, S. Eilers, E. Ortega, and G. Restorff.  Flow equivalence and orbit equivalence for shifts of finite type and isomorphism of their groupoids.  J. Math. Anal. Appl., 469(2):1088–1110, 2019.
  * [6] G. Cornelissen, O. Lorscheid, and M. Marcolli.  On the $K$-theory of graph $\mathrm{C}^{*}$-algebras.  Acta Appl. Math., 102(1):57–69, 2008.
  * [7] J. Cuntz.  Simple $\mathrm{C}^{*}$-algebras generated by isometries.  Comm. Math. Phys., 57(2):173–185, 1977.
  * [8] J. Cuntz.  $K$-theory for certain $\mathrm{C}^{*}$-algebras.  Ann. of Math. (2), 113(1):181–197, 1981.
  * [9] J. Cuntz and W. Krieger.  A class of $\mathrm{C}^{*}$-algebras and topological Markov chains.  Invent. Math., 56(3):251–268, 1980.
  * [10] W. Deuber and B. Rothschild.  Categories without the Ramsey property.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 of Colloq. Math. Soc. János Bolyai, pages 225–249. North-Holland, Amsterdam-New York, 1978.
  * [11] N. Dunford and J. T. Schwartz.  Linear Operators. I. General Theory. Interscience Publishers, New York-London, 1958.
  * [12] K. Dutta and A. Prasad.  Degenerations and orbits in finite abelian groups.  J. Combin. Theory Ser. A, 118(6):1685–1694, 2011.
  * [13] C. J. Eagle, I. Farah, B. Hart, B. Kadets, V. Kalashnyk, and M. Lupini.  Fraïssé limits of $\mathrm{C}^{*}$-algebras.  J. Symb. Log., 81(2):755–773, 2016. ISBN 0470226056
  * [14] S. Eilers, T. Katsura, M. Tomforde, and J. West.  The ranges of $K$-theoretic invariants for nonsimple graph algebras.  Trans. Amer. Math. Soc., 368(6):3811–3847, 2016.
  * [15] S. Eilers, G. Restorff, E. Ruiz, and A. P. W. Sørensen.  The complete classification of unital graph $\mathrm{C}^{*}$-algebras: geometric and strong.  Duke Math. J., 170(11):2421–2517, 2021.
  * [16] P. Erdős and A. Rényi.  On random graphs. I.  Publ. Math. Debrecen, 6:290–297, 1959.
  * [17] J. Franks.  Flow equivalence of subshifts of finite type.  Ergodic Theory Dynam. Systems, 4(1):53–66, 1984.
  * [18] A. Frieze and M. Karoński.  Introduction to random graphs.  Cambridge University Press, Cambridge, 2016.
  * [19] E. N. Gilbert.  Random graphs.  Ann. Math. Statist., 30:1141–1144, 1959.
  * [20] B. Jacelon.  Random amenable $\mathrm{C}^{*}$-algebras.  Math. Proc. Cambridge Philos. Soc., 175(2):345–366, 2023.
  * [21] B. Jacelon and A. Vignati.  Stably projectionless Fraïssé limits.  Studia Math., 267(2):161–199, 2022.
  * [22] A. S. Kechris, V. G. Pestov, and S. Todorcevic.  Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups.  Geom. Funct. Anal., 15(1):106–189, 2005.
  * [23] E. Kirchberg and N. C. Phillips.  Embedding of exact $\mathrm{C}^{*}$-algebras in the Cuntz algebra $\mathcal{O}_{2}$.  J. Reine Angew. Math., 525:17–53, 2000.
  * [24] Z. Kostana.  Cohen-like first order structures.  Ann. Pure Appl. Logic, 174(1):Paper No. 103172, 2023.
  * [25] D. Lind and B. Marcus.  An introduction to symbolic dynamics and coding.  Cambridge University Press, Cambridge, 1995.
  * [26] K. Maples.  Singularity of random matrices over finite fields.  arXiv:1012.2372 [math.CO], 2013.
  * [27] S. Masumoto.  The Jiang-Su algebra as a Fraïssé limit.  J. Symb. Log., 82(4):1541–1559, 2017.
  * [28] H. H. Nguyen and E. Paquette.  Surjectivity of near-square random matrices.  Combin. Probab. Comput., 29(2):267–292, 2020.
  * [29] H. H. Nguyen and M. M. Wood.  Cokernels of adjacency matrices of random $r$-regular graphs.  arXiv:1806.10068 [math.PR], 2018.
  * [30] H. H. Nguyen and M. M. Wood.  Random integral matrices: universality of surjectivity and the cokernel.  Invent. Math., 228(1):1–76, 2022.
  * [31] OpenAI.  ChatGPT [Large language model], June 2023.  https://chat.openai.com/chat
  * [32] The PARI Group.  PARI/GP version 2.13.4, Univ. Bordeaux, 2022.  Available from http://pari.math.u-bordeaux.fr/.
  * [33] N. C. Phillips.  A classification theorem for nuclear purely infinite simple $\mathrm{C}^{*}$-algebras.  Doc. Math., 5:49–114 (electronic), 2000.
  * [34] I. Raeburn.  Graph algebras, volume 103 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2005.
  * [35] I. Raeburn and W. Szymański.  Cuntz-Krieger algebras of infinite graphs and matrices.  Trans. Amer. Math. Soc., 356(1):39–59, 2004.
  * [36] M. Rørdam.  Classification of Cuntz-Krieger algebras.  $K$-Theory, 9(1):31–58, 1995.
  * [37] M. Rørdam and E. Størmer.  Classification of nuclear $\mathrm{C}^{*}$-algebras. Entropy in operator algebras, volume 126 of Encyclopaedia of Mathematical Sciences.  Springer-Verlag, Berlin, 2002.  Operator Algebras and Non-commutative Geometry, 7.
  * [38] M. Schwachhöfer and M. Stroppel.  Finding representatives for the orbits under the automorphism group of a bounded abelian group.  J. Algebra, 211(1):225–239, 1999.
  * [39] A. P. W. Sørensen.  Geometric classification of simple graph algebras.  Ergodic Theory Dynam. Systems, 33(4):1199–1220, 2013.
  * [40] W. Szymański.  The range of $K$-invariants for $\mathrm{C}^{*}$-algebras of infinite graphs.  Indiana Univ. Math. J., 51(1):239–249, 2002.
  * [41] F. Trèves.  Topological vector spaces, distributions and kernels. Academic Press, New York-London, 1967.
  * [42] M. M. Wood.  The distribution of sandpile groups of random graphs.  J. Amer. Math. Soc., 30(4):915–958, 2017.
  * [43] M. M. Wood.  Random integral matrices and the Cohen-Lenstra heuristics.  Amer. J. Math., 141(2):383–398, 2019.
  * [44] M. M. Wood.  Probability theory for random groups arising in number theory.  arXiv:2301.09687 [math.NT], 2023.