Quasi‐complements of the cappable degrees

Say that a nonzero c. e. degree b is a quasi‐complement of a c. e. degree a if a ∩ b = 0 and a ∪ b is high. It is well‐known (due to Shore) that each cappable degree has a high quasi‐complement. However, by the existence of the almost deep degrees, there are nonzero cappable degrees having no low quasi‐complements. In this paper, we prove that any nonzero cappable degree has a low₂ quasi‐complement. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bounding the feedback vertex number of digraphs in terms of vertex degrees

The Turán bound (Turán (1941) [17]) is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality (Caro (1979) [4] and Wei (1981) [18]), which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex out-degrees and in terms of average out-degree, respectively.     

Bounding one-way differences

Letf(n, k) denote the maximum length of a sequence (F ₁,F ₂,...) of distinct subsets of ann-element set with the property that|F _i F _j | < k for alli < j. We determine the exact values off(n, 2) and characterize all the extremal sequences. Fork 3 we prove that . Some related problems are also considered.     

Bounding the piercing number

It is shown that for everyk and everyp≥q≥d+1 there is ac=c(k,p,q,d)<∞ such that the following holds. For every familyℋ whose members are unions of at mostk compact convex sets inR ^d in which any set ofp members of the family contains a subset of cardinalityq with a nonempty intersection there is a set of at mostc points inR ^d that intersects each member ofℋ. It is also shown that for everyp≥q≥d+1 there is aC=C(p,q,d)<∞ such that, for every family of compact, convex sets inR ^d so that among andp of them someq have a common hyperplane transversal, there is a set of at mostC hyperplanes that together meet all the members of . This research was supported in part by a United States-Israel BSF Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Variance Bounding of Delayed-Acceptance Kernels

Methodology and Computing in Applied Probability - A delayed-acceptance version of a Metropolis–Hastings algorithm can be useful for Bayesian inference when it is computationally expensive to...     

Multi-Input Multi-Output Ellipsoidal State Bounding

Ellipsoidal state outer bounding has been considered in the literature since the late sixties. As in the Kalman filtering, two basic steps are alternated: a prediction phase, based on the approximation of the sum of ellipsoids, and a correction phase, involving the approximation of the intersection of ellipsoids. The present paper considers the general case where K ellipsoids are involved at each step. Two measures of the size of an ellipsoid are employed to characterize uncertainty, namely, its volume and the sum of the squares of its semiaxes. In the case of multi-input multi-output state bounding, the algorithms presented lead to less pessimistic ellipsoids than the usual approaches incorporating ellipsoids one by one.     

Bounding differences in Jager Pairs

Symmetrical subdivisions in the space of Jager Pairs for continued fractions-like expansions will provide us with bounds on their differences. Results will also apply to the classical regular and backwards continued fractions expansions, which are realized as special cases.     

Bounding families of ruled surfaces

In this paper we provide a sharp bound for the dimension of a family of ruled surfaces of degree in . We also find the families with maximal dimension: the family of ruled surfaces containing two unisecant skew lines, when and the family of rational ruled surfaces, when .

The first tool we use is a Castelnuovo-type bound for the irregularity of ruled surfaces in . The second tool is an exact sequence involving the normal sheaf of a curve in the grassmannian. This sequence is analogous to the one constructed by Eisenbud and Harris in 1992, where they deal with the problem of bounding families of curves in projective space. However, our construction is more general since we obtain the mentioned sequence by purely algebraic means, studying the geometry of ruled surfaces and of the grassmannian.

     

Bounding eigenvalues of clamped plates

Zusammenfassung Es wird ein Verfahren zur Berechnung von oberen und unteren Schranken für die Eigenwerte einer eingespannten Platte beliebiger Form dargestellt. Die Methode besteht darin, exakte Partikulärlösungen der Plattengleichung ( ² u=u) zu konstruieren, welche die Randbedingungen des Plattenproblems approximativ erfüllen. Der Abstand zwischen dem Eigenwert der Partikulärlösung und einem Eigenwert des Plattenproblems kann dann mit Hilfe eines Lemmas vonMoler undPayne abgeschätzt werden.Als Beispiele wurden die ersten Eigenwerte der quadratischen Platte sowie einiger elliptischer Platten berechnet. Für eine spezielle elliptische Platte sind die ersten vier Eigenwerte angegeben.     

