Transience and capacity of minimal submanifolds

We prove explicit lower bounds for the capacity of annular domains of minimal submanifolds P ^m in ambient Riemannian spaces N ⁿ with sectional curvatures bounded from above. We characterize the situations in which the lower bounds for the capacity are actually attained. Furthermore we apply these bounds to prove that Brownian motion defined on a complete minimal submanifold is transient when the ambient space is a negatively curved Hadamard-Cartan manifold. The proof stems directly from the capacity bounds and also covers the case of minimal submanifolds of dimension m > 2 in Euclidean spaces.     

Conditional extremals in complete Riemannian manifolds

Conditional extremal curves in a complete Riemannian manifold M are defined as the critical points of the squared L² distance between the tangent vector field of a curve and a so-called prior vector field. We prove that this L² distance satisfies the Palais-Smale condition on the space of absolutely continuous curves joining two submanifolds of M, and thus establish the existence of critical points. We also prove a Morse index theorem in the case where the two submanifolds are single points, and use the Morse inequalities to place lower bounds on the number of critical points of each index.     

Tail dependence between order statistics

In this work, we introduce the s,k-extremal coefficients for studying the tail dependence between the s-th lower and k-th upper order statistics of a normalized random vector. If its margins have tail dependence then so do their order statistics, with the strength of bivariate tail dependence decreasing as two order statistics become farther apart. Some general properties are derived for these dependence measures which can be expressed via copulas of random vectors. Its relations with other extremal dependence measures used in the literature are discussed, such as multivariate tail dependence coefficients, the coefficient η of tail dependence, coefficients based on tail dependence functions, the extremal coefficient ?, the multivariate extremal index and an extremal coefficient for min-stable distributions. Several examples are presented to illustrate the results, including multivariate exponential and multivariate Gumbel distributions widely used in applications.     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free

A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.     

New lower bounds for Hopcroft's problem

We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in $\mathbb{R}^d $ , is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n ^2/3m^2/3 + m logn) in two dimensions, or Ω(n logm + n ^5/6m^1/2 + n^1/2m^5/6 + m logn) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log^*(n+m)) of the best known upper bound, due to Matou?ek. Previously, the best known lower bound, in any dimension, was Ω(n logm + m logn). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called amonochromatic cover, and derive lower bounds on its size in the worst case. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover. As a related result, using a straightforward adversary argument, we derive aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.     

On a conjecture of Murty and Simon on diameter 2-critical graphs

A graph G is diameter 2-critical if its diameter is two, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.     

Nodal volumes for eigenfunctions of analytic regular elliptic problems

We establish sharp upper bounds on the (n−1)-dimensional Hausdorff measure of the zero (nodal) sets and on the maximal order of vanishing corresponding to eigenfunctions of a regular elliptic problem on a bounded domain Ω ⊆ ℝ ⁿ with real-analytic boundary. The elliptic operator may be of an arbitrary even order, and its coefficients are assumed to be real-analytic. This extends a result of Donnelly and Fefferman ([DF1], [DF3]) concerning upper bounds for nodal volumes of eigenfunctions corresponding to the Laplacian on compact Riemannian manifolds with boundary.     

On extremal problems on classes of functions defined by integral moduli of continuity

We obtain lower bounds for solutions of some extremal problems on classes of functions W ^rH₁^ω with integral modulus of continuity ω(t). Some of these bounds are regarded as exact. Dneprodzerzhinsk Technical University, Dneprodzerzhinsk. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 11. pp. 1499–1503, November, 1997.     

On the smallest sets blocking simple perfect matchings in a convex geometric graph

In this paper we present a complete characterization of the smallest sets which block all the simple perfect matchings in a complete convex geometric graph on 2m vertices. In particular, we show that all these sets are caterpillar graphs with a special structure, and that their total number is m·2 ^m−1.     

Capturing the multivariate extremal index: bounds and interconnections

The multivariate extremal index function is a direction specific extension of the well-known univariate extremal index. Since statistical inference on this function is difficult it is desirable to have a broad characterization of its attributes. We extend the set of common properties of the multivariate extremal index function and derive sharp bounds for the entire function given only marginal dependence. Our results correspond to certain restrictions on the two dependence functions defining the multivariate extremal index, which are opposed to Smith and Weissman’s (1996) conjecture on arbitrary dependence functions. We show further how another popular dependence measure, the extremal coefficient, is closely related to the multivariate extremal index. Thus, given the value of the former it turns out that the above bounds may be improved substantially. Conversely, we specify improved bounds for the extremal coefficient itself that capitalize on marginal dependence, thereby approximating two views of dependence that have frequently been treated separately. Our results are completed with example processes.      

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

A classification of invariant distributions and convergence of imprecise Markov chains

We analyse the structure of imprecise Markov chains and study their convergence by means of accessibility relations. We first identify the sets of states, so-called minimal permanent classes, that are the minimal sets capable of containing and preserving the whole probability mass of the chain. These classes generalise the essential classes known from the classical theory. We then define a class of extremal imprecise invariant distributions and show that they are uniquely determined by the values of the upper probability on minimal permanent classes. Moreover, we give conditions for unique convergence to these extremal invariant distributions.     

The Rate of Convergence of Finite-Difference Approximations for Bellman Equations with Lipschitz Coefficients

We consider parabolic Bellman equations with Lipschitz coefficients. Error bounds of order h^1/2 for certain types of finite-difference schemes are obtained.     

On the measurable chromatic number of a space of dimension n ≤ 24

This paper is devoted to the classical problem of finding the measurable chromatic number of n-dimensional Euclidean space, i.e., the value χ _m (? ⁿ ) equal to the least possible number of Lebesgue measurable sets that do not contain pairs of points at a distance of 1 and cover the whole space. Assuming that a certain hypothesis is true, we significantly improve the lower bounds for χ _m (? ⁿ ).     

Optimal cubature formulas on compact homogeneous manifolds

We find lower bounds for the rate of convergence of optimal cubature formulas on sets of differentiable functions on compact homogeneous manifolds of rank I or two-point homogeneous spaces. It is shown that these lower bounds are sharp in the power scale in the case of S², the unit sphere in R³.     

Application of the problem of moments to derive bounds on integrals with integral constraints

Recently a lot of results (for a review see Goovaerts et al. (1983)) have been obtained for bounds on stop-loss premiums in case of incomplete information on the claim distribution.As a consequence some extremal distributions (depending on the retention limit) have been characterized. The extremal distributions for the stop-loss ordering in case of fixed values of the retention limit are obtained by means of deep results from the theory of convex analysis. In the present contribution it is shown, by means of some results from the problem of moments, how bounds on integrals with integral constraints can be obtained. We assume only the knowledge of the moments μ₀, μ₁, …, μ_n.     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.