Bounding Ramsey numbers through large deviation inequalities

We develop a new approach for proving lower bounds for various Ramsey numbers, based on using large deviation inequalities. This approach enables us to obtain the bounds for the off-diagonal Ramsey numbers R(K^r, K^k), r ≤ k, that match the best known bounds, obtained through the local lemma. We discuss also the bounds for a related Ramsey-type problem and show, for example, that there exists a K⁴-free graph G on n vertices in which every cn^3/5 log^1/2 n vertices span a copy of K³. © 1995 John Wiley & Sons, Inc.     

Sharp Estimates for the Global Attractor of Scalar Reaction–Diffusion Equations with a Wentzell Boundary Condition

In this paper, we derive optimal upper and lower bounds on the dimension of the attractor A_W\mathcal{A}_{\mathrm{W}} for scalar reaction–diffusion equations with a Wentzell (dynamic) boundary condition. We are also interested in obtaining explicit bounds on the constants involved in our asymptotic estimates, and to compare these bounds to previously known estimates for the dimension of the global attractor A_K\mathcal{A}_{K}, K∈{D,N,P}, of reaction–diffusion equations subject to Dirichlet, Neumann and periodic boundary conditions. The explicit estimates we obtain show that the dimension of the global attractor A_W\mathcal {A}_{\mathrm{W}} is of different order than the dimension of A_K\mathcal{A}_{K}, for each K∈{D,N,P}, in all space dimensions that are greater than or equal to three.     

An application of the Lovász–Schrijver <Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">K</Emphasis>) operator to the stable set problem

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.      

Bounds for the Multiplicities of the Irreducible Factors of a Multivariate Polynomial

We provide explicit upper bounds for the multiplicities of the irreducible factors for some classes of polynomials in two variables X, Y over a field K, regarded as polynomials in Y with coefficients in K[X] whose degrees satisfy certain inequalities. We then obtain similar results for polynomials in an arbitrary number of variables over K.     

On exit time from balls of jump-type symmetric Markov processes

We obtain upper and lower bounds of the exit times from balls of a jump-type symmetric Markov process. The proofs are delivered separately. The upper bounds are obtained by using the Levy system corresponding to the process, while the precise expression of the （L^2-）generator of the Dirichlet form associated with the process is used to obtain the lower bounds.     

Some explicit upper bounds for residues of zeta functions of number fields taking into account the behavior of the prime 2

We recall the known explicit upper bounds for the residue at s = 1 of the Dedekind zeta function of a number field K. Then, we improve upon these previously known upper bounds by taking into account the behavior of the prime 2 in K. We finally give several examples showing how such improvements yield better bounds on the absolute values of the discriminants of CM-fields of a given relative class number. In particular, we will obtain a 4,000-fold improvement on our previous bound for the absolute values of the discriminants of the non-normal sextic CM-fields with relative class number one.     

Cache-Oblivious Range Reporting with Optimal Queries Requires Superlinear Space

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space used by any cache-oblivious data structure for these problems that achieves the optimal query bound of O(log  _B N+K/B) block transfers, where K is the size of the query output.     

Quantitative property A, Poincaré inequalities, Lp-compression and Lp-distortion for metric measure spaces

We introduce a quantitative version of Property A in order to estimate the L ^p -compressions of a metric measure space X. We obtain various estimates for spaces with sub-exponential volume growth. This quantitative property A also appears to be useful to yield upper bounds on the L ^p -distortion of finite metric spaces. Namely, we obtain new optimal results for finite subsets of homogeneous Riemannian manifolds. We also introduce a general form of Poincaré inequalities that provide constraints on compressions, and lower bounds on distortion. These inequalities are used to prove the optimality of some of our results.      

On an optimal quadrature formula in the sense of Sard

In this paper we construct an optimal quadrature formula in the sense of Sard in the Hilbert space K ₂(P ₂). Using S.L. Sobolev’s method we obtain new optimal quadrature formula of such type and give explicit expressions for the corresponding optimal coefficients. Furthermore, we investigate order of the convergence of the optimal formula and prove an asymptotic optimality of such a formula in the Sobolev space L₂⁽²⁾(0,1)L_2^{(2)}(0,1). The obtained optimal quadrature formula is exact for the trigonometric functions sinx and cosx. Also, we include a few numerical examples in order to illustrate the application of the obtained optimal quadrature formula.     

Global optima results for the Kauffman NK model

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N−1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.     

Quasi-Norm interpolation error estimates for the piecewise linear finite element approximation of p-Laplacian problems

Summary. In this work, new interpolation error estimates have been derived for some well-known interpolators in the quasi-norms. The estimates are found to be essential to obtain the optimal a priori error bounds under the weakened regularity conditions for the piecewise linear finite element approximation of a class of degenerate equations. In particular, by using these estimates, we can close the existing gap between the regularity required for deriving the optimal error bounds and the regularity achievable for the smooth data for the 2-d and 3-d p-Laplacian.Mathematics Subject Classification (1991): 65N30     

