首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
Let r ≥ 3, nr and π = (d 1, d 2, ..., d n ) be a non-increasing sequence of nonnegative integers. If π has a realization G with vertex set V (G) = {v 1, v 2, ..., v n } such that d G (v i ) = d i for i = 1, 2, ..., n and v 1 v 2 ... v r v 1 is a cycle of length r in G, then π is said to be potentially C r ″-graphic. In this paper, we give a characterization for π to be potentially C r ″-graphic. This work was supported by the grant of National Natural Science Foundation of China No. 10861006 and China Scholarship Council.  相似文献   

2.
LetX 1, ...,X n be events in a probability space. Let ϱi be the probabilityX i occurs. Let ϱ be the probability that none of theX i occur. LetG be a graph on [n] so that for 1 ≦i≦n X i is independent of ≈X j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ1, ..., ϱ n x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) d−1 d −d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ i andG.  相似文献   

3.
Letx 1, x2, ..., xNbep×1 random vectors distributed independently asN(u, Σ), Σ>0;u and Σ are unknown. In this paper, we derive the exact non-null distribution of Wilks' likelihood ratio criterion,L VC, for testingH:∑=σ 2[(1−ρ)I+ρee′], σ>0 and ρ are unknown against the alternativeA≠H,e′=(1, 1, …, 1): 1×p. The distribution has been derived in three series forms: (1) a series of Meijer'sG-functions through Mellin transform, (2) an, alternate series using contour, intergration and (3) a series of chi square distributions. Powers have been computed based on these forms of the distribution forp=2 and 3.  相似文献   

4.
Given a permutation , construct a graph G π on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if G π is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which G π is a tree, or a path, and recover the known generating function of smooth permutations. Received March 27, 2006  相似文献   

5.
LetB d be thed-dimensional unit ball and, for an integern, letC n ={x 1,...,x n } be a packing set forB d , i.e.,|x i −x j |≥2, 1≤i<j≤n. We show that for every a dimensiond(ρ) exists such that, ford≥d(ρ),V(conv(C n )+ρB d )≥V(conv(S n )+ρB d ), whereS n is a “sausage” arrangement ofn balls, holds. This gives considerable improvement to Fejes Tóth's “sausage” conjecture in high dimensions. Further, we prove that, for every convex bodyK and ρ<1/32d −2,V(conv(C n )+ρK)≥V(conv(S n )+ρK), whereC n is a packing set with respect toK andS n is a minimal “sausage” arrangement ofK, holds.  相似文献   

6.
. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ i =1 n T i admits an (r, d)-invariant orientation provided that d(T 1)≥d(T 2)≥4 for n=2, and d(T 1)≥5 and d(T 2)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998  相似文献   

7.
Let R be a prime ring of char R ≠ = 2 with center Z(R) and with extended centroid C, d a nonzero derivation of R and f(x 1, ..., x n ) a nonzero multilinear polynomial over C. Suppose that x s d(x)x t Z(R) for all x ∈ {d(f(x 1, ..., x n ))|x 1, ..., x n ρ}, where ρ is a nonzero right ideal of R and s ≥ 0, t ≥ 0 are fixed integers. If d(ρ)ρ ≠ = 0, then ρ C = eRC for some idempotent e in the socle of RC and f(x 1, ..., x n ) N is central-valued in eRCe, where N = s + t + 1.   相似文献   

