Threshold functions for small subgraphs in simple graphs and multigraphs

We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce the notion of patchworks to describe the possible overlappings of copies of subgraphs. Furthermore, the proofs are based on analytic combinatorics to carry out asymptotic computations. The flexibility of our approach allows us to tackle a wide range of problems. We obtain the asymptotic number and the limiting distribution of the number of subgraphs which are isomorphic to a graph from a given set of graphs. The results apply to multigraphs as well as to (multi)graphs with degree constraints. One application is to scale-free multigraphs, where the degree distribution follows a power law, for which we show how to obtain the asymptotic number of copies of a given subgraph and give as an illustration the expected number of small cycles.     

On the degrees of vertices in A bichromatic random graph

The asymptotic probability distribution of the number of vertices of a given degree in a random bichromatic graph is presented.     

Asymptotic normality in random graphs with given vertex degrees

We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph.     

On a 2-parameter class of scale free random graphs

A process of evolving random graphs is considered where vertices are added to the graph one by one, and edges connecting the new vertex to the old ones are drawn independently, each with probability depending linearly on the degree of the endpoint. In the paper the asymptotic degree distribution and the order of the maxdegree are determined.     

Random graphs with given vertex degrees and switchings

Random graphs with a given degree sequence are often constructed using the configuration model, which yields a random multigraph. We may adjust this multigraph by a sequence of switchings, eventually yielding a simple graph. We show that, assuming essentially a bounded second moment of the degree distribution, this construction with the simplest types of switchings yields a simple random graph with an almost uniform distribution, in the sense that the total variation distance is o(1). This construction can be used to transfer results on distributional convergence from the configuration model multigraph to the uniform random simple graph with the given vertex degrees. As examples, we give a few applications to asymptotic normality. We show also a weaker result yielding contiguity when the maximum degree is too large for the main theorem to hold.     

Further results on random cubic planar graphs

We provide precise asymptotic estimates for the number of several classes of labeled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky and coworkers. We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.     

Weights and Degrees in a Random Graph Model Based on 3-Interactions

In a random graph model introduced in [1] we give the joint asymptotic distribution of weights and degrees and prove scale-free property for the model. Moreover, we determine the asymptotics of the maximal weight and the maximal degree.     

Conditions for graphs to be path partition optimal

The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.     

Complete entrainment of Kuramoto oscillators with inertia on networks via gradient-like flow

We study the asymptotic complete entrainment of Kuramoto oscillators with inertia on symmetric and connected network. We provide several sufficient conditions for the asymptotic complete entrainment in terms of initial phase-frequency configurations, strengths of inertia and coupling, and natural frequency distributions. For this purpose, we reinterpret the Kuramoto oscillators with inertia as a second-order gradient-like flow, and adopt analytical methods based on several Lyapunov functions to apply the convergence estimate studied by Haraux and Jendoubi [21]. Our approach does not require any spectral information of the graph associated with the given network structure.     

Asymptotic spectral analysis of growing regular graphs

We propose the quantum probabilistic techniques to obtain the asymptotic spectral distribution of the adjacency matrix of a growing regular graph. We prove the quantum central limit theorem for the adjacency matrix of a growing regular graph in the vacuum and deformed vacuum states. The condition for the growth is described in terms of simple statistics arising from the stratification of the graph. The asymptotic spectral distribution of the adjacency matrix is obtained from the classical reduction.

     

Continuous spin models on annealed generalized random graphs

We study Gibbs distributions of spins taking values in a general compact Polish space, interacting via a pair potential along the edges of a generalized random graph with a given asymptotic weight distribution $P$, obtained by annealing over the random graph distribution.First we prove a variational formula for the corresponding annealed pressure and provide criteria for absence of phase transitions in the general case.We furthermore study classes of models with second order phase transitions which include rotation-invariant models on spheres and models on intervals, and classify their critical exponents. We find critical exponents which are modified relative to the corresponding mean-field values when $P$ becomes too heavy-tailed, in which case they move continuously with the tail-exponent of $P$. For large classes of models they are the same as for the Ising model treated in Dommers et al. (2016). On the other hand, we provide conditions under which the model is in a different universality class, and construct an explicit example of such a model on the interval.     

Minimisers of the Allen–Cahn equation on hyperbolic graphs

We investigate minimal solutions of the Allen–Cahn equation on a Gromov-hyperbolic graph. Under some natural conditions on the graph, we show the existence of non-constant uniformly-bounded minimal solutions with prescribed asymptotic behaviours. For a phase field model on a hyperbolic graph, such solutions describe energy-minimising steady-state phase transitions that converge towards prescribed phases given by the asymptotic directions on the graph.     

A random tree model associated with random graphs

Grow a tree on n vertices by starting with no edges and successively adding an edge chosen uniformly from the set of possible edges whose addition would not create a cycle. This process is closely related to the classical random graph process. We describe the asymptotic structure of the tree, as seen locally from a given vertex. In particular, we give an explicit expression for the asymptotic degree distribution. Our results an be applied to study the random minimum-weight spanning tree question, when the edge-weight distribution is allowed to vary almost arbitrarily with n.     

A Normal Law for Matchings

Dedicated to the memory of Paul Erdős, both for his pioneering discovery of normality in unexpected places, and for his questions, some of which led (eventually) to the present work.   For a simple graph G, let be the size of a matching drawn uniformly at random from the set of all matchings of G. Motivated by work of C. Godsil [11], we give, for a sequence and , several necessary and sufficient conditions for asymptotic normality of the distribution of , for instance

Quasi-maximum likelihood estimation in GARCH processes when some coefficients are equal to zero

The asymptotic distribution of the quasi-maximum likelihood (QML) estimator is established for generalized autoregressive conditional heteroskedastic (GARCH) processes, when the true parameter may have zero coefficients. This asymptotic distribution is the projection of a normal vector distribution onto a convex cone. The results are derived under mild conditions. For an important subclass of models, no moment condition is imposed on the GARCH process. The main practical implication of these results concerns the estimation of overidentified GARCH models.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Connectivity of a general class of inhomogeneous random digraphs

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.     

Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon

We give asymptotics for the cumulative distribution function (CDF) for degrees of large dense random graphs sampled from a graphon. The proof is based on precise asymptotics for binomial random variables. This result is a first step for giving a nonparametric test for identifying the degree function of a large random graph. Replacing the indicator function in the empirical CDF by a smoother function, we get general asymptotic results for functionals of homomorphism densities for partially labeled graphs. This general setting allows to recover recent results on asymptotics for homomorphism densities of sampled graphon.     

A Note on the Vertex Degree Distribution of Random Intersection Graphs

We establish the asymptotic degree distribution of the typical vertex of inhomogeneous and passive random intersection graphs under minimal moment conditions.

     

Measurement Error Models with Nonconstant Covariance Matrices

In this paper we consider measurement error models when the observed random vectors are independent and have mean vector and covariance matrix changing with each observation. The asymptotic behavior of the sample mean vector and the sample covariance matrix are studied for such models. Using the derived results, we study the case of the elliptical multiplicative error-in-variables models, providing formal justification for the asymptotic distribution of consistent slope parameter estimators. The model considered extends a normal model previously considered in the literature. Asymptotic relative efficiencies comparing several estimators are also reported.