共查询到20条相似文献，搜索用时 125 毫秒
1.
Let 𝔏(n, q) be the game in which two players, Maker and Breaker, alternately claim 1 and q edges of the complete graph Kn, respectively. Maker's goal is to maximize the number of vertices in the largest component of his graph; Breaker tries to make it as small as possible. Let L(n,q) denote the size of the largest component in Maker's graph when both players follow their optimal strategies. We study the behavior of L(n, q) for large n and q=q(n). In particular, we show that the value of L(n, q) abruptly changes for q∼n and discuss the differences between this phenomenon and a similar one, which occurs in the evolution of random graphs. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 141–152, 2001 相似文献
2.
We study a random graph model which is a superposition of bond percolation on Zd with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < pc, where pc = pc(d) is the critical probability for the bond percolation on Zd. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010 相似文献
3.
For 0 < p < 1 and q > 0 let Gq(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that Gq(n,p)=G is proportional to . The first systematic study of Gq(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of Gq(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 相似文献
4.
Mihyun Kang Michael Moßhammer Philipp Sprüssel 《Random Structures and Algorithms》2020,56(4):1117-1170
Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces. 相似文献
5.
We study the number of n‐vertex graphs that can be written as the edge‐union of k‐vertex cliques. We obtain reasonably tight estimates for in the cases (i) k = n ? o(n) and (ii) k = o(n) but . We also show that exhibits a phase transition around . We leave open several potentially interesting cases, and raise some other questions of a similar nature. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 87–107, 2006 相似文献
6.
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 相似文献
7.
Sergey Dovgal;Élie de Panafieu;Dimbinaina Ralaivaosaona;Vonjy Rasendrahasina;Stephan Wagner; 《Random Structures and Algorithms》2024,64(2):170-266
It is known that random directed graphs D(n,p)$$ Dleft(n,pright) $$ undergo a phase transition around the point p=1/n$$ p=1/n $$. Earlier, Łuczak and Seierstad have established that as n→∞$$ nto infty $$ when p=(1+μn−1/3)/n$$ p=left(1+mu {n}^{-1/3}right)/n $$, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as goes from to . By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of and provide more statistical insights into the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter , we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations when the number of vertices is finite, and we provide tables of numerical values for the integrals of Airy functions that appear in this study. 相似文献
8.
The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around begin{align*}p=frac{1}{n}end{align*} – for any ε > 0 and begin{align*}p=frac{1-epsilon}{n}end{align*}, all connected components of G(n,p) are typically of size Oε(log n), while for begin{align*}p=frac{1+epsilon}{n}end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime begin{align*}p=frac{1+epsilon}{n}end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 相似文献
9.
We introduce a model of a preferential attachment based random graph which extends the family of models in which condensation phenomena can occur. Each vertex has an associated uniform random variable which we call its location. Our model evolves in discrete time by selecting r vertices from the graph with replacement, with probabilities proportional to their degrees plus a constant α. A new vertex joins the network and attaches to one of these vertices according to a given probability associated to the ranking of their locations. We give conditions for the occurrence of condensation, showing the existence of phase transitions in α below which condensation occurs. The condensation in our model differs from that in preferential attachment models with fitness in that the condensation can occur at a random location, that it can be due to a persistent hub, and that there can be more than one point of condensation. 相似文献
10.
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 相似文献
11.
We consider a model for gene regulatory networks that is a modification of Kauffmann's J Theor Biol 22 (1969), 437–467 random Boolean networks. There are three parameters: $n = {rm the}$ number of nodes, $r = {rm the}$ number of inputs to each node, and $p = {rm the}$ expected fraction of 1'sin the Boolean functions at each node. Following a standard practice in thephysics literature, we use a threshold contact process on a random graph on n nodes, in which each node has in degree r, to approximate its dynamics. We show that if $rge 3$ and $r cdot 2p(1-p)>1$ , then the threshold contact process persists for a long time, which correspond to chaotic behavior of the Boolean network. Unfortunately, we are only able to prove the persistence time is $ge exp(cn^{b(p)})$ with $b(p)>0$ when $rcdot 2p(1-p)> 1$ , and $b(p)=1$ when $(r-1)cdot 2p(1-p)>1$ . © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
12.
Ariane Carrance 《Random Structures and Algorithms》2019,55(3):615-648
We present here random distributions on (D + 1)‐edge‐colored, bipartite graphs with a fixed number of vertices 2p. These graphs encode D‐dimensional orientable colored complexes. We investigate the behavior of those graphs as p→∞. The techniques involved in this study also yield a Central Limit Theorem for the genus of a uniform map of order p, as p→∞. 相似文献
13.
It is shown explicitly how self-similar graphs can be obtained as `blow-up' constructions of finite cell graphs . This yields a larger family of graphs than the graphs obtained by discretising continuous self-similar fractals.
For a class of symmetrically self-similar graphs we study the simple random walk on a cell graph , starting at a vertex of the boundary of . It is proved that the expected number of returns to before hitting another vertex in the boundary coincides with the resistance scaling factor.
Using techniques from complex rational iteration and singularity analysis for Green functions, we compute the asymptotic behaviour of the -step transition probabilities of the simple random walk on the whole graph. The results of Grabner and Woess for the Sierpinski graph are generalised to the class of symmetrically self-similar graphs, and at the same time the error term of the asymptotic expression is improved. Finally, we present a criterion for the occurrence of oscillating phenomena of the -step transition probabilities.
14.
《Random Structures and Algorithms》2018,52(2):197-218
We study a random system of cn linear equations over n variables in GF(2), where each equation contains exactly r variables; this is equivalent to r‐XORSAT. Previous work has established a clustering threshold, for this model: if for any constant then with high probability all solutions form a well‐connected cluster; whereas if , then with high probability the solutions partition into well‐connected, well‐separated clusters (with probability tending to 1 as ). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly nonrigorous techniques from statistical physics. We extend that study to the range , and prove that the connectivity parameters of the r‐XORSAT clusters undergo a smooth transition around the clustering threshold. 相似文献
15.
Martin Hildebrand 《Random Structures and Algorithms》1996,8(4):301-318
This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc. 相似文献
16.
Gabriel Istrate 《Random Structures and Algorithms》2002,20(4):483-506
Let c > 0 be a constant, and Φ be a random Horn formula with n variables and m = c · 2n clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing PUR, a natural implementation of positive unit resolution, we show that limn→∞ Pr(Φ is satisfiable) = 1 ? F(e?c), where F(x) = (1 ? x)(1 ? x2)(1 ? x4)(1 ? x8) …. Our method also yields as a byproduct an average‐case analysis of this algorithm. Published 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 483–506, 2002 相似文献
17.
We study the threshold for the existence of a spanning maximal planar subgraph in the random graph Gn, p . We show that it is very near p = 1/n? We also discuss the threshold for the existence of a spanning maximal outerplanar subgraph. This is very near p = 1/n½. 相似文献
18.
Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6]. 相似文献
19.
Recently, in [Random Struct Algorithm 41 (2012), 441–450] we adapted exploration and martingale arguments of Nachmias and Peres [ALEA Lat Am J Probab Math Stat 3 (2007), 133–142], in turn based on ideas of Martin‐Löf [J Appl Probab 23 (1986), 265–282], Karp [Random Struct Alg 1 (1990), 73–93] and Aldous [Ann Probab 25 (1997), 812–854], to prove asymptotic normality of the number L1 of vertices in the largest component of the random r‐uniform hypergraph in the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of L1, and joint asymptotic normality of L1 and the number M1 of edges of in the sparsely supercritical case. These results are used in [Combin Probab Comput 25 (2016), 21–75], where we enumerate sparsely connected hypergraphs asymptotically. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 325–352, 2017 相似文献
20.
Thomas S. Salisbury 《Random Structures and Algorithms》2014,45(1):111-137
We consider connectivity properties of certain i.i.d. random environments on , where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the (random) set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two‐dimensional models that are non‐monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111–137, 2014 相似文献