Spectral Statistics of Erdős-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues

We consider the ensemble of adjacency matrices of Erd?s-Rényi random graphs, i.e. graphs on N vertices where every edge is chosen independently and with probability p ≡ p(N). We rescale the matrix so that its bulk eigenvalues are of order one. Under the assumption \({p N \gg N^{2/3}}\), we prove the universality of eigenvalue distributions both in the bulk and at the edge of the spectrum. More precisely, we prove (1) that the eigenvalue spacing of the Erd?s-Rényi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble; and (2) that the second largest eigenvalue of the Erd?s-Rényi graph has the same distribution as the largest eigenvalue of the Gaussian orthogonal ensemble. As an application of our method, we prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have at least 4 + ε moments.     

Evolution of a Modified Binomial Random Graph by Agglomeration

In the classical Erd?s–Rényi random graph G(n, p) there are n vertices and each of the possible edges is independently present with probability p. The random graph G(n, p) is homogeneous in the sense that all vertices have the same characteristics. On the other hand, numerous real-world networks are inhomogeneous in this respect. Such an inhomogeneity of vertices may influence the connection probability between pairs of vertices. The purpose of this paper is to propose a new inhomogeneous random graph model which is obtained in a constructive way from the Erd?s-Rényi random graph G(n, p). Given a configuration of n vertices arranged in N subsets of vertices (we call each subset a super-vertex), we define a random graph with N super-vertices by letting two super-vertices be connected if and only if there is at least one edge between them in G(n, p). Our main result concerns the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. Even though our model begins with G(n, p), it assumes the existence of some community structure encoded in the configuration. Furthermore, under certain conditions it exhibits a power law degree distribution. Both properties are important for real-world applications.     

1 / <Emphasis Type="Italic">n</Emphasis> Expansion for the Number of Matchings on Regular Graphs and Monomer-Dimer Entropy

Using a 1 / n expansion, that is an expansion in descending powers of n, for the number of matchings in regular graphs with 2n vertices, we study the monomer-dimer entropy for two classes of graphs. We study the difference between the extensive monomer-dimer entropy of a random r-regular graph G (bipartite or not) with 2n vertices and the average extensive entropy of r-regular graphs with 2n vertices, in the limit \(n \rightarrow \infty \). We find a series expansion for it in the numbers of cycles; with probability 1 it converges for dimer density \(p < 1\) and, for G bipartite, it diverges as \(|\mathrm{ln}(1-p)|\) for \(p \rightarrow 1\). In the case of regular lattices, we similarly expand the difference between the specific monomer-dimer entropy on a lattice and the one on the Bethe lattice; we write down its Taylor expansion in powers of p through the order 10, expressed in terms of the number of totally reducible walks which are not tree-like. We prove through order 6 that its expansion coefficients in powers of p are non-negative.     

Almost One Bit Violation for the Additivity of the Minimum Output Entropy

In a previous paper, we proved that, in the appropriate asymptotic regime, the limit of the collection of possible eigenvalues of output states of a random quantum channel is a deterministic, compact set K_k,t. We also showed that the set K_k,t is obtained, up to an intersection, as the unit ball of the dual of a free compression norm. In this paper, we identify the maximum of \({\ell^p}\) norms on the set K_k,t and prove that the maximum is attained on a vector of shape (a, b, . . . , b) where a > b. In particular, we compute the precise limit value of the minimum output entropy of a single random quantum channel. As a corollary, we show that for any \({\varepsilon > 0}\), it is possible to obtain a violation for the additivity of the minimum output entropy for an output dimension as low as 183, and that for appropriate choice of parameters, the violation can be as large as \({\log 2 -\varepsilon}\). Conversely, our result implies that, with probability one in the limit, one does not obtain a violation of additivity using conjugate random quantum channels and the Bell state, in dimension 182 and less.     

Equidistribution of Zeros of Holomorphic Sections in the Non-compact Setting

