An official website of the United States government
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
Counting extensions revisited
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
- PAR ID:
- 10445399
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 61
- Issue:
- 1
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 3-30
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We prove that the number of edges of a multigraph with vertices is at most , provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi, and Leighton, if has edges, in any drawing of with the above property, the number of crossings is . This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.more » « less
-
Abstract A well‐known result of Ajtai Komlós, Pintz, Spencer, and Szemerédi (J. Combin. Theory Ser. A32(1982), 321–335) states that every ‐graph on vertices, with girth at least five, and average degree contains an independent set of size for some . In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3, and 4. Our work is motivated by a problem of Lo and Zhao, who asked for , how large of an independent set a ‐graph on vertices necessarily has when its maximum ‐degree . (The corresponding problem with respect to ‐degrees was solved by Kostochka, Mubayi, and Verstraëte (Random Struct. & Algorithms44(2014), 224–239).) In this paper we show that every ‐graph on vertices with contains an independent set of size , and under additional conditions, an independent set of size . The former assertion gives a new upper bound for the ‐degree Turán density of complete ‐graphs.more » « less
-
Abstract Let be a finite, connected graph. We consider a greedy selection of vertices: given a list of vertices , take to be any vertex maximizing the sum of distances to the vertices already chosen and iterate, keep adding the “most remote” vertex. The frequency with which the vertices of the graph appear in this sequence converges to a set of probability measures with nice properties. The support of these measures is, generically, given by a rather small number of vertices . We prove that this suggests that the graphGis, in a suitable sense, “m‐dimensional” by exhibiting an explicit 1‐Lipschitz embedding with good properties.more » « less
-
Abstract Theq-color Ramsey number of ak-uniform hypergraphG, denotedr(G; q), is the minimum integerNsuch that any coloring of the edges of the completek-uniform hypergraph onNvertices contains a monochromatic copy ofG. The study of these numbers is one of the most central topics in combinatorics. One natural question, which for triangles goes back to the work of Schur in 1916, is to determine the behavior ofr(G; q) for fixedGandqtending to infinity. In this paper, we study this problem for 3-uniform hypergraphs and determine the tower height ofr(G; q) as a function ofq. More precisely, given a hypergraphG, we determine whenr(G; q) behaves polynomially, exponentially or double exponentially inq. This answers a question of Axenovich, Gyárfás, Liu and Mubayi.more » « less