Sensitivity analysis of nondifferentiable sums of singular values of rectangular matrices

Let K(x) be an s-by-r rectangular matrix depending on a parameter x ε E and denote by g(x) the sum of its m largest singular values (1 ≤ m ≤ Min{s,r}). If K(x) depends affinely on x, then g is a nondifferentiable convex function. In this paper we consider first the affine case and give some formulas for the conjugate, subdifferential, and ε-subdifferential of g. These formulas are then used to obtain perturbation bounds for g(x). We study next the nonaffine case and discuss some questions related with the regularity, generalized subdifferentiability, and directional differentiability of g.     

Finite element approximation of a semilinear elliptic problem with a singular nonlinearity

Given , we consider the following problem: find , such that where or 3, and in . We prove and error bounds for the standard continuous piecewise linear Galerkin finite element approximation with a (weakly) acute triangulation. Our bounds are nearly optimal. In addition, for d = 1 and 2 and we analyze a more practical scheme involving numerical integration on the nonlinear term. We obtain nearly optimal and error bounds for d = 1. For this case we also present some numerical results. Received July 4, 1996 / Revised version received December 18, 1997     

An average discrepancy for optimal vertex‐modified number‐theoretic rules

Number‐theoretic rules are particularly suited for the approximation of multidimensional integrals in which the integrands are periodic. When the integrands are not periodic, then a vertex‐modified variant has been proposed. Error bounds for such vertex‐modified rules may be obtained in terms of the L ₂ discrepancy. In s dimensions these vertex‐modified rules contain 2^s weights which may be chosen optimally so that the discrepancy is minimized. We obtain an expression for the squared L ₂ discrepancy of optimal vertex‐modified rules. This expression is used to derive an expression for the average of the squared L ₂ discrepancy for optimal vertex‐modified number‐theoretic rules. Values of this average are then compared with the corresponding average for normal number‐theoretic rules and the expected value for Monte Carlo rules. This revised version was published online in June 2006 with corrections to the Cover Date.     

Singular values, quasiconformal maps and the Schottky upper bound

Some properties and asymptotically sharp bounds are obtained for singdar values of Ramanujan’s generalized modular equation. from which infinite-product representations of the Hersch-Pfluger ϕdimtortion function ϕ _K (r) and the Agard η-distortion function η _K (t) follow. By these results, the explicit quasiconformal Schwan lemma is improved, several properties are obtained for the Schottky upper bound, and a conjecture on the linear distortion function λ (K) is proved to be true.     

Optimale Fehlerabschätzungen mit dualen Funktionalen bei semilinearen Randwertaufgaben gewöhnlicher Differentialgleichungen

In Shampine [7] it is shown how to obtain variational error bounds for approximate solutions of boundary value problems for semilinear ordinary differential equations. These bounds are depending on a certain constantK, the existence of which is assumed. Our paper aims at practical computation; in order to get applicableL _∞-error bounds,K has to be computed explicitly. Using Gårding's inequality, we obtainK=K(?) depending on a positive parameter ?. In order to make these bounds efficient,K(?) will be optimized. In application only the maximal zeros of three polynomials have to be computed. Some numerical examples are given to compare the error bounds with the actual errors.     

Empty Simplices of Polytopes and Graded Betti Numbers

The conjecture of Kalai, Kleinschmidt, and Lee on the number of empty simplices of a simplicial polytope is established by relating it to the first graded Betti numbers of the polytope and applying a result of Migliore and the author. This approach allows us to derive explicit optimal bounds on the number of empty simplices of any given dimension. As a key result, we prove optimal bounds for the graded Betti numbers of any standard graded K-algebra in terms of its Hilbert function.     

On the mean number of normals through a point in the interior of a convex body

Recently, Kathy Hann established bounds on the average number of normals through a point in a convex bodyK, in the cases whereK is either a polytope or sufficiently smooth. In addition, an Euler-type theorem was obtained for these particular classes of convex bodies. In the present work we show that all these statements are true for an arbitrary convex bodyK. For this purpose measure geometric tools and a general approximation technique will be essential.     

Über die Führer von Gaußschen Summen als Größencharaktere

Let K be an absolute abelian number field. The conductor of the Hecke characters of K formed by Gaussian sums is investigated. In some cases we obtain formulas for this conductor while in others a bound is given. These enable us to obtain a general upper bound for the conductor in terms of the class field theoretic conductor of K. Our bound is an improvement on existing bounds in the literature.     

One‐factorizations of complete graphs with vertex‐regular automorphism groups

We consider one‐factorizations of K_2n possessing an automorphism group acting regularly (sharply transitively) on vertices. We present some upper bounds on the number of one‐factors which are fixed by the group; further information is obtained when equality holds in these bounds. The case where the group is dihedral is studied in some detail, with some non‐existence statements in case the number of fixed one‐factors is as large as possible. Constructions both for dihedral groups and for some classes of abelian groups are given. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 1–16, 2002