共查询到20条相似文献，搜索用时 15 毫秒
1.
In this paper, we prove the semi‐circular law for the eigenvalues of regular random graph Gn,d in the case d →∞, complementing a previous result of McKay for fixed d. We also obtain a upper bound on the infinity norm of eigenvectors of Erd?s–Rényi random graph G(n,p), answering a question raised by Dekel–Lee–Linial. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 相似文献
2.
The cycle length distribution of a graph G of order n is a sequence (c1 (G),..., cn (G)), where ci(G) is the number of cycles of length i in G. In general, the graphs with cycle length distribution (c1(G),...,cn(G)) are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution (c1 (G),..., cn (G)) is unique. Let Kn,n+r be a complete bipartite graph and A(∈)E(Kn,n+r). In this paper, we obtain: Let s > 1 be an integer. (1) If r = 2s, n > s(s - 1) + 2|A|, then Kn,n+r - A (A(∈)E(Kn,n+r),|A| ≤ 3) is determined by its cycle length distribution; (2) If r = 2s + 1,n > s2 + 2|A|, Kn,n+r - A (A(∈)E(Kn,n+r), |A| ≤ 3) is determined by its cycle length distribution. 相似文献
3.
在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计． 相似文献
4.
Charles Bordenave 《Random Structures and Algorithms》2008,33(4):515-532
We study the spectral measure of large Euclidean random matrices. The entries of these matrices are determined by the relative position of n random points in a compact set Ωn of ?d. Under various assumptions, we establish the almost sure convergence of the limiting spectral measure as the number of points goes to infinity. The moments of the limiting distribution are computed, and we prove that the limit of this limiting distribution as the density of points goes to infinity has a nice expression. We apply our results to the adjacency matrix of the geometric graph. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
5.
Holger Dette 《Journal of Approximation Theory》2002,118(2):290-304
The purpose of this note is to establish a link between recent results on asymptotics for classical orthogonal polynomials and random matrix theory. Roughly speaking it is demonstrated that the ith eigenvalue of a Wishart matrix W(In,s) is close to the ith zero of an appropriately scaled Laguerre polynomial, when
. As a by-product we obtain an elemantary proof of the Mar
enko–Pastur and the semicircle law without relying on combinatorical arguments. 相似文献
6.
In this remark, we show that under the assumption of the finite fourth moment elements in the empirical spectral distribution of a large Wigner matrix converges to the Wigner semicircular law in probability of the order O(n
–1/3). 相似文献
7.
We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this article is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties. Our main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most two large nodal domains, and in addition at most c exceptional vertices outside these primary domains. We also discuss variations of these questions and briefly report on some numerical experiments which, in particular, suggest that almost surely there are just two nodal domains and no exceptional vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 39–58, 2011 相似文献
8.
方碧琪 《应用数学学报(英文版)》1999,15(2):220-224
1.IntrodnctionThispaperextendsthestudyofthesingularmatrixvariatebetadistributionofrank1[1]tothecaseofageneralrank.Astherelateddistributiontonormalsampling,thematrixvariatebetadistribution(alsocalledthemultivariatebetadistribution)hasbeenstudiedextens... 相似文献
9.
Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α1,…,αk be positive reals satisfying begin{align*}sum_{i} alpha_i = 1end{align*} and (α1,…,αk)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V 1,…,V k of size α1n,…,αkn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 相似文献
10.
For a distribution ?? over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions ??. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where ?? is the uniform distribution over the k‐regular bipartite graphs on W and M. For k = o(n1/4), we establish that $L(n) slash sqrt{kn}$ tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n2 possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant γp in probability and in mean when n → ∞. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162–181, 2002 相似文献
11.
《Discrete Mathematics》2022,345(8):112916
In this article, we construct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices using the notion of partitioned tensor products. This extends the construction of Ji, Gong, and Wang [9]. Our proof of the cospectrality of adjacency matrices simplifies the proof of the bipartite case of Godsil and McKay's construction [4], and shows that the corresponding normalized Laplacian matrices are also cospectral. We partially characterize the isomorphism in Godsil and McKay's construction, and generalize Ji et al.'s characterization of the isomorphism to biregular bipartite graphs. The essential idea in characterizing the isomorphism uses Hammack's cancellation law as opposed to Hall's marriage theorem used by Ji et al. 相似文献
12.
13.
Ath Y. Ebneshahrashoob M. Gao T. Sobel M. 《Methodology and Computing in Applied Probability》2002,4(2):153-161
In the recently published atlas of graphs [9] the general listing of graphs with diagrams went up to V=7 vertices but the special listing for connected bipartite graphs carried further up to V=8. In this paper we wish to study the random accessibility of these connected bipartite graphs by means of random walks on the graphs using the degree of the gratis starting point as a weighting factor. The accessibility is then related to the concept of reliability of the graphs with only edge failures. Exact expectation results for accessibility are given for any complete connected bipartite graph N1 cbp N2 (where cbp denotes connected bipartite) for several values of J (the number of new vertices searched for). The main conjecture in this paper is that for any complete connected bipartite graph N1 cbp N2: if |N1–N2| 1, then the graph is both uniformly optimal in reliability and optimal in random accessibility within its family. Numerical results are provided to support the conjecture. 相似文献
14.
We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large “bipartite hole” (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erd?s. In detail, an ‐bipartite‐hole in a graph G consists of two disjoint sets of vertices S and T with and such that there are no edges between S and T ; and is the maximum integer r such that G contains an ‐bipartite‐hole for every pair of nonnegative integers s and t with . Our central theorem is that a graph G with at least three vertices is Hamiltonian if its minimum degree is at least . From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of k edge‐disjoint Hamilton cycles. We see that for dense random graphs , the probability of failing to contain many edge‐disjoint Hamilton cycles is . Finally, we discuss the complexity of calculating and approximating . 相似文献
15.
Yizhe Zhu 《Random Structures and Algorithms》2020,56(1):251-279
We present a new approach, based on graphon theory, to finding the limiting spectral distributions of general Wigner‐type matrices. This approach determines the moments of the limiting measures and the equations of their Stieltjes transforms explicitly with weaker assumptions on the convergence of variance profiles than previous results. As applications, we give a new proof of the semicircle law for generalized Wigner matrices and determine the limiting spectral distributions for three sparse inhomogeneous random graph models with sparsity ω(1/n): inhomogeneous random graphs with roughly equal expected degrees, W‐random graphs and stochastic block models with a growing number of blocks. Furthermore, we show our theorems can be applied to random Gram matrices with a variance profile for which we can find the limiting spectral distributions under weaker assumptions than previous results. 相似文献
16.
We extend Zeifman's method for bounding the spectral gap and obtain the asymptotical behaviour, as N→∞, of the spectral gap of a class of birth–death Markov chains known as random walks on a complete graph of size N. Copyright © 2000 John Wiley & Sons, Ltd. 相似文献
17.
We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence. 相似文献
18.
Bernardo A. Huberman 《Computational & Mathematical Organization Theory》2001,7(2):145-153
This paper presents a dynamical theory of organizational learning that explicitly accounts for both the introduction of new routines into the manufacturing process and improvements in the selection of which procedures to follow. Besides producing a power law of organizational learning with a rate that depends on the effectiveness of the decision procedure, the theory also accounts for observed anomalies characterized by price increases with cumulative output. 相似文献
19.
Let W
n be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here
is independent of n. We show that the limit of the expected spectral distribution functions of W
n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points
, and 0 belong to this set. 相似文献
20.
R. Radhakrishnan Askar Choudhury 《International Journal of Mathematical Education in Science & Technology》2013,44(3):434-440
Computing the mean and covariance matrix of some multivariate distributions, in particular, multivariate normal distribution and Wishart distribution are considered in this article. It involves a matrix transformation of the normal random vector into a random vector whose components are independent normal random variables, and then integrating univariate integrals for computing the mean and covariance matrix of a multivariate normal distribution. Moment generating function technique is used for computing the mean and covariances between the elements of a Wishart matrix. In this article, an alternative method that uses matrix differentiation and differentiation of the determinant of a matrix is presented. This method does not involve any integration. 相似文献