共查询到20条相似文献,搜索用时 46 毫秒
1.
The Erd?s‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erd?s and Rényi states that the Erd?s‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erd?s and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erd?s‐Rényi process. The Bohman‐Frieze process also begins with an empty graph on n vertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erd?s‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time tc ? ? (that is, when the number of edges are (tc ? ?)n/2) are trees or unicyclic components and that the largest component is of size Ω(?‐2log n). Further, at tc + ?, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(?‐2log n). Each of these results corresponds to an analogous well‐known result for the Erd?s‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 相似文献
2.
The standard Erdős-Rényi model of random graphs begins with n isolated vertices, and at each round a random edge is added. Parametrizing n/2 rounds as one time unit, a phase transition occurs at time t = 1 when a giant component (one of size constant times n) first appears. Under the influence of statistical mechanics, the investigation of related phase transitions has become an
important topic in random graph theory.
We define a broad class of graph evolutions in which at each round one chooses one of two random edges {v
1, v
2}, {v
3, v
4} to add to the graph. The selection is made by examining the sizes of the components of the four vertices. We consider the
susceptibility S(t) at time t, being the expected component size of a uniformly chosen vertex. The expected change in S(t) is found which produces in the limit a differential equation for S(t). There is a critical time t
c
so that S(t) → ∞ as t approaches t
c
from below. We show that the discrete random process asymptotically follows the differential equation for all subcritical
t < t
c
. Employing classic results of Cramér on branching processes we show that the component sizes of the graph in the subcritical
regime have an exponential tail. In particular, the largest component is only logarithmic in size. In the supercritical regime
t > t
c
we show the existence of a giant component, so that t = t
c
may be fairly considered a phase transition.
Computer aided solutions to the possible differential equations for susceptibility allow us to establish lower and upper bounds
on the extent to which we can either delay or accelerate the birth of the giant component.
Research supported by the Australian Research Council, the Canada Research Chairs Program and NSERC. Research partly carried
out while the author was at the Department of Mathematics and Statistics, University of Melbourne. 相似文献
3.
be a random Qn”-process, that is let Q0 be the empty spanning subgraph of the cube Qn and, for 1 ? t ? M = nN/2 = n2n?1, let the graph Qt be obtained from Qt?1 by the random addition of an edge of Qn not present in Qt?1. When t is about N/2, a typical Qt undergoes a certain “phase transition'': the component structure changes in a sudden and surprising way. Let t = (1 + ?) N/2 where ? is independent of n. Then all the components of a typical Qt have o(N) vertices if ? < 0, while if ? > 0 then, as proved by Ajtai, Komlós, and Szemerédi, a typical Qt has a “giant” component with at least α(?)N vertices, where α(?) > 0. In this note we give essentially best possible results concerning the emergence of this giant component close to the time of phase transition. Our results imply that if η > 0 is fixed and t ? (1 ? n?η) N/2, then all components of a typical Qt have at most nβ(η) vertices, where β(η) > 0. More importantly, if 60(log n)3/n ? ? = ?n = o(1), then the largest component of a typical Qt has about 2?N vertices, while the second largest component has order O(n??2). Loosely put, the evolution of a typical Qn process is such that shortly after time N/2 the appearance of each new edge results in the giant component acquiring 4 new vertices. 相似文献
4.
We analyze the large deviation properties for the (multitype) version of percolation on the complete graph – the simplest substitutive generalization of the Erd&0151;s‐Rènyi random graph that was treated in article by Bollobás et al. (Random Structures Algorithms 31 (2007), 3–122). Here the vertices of the graph are divided into a fixed finite number of sets (called layers) the probability of {u,v} being in our edge set depends on the respective layers of u and v. We determine the exponential rate function for the probability that a giant component occupies a fixed fraction of the graph, while all other components are small. We also determine the exponential rate function for the probability that a particular exploration process on the random graph will discover a certain fraction of vertices in each layer, without encountering a giant component.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 460–492, 2012 相似文献
5.
A subset S of vertices of a graph G is called cyclable in G if there is in G some cycle containing all the vertices of S. We denote by α(S, G) the number of vertices of a maximum independent set of G[S]. We prove that if G is a 3‐connected graph or order n and if S is a subset of vertices such that the degree sum of any four independent vertices of S is at least n + 2α(S, G) −2, then S is cyclable. This result implies several known results on cyclability or Hamiltonicity. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 191–203, 2000 相似文献
6.
We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs Gn,p (above the connectivity threshold) and for random regular graphs Gr,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t* all components are of size O(log n). For Gn,p and Gr we give the value of t*, and the size of Γ(t). For Gr, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs Dn,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 相似文献
7.
The percolation phase transition and the mechanism of the emergence of the giant component through the critical scaling window for random graph models, has been a topic of great interest in many different communities ranging from statistical physics, combinatorics, computer science, social networks and probability theory. The last few years have witnessed an explosion of models which couple random aggregation rules, that specify how one adds edges to existing configurations, and choice, wherein one selects from a “limited” set of edges at random to use in the configuration. While an intense study of such models has ensued, understanding the actual emergence of the giant component and merging dynamics in the critical scaling window has remained impenetrable to a rigorous analysis. In this work we take an important step in the analysis of such models by studying one of the standard examples of such processes, namely the Bohman‐Frieze model, and provide first results on the asymptotic dynamics, through the critical scaling window, that lead to the emergence of the giant component for such models. We identify the scaling window and show that through this window, the component sizes properly rescaled converge to the standard multiplicative coalescent. Proofs hinge on a careful analysis of certain infinite‐type branching processes with types taking values in the space of cadlag paths, and stochastic analytic techniques to estimate susceptibility functions of the components all the way through the scaling window where these functions explode. Previous approaches for analyzing random graphs at criticality have relied largely on classical breadth‐first search techniques that exploit asymptotic connections with Brownian excursions. For dynamic random graph models evolving via general Markovian rules, such approaches fail and we develop a quite different set of tools that can potentially be used for the study of critical dynamics for all bounded size rules. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 55–116, 2015 相似文献
8.
The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models. One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007 相似文献
9.
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γt(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γt(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γt(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009 相似文献
10.
Jill R. Faudree Ralph J. Faudree Ronald J. Gould Michael S. Jacobson Linda Lesniak 《Journal of Graph Theory》2000,35(2):69-82
Ng and Schultz [J Graph Theory 1 ( 6 ), 45–57] introduced the idea of cycle orderability. For a positive integer k, a graph G is k‐ordered if for every ordered sequence of k vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a Hamiltonian cycle, then G is said to be k‐ordered Hamiltonian. We give sum of degree conditions for nonadjacent vertices and neighborhood union conditions that imply a graph is k‐ordered Hamiltonian. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 69–82, 2000 相似文献
11.
Louigi Addario‐Berry Shankar Bhamidi Sanchayan Sen 《Random Structures and Algorithms》2021,58(1):34-67
We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erd?s‐Rényi process. We show tightness of the fixation time in the “Brownian” regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes ?uczak's result for the Erd?s‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes. 相似文献
12.
We show that almost surely the rank of the adjacency matrix of the Erd?s‐Rényi random graph G(n,p) equals the number of nonisolated vertices for any c ln n/n ≤ p ≤ 1/2, where c is an arbitrary positive constant larger than 1/2. In particular, the adjacency matrix of the giant component (a.s.) has full rank in this range. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
13.
Shankar Bhamidi Amarjit Budhiraja Xuan Wang 《Probability Theory and Related Fields》2014,160(3-4):733-796
Random graph models with limited choice have been studied extensively with the goal of understanding the mechanism of the emergence of the giant component. One of the standard models are the Achlioptas random graph processes on a fixed set of \(n\) vertices. Here at each step, one chooses two edges uniformly at random and then decides which one to add to the existing configuration according to some criterion. An important class of such rules are the bounded-size rules where for a fixed \(K\ge 1\) , all components of size greater than \(K\) are treated equally. While a great deal of work has gone into analyzing the subcritical and supercritical regimes, the nature of the critical scaling window, the size and complexity (deviation from trees) of the components in the critical regime and nature of the merging dynamics has not been well understood. In this work we study such questions for general bounded-size rules. Our first main contribution is the construction of an extension of Aldous’s standard multiplicative coalescent process which describes the asymptotic evolution of the vector of sizes and surplus of all components. We show that this process, referred to as the standard augmented multiplicative coalescent (AMC) is ‘nearly’ Feller with a suitable topology on the state space. Our second main result proves the convergence of suitably scaled component size and surplus vector, for any bounded-size rule, to the standard AMC. This result is new even for the classical Erd?s–Rényi setting. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from Bhamidi et al. (The barely subcritical regime. Arxiv preprint, 2012) on the size of the largest component in the barely subcritical regime. 相似文献
14.
An n‐state deterministic finite automaton over a k‐letter alphabet can be seen as a digraph with n vertices which all have k labeled out‐arcs. Grusho (Publ Math Inst Hungarian Acad Sci 5 (1960), 17–61). proved that whp in a random k‐out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of tree‐like structures, and present a new proof of Grusho's theorem. Among other things, we pinpoint the phase transition for strong connectivity. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 428–458, 2017 相似文献
15.
Ralph J. Faudree 《Journal of Graph Theory》1992,16(4):327-334
Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph Kk+1. It is shown that if G is a graph on n vertices with n ≥ k2(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph Kk such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of Kk is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc. 相似文献
16.
We prove that a graph G of order n has a hamiltonian prism if and only if the graph Cl4n/3–4/3(G) has a hamiltonian prism where Cl4n/3–4/3(G) is the graph obtained from G by sequential adding edges between non‐adjacent vertices whose degree sum is at least 4n/3–4/3. We show that this cannot be improved to less than 4n/3–5. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 209–220, 2007 相似文献
17.
Derényi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph Ggenerated by some rule, form an auxiliary graph G′ whose vertices are the k‐cliques of G, in which two vertices are joined if the corresponding cliques share k – 1 vertices. They considered in particular the case where G = G(n,p), and found heuristically the threshold function p = p(n) above which a giant component appears in G′. Here we give a rigorous proof of this result, as well as many extensions. The model turns out to be very interesting due to the essential global dependence present in G′. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
18.
Tamás Makai 《Journal of Graph Theory》2015,79(2):125-144
Consider the random graph process that starts from the complete graph on n vertices. In every step, the process selects an edge uniformly at random from the set of edges that are in a copy of a fixed graph H and removes it from the graph. The process stops when no more copies of H exist. When H is a strictly 2‐balanced graph we give the exact asymptotics on the number of edges remaining in the graph when the process terminates and investigate some basic properties namely the size of the maximal independent set and the presence of subgraphs. 相似文献
19.
《Random Structures and Algorithms》2018,53(2):238-288
The phase transition in the size of the giant component in random graphs is one of the most well‐studied phenomena in random graph theory. For hypergraphs, there are many possible generalizations of the notion of a connected component. We consider the following: two j‐sets (sets of j vertices) are j‐connected if there is a walk of edges between them such that two consecutive edges intersect in at least j vertices. A hypergraph is j‐connected if all j‐sets are pairwise j‐connected. In this paper, we determine the asymptotic size of the unique giant j‐connected component in random k‐uniform hypergraphs for any and . 相似文献
20.
Odile Favaron Michael A. Henning Christina M. Mynhart Joël Puech 《Journal of Graph Theory》2000,34(1):9-19
A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γt(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γt(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000 相似文献