An Upper Bound for the w-Weak Global Dimension of Pullbacks

Let R be a commutative ring with identity and I0 an ideal of R.We introduce and study the c-weak global dimension c-w.gl.dim(R/I0) of the factor ring R/I0.Let T be a w-linked extension of R,and we also introduce the wR-weak global dimension wR-w.gl.dim(T) of T.We show that the ring T with wR-w.gl.dim(T) =0 is exactly a field and the ring T with wR-w.gl.dim(T) ≤ 1 is exactly a PwRMD.As an application,we give an upper bound for the w-weak global dimension of a Cartesian square (RDTF,M).More precisely,if T is w-linked over R,then w-w.gl.dim(R) ≤ max{wR-w.gl.dim(T) + w-fdR T,c-w.gl.dim(D) + w-fdn D}.Furthermore,for a Milnor square (RDTF,M),we obtain w-w.gl.dim(R) ≤ max{wR-w.gl.dim(T) + w-fdR T,w-w.gl.dim(D) + w-fdR D}.     

A New Upper Bound for Sampling Numbers

Foundations of Computational Mathematics - We provide a new upper bound for sampling numbers $$(g_n)_{nin mathbb {N}}$$ associated with the compact embedding of a separable reproducing kernel...     

有限域上一类等维码的下界

等维码凭借其在随机线性网络编码中的良好的差错控制得到广泛研究,对于给定维数和最小距离的等维码所含码字的最大个数目前还没有一般性结果.Tuvi Etzion和Alexander Vardy给出了一定等维码所含码字最大个数的上界和下界,首先利用对偶空间构造等维码C(n,M,2k,k),达到了此类码所含码字的下界,然后具体构造了最优等维码C(7,41,4,2).     

True Dimension of Some Binary Quadratic Trace Goppa Codes

We compute in this paper the true dimension over of Goppa Codes (L, g) defined by the polynomial proving, this way, a conjecture stated in [14,16].     

A Trace Bound for the Hereditary Discrepancy

Let A be the incidence matrix of a set system with m sets and n points, m ≤ n , and let t= \mathop \rm tr M , where M= A ^T A . Finally, let σ = \mathop \rm tr M ² be the sum of squares of the elements of M . We prove that the hereditary discrepancy of the set system is at least . This general trace bound allows us to resolve discrepancy-type questions for which spectral methods had previously failed. Also, by using this result in conjunction with the spectral lemma for linear circuits, we derive new complexity bounds for range searching. We show that the (red—blue) discrepancy of the set system formed by n points and n lines in the plane is Ω(n ^1/6 ) in the worst case and always ¹ \tilde O(n ^1/6 ) . We give a simple explicit construction of n points and n halfplanes with hereditary discrepancy \tildeΩ(n ^1/4 ) . We show that in any dimension d= Ω( log n/\kern -1ptlog log n ) , there is a set system of n points and n axis-parallel boxes in \bf R ^d with discrepancy n ^{Ω(1/\kern -1pt log log n)} . Applying these discrepancy results together with a new variation of the spectral lemma, we derive a lower bound of Ω(nlog n) on the arithmetic complexity of off-line range searching for points and lines (for nonmonotone circuits). We also prove a lower bound of Ω(nlog n/\kern -1ptlog log n) on the complexity of orthogonal range searching in any dimension Ω(log n/\kern -1ptlog log n) . ¹ We use the notation \tilde O(m) and \tilde Ω(m) as shorthand for O(mlog ^c m) and Ω(m/\kern -1ptlog ^c m) , respectively, for some constant c>0 . Received April 5, 2000, and in revised form October 17, 2000. Online publication June 22, 2001.     

A Lower Bound for the Dimension of Trivariate Spline Spaces

We consider trivariate C^r spline spaces of degree d defined on arbitrary tetrahedral partitions. A lower bound for the dimension of trivariate spline spaces over arbitrary tetrahedral partitions for d > r is computed. This is the first general lower bound known.     

无符号拉普拉斯谱半径的新上界

如果一个图存在定向满足其最大出度△~＋不超过最大度△的一半,则通过估计图的半边路径（semi-edge walk）的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界.进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界.     

A Homological Lower Bound for Order Dimension of Lattices

We prove that if a finite lattice L has order dimension at most d, then the homology of the order complex of its proper part L vanishes in dimensions d – 1 and higher. If L can be embedded as a join-sublattice in N ^d , then L actually has the homotopy type of a simplicial complex with d vertices.     

A Lower Bound for Pseudodimension in Terms of Topological Dimension

Mathematical Notes -     

A Lower Bound on the Greedy Weights of Product Codes

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e _r is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.     

A Continuous Analogue of the Upper Bound Theorem

For an absolutely continuous probability measure μ on R ^d and a nonnegative integer k , let tilde s _k (μ ,origin ) denote the probability that the convex hull of k+d+1 random points which are i.i.d. according to μ contains the origin bf 0 . For d and k given, we determine a tight upper bound on tilde s _k (μ ,origin ) , and we characterize the measures in R ^d which attain this bound. As we will see, this result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h -functions, continuous counterparts of h -vectors of simplicial convex polytopes. Received April 14, 2000, and in revised form October 6, 2000. Online publication June 20, 2001.     

An Upper Bound for List T-Colourings

Erds, Rubin and Taylor showed in 1979 that for any connectedgraph G which is not a complete graph or an odd cycle, ch(G) , where is the maximum degree of a vertex in G and ch(G) isthe choice number of the graph (also proved by Vizing in 1976).They also gave a characterisation of D-choosability. A graphG is D-choosable if, when we assign to each vertex v of G alist containing d(v) elements, where d(v) is the degree of vertexv, we can always choose a proper vertex colouring from theselists, however the lists were chosen. In this paper we shallgeneralise their results on the choice number of G and D-choosabilityto the case where we have T-colourings.     

The Upper Bound for the Stable Marriage Problem

The stable problem was originally posed by Gale and Shapley. The worst case performance of their solution is derived in a manner that illustrates the complexity characteristics of the problem. Several conclusions about the nature of the worst case situation are presented.     

关于对数平均的上界和下界

本文指出关于对数平均的上界的一项研究工作中存在的错误,并且给出对数平均的一些更精密的上界和下界.     

Universal Upper Bound for the Growth of Artin Monoids

In this paper we study the growth rates of Artin monoids, and we show that 4 is a universal upper bound. We also show that the generating functions of the associated right-angled Artin monoids are given by families of Chebyshev polynomials. Applications to Artin groups and positive braids are given.     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

Ramsey数R_m(3)的计算及Schur数的新上界

利用抽屉原理,给出了Ramsey数Rm(3)的一个递推公式,得到Rm(3)准确值计算的一个具体表达式,并利用Rm(3)的计算公式给出了Schur数的一个新的上界。