共查询到20条相似文献，搜索用时 0 毫秒
1.
Michael Capalbo 《Random Structures and Algorithms》2010,37(4):437-454
For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 相似文献
2.
Tony Johansson 《Random Structures and Algorithms》2020,57(1):132-149
Given a graph Γn=(V,E) on n vertices and m edges, we define the Erd?s‐Rényi graph process with host Γn as follows. A permutation e1,…,em of E is chosen uniformly at random, and for t ≤ m we let Γn,t=(V,{e1,…,et}). Suppose the minimum degree of Γn is δ(Γn) ≥ (1/2+ε)n for some constant ε>0. Then with high probability (An event holds with high probability (whp) if as n→∞.), Γn,t becomes Hamiltonian at the same moment that its minimum degree reaches 2. Given 0 ≤ p ≤ 1 let Γn,p be the Erd?s‐Rényi subgraph of Γn, obtained by retaining each edge independently with probability p. When δ(Γn) ≥ (1/2+ε)n, we provide a threshold for Hamiltonicity in Γn,p. 相似文献
3.
Sourav Chatterjee 《Random Structures and Algorithms》2012,40(4):437-451
This paper solves the problem of sharp large deviation estimates for the upper tail of the number of triangles in an Erd?s‐Rényi random graph, by establishing a logarithmic factor in the exponent that was missing till now. It is possible that the method of proof may extend to general subgraph counts. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 437–451, 2012 相似文献
4.
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. 相似文献
5.
Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s‐Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 ‐ o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n1+Ω(1/log log n). Recall that the Ising model with inverse temperature β defined on a graph G = (V,E) is the distribution over {±}Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of β or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < ∞ and the Ising model defined on G (n, d/n), there exists a βd > 0, such that for all β < βd with probability going to 1 as n →∞, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd?s‐Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub‐graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and β < βd, where d tanh(βd) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
6.
We compute an asymptotic expansion in of the limit in of the empirical spectral measure of the adjacency matrix of an Erd?s‐Rényi random graph with vertices and parameter . We present two different methods, one of which is valid for the more general setting of locally tree‐like graphs. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 160–184, 2016 相似文献
7.
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 相似文献
8.
Klaus Metsch 《组合设计杂志》2006,14(6):441-450
It was remarked by P. Erd?s, J. C. Fowler, V. T. Sós, and R. M. Wilson, (J Combin Theory Ser A 38, 1985, 131–142), that a non‐degenerate finite linear space on v points has the following property. For every point P the number of lines not passing through P is at least with equality if and only if the linear space is a projective plane. We give a short proof for this result using an algebraic tool. The main purpose of the article however is to generalize this result in the direction that gives a lower bound for the number of lines not passing through a given number d of points. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 441–450, 2006 相似文献
9.
Wojciech Samotij 《Random Structures and Algorithms》2014,44(3):269-289
Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long‐standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. In particular, the theorem of Schacht yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erd?s and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting. We then use this theorem to derive several new results, among them a random version of the Erd?s‐Simonovits stability theorem for arbitrary graphs, extending the result of Conlon and Gowers, who proved such a statement for so‐called strictly 2‐balanced graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 269‐289, 2014 相似文献
10.
Ross J. Kang Colin McDiarmid Bruce Reed Alex Scott 《Random Structures and Algorithms》2014,45(3):343-361
Erd?s and Hajnal conjectured that for every graph H there is a constant such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order . The conjecture would be false if we set ; however, in an asymptotic setting, we obtain this strengthened form of Erd?s and Hajnal's conjecture for almost every graph H, and in particular for a large class of graphs H defined by variants of the colouring number. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 343–361, 2014 相似文献
11.
We prove that there exists a bivariate function f with such that for every natural k and ?, every graph G has at least k vertex‐disjoint cycles of length at least ? or a set of at most vertices that meets all cycles of length at least ?. This improves a result by Birmelé et al. (Combinatorica, 27 (2007), 135–145), who proved the same result with . 相似文献
12.
Andrew McLennan 《Journal of Graph Theory》2005,49(4):291-301
The Erd?s‐Sós Conjecture is that a finite graph G with average degree greater than k ? 2 contains every tree with k vertices. Theorem 1 is a special case: every k‐vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005 相似文献
13.
Adam Zsolt Wagner 《Journal of Graph Theory》2017,86(2):141-148
Fox–Grinshpun–Pach showed that every 3‐coloring of the complete graph on n vertices without a rainbow triangle contains a clique of size that uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. We show that every such coloring contains a 2‐colored subgraph with chromatic number at least , and this is best possible. We further show that for fixed positive integers with , every r‐coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a subgraph that uses at most s colors and has chromatic number at least , and this is best possible. Fox–Grinshpun–Pach previously showed a clique version of this result. As a direct corollary of our result we obtain a generalization of the celebrated theorem of Erd?s‐Szekeres, which states that any sequence of n numbers contains a monotone subsequence of length at least . We prove that if an r‐coloring of the edges of an n‐vertex tournament does not contain a rainbow triangle then there is an s‐colored directed path on vertices, which is best possible. This gives a partial answer to a question of Loh. 相似文献
14.
A well‐known conjecture of Erd?s states that given an infinite graph G and sets A, ? V(G), there exists a family of disjoint A ? B paths ?? together with an A ? B separator X consisting of a choice of one vertex from each path in ??. There is a natural extension of this conjecture in which A, B, and X may contain ends as well as vertices. We prove this extension by reducing it to the vertex version, which was recently proved by Aharoni and Berger. © 2005 Wiley Periodicals, Inc. J Graph Theory 50: 199–211, 2005 相似文献
15.
16.
Christian Tfula 《Random Structures and Algorithms》2019,55(1):173-214
Given a sequence , let r??,h(n) denote the number of ways n can be written as the sum of h elements of ??. Fixing h ≥ 2, we show that if f is a suitable real function (namely: locally integrable, O‐regularly varying and of positive increase) satisfying then there must exist with for which r??,h + ?(n) = Θ(f(n)h + ?/n) for all ? ≥ 0. Furthermore, for h = 2 this condition can be weakened to . The proof is somewhat technical and the methods rely on ideas from regular variation theory, which are presented in an appendix with a view towards the general theory of additive bases. We also mention an application of these ideas to Schnirelmann's method. 相似文献
17.
Jean-Marie Barbaroux Franois Germinet Serguei Tcheremchantsev 《Journal de Mathématiques Pures et Appliquées》2001,80(10):411
Given a positive probability Borel measure μ on
, we establish some basic properties of the associated functions τμ±(q) and of the generalized fractal dimensions Dμ±(q) for
. We first give the equivalence of the Hentschel–Procaccia dimensions with the Rényi dimensions and the mean-q dimensions, for q>0. We then use these relations to prove some regularity properties for τμ±(q) and Dμ±(q); we also provide some estimates for these functions, in particular estimates on their behaviour at ±∞, as well as for the dimensions corresponding to convolution of two measures. We finally present some calculations for specific examples illustrating the different cases met in the article. 相似文献
18.
The original Erd
s—Rényi theorem states that max0kn∑k+[clogn]i=k+1Xi/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {Xn, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd
s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X1. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑k+[clogn]i=k+1(X2i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric. 相似文献
19.
Let s ≥ 2 be an integer and k > 12(s ? 1) an integer. We give a necessary and sufficient condition for a graph G containing no K2,s with and to contain every tree T of order k + 1. We then show that every graph G with no K2,s and average degree greater than k ? 1 satisfies this condition, improving a result of Haxell, and verifying a special case of the Erd?s—Sós conjecture, which states that every graph of average degree greater than k ? 1 contains every tree of order k + 1. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 301–310, 2007 相似文献
20.
Let A={a1,a2,…}(a1<a2<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by rk(A,n) the number of solutions of ai1+ai2++aik≤n. Montgomery and Vaughan proved that r2(A,n)=cn+o(n1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2. 相似文献