  We discuss numerically the non-perturbative effects in exponential random
graphs which are analogue of eigenvalue instantons in matrix models. The phase
structure of exponential random graphs with chemical potential for 4-cycles and
degree preserving constraint is clarified. The first order phase transition at
critical value of chemical potential for 4-cycles into bipartite phase with a
formation of fixed number of bipartite clusters is found for ensemble of random
regular graphs (RRG). We consider the similar phase transition in combinatorial
quantum gravity based of the Ollivier graph curvature for RRG supplemented with
hard-core constraint and show that a order of a phase transition and the
structure of emerging phase depend on a vertex degree d in RRG. For d = 3 the
bipartite closed ribbon emerges at bipartite phase while for d > 3 the ensemble
of isolated or weakly interacting hypercubes supplemented with the bipartite
closed ribbon gets emerged at the first order phase transition with a clear-cut
hysteresis. If the additional connectedness condition is imposed the bipartite
phase gets identified as the closed chain of weakly coupled hypercubes. Since
the ground state of isolated hypercube is the thermofield double (TFD) we
suggest that the dual holographic picture involves multiboundary wormholes.
Treating RRG as a model of a Hilbert space for a interacting many-body system
we discuss the patterns of the Hilbert space fragmentation at the phase
transition. We also briefly comment on a possible relation of the found phase
transition to the problem of holographic interpretation of a partial
deconfinement transition in the gauge theories.