Bounding the Reliability of Networks

Various applied problems require the analysis of systems with randomly failing elements. A typical such instance occurs in assessing the reliability of a transportation or communication network, in which the individual links fail independently with known probabilities. One is then interested in the probability that goods or information will be successfully transported from some source location to some terminal location. Exact calculation of this probability is known to be difficult, so this paper develops a method for obtaining lower and upper bounds on the required value. In fact, our procedure yields a sequence of matched lower and upper bounds, which can be monitored as the algorithm progresses. Rather than simply producing a numerical value, the method produces a functional (symbolic) form for the answer, especially useful for subsequent sensitivity analyses.     

Bounding graph diameters of solvable groups

We define a graph associated with a group G by letting nontrivial degrees be the vertices, and placing an edge between distinct degrees if they are not relatively prime. Using results in the literature, it is not difficult to show that when G is solvable and the graph is connected, its diameter is at most 4. Recent results suggest that this bound might be obtained. We show that in fact this diameter is at most 3, which is best possible.     

Bounding Distributions for Stochastic Logic Networks

A stochastic logic network is defined as a connected set of logic and time delay elements. Each of the latter elements has an associated probability distribution describing the nature of that element's delay. When used, for example, in project planning and scheduling, combinations of logic and time delay elements in such networks may represent conditions for the starting of project activities which are themselves represented by time delay elements. It is at present not known how to calculate the probability distributions for the events in such a network. This paper shows how to obtain upper and lower bounds for these probability distributions. The method is not a simulation technique; rather, it is a straightforward computational scheme derived from elementary probability theory. An example is given where the method is applied to a stochastic project scheduling network in which alternative ways exist for carrying out one of the jobs in the network.     

Bounding the sup-norm of automorphic forms

No Abstract.  .     

Bounding multiplicative energy by the sumset

We prove that the sumset or the productset of any finite set of real numbers, A, is at least |A|^4/3−ε, improving earlier bounds. Our main tool is a new upper bound on the multiplicative energy, E(A,A).     

Bounding the Elliptic Mahler Measure II

The theory of heights for rational points on arithmetic ellipticcurves is becoming well known. An important fact in the basictheory is the relationship between the naïve and the canonicalheight of a rational point; in fact, they differ by a uniformlybounded amount. The paper provides a generalisation of thisfact from the point of view of heights of polynomials, ratherthan heights of points. This concept is extended to polynomialsin several variables.     

Bounding surface actions on hyperbolic spaces

Given an isometric action of the fundamental group of a closed orientable surface on a δ-hyperbolic space, we find a standard generating set whose translation distances are bounded above in terms of the hyperbolicity constant δ, the genus of the surface, and the injectivity radius of the action, which we assume to be strictly positive.     

极限分析的广义界限定理

本文研究了非连续流动场中,刚塑性介质极限分析完全解的界限问题.提出了一个包括界面条件及间断面条件在内的混合边值问题的广义变分原理,建立了极限载荷乘子的变分解析公式.并证明了一个新的界限定理,其中的场变量将不再受到屈服条件、不可压缩条件等约束的限制.此定理的推论给出了变分解与完全解之间的关系.初步应用表明,对于简单选取的场变量,由本文公式可以得到准确解的较佳界限值,结果具有较好的稳定性.     

Bounding the diameter of distance-regular graphs

LetG be a connected distance-regular graph with valencyk>2 and diameterd, but not a complete multipartite graph. Suppose that is an eigenvalue ofG with multiplicitym and that±k. We prove that bothd andk are bounded by functions ofm. This implies that, ifm>1 is given, there are only finitely many connected, co-connected distance-regular graphs with an eigenvalue of multiplicitym.This work was supported by NSERC grant A5367.