An official website of the United States government
Abstract We consider rooted subgraphs in random graphs, that is, extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. In 1989, Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices. For the important strictly balanced case, Spencer also raised the fundamental question as to whether these conditions are necessary. We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open.
more »
« less
A functional central limit theorem for SI processes on configuration model graphs
Abstract We study a stochastic compartmental susceptible–infected (SI) epidemic process on a configuration model random graph with a given degree distribution over a finite time interval. We split the population of graph vertices into two compartments, namely, S and I, denoting susceptible and infected vertices, respectively. In addition to the sizes of these two compartments, we keep track of the counts of SI-edges (those connecting a susceptible and an infected vertex) and SS-edges (those connecting two susceptible vertices). We describe the dynamical process in terms of these counts and present a functional central limit theorem (FCLT) for them as the number of vertices in the random graph grows to infinity. The FCLT asserts that the counts, when appropriately scaled, converge weakly to a continuous Gaussian vector semimartingale process in the space of vector-valued càdlàg functions endowed with the Skorokhod topology. We discuss applications of the FCLT in percolation theory and in modelling the spread of computer viruses. We also provide simulation results illustrating the FCLT for some common degree distributions.
more »
« less
- Award ID(s):
- 1853587
- PAR ID:
- 10471782
- Publisher / Repository:
- Applied Probability Trust
- Date Published:
- Journal Name:
- Advances in Applied Probability
- Volume:
- 54
- Issue:
- 3
- ISSN:
- 0001-8678
- Page Range / eLocation ID:
- 880 to 912
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Linear structural equation models relate the components of a random vector using linear interdependencies and Gaussian noise. Each such model can be naturally associated with a mixed graph whose vertices correspond to the components of the random vector. The graph contains directed edges that represent the linear relationships between components, and bidirected edges that encode unobserved confounding. We study the problem of generic identifiability, that is, whether a generic choice of linear and confounding effects can be uniquely recovered from the joint covariance matrix of the observed random vector. An existing combinatorial criterion for establishing generic identifiability is the half-trek criterion (HTC), which uses the existence of trek systems in the mixed graph to iteratively discover generically invertible linear equation systems in polynomial time. By focusing on edges one at a time, we establish new sufficient and new necessary conditions for generic identifiability of edge effects extending those of the HTC. In particular, we show how edge coefficients can be recovered as quotients of subdeterminants of the covariance matrix, which constitutes a determinantal generalization of formulas obtained when using instrumental variables for identification. While our results do not completely close the gap between existing sufficient and necessary conditions we find, empirically, that our results allow us to prove the generic identifiability of many more mixed graphs than the prior state-of-the-art.more » « less
-
null (Ed.)Recently Cutler and Radcliffe proved that the graph on $$n$$ vertices with maximum degree at most $$r$$ having the most cliques is a disjoint union of $$\lfloor n/(r+1)\rfloor$$ cliques of size $r+1$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $$m$$ edges and maximum degree at most $$r$$, the graph that has the most cliques of size at least two is the disjoint union of $$\bigl\lfloor m \bigm/\binom{r+1}{2} \bigr\rfloor$$ cliques of size $r+1$ together with the colex graph using the remainder of the edges.more » « less
-
Abstract In this note we examine the following random graph model: for an arbitrary graph , with quadratic many edges, construct a graph by randomly adding edges to and randomly coloring the edges of with colors. We show that for a large enough constant and , every pair of vertices in are joined by a rainbow path, that is, israinbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for and resolved the case when and is a function of .more » « less
-
Abstract In the anisotropic random geometric graph model, vertices correspond to points drawn from a high‐dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to hypothesis test between such a graph and an Erdős‐Rényi graph with the same edge probability. If is the number of vertices and is the vector of eigenvalues, Eldan and Mikulincer, Geo. Aspects Func. Analysis: Israel seminar, 2017 shows that detection is possible when and impossible when . We show detection is impossible when , closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer, Geo. Aspects Func. Analysis: Israel seminar, 2017.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/apr.2022.52