We consider tensor powers L ^N of a positive Hermitian line bundle (L,h ^L ) over a non-compact complex manifold X. In the compact case, B. Shiffman and S. Zelditch proved that the zeros of random sections become asymptotically uniformly distributed as N→∞ with respect to the natural measure coming from the curvature of L. Under certain boundedness assumptions on the curvature of the canonical line bundle of X and on the Chern form of L we prove a non-compact version of this result. We give various applications, including the limiting distribution of zeros of cusp forms with respect to the principal congruence subgroups of SL ₂(?) and to the hyperbolic measure, the higher dimensional case of arithmetic quotients and the case of orthogonal polynomials with weights at infinity. We also give estimates for the speed of convergence of the currents of integration on the zero-divisors.     

Statistical mechanics of rotating systems

A microcanonical distribution function depending on the total energyE and thez-componentM of the total angular momentum of a rotating system is examined. ForM=0 the generalized microcanonical ensemble is found to give the same entropy as the usual microcanonical ensemble. The moment of inertia of a rotating gas is calculated, and the kinetic energy of rotation is given as a power series in the small parameterM ²/2I ₀E_int, whereI ₀ is the moment of inertia of the gas at rest andE _int the internal energy.     

Large Communities in a Scale-Free Network

We prove the existence of a large complete subgraph w.h.p. in a preferential attachment random graph process with an edge-step. That is, we consider a dynamic stochastic process for constructing a graph in which at each step we independently decide, with probability \(p\in (0,1)\), whether the graph receives a new vertex or a new edge between existing vertices. The connections are then made according to a preferential attachment rule. We prove that the random graph \(G_{t}\) produced by this so-called generalized linear preferential (GLP) model at time t contains a complete subgraph whose vertex set cardinality is given by \(t^\alpha \), where \(\alpha = (1-\varepsilon )\frac{1-p}{2-p}\), for any small \(\varepsilon >0\) asymptotically almost surely.     

Angular Momentum-Free of the Entropy Relations for Rotating Kaluza-Klein Black Holes

Based on a mathematical lemma related to the Vandermonde determinant and two theorems derived from the first law of black hole thermodynamics, we investigate the angular momentum independence of the entropy sum as well as the entropy product of general rotating Kaluza-Klein black holes in higher dimensions. We show that for both non-charged rotating Kaluza-Klein black holes and non-charged rotating Kaluza-Klein-AdS black holes, the angular momentum of the black holes will not be present in entropy sum relation in dimensions d≥4, while the independence of angular momentum of the entropy product holds provided that the black holes possess at least one zero rotation parameter a _j = 0 in higher dimensions d≥5, which means that the cosmological constant does not affect the angular momentum-free property of entropy sum and entropy product under the circumstances that charge δ=0. For the reason that the entropy relations of charged rotating Kaluza-Klein black holes as well as the non-charged rotating Kaluza-Klein black holes in asymptotically flat spacetime act the same way, it is found that the charge has no effect in the angular momentum-independence of entropy sum and product in asymptotically flat spactime.     

Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution

Even though power-law or close-to-power-law degree distributions are ubiquitously observed in a great variety of large real networks, the mathematically satisfactory treatment of random power-law graphs satisfying basic statistical requirements of realism is still lacking. These requirements are: sparsity, exchangeability, projectivity, and unbiasedness. The last requirement states that entropy of the graph ensemble must be maximized under the degree distribution constraints. Here we prove that the hypersoft configuration model, belonging to the class of random graphs with latent hyperparameters, also known as inhomogeneous random graphs or W-random graphs, is an ensemble of random power-law graphs that are sparse, unbiased, and either exchangeable or projective. The proof of their unbiasedness relies on generalized graphons, and on mapping the problem of maximization of the normalized Gibbs entropy of a random graph ensemble, to the graphon entropy maximization problem, showing that the two entropies converge to each other in the large-graph limit.     

Random time averaged diffusivities for Lévy walks

