Monotonicity on nonuniform grids

In this paper we study a class of numerical methods used to solve two-point boundary value problems on nonuniform grids. Particular attention is devoted to positive solutions, i.e. conditions under which the solutions of the problem are positive. Applications to steady states of air pollution problems are also referred to.     

Geodesics on the regular tetrahedron and the cube

Consider all geodesics between two given points on a polyhedron. On the regular tetrahedron, we describe all the geodesics from a vertex to a point, which could be another vertex. Using the Stern–Brocot tree to explore the recursive structure of geodesics between vertices on a cube, we prove, in some precise sense, that there are twice as many geodesics between certain pairs of vertices than other pairs. We also obtain the fact that there are no geodesics that start and end at the same vertex on the regular tetrahedron or the cube.     

Monotonicity preservation on triangles

It is well known that Bernstein polynomials on triangles preserve monotonicity. In this paper we define and study three kinds of monotonicity preservation of systems of bivariate functions on a triangle. We characterize and compare several of these systems and derive some geometric applications.

     

Monotonicity and the principle of optimality

This paper explores some of the theoretical and algorithmic implications of the fact that the Monotonicity Assumption does not ensure either the validity of the Principle of Optimality or the discovery of all optimal solutions in finite dynamic programs, even though it is sufficient to ensure the validity of the functional equations. A slightly stronger assumption is introduced to resolve these problems. Our analysis is illustrated with some extremely simple examples.     

Monotonicity and independence axioms

Given σ, a family ofchoice problems, subsets ofR ⁿ representing the payoff vectors (measured in von Neumann-Morgenstern utility scales) attainable by a group ofn players, asolution f on σ associates to everyS in σ a unique elementf (S) ofS. Amonotonicity axiom specifies how the solution outcome should change when the choice problem is subjected to certain geometric transformations while anindependence axiom requires, in similar circumstances, the invariance of the solution outcome. A number of such axioms are here formulated and the logical relationships among them are established.Strong monotonicity is shown to be the strongest axiom and strongly monotonic solutions are characterized.     

On concentration of measure on the cube

Concentration property of the uniform distribution on the cube is considered for the class of permutation invariant sets. Bibliography: 10 titles.     

Concentration of measures supported on the cube

We prove a log-Sobolev inequality for a certain class of log-concave measures in high dimension. These are the probability measures supported on the unit cube [0, 1] ⁿ ? ? ⁿ whose density takes the form exp(?ψ), where the function ψ is assumed to be convex (but not strictly convex) with bounded pure second derivatives. Our argument relies on a transportation-cost inequality á la Talagrand.     

Monotonicity and Market Equilibrium

Economic theory relates prices to quantities via ” market curves.” Typically, such curves are monotone, hence they admit functional representations. The latter invoke linear pricing of quantities so as to obtain market values. Specifically, if higher prices call forward greater supply, a convex function, bounded below by market values, represents the resulting supply curve. Likewise, if demand decreases at higher prices, a concave function, bounded above by market values, represents the attending demand curve. In short, grantedmonotonicity, market curves are described by bivariate functions, either convex or concave, appropriately bounded by linear valuations of quantities. The bounding supply (demand) function generates ask (resp. bid)valuations. Exchange and trade, as modelled here, are driven by valuation differentials, called bid-ask spreads. These disappear, and market equilibrium prevails, if all ”inverse market curves” intersect in a common price. A main issue is whether and how market agents, by themselves, may reach such equilibrium. The paper provides positive and constructive answers. As vehicle it contends with bilateral transactions.     

Rainbow coloring the cube

We prove that for d ≥ 4, d ≠ 5, the edges of the d-dimensional cube can be colored by d colors so that all quadrangles have four distinct colors. © 1993 John Wiley & Sons, Inc.     

Duplicating the cube and functional equations

In the present paper we consider a system of equations (1), (2) introduced in [2] in connection with the ancient Greek problem of duplicating the cube. We prove also some results in the case of a restricted domain, namely, if y = 2x:.¹     

Decomposition and approximation of multivariate functions on the cube

In this paper, we present a decomposition method of multivariate functions. This method shows that any multivariate function f on [0, 1]d is a finite sum of the form ∑jφjψj , where each φj can be extended to a smooth periodic function, each ψj is an algebraic polynomial, and each φjψj is a product of separated variable type and its smoothness is same as f . Since any smooth periodic function can be approximated well by trigonometric polynomials, using our decomposition method, we find that any smooth multivariate function on [0, 1]d can be approximated well by a combination of algebraic polynomials and trigonometric polynomials. Meanwhile, we give a precise estimate of the approximation error.     

Embeddings on a boolean cube

In this paper, we characterize a class of graphs which can be embedded on a boolean cube. Some of the graphs in this class are identified with the well known graphs such asmulti-dimensional mesh of trees, tree of meshes, etc. We suggest (i) an embedding of anr-dimensional mesh of trees ofn ^r (r+1)–rn ^r–1 nodes on a boolean cube of (2n) ^r nodes, and (ii) an embedding of a tree of meshes with 2n ² logn+n ² nodes on a boolean cube withn ² exp₂ (log (2 logn+1)]) nodes.     

A class of graph-geodetic distances generalizing the shortest-path and the resistance distances

A new class of distances for graph vertices is proposed. This class contains parametric families of distances which reduce to the shortest-path, weighted shortest-path, and the resistance distances at the limiting values of the family parameters. The main property of the class is that all distances it comprises are graph-geodetic: d(i,j)+d(j,k)=d(i,k) if and only if every path from i to k passes through j. The construction of the class is based on the matrix forest theorem and the transition inequality.     

Monotonicity and the Expressibility of NP Operators

We investigate why similar extensions of first-order logic using operators (that is, generalized quantifiers) corresponding to NP-complete decision problems apparently differ in expressibility: the logics capture either NP or L^NP. It had been conjectured that the complexity class captured is NP if and only if the operator is monotone. We show that this conjecture is false. However, we provide evidence supporting a revised conjecture involving finite variations of monotone problems. Mathematics Subject Classification: 68Q15, 03D15, 03C13.     

Monotonicity and unimodality of the pattern inventory

It is shown that the Kostka numbers respect a natural partial order (reverse domination) on the integer partitions. It is then proved that the number of Pólya patterns with a given weight also respects this order. Immediate consequences include the unimodality of the number of graphs with n vertices and k edges and the unimodality of the coefficients of the expansion of the Gaussian coefficient $\text{m+n}\text{n}$.     

Hamming cube and martingales

In the present paper, we show that a correctly chosen Legendre transform of the Bellman functions of martingale problems give us the right tool to prove isoperimetric inequalities on Hamming cube independent of the dimension. We illustrate the power of this “dual function approach” by proving certain Poincaré inequalities on Hamming cube and by improving a particular inequality of Beckner on the Hamming cube.