8.
 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph GJ on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G 1, G 2 and G 3 such that E G (G i , G j ) = {u i , u j , v i v j } for ij and i,j = 1, 2, 3 (where u i v i V(G i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999  相似文献   

9.
In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f([`(x)]) = ?i = 1k hi ([`(x)]) ·gi ([`(x)])f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} , where each h i is a polynomial that depends on only ρ linear functions, and each g i is a product of linear functions (when h i = 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When max i (deg(h i · g i )) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.
1.  A deterministic black-box identity testing algorithm for ΣΠΣ(k; d;ρ) circuits that runs in quasi-polynomial time (for ρ=polylog(n+d)). In particular this gives the first black-box quasi-polynomial time PIT algorithm for depth-3 circuits with k multiplication gates.  相似文献   

10.
A model for cleaning a graph with brushes was recently introduced. Let α = (v 1, v 2, . . . , v n ) be a permutation of the vertices of G; for each vertex v i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N-(vi)={j: vj vi ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let ba(G)=?i=1n max{|N+(vi)|-|N-(vi)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max α b α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.  相似文献   

11.
Summary Considerk p-variate normal populationsπ i with meansμ i and common covariance matrix Σ, i.e.,π i :N(μ i ,Σ). The problem is to design a sequential procedure to rank these populations with respect to some distance function. We consider two distance functionsμ i μ i andμ i Σ -1 μ i . Procedures on the lines of Chow and Robbins [3], Paulson [5] and Hoel and Majumdar [4] are obtained. Research supported by National Research Council of Canada and Canada Council.  相似文献   

12.
Let {ξ j ; j ∈ ℤ+ d be a centered stationary Gaussian random field, where ℤ+ d is the d-dimensional lattice of all points in d-dimensional Euclidean space ℝd, having nonnegative integer coordinates. For each j = (j 1 , ..., jd) in ℤ+ d , we denote |j| = j 1 ... j d and for m, n ∈ ℤ+ d , define S(m, n] = Σ m<j≤n ζ j , σ2(|nm|) = ES 2 (m, n], S n = S(0, n] and S 0 = 0. Assume that σ(|n|) can be extended to a continuous function σ(t) of t > 0, which is nondecreasing and regularly varying with exponent α at b ≥ 0 for some 0 < α < 1. Under some additional conditions, we study limsup results for increments of partial sum processes and prove as well the law of the iterated logarithm for such partial sum processes. Research supported by NSERC Canada grants at Carleton University, Ottawa  相似文献   

13.
We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ d , the infinite graph with vertex set ℤ d and an edge (u, v) whenever ∥uv = 1. The growth rate of G, denoted ρ G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ρ vertices. By simple volume arguments, dim(G) = Ω(ρ G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ G ) for every graph G. Previously, it was unknown whether dim(G) could be bounded above by any function of ρ G . We show that a weaker form of Levin’s conjecture holds by proving that dim(G) = O(ρ G log ρ G ) for any graph G. We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) = Ω(ρ G log ρ G ). For several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. Supported by NSF grant CCR-0121555 and by an NSF Graduate Research Fellowship.  相似文献   

14.
A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d1, d2,⋯, d2) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP k-graphic if it has a realizationG having propertyP k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d1, d2,…, d2) without zero terms and with degree sum σ(π)=(d 1+d 2+ …+d 2) at least σ(k,n) is potentially Pk-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.  相似文献   

15.
§1 IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

16.
Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f 1, f 2, …, f d } of distinct Roman k-dominating functions on G with the property that Σ i=1 d f i (v) ≤ 2 for each vV (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d kR (G). Note that the Roman 1-domatic number d 1R (G) is the usual Roman domatic number d R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.  相似文献   

17.
Let μ be a measure on ℝn that satisfies the estimate μ(B r(x))≤cr α for allx ∈n and allr ≤ 1 (B r(x) denotes the ball of radius r centered atx. Let ϕ j,k (ɛ) (x)=2 nj2ϕ(ɛ)(2 j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤn, and ∈ ∈E, a finite set, and letP j (T)=Σɛ,k <T j,k (ɛ) j,k (ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). IffLs p(dμ) for 1 ≤p ≤ ∞, we show thatP j(f dμ) ∈ Lp(dx) and ||P j (fdμ)||L p(dx)c2 j((n-α)/p′))||f||L p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P j (fdμ)||L p(dx) under more restrictive hypotheses. Communicated by Guido Weiss  相似文献   

18.
Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q 1(t)q 2(t)2 ... q m (t)m, where each q i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q j (t). We give an algorithm to construct the polynomials q i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λi| of G, where λ1, λ2, ..., λn are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.  相似文献   

19.
It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev 1, ...,v n V(G) and for any sequence of positive integersk 1, ...,k n such thatk 1+...+k n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv 1, ...,v(n), and the class of the partition containingv i induces a connected subgraph consisting ofk i vertices, fori=1, 2, ...,n. Now fix the integersk 1, ...,k n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv 1, ...,v n V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.  相似文献   

20.
A random geometric graph G n is constructed by taking vertices X 1,…,X n ∈ℝ d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X i and X j if ‖X i -X j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr d = o(lnn) then the probability distribution of the clique number ω(G n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.  相似文献   

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

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