We investigate a Lévy walk alternating between velocities ±v ₀ with opposite sign. The sojourn time probability distribution at large times is a power law lacking its mean or second moment. The first case corresponds to a ballistic regime where the ensemble averaged mean squared displacement (MSD) at large times is ?x ²? ∝ t ², the latter to enhanced diffusion with ?x ²? ∝ t ^ν, 1 < ν < 2. The correlation function and the time averaged MSD are calculated. In the ballistic case, the deviations of the time averaged MSD from a purely ballistic behavior are shown to be distributed according to a Mittag-Leffler density function. In the enhanced diffusion regime, the fluctuations of the time averages MSD vanish at large times, yet very slowly. In both cases we quantify the discrepancy between the time averaged and ensemble averaged MSDs.     

The Condensation Phase Transition in Random Graph Coloring

Based on a non-rigorous formalism called the “cavity method”, physicists have put forward intriguing predictions on phase transitions in diluted mean-field models, in which the geometry of interactions is induced by a sparse random graph or hypergraph. One example of such a model is the graph coloring problem on the Erd?s–Renyi random graph G(n, d/n), which can be viewed as the zero temperature case of the Potts antiferromagnet. The cavity method predicts that in addition to the k-colorability phase transition studied intensively in combinatorics, there exists a second phase transition called the condensation phase transition (Krzakala et al. in Proc Natl Acad Sci 104:10318–10323, 2007). In fact, there is a conjecture as to the precise location of this phase transition in terms of a certain distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k₀.     

Thermodynamics and relativistic kinetic theory for <Emphasis Type="Italic">q</Emphasis>-generalized Bose–Einstein and Fermi–Dirac systems

The thermodynamics and covariant kinetic theory are elaborately investigated in a non-extensive environment considering the non-extensive generalization of Bose–Einstein (BE) and Fermi–Dirac (FD) statistics. Starting with Tsallis’ entropy formula, the fundamental principles of thermostatistics are established for a grand canonical system having q-generalized BE/FD degrees of freedom. Many particle kinetic theory is set up in terms of the relativistic transport equation with q-generalized Uehling–Uhlenbeck collision term. The conservation laws are realized in terms of appropriate moments of the transport equation. The thermodynamic quantities are obtained in a weak non-extensive environment for a massive pion–nucleon and a massless quark–gluon system with non-zero baryon chemical potential. In order to get an estimate of the impact of non-extensivity on the system dynamics, the q-modified Debye mass and hence the q-modified effective coupling are estimated for a quark–gluon system.     

Models of random graph hierarchies

We introduce two models of inclusion hierarchies: random graph hierarchy (RGH) and limited random graph hierarchy (LRGH). In both models a set of nodes at a given hierarchy level is connected randomly, as in the Erd?s-Rényi random graph, with a fixed average degree equal to a system parameter c. Clusters of the resulting network are treated as nodes at the next hierarchy level and they are connected again at this level and so on, until the process cannot continue. In the RGH model we use all clusters, including those of size 1, when building the next hierarchy level, while in the LRGH model clusters of size 1 stop participating in further steps. We find that in both models the number of nodes at a given hierarchy level h decreases approximately exponentially with h. The height of the hierarchy H, i.e. the number of all hierarchy levels, increases logarithmically with the system size N, i.e. with the number of nodes at the first level. The height H decreases monotonically with the connectivity parameter c in the RGH model and it reaches a maximum for a certain c _max in the LRGH model. The distribution of separate cluster sizes in the LRGH model is a power law with an exponent about ? 1.25. The above results follow from approximate analytical calculations and have been confirmed by numerical simulations.     

Ground State Energy of the One-Dimensional Discrete Random Schrödinger Operator with Bernoulli Potential

In this paper we show the that the ground state energy of the one-dimensional discrete random Schrödinger operator with Bernoulli potential is controlled asymptotically as the system size N goes to infinity by the random variable ? _N , the length the longest consecutive sequence of sites on the lattice with potential equal to zero. Specifically, we will show that for almost every realization of the potential the ground state energy behaves asymptotically as \({\frac{\pi^{2}}{(\ell_{N} +1)^{2}}} \) in the sense that the ratio of the quantities goes to one.     

Optimal Segmentation of Directed Graph and the Minimum Number of Feedback Arcs

