Limit behaviors of random connected graphs driven by a Poisson process

We consider a class of random connected graphs with random vertices and random edges with the random distribution of vertices given by a Poisson point process with the intensity n localized at the vertices and the random distribution of the edges given by a connection function. Using the Avram-Bertsimas method constructed in 1992 for the central limit theorem on Euclidean functionals, we find the convergence rate of the central limit theorem process, the moderate deviation, and an upper bound for large deviations depending on the total length of all edges of the random connected graph.     

Tree components in random distance graphs of special form

In this work, we consider the problem of distribution of the number of tree components with given number of vertices k(k ?? 2) for a certain series of random distance graphs. Generalizations of the classical Erd?s?CRényi results are obtained in the case of geometric graphs of special form.     

顶点着色随机图边数的中偏差

本文讨论了对顶点按照一定比列着色的随机图,利用泰勒展式和斯特灵公式,得到了随机图边数的中偏差和重对数律.     

Large and moderate deviation principles for susceptible-infected-removed epidemic in a random environment

We are concerned with SIR epidemics in a random environment on complete graphs, where edges are assigned with i.i.d. weights. Our main results give large and moderate deviation principles of sample paths of this model. Our results generalize large and moderate deviation principles of the classic SIR models given by E. Pardoux and B. Samegni-Kepgnou [J. Appl. Probab., 2017, 54: 905-920] and X. F. Xue [Stochastic Process. Appl., 2019, 140: 49-80].     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

Large deviations for functionals of spatial point processes with applications to random packing and spatial graphs

Functionals of spatial point process often satisfy a weak spatial dependence condition known as stabilization. We prove general Donsker–Varadhan large deviation principles (LDP) for such functionals and show that the general result can be applied to prove LDPs for various particular functionals, including those concerned with random packing, nearest neighbor graphs, and lattice versions of the Voronoi and sphere of influence graphs.     

The Poisson aggregation process

In this paper we introduce and analyze the Poisson Aggregation Process (PAP): a stochastic model in which a random collection of random balls is stacked over a general metric space. The scattering of the balls’ centers follows a general Poisson process over the metric space, and the balls’ radii are independent and identically distributed random variables governed by a general distribution. For each point of the metric space, the PAP counts the number of balls that are stacked over it. The PAP model is a highly versatile spatial counterpart of the temporal M/G/∞ model in queueing theory. The surface of the moon, scarred by circular meteor-impact craters, exemplifies the PAP model in two dimensions: the PAP counts the number of meteor-impacts that any given moon-surface point sustained. A comprehensive analysis of the PAP is presented, and the closed-form results established include: general statistics, stationary statistics, short-range and long-range dependencies, a Central Limit Theorem, an Extreme Limit Theorem, and fractality.     

Large and Moderate Deviations of Random Upper Semicontinuous Functions

We firstly discuss the topological properties of the space of upper semicontinuous functions, and then we obtain large deviation principles for random upper semicontinuous functions under various topologies. Finally, we prove moderate deviation principles for random sets and random upper semicontinuous functions.     

Cramér-type moderate deviations for stationary sequences of bounded random variables

We derive Cramér-type moderate deviations for stationary sequences of bounded random variables. Our results imply the moderate deviation principles and a Berry–Esseen bound. Applications to quantile coupling inequalities, functions of ?-mixing sequences, and contracting Markov chains are discussed.     

The Road to Deterministic Matrices with the Restricted Isometry Property

The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.     

Space graphs and sphericity

For a finite point set in Euclidean n-space, if we connect each pair of points by a line segment whenever the distance between them is less than a certain positive constant, we obtain a space graph in n-space. The sphericity of a graph G is defined to be the minimum number n such that G is isomorphic to a space graph in n-space. In this paper we study the sphericities of graphs and present upper bounds on the sphericity for several types of graphs.     

Quasi‐random hypergraphs revisited

The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given (k ‐ 1) ‐graph on the same vertex set) as well as the k ‐deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of (l,s) ‐discrepancy for k ‐graphs and prove that the equivalence of the (k,s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Asymptotic analysis of the optimal cost in some transportation problems with random locations

In this paper we provide an asymptotic analysis of the optimal transport cost in some matching problems with random locations. More precisely, under various assumptions on the distribution of the locations and the cost function, we prove almost sure convergence, and large and moderate deviation principles. In general, the rate functions are given in terms of infinite-dimensional variational problems. For a suitable one-dimensional transportation problem, we provide the expression of the large deviation rate function in terms of a one-dimensional optimization problem, which allows the numerical estimation of the rate function. Finally, for certain one-dimensional transportation problems, we prove a central limit theorem.     

Low-lying zeros of number field L-functions

TextOne of the most important statistics in studying the zeros of L-functions is the 1-level density, which measures the concentration of zeros near the central point. Fouvry and Iwaniec (2003) [FI] proved that the 1-level density for L-functions attached to imaginary quadratic fields agrees with results predicted by random matrix theory. In this paper, we show a similar agreement with random matrix theory occurring in more general sequences of number fields. We first show that the main term agrees with random matrix theory, and similar to all other families studied to date, is independent of the arithmetic of the fields. We then derive the first lower order term of the 1-level density, and see the arithmetic enter.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=zpb-gu3G8i0.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.     

Efficient algorithms for finding critical subgraphs

This paper presents algorithms to find vertex-critical and edge-critical subgraphs in a given graph G, and demonstrates how these critical subgraphs can be used to determine the chromatic number of G. Computational experiments are reported on random and DIMACS benchmark graphs to compare the proposed algorithms, as well as to find lower bounds on the chromatic number of these graphs. We improve the best known lower bound for some of these graphs, and we are even able to determine the chromatic number of some graphs for which only bounds were known.     

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.     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.