首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 109 毫秒
1.
Many graphs arising in various information networks exhibit the "power law" behavior -the number of vertices of degree k is proportional to k-# for some positive #. We show that if # > 2.5, the largest eigenvalue of a random power law graph is almost surely(1+ o(1))?m (1+ o(1))\sqrt{m} where m is the maximum degree. Moreover, the klargest eigenvalues of a random power law graph with exponent # have power law distribution with exponent 2# if the maximum degree is sufficiently large, where k is a function depending on #, mand d, the average degree. When 2<#< 2.5, the largest eigenvalue is heavily concentrated at cm3-# for some constant c depending on # and the average degree. This result follows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by m, the maximum degree, and [(d)\tilde] \tilde{d} , the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely (1+ o(1))?{mk} (1+ o(1))\sqrt{m_k} where mk is the k-th largest expected degree provided mk is large enough. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval.  相似文献   

2.
Sufficient conditions on bounded domains D ² R d={(t,x)} of class C4 are given under which solutions of the heat equation ut=j u+f in D have continuous second-order derivatives with respect to (t,x) in D- . The equation is supplemented with C4 boundary data and it is assumed that f] C2 .  相似文献   

3.
The main aim of this paper is to obtain a dual result to the now well known Auslander-Bridger formula for G-dimension. We will show that if R is a complete Cohen-Macaulay ring with residue field k, and M is a non-injective h-divisible Ext-finite R-module of finite Gorenstein injective dimension such that for each i 3 1i \geq 1 Exti (E,M) = 0 for all indecomposable injective R-modules E 1 E(k)E \neq E(k), then the depth of the ring is equal to the sum of the Gorenstein injective dimension and Tor-depth of M. As a consequence, we get that this formula holds over a d-dimensional Gorenstein local ring for every nonzero cosyzygy of a finitely generated R-module and thus in particular each such nth cosyzygy has its Tor-depth equal to the depth of the ring whenever n 3 dn \geq d.  相似文献   

4.
The Euler monoid En = {(a,b,t) epsilon Z3 : a2 + b2 = tn, n S 1, is free if and only if n is odd (Theorem 1). We extend the results of Lyndon and Ullman, and Beardon concerning the set of those rational numbers mu epsilon (-2,2) for which the matrix Möbius group Gmu generated by A= and B = is not free (Theorems 2, 3, 4).  相似文献   

5.
Let Ln denote the homogeneous component of degree n in the free Lie ring on three generators, viewed as a module for the symmetric group S3 of all permutations of those generators. This paper gives a Krull-Schmidt Theorem for the LnL^n: if n > 1n>1 and Ln is written as a direct sum of indecomposable submodules, then the summands come from four isomorphism classes, and explicit formulas for the number of summands from each isomorphism class show that these multiplicities are independent of the decomposition chosen.¶A similar result for the free Lie ring on two generators was implicit in a recent paper of R.M. Bryant and the second author. That work, and its continuation on free Lie algebras of prime rank p over fields of characteristic p, provide the critical tools here. The proof also makes use of the identification of the isomorphism types of \Bbb Z \Bbb Z -free indecomposable \Bbb Z S 3\Bbb Z S _3-modules due to M. P. Lee. (There are, in all, ten such isomorphism types, and in general there is no Krull-Schmidt Theorem for their direct sums.)  相似文献   

6.
We consider spectral functions f : 5 where f is any permutation-invariant mapping from Cn to R, and 5 is the eigenvalue map from the set of n 2 n complex matrices to Cn, ordering the eigenvalues lexicographically. For example, if f is the function "maximum real part", then f : 5 is the spectral abscissa, while if f is "maximum modulus", then f : 5 is the spectral radius. Both these spectral functions are continuous, but they are neither convex nor Lipschitz. For our analysis, we use the notion of subgradient extensively analyzed in Variational Analysis, R.T. Rockafellar and R. J.-B. Wets (Springer, 1998). We show that a necessary condition for Y to be a subgradient of an eigenvalue function f : 5 at X is that Y* commutes with X. We also give a number of other necessary conditions for Y based on the Schur form and the Jordan form of X. In the case of the spectral abscissa, we refine these conditions, and we precisely identify the case where subdifferential regularity holds. We conclude by introducing the notion of a semistable program: maximize a linear function on the set of square matrices subject to linear equality constraints together with the constraint that the real parts of the eigenvalues of the solution matrix are non-positive. Semistable programming is a nonconvex generalization of semidefinite programming. Using our analysis, we derive a necessary condition for a local maximizer of a semistable program, and we give a generalization of the complementarity condition familiar from semidefinite programming.  相似文献   

7.
We study compact minimal hypersurfaces Mn in Sn+1S^{n+1} with two distinct principal curvatures and prove that if the squared norm S of the second fundamental form of Mn satisfies S \geqq nS \geqq n, then S o nS \equiv n and Mn is a minimal Clifford torus.  相似文献   

8.
In this paper, the notions of f-injective and f*-injective modules are introduced. Elementary properties of these modules are given. For instance, a ring R is coherent iff any ultraproduct of f-injective modules is absolutely pure. We prove that the class S* \Sigma^* of f*-injective modules is closed under ultraproducts. On the other hand, S* \Sigma^* is not axiomatisable. For coherent rings R, S* \Sigma^* is axiomatisable iff every c0 \chi_0 -injective module is f*-injective. Further, it is shown that the class S \Sigma of f-injective modules is axiomatisable iff R is coherent and every c0 \chi_0 -injective module is f-injective. Finally, an f-injective module H, such that every module embeds in an ultraprower of H, is given.  相似文献   

9.
Let G be a closed group of automorphisms of a graph X. We relate geometric properties of G and X, such as amenability and unimodularity, to properties of G-invariant percolation processes on X, such as the number of infinite components, the expected degree, and the topology of the components. Our fundamental tool is a new masstransport technique that has been occasionally used elsewhere and is developed further here.¶ Perhaps surprisingly, these investigations of group-invariant percolation produce results that are new in the Bernoulli setting. Most notably, we prove that critical Bernoulli percolation on any nonamenable Cayley graph has no infinite clusters. More generally, the same is true for any nonamenable graph with a unimodular transitive automorphism group.¶ We show that G is amenable if for all $ \alpha < 1 $ \alpha < 1 , there is a G-invariant site percolation process w \omega on X with $ {\bf P} [x \in \omega] > \alpha $ {\bf P} [x \in \omega] > \alpha for all vertices x and with no infinite components. When G is not amenable, a threshold $ \alpha < 1 $ \alpha < 1 appears. An inequality for the threshold in terms of the isoperimetric constant is obtained, extending an inequality of Häggström for regular trees.¶ If G acts transitively on X, we show that G is unimodular if the expected degree is at least 2 in any G-invariant bond percolation on X with all components infinite.¶ The investigation of dependent percolation also yields some results on automorphism groups of graphs that do not involve percolation.  相似文献   

10.
Summary. We present a result concerning the periodic structure of certain maps on In = [0,1]n which are called s \sigma -permutation maps. This structure resembles that given by the xarkovskii's ordering for continuous interval maps.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号