The minimum feedback arc set problem asks to delete a minimum number of arcs (directed edges) from a digraph (directed graph) to make it free of any directed cycles. In this work we approach this fundamental cycle-constrained optimization problem by considering a generalized task of dividing the digraph into D layers of equal size. We solve the D-segmentation problem by the replica-symmetric mean field theory and belief-propagation heuristic algorithms. The minimum feedback arc density of a given random digraph ensemble is then obtained by extrapolating the theoretical results to the limit of large D. A divide-and-conquer algorithm (nested-BPR) is devised to solve the minimum feedback arc set problem with very good performance and high efficiency.     

An Inverse Problem in Quantum Statistical Physics

We address the following inverse problem in quantum statistical physics: does the quantum free energy (von Neumann entropy + kinetic energy) admit a unique minimizer among the density operators having a given local density n(x)? We give a positive answer to that question, in dimension one. This enables to define rigourously the notion of local quantum equilibrium, or quantum Maxwellian, which is at the basis of recently derived quantum hydrodynamic models and quantum drift-diffusion models. We also characterize this unique minimizer, which takes the form of a global thermodynamic equilibrium (canonical ensemble) with a quantum chemical potential.     

Scattering of Josephson plasmons on random quantum jumpers in a disordered <Emphasis Type="Italic">I</Emphasis>-layer of an <Emphasis Type="Italic">S</Emphasis>–<Emphasis Type="Italic">I</Emphasis>–<Emphasis Type="Italic">S</Emphasis> junction

A formula for the relaxation time of Josephson plasmons on random quantum jumpers, i.e., quantum resonant-percolation trajectories (QRPT) in a disordered I-layer of a tunnel S–I–S junction is derived. Domain Ω_r (μ ? E₀, c), in which the strongest plasmon damping takes place, is plotted in the plane of parameters (μ ? E₀, c).     

$${\mathcal{N}=2}$$ Superconformal Algebra and the Entropy of Calabi–Yau Manifolds

We use the representation theory of \({\mathcal{N}=2}\) superconformal algebra to study the elliptic genera of Calabi–Yau (CY) D-folds. We compute the entropy of CY manifolds from the growth rate of multiplicities of the massive (non-BPS) representations in the decomposition of their elliptic genera. We find that the entropy of CY manifolds of complex dimension D behaves differently depending on whether D is even or odd. When D is odd, CY entropy coincides with the entropy of the corresponding hyperKähler (D ? 3)-folds due to a structural theorem on Jacobi forms. In particular, we find that the Calabi–Yau 3-fold has a vanishing entropy. At D > 3, using our previous results on hyperKähler manifolds, we find \({S_{CY_D}\sim 2\pi \sqrt{\frac{(D-3)^2}{2(D-1)}n}}\). When D is even, we find the behavior of CY entropy behaving as \({S_{CY_D}\sim 2 \pi\sqrt{\frac{D-1}{2}n}}\). These agree with Cardy’s formula at large D.     

Analyses of multiplicity distributions with <Emphasis Type="Italic">η</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript> and Bose–Einstein correlations at LHC by means of generalized Glauber–Lachs formula

Using the negative binomial distribution (NBD) and the generalized Glauber–Lachs (GGL) formula, we analyze the data on charged multiplicity distributions with pseudo-rapidity cutoffs η _c at 0.9, 2.36, and 7 TeV by ALICE Collaboration and at 0.2, 0.54, and 0.9 TeV by UA5 Collaboration. We confirm that the KNO scaling holds among the multiplicity distributions with η _c =0.5 at \(\sqrt{s} = 0.2\)–2.36 TeV and estimate the energy dependence of a parameter 1/k in NBD and parameters 1/k and γ (the ratio of the average value of the coherent hadrons to that of the chaotic hadrons) in the GGL formula. Using empirical formulas for the parameters 1/k and γ in the GGL formula, we predict the multiplicity distributions with η _c =0.5 at 7 and 14 TeV. Data on the second order Bose–Einstein correlations (BEC) at 0.9 TeV by ALICE Collaboration and 0.9 and 2.36 TeV by CMS Collaboration are also analyzed based on the GGL formula. Prediction for the third order BEC at 0.9 and 2.36 TeV are presented. Moreover, the information entropy is discussed.