Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

On a kind of integrals of empirical processes concerning insurance risk

This paper proves the strong consistence and the central limit theorems for empirical right tail deviations.     

Vector Equilibrium Problems Under Asymptotic Analysis

Given a closed convex set K in Rⁿ; a vector function F:K×K R^m; a closed convex (not necessarily pointed) cone P(x) in ^m with non-empty interior, PP(x) Ø, various existence results to the problemfind xK such that F(x,y)- int P(x) y K under P(x)-convexity/lower semicontinuity of F(x,) and pseudomonotonicity on F, are established. Moreover, under a stronger pseudomonotonicity assumption on F (which reduces to the previous one in case m=1), some characterizations of the non-emptiness of the solution set are given. Also, several alternative necessary and/or sufficient conditions for the solution set to be non-empty and compact are presented. However, the solution set fails to be convex in general. A sufficient condition to the solution set to be a singleton is also stated. The classical case P(x)=^m ₊ is specially discussed by assuming semi-strict quasiconvexity. The results are then applied to vector variational inequalities and minimization problems. Our approach is based upon the computing of certain cones containing particular recession directions of K and F.     

Large Deviation Principle for Additive Functionals of Brownian Motion Corresponding to Kato Measures

Let (B _t ,P ^W _x ) be the Brownian motion. Let be a Radon measure in the Kato class and A _t the additive functional associated with . We prove that A _t /t obeys the large deviation principle.     

Certain extremal problems for polynomials

Extensions of two classical results about polynomials, one due to W. Markov and the other due to Duffin and Schaeffer, are obtained in this paper. An interesting result of S. Bernstein, which went unnoticed until it was rediscovered by P. Erdos, years later, is also generalized. Our results are especially amenable to numerical calculations, and may, therefore, be of some practical importance.

     

A version of Burkholder's theorem for operator-weighted spaces

Let be an operator weight, i.e. a weight function taking values in the bounded linear operators on a Hilbert space . We prove that if the dyadic martingale transforms are uniformly bounded on for each dyadic grid in , then the Hilbert transform is bounded on as well, thus providing an analogue of Burkholder's theorem for operator-weighted -spaces. We also give a short new proof of Burkholder's theorem itself. Our proof is based on the decomposition of the Hilbert transform into ``dyadic shifts'.

     

Variational representations of Varadhan functionals

Motivated by the theory of large deviations, we introduce a class of non-negative non-linear functionals that have a variational ``rate function" representation.

     

Bilinear estimates and applications to 2d NLS

The three bilinearities for functions are sharply estimated in function spaces associated to the Schrödinger operator . These bilinear estimates imply local wellposedness results for Schrödinger equations with quadratic nonlinearity. Improved bounds on the growth of spatial Sobolev norms of finite energy global-in-time and blow-up solutions of the cubic nonlinear Schrödinger equation (and certain generalizations) are also obtained.

     

Uniformly More Powerful, Two-Sided Tests for Hypotheses about Linear Inequalities

Let Xhave a multivariate, p-dimensional normal distribution (p 2) with unknown mean and known, nonsingular covariance . Consider testing H ₀ : b _i 0, for some i = 1,..., k, and b _i 0, for some i = 1,..., k, versus H ₁ : b _i < 0, for all i = 1,..., k, or b _i < 0, for all i = 1,..., k, where b ₁,..., b _k , k 2, are known vectors that define the hypotheses and suppose that for each i = 1,..., k there is an j {1,..., k} (j will depend on i) such that b _i b _j 0. For any 0 < < 1/2. We construct a test that has the same size as the likelihood ratio test (LRT) and is uniformly more powerful than the LRT. The proposed test is an intersection-union test. We apply the result to compare linear regression functions.     

Inequalities for the gamma function

We prove the following two theorems:

(i) Let be the th power mean of and . The inequality

holds for all if and only if , where denotes Euler's constant. This refines results established by W. Gautschi (1974) and the author (1997).

(ii) The inequalities

are valid for all if and only if and , while holds for all if and only if and . These bounds for improve those given by G. D. Anderson an S.-L. Qiu (1997).