A graphon approach to limiting spectral distributions of Wigner‐type matrices

We present a new approach, based on graphon theory, to finding the limiting spectral distributions of general Wigner‐type matrices. This approach determines the moments of the limiting measures and the equations of their Stieltjes transforms explicitly with weaker assumptions on the convergence of variance profiles than previous results. As applications, we give a new proof of the semicircle law for generalized Wigner matrices and determine the limiting spectral distributions for three sparse inhomogeneous random graph models with sparsity ω(1/n): inhomogeneous random graphs with roughly equal expected degrees, W‐random graphs and stochastic block models with a growing number of blocks. Furthermore, we show our theorems can be applied to random Gram matrices with a variance profile for which we can find the limiting spectral distributions under weaker assumptions than previous results.     

Equality of Lifshitz and van Hove exponents on amenable Cayley graphs

We study the low energy asymptotics of periodic and random Laplace operators on Cayley graphs of amenable, finitely generated groups. For the periodic operator the asymptotics is characterised by the van Hove exponent or zeroth Novikov–Shubin invariant. The random model we consider is given in terms of an adjacency Laplacian on site or edge percolation subgraphs of the Cayley graph. The asymptotic behaviour of the spectral distribution is exponential, characterised by the Lifshitz exponent. We show that for the adjacency Laplacian the two invariants/exponents coincide. The result holds also for more general symmetric transition operators. For combinatorial Laplacians one has a different universal behaviour of the low energy asymptotics of the spectral distribution function, which can be actually established on quasi-transitive graphs without an amenability assumption. The latter result holds also for long range bond percolation models.     

Equivalent Conditions of Asymptotics for the Density of the Supremum of a Random Walk in the Intermediate Case

This paper obtains some equivalent conditions about the asymptotics for the density of the supremum of a random walk with light-tailed increments in the intermediate case. To do this, the paper first corrects the proofs of some existing results about densities of random sums. On the basis of the above results, the paper obtains some equivalent conditions about the asymptotics for densities of ruin distributions in the intermediate case and densities of infinitely divisible distributions. In the above studies, some differences and relations between the results on a distribution and its corresponding density can be discovered.      

Sparse graphs: Metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with n vertices and Θ(n) edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function κ: [0, 1]² → [0, ∞). To understand these models, we should like to know when different kernels κ give rise to “similar” graphs, and, given a real‐world network, how “similar” is it to a typical graph G(n, κ) derived from a given kernel κ. The analogous questions for dense graphs, with Θ(n²) edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in [0, 1]. Possible generalizations of these results to graphs with o(n²) but ω(n) edges are discussed in a companion article [Bollobás and Riordan, London Math Soc Lecture Note Series 365 (2009), 211–287]; here we focus only on graphs with Θ(n) edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models and vice versa. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1‐38, 2011     

Komlós's tiling theorem via graphon covers

Komlós [Komlós: Tiling Turán Theorems, Combinatorica, 2000] determined the asymptotically optimal minimum-degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H, thus essentially extending the Hajnal–Szemerédi theorem that deals with the case when H is a clique. We give a proof of a graphon version of Komlós's theorem. To prove this graphon version, and also to deduce from it the original statement about finite graphs, we use the machinery introduced in [Hladký, Hu, Piguet: Tilings in graphons, arXiv:1606.03113]. We further prove a stability version of Komlós's theorem.     

Tails for (max, plus) recursions under subexponentiality

We study the stationary solution of a (max, plus)-linear recursion. Under subexponentiality assumptions on the input to the recursion, we obtain the tail asymptotics of certain (max, plus)-linear functionals of this solution. (Max, plus)-linear recursions arise from FIFO queueing networks; more specifically, from stochastic event graphs. In the event graph setting, two special cases of our results are of particular interest and have already been investigated in the literature. First, the functional may correspond to the end-to-end sojourn time of a customer. Second, for two queues in tandem, the functional may correspond to the sojourn time in the second queue. Our results allow for more general networks, which we illustrate by studying the tail asymptotics of the resequencing delay due to multi-path routing.     

The good, the bad, and the great: Homomorphisms and cores of random graphs

We consider homomorphism properties of a random graph G(n,p), where p is a function of n. A core H is great if for all e∈E(H), there is some homomorphism from H−e to H that is not onto. Great cores arise in the study of uniquely H-colourable graphs, where two inequivalent definitions arise for general cores H. For a large range of p, we prove that with probability tending to 1 as n→∞, G∈G(n,p) is a core that is not great. Further, we give a construction of infinitely many non-great cores where the two definitions of uniquely H-colourable coincide.     

