首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
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,vV (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.
In this paper we prove the following theorem (for notation and definitions, see the paragraphs below): “Let Ω ⊆ ℝn be a domain, m ∈ ℕ, and λ, q > 0. Then, there exists r (= r(λ, q)) > 1 such that for every 0 < p < q, whenever are weak solutions of a strongly elliptic system with m equations of ellipticity λ satisfying ∈ 𝒫r a.e. and Ω′ ⊆ Ω subdomain, the following inequalities hold: where C (= C(n,m,λ,q,p,Ω,Ω′)) is a positive constant.” © 1999 John Wiley & Sons, Inc.  相似文献   

3.
The d-dimensional Hardy spaces Hp ( T × … × T ) (d = d1 + … + dkand a general summability method of Fourier series and Fourier transforms are introduced with the help of integrable functions θj having integrable Fourier transforms. Under some conditions on θj we show that the maximal operator of the θ-means of a distribution is bounded from Hp ( T × … × T ) to Lp ( T d) where p0 < p < ∞ and p0 < 1 is depending only on the functions θj. By an interpolation theorem we get that the maximal operator is also of weak type ( L1) (i = 1, …, k) where the Hardy space is defined by a hybrid maximal function and if k = 1. As a consequence we obtain that the θ-means of a function (log L)k–1 converge a.e. to the function in question. If k = 1 then we get this convergence result for all fL1. Moreover, we prove that the θ-means are uniformly bounded on the spaces Hp ( T × … × T ) whenever p0 <p < ∞, thus the θ-means converge to f in ( T × … × T ) norm. The same results are proved for the conjugate θ-means and for d-dimensional Fourier transforms, too. Some special cases of the θ-summation are considered, such as the Weierstrass, Picar, Bessel, Fejér, Riemann, de La Vallée-Poussin, Rogosinski and Riesz summations.  相似文献   

4.
Let Xn be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for Xn. The basic observation for its proof is that the probability distributions of are recursively defined by , where Dn is a discrete random variable with ? , which is independent of . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009  相似文献   

5.
In this paper we prove a Tauberian type theorem for the space L ( H n ). This theorem gives sufficient conditions for a L ( H n ) submodule J ? L ( H n ) to make up all of L ( H n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L( H n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z m L g f ( z , 0) ( z ) = 0 for all g ∈ H n and i = 1, 2 for appropriate radii r1 and r2, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T(0,1)( H n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)  相似文献   

6.
The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets SV (G) of size at most n/2, where S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008  相似文献   

7.
For each 0 < s < 1, define where , denote respectively the s‐dimensional packing measure and Hausdorff measure, and the infimum is taken over all the sets E ⊂ R with . In this paper we give a nontrivial estimation of c(s), namely, for each 0 < s < 1, where . As an application, we obtain a lower density theorem for Hausdorff measures.  相似文献   

8.
An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022  相似文献   

9.
Suppose r ≥ 2 is a real number. A proper r‐flow of a directed multi‐graph is a mapping such that (i) for every edge , ; (ii) for every vertex , . The circular flow number of a graph G is the least r for which an orientation of G admits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003  相似文献   

10.
Let be bounded Lipschitz and relatively open. We show that the solution to the linear first order system 1 : (1) vanishes if and , (e.g. ). We prove to be a norm if with , for some p, q > 1 with 1/p + 1/q = 1 and . We give a new proof for the so called ‘in-finitesimal rigid displacement lemma’ in curvilinear coordinates: Let , satisfy for some with . Then there are and a constant skew-symmetric matrix , such that . (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)  相似文献   

11.
We investigate the evolution problem where H is a Hilbert space, A is a self‐adjoint linear non‐negative operator on H with domain D(A), and is a continuous function. We prove that if , and , then there exists at least one global solution, which is unique if either m never vanishes, or m is locally Lipschitz continuous. Moreover, we prove that if for all , then this problem is well posed in H. On the contrary, if for some it happens that for all , then this problem has no solution if with β small enough. We apply these results to degenerate parabolic PDEs with non‐local non‐linearities. Copyright © 1999 John Wiley & Sons, Ltd.  相似文献   

12.
In this paper the degenerate parabolic system ut=u(uxx+av). vt=v(vxx+bu) with Dirichlet boundary condition is studied. For , the global existence and the asymptotic behaviour (α12) of solution are analysed. For , the blow‐up time, blow‐up rate and blow‐up set of blow‐up solution are estimated and the asymptotic behaviour of solution near the blow‐up time is discussed by using the ‘energy’ method. Copyright © 2003 John Wiley & Sons, Ltd.  相似文献   

13.
Let the random variable Zn,k denote the number of increasing subsequences of length k in a random permutation from Sn, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)2) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure Un on Sn. Define the probability measure μ on Sn by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x1,x2,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006  相似文献   

14.
A p‐list assignment L of a graph G assigns to each vertex v of G a set of permissible colors. We say G is L‐(P, q)‐colorable if G has a (P, q)‐coloring h such that h(v) ? L(v) for each vertex v. The circular list chromatic number of a graph G is the infimum of those real numbers t for which the following holds: For any P, q, for any P‐list assignment L with , G is L‐(P, q)‐colorable. We prove that if G has an orientation D which has no odd directed cycles, and L is a P‐list assignment of G such that for each vertex v, , then G is L‐(P, q)‐colorable. This implies that if G is a bipartite graph, then , where is the maximum average degree of a subgraph of G. We further prove that if G is a connected bipartite graph which is not a tree, then . © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 190–204, 2008  相似文献   

15.
Let be a k‐uniform hypergraph on n vertices. Suppose that holds for all . We prove that the size of is at most if satisfies and n is sufficiently large. © 2005 Wiley Periodicals, Inc. J Combin Designs  相似文献   

16.
In this paper we provide a new arithmetic characterization of the levels of the og‐time hierarchy (LH). We define arithmetic classes and that correspond to ‐LOGTIME and ‐LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose ‐definable functions are precisely B( ‐LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)‐definable functions are LH, proves LH is not equal to ‐TIME(s) for any m> 0, where 2sL, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.  相似文献   

17.
Let G be a graph on n vertices in which every induced subgraph on vertices has an independent set of size at least . What is the largest so that every such G must contain an independent set of size at least q? This is one of the several related questions raised by Erd?s and Hajnal. We show that , investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey‐type problem. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 149–157, 2007  相似文献   

18.
In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χc(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χc(G) = and χ(G) = , consequently, there exist graphs G such that χc(G) is as close to χ(G) − 1 as you want, but χc(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999  相似文献   

19.
We consider the following semilinear wave equation: (1) for (t,x) ∈ ?t × ?. We prove that if the potential V(t,x) is a measurable function that satisfies the following decay assumption: V(t,x)∣?C(1+t)(1+∣x∣) for a.e. (t,x) ∈ ?t × ? where C, σ0>0 are real constants, then for any real number λ that satisfies there exists a real number ρ(f,g,λ)>0 such that the equation has a global solution provided that 0<ρ?ρ(f,g,λ). Copyright © 2004 John Wiley & Sons, Ltd.  相似文献   

20.
Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n) distinct hamilton cycles for any fixed ?>0.  相似文献   

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

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