共查询到20条相似文献,搜索用时 15 毫秒
1.
Benedikt Stufler 《Random Structures and Algorithms》2019,55(2):496-528
We show that the uniform unlabeled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov‐Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This confirms a conjecture by Aldous (1991). We also establish Benjamini‐Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees. 相似文献
2.
Let 𝒯n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of 𝒯n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ μkn and variance ∼ σn with positive constants μk and σk. Besides, the asymptotic behavior of μk and σk for k → ∞ as well as the corresponding multivariate distributions are derived. Furthermore, similar results can be proved for plane trees, for labeled trees, and for forests. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 227–253, 1999 相似文献
3.
David Zuckerman 《Journal of Theoretical Probability》1989,2(1):147-157
The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)(1) andO(|V| |E|/d
min)(2) imply an upper bound ofO(n
2). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log2
n). The previous lower bound was (|V| log |V|) for trees.(2) In our main result, we show a lower bound of (|V| (log
d
max |V|)2) for trees, which yields a lower bound of (n log2
n). We also extend our techniques to show an upper bound for general graphs ofO(max{E
Ti} log |V|). 相似文献
4.
In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows: let
G(n; {p
k
}) be the probability space of all the labelled loopless multigraphs with vertex set V = {υ
1, υ
2, …, υ
n
}, in which the distribution of tvi ,vj t_{v_i ,v_j } , the number of the edges between any two vertices υ
i
and υ
j
is
P{ tvi ,vj = k} = pk ,k = 0,1,2,...P\{ t_{v_i ,v_j } = k\} = p_k ,k = 0,1,2,... 相似文献
5.
In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear. 相似文献
6.
It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
7.
We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If Hn is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, Hn∼(12/π2)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998 相似文献
8.
Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and c′ depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012 相似文献
9.
Svante Janson 《Random Structures and Algorithms》2003,22(4):337-358
Asymptotics are obtained for the mean, variance, and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a critical Galton–Watson tree). We also establish a joint asymptotic distribution of the Wiener index and the internal path length, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion. The methods include both Aldous' theory of the continuum random tree and analysis of generating functions. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 337–358, 2003 相似文献
10.
We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least , the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in , and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017 相似文献
11.
Yuri Bakhtin 《Random Structures and Algorithms》2010,37(3):312-331
We consider Gibbs distributions on finite random plane trees with bounded branching. We show that as the order of the tree grows to infinity, the distribution of any finite neighborhood of the root of the tree converges to a limit. We compute the limiting distribution explicitly and study its properties. We introduce an infinite random tree consistent with these limiting distributions and show that it satisfies a certain form of the Markov property. We also study the growth of this tree and prove several limit theorems including a diffusion approximation. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 相似文献
12.
Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree may be described by the number of nodes or the number of leaves in layer , respectively. It is shown that these two processes converge weakly to Brownian excursion local time. This is done via characteristic functions obtained by means of generating functions arising from the combinatorial setup and complex contour integration. Besides, an integral representation for the two-dimensional density of Brownian excursion local time is derived. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 421–451, 1997 相似文献
13.
Luc Devroye 《Random Structures and Algorithms》1991,2(3):303-315
Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (Ln), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply. 相似文献
14.
《Random Structures and Algorithms》2018,52(4):560-575
For , let Tn be a random recursive tree (RRT) on the vertex set . Let be the degree of vertex v in Tn, that is, the number of children of v in Tn. Devroye and Lu showed that the maximum degree Δn of Tn satisfies almost surely; Goh and Schmutz showed distributional convergence of along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in Tn. For any , let . Also, let be a Poisson point process on with rate function . We show that, up to lattice effects, the vectors converge weakly in distribution to . We also prove asymptotic normality of when slowly, and obtain precise asymptotics for when and is not too large. Our results recover and extends the previous distributional convergence results on maximal and near‐maximal degrees in RRT. 相似文献
15.
Julia Bttcher Jie Han Yoshiharu Kohayakawa Richard Montgomery Olaf Parczyk Yury Person 《Random Structures and Algorithms》2019,55(4):854-864
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph Gα on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ. 相似文献
16.
Given a bipartite graph with bipartition each spanning tree in has a degree sequence on and one on . Löhne and Rudloff showed that the number of possible degree sequences on equals the number of possible degree sequences on . Their proof uses a non-trivial characterization of degree sequences by -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result. 相似文献
17.
Bla Bollobs 《Journal of Graph Theory》1982,6(2):147-155
This paper concerns the degree sequence d1 ≥ d2 ≥ … ≥ dn of a randomly labeled graph of order n in which the probability of an edge is p(n) ≦ 1/2. Among other results the following questions are answered. What are the values of p(n) for which d1, the maximum degree, is the same for almost every graph? For what values of p(n) is it true that d2 > d2 for almost every graph, that is, there is a unique vertex of maximum degree? The answers are (essentially) p(n) = o(logn/n/n) and p(n)n/logn → ∞. Also included is a detailed study of the distribution of degrees when 0 < lim n p(n)/log n ≦ lim n p(n)/log n < ∞. 相似文献
18.
Let Gn,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property Ak, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant Ck such that if 2m ≥ Ckn then Ak occurs in Gn,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000 相似文献
19.
We study depth properties of a general class of random recursive trees where each node i attaches to the random node \begin{align*}\left\lfloor iX_i\right\rfloor\end{align*} and X0,…,Xn is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (sarrt). We prove that the typical depth Dn, the maximum depth (or height) Hn and the minimum depth Mn of a sarrt are asymptotically given by Dn ~μ‐1 log n, Hn ~ αmax log n and Mn ~ αmin log n where μ,αmax and αmin are constants depending only on the distribution of X0 whenever X0 has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees Hn ~ elog n that does not use branching random walks.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
20.
Abbas Mehrabian 《Random Structures and Algorithms》2017,50(2):201-224
We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017 相似文献
|