Growth of preferential attachment random graphs via continuous-time branching processes

Some growth asymptotics of a version of ‘preferential attachment’ random graphs are studied through an embedding into a continuous-time branching scheme. These results complement and extend previous work in the literature.     

Homomorphism bounds for oriented planar graphs

If is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a homomorphism bound for if there is a homomorphism from each graph in to H. We find some necessary conditions for a graph to be a homomorphism bound for the class of oriented planar graphs and prove that such a graph must have maximum degree at least 16; thus there exists an oriented planar graph with oriented chromatic number at least 17. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 175–190, 2007     

Enumeration of labeled outerplanar bicyclic and tricyclic graphs

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.     

Mapping Planar Graphs into Projective Cubes

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism.     

Random graphons and a weak Positivstellensatz for graphs

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Graph structural properties of non-Yutsis graphs allowing fast recognition

Yutsis graphs are connected simple graphs which can be partitioned into two vertex-induced trees. Cubic Yutsis graphs were introduced by Jaeger as cubic dual Hamiltonian graphs, and these are our main focus.Cubic Yutsis graphs also appear in the context of the quantum theory of angular momenta, where they are used to generate summation formulae for general recoupling coefficients. Large Yutsis graphs are of interest for benchmarking algorithms which generate these formulae.In an earlier paper we showed that the decision problem of whether a given cubic graph is Yutsis is NP-complete. We also described a heuristic that was tested on graphs with up to 300,000 vertices and found Yutsis decompositions for all large Yutsis graphs very quickly.In contrast, no fast technique was known by which a significant fraction of bridgeless non-Yutsis cubic graphs could be shown to be non-Yutsis. One of the contributions of this article is to describe some structural impediments to Yutsisness. We also provide experimental evidence that almost all non-Yutsis cubic graphs can be rapidly shown to be non-Yutsis by applying a heuristic based on some of these criteria. Combined with the algorithm described in the earlier paper this gives an algorithm that, according to experimental evidence, runs efficiently on practically every large random cubic graph and can decide on whether the graph is Yutsis or not.The second contribution of this article is a set of construction techniques for non-Yutsis graphs implying, for example, the existence of 3-connected non-Yutsis cubic graphs of arbitrary girth and with few non-trivial 3-cuts.     

Geometry of the vacant set left by random walk on random graphs,Wright's constants,and critical random graphs with prescribed degrees

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by ?erný and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs.     

Minimum congestion spanning trees in bipartite and random graphs

The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n 3 2 , where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n 3 2 .     

Precise asymptotics for random matrices and random growth models

The author considers the largest eigenvaiues of random matrices from Gaussian unitary ensemble and Laguerre unitary ensemble, and the rightmost charge in certain random growth models. We obtain some precise asymptotics results, which are in a sense similar to the precise asymptotics for sums of independent random variables in the context of the law of large numbers and complete convergence. Our proofs depend heavily upon the upper and lower tail estimates for random matrices and random growth models. The Tracy-Widom distribution plays a central role as well.     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs

In this article, we introduce and study the properties of some target graphs for 2‐edge‐colored homomorphism. Using these properties, we obtain in particular that the 2‐edge‐colored chromatic number of the class of triangle‐free planar graphs is at most 50. We also show that it is at least 12.     

A Semiparametric Two-Sample Hypothesis Testing Problem for Random Graphs

Two-sample hypothesis testing for random graphs arises naturally in neuroscience, social networks, and machine learning. In this article, we consider a semiparametric problem of two-sample hypothesis testing for a class of latent position random graphs. We formulate a notion of consistency in this context and propose a valid test for the hypothesis that two finite-dimensional random dot product graphs on a common vertex set have the same generating latent positions or have generating latent positions that are scaled or diagonal transformations of one another. Our test statistic is a function of a spectral decomposition of the adjacency matrix for each graph and our test procedure is consistent across a broad range of alternatives. We apply our test procedure to real biological data: in a test-retest dataset of neural connectome graphs, we are able to distinguish between scans from different subjects; and in the C. elegans connectome, we are able to distinguish between chemical and electrical networks. The latter example is a concrete demonstration that our test can have power even for small-sample sizes. We conclude by discussing the relationship between our test procedure and generalized likelihood ratio tests. Supplementary materials for this article are available online.