Symmetries of flat rank two distributions and sub-Riemannian structures

Flat sub-Riemannian structures are local approximations -- nilpotentizations -- of sub-Riemannian structures at regular points. Lie algebras of symmetries of flat maximal growth distributions and sub-Riemannian structures of rank two are computed in dimensions 3, 4, and 5.

     

On extensions of sub-Riemannian structures on Lie groups

We define the extension of a left-invariant sub-Riemannian structure in terms of an extension of the underlying Lie group and compatibility of the respective distributions and metrics. We show that geodesics of a structure can be lifted to geodesics of any extension of the structure. In the case of central extensions, we show that the normal geodesics of the minimal extension are the projection (in a sense) of the normal geodesics of any other compatible extension. Several illustrative examples are discussed.     

Mass transportation and rough curvature bounds for discrete spaces

We introduce and study rough (approximate) lower curvature bounds for discrete spaces and for graphs. This notion agrees with the one introduced in [J. Lott, C. Villani, Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math. 169 (2009), in press] and [K.T. Sturm, On the geometry of metric measure spaces. I, Acta Math. 196 (2006) 65-131], in the sense that the metric measure space which is approximated by a sequence of discrete spaces with rough curvature ?K will have curvature ?K in the sense of [J. Lott, C. Villani, Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math. 169 (2009), in press; K.T. Sturm, On the geometry of metric measure spaces. I, Acta Math. 196 (2006) 65-131]. Moreover, in the converse direction, discretizations of metric measure spaces with curvature ?K will have rough curvature ?K. We apply our results to concrete examples of homogeneous planar graphs.     

Asymptotic analysis of the optimal cost in some transportation problems with random locations

In this paper we provide an asymptotic analysis of the optimal transport cost in some matching problems with random locations. More precisely, under various assumptions on the distribution of the locations and the cost function, we prove almost sure convergence, and large and moderate deviation principles. In general, the rate functions are given in terms of infinite-dimensional variational problems. For a suitable one-dimensional transportation problem, we provide the expression of the large deviation rate function in terms of a one-dimensional optimization problem, which allows the numerical estimation of the rate function. Finally, for certain one-dimensional transportation problems, we prove a central limit theorem.     

Optimal conditioning in the convex class of rank two updates

Davidon's new quasi-Newton optimization algorithm selects the new inverse Hessian approximation at each step to be the optimally conditioned member of a certain one-parameter class of rank two updates to the last inverse Hessian approximationH. In this paper we show that virtually the same goals of conditioning can be achieved while restricting to the convex class of updates, which are bounded by the popular DFP and BFGS updates. This suggests the computational testing of alternatives to the optimal conditioning strategy.This research supported by NSF grant 73-03413, contract P04361 of the National Bureau of Economic Research, Cambridge, Massachusetts, and a National Science Foundation Graduate Fellowship, forms a portion of the author's doctoral thesis at Cornell University directed by Professor J.E. Dennis.     

The value function of a transportation problem

We investigate the value of an optimal transportation problem with the maximization objective as a function of costs and vectors of production and consumption. The value is concave in production. For generic costs, the numbers of linearity domains and peak points are independent of costs and consumption. The peak points are determined by an auxiliary assignment problem. The volumes of the linearity domains are independent of costs while their dependence on consumption can be expressed via the multinomial distribution.     

Optimal makespan schedule for three jobs on two machines

This paper deals with the problem of scheduling three jobs on two machines in order to minimize the makespan, when operation preemptions are forbidden and routes are fixed and may vary per job. It is shown that this problem can be solved by anO(r ⁴) algorithm, wherer is the maximal number of operations per job. Supported by Belarussian Fundamental Research Found, Project Φ60–242, and Deutsche Forschungsgemeinschaft, Project ScheMA     

Mass transportation proofs of free functional inequalities, and free Poincaré inequalities

This work is devoted to direct mass transportation proofs of families of functional inequalities in the context of one-dimensional free probability, avoiding random matrix approximation. The inequalities include the free form of the transportation, Log-Sobolev, HWI interpolation and Brunn-Minkowski inequalities for strictly convex potentials. Sharp constants and some extended versions are put forward. The paper also addresses two versions of free Poincaré inequalities and their interpretation in terms of spectral properties of Jacobi operators. The last part establishes the corresponding inequalities for measures on R₊ with the reference example of the Marcenko-Pastur distribution.     

Homomorphisms of matrix semigroups over division rings from dimension two to four

Let D be an arbitrary division ring and M_n(D) the multiplicative semigroup of all n×n matrices over D. We study non-degenerate, injective homomorphisms from M₂(D) to M₄(D). In particular, we present a structural result for the case when D is the ring of quaternions.     

Dirichlet regularity in arbitrary o‐minimal structures on the field ℝ up to dimension 4

In this article we show that the set of Dirichlet regular boundary points of a bounded domain of dimension up to 4, definable in an arbitrary o‐minimal structure on the field ?, is definable in the same structure. Moreover we give estimates for the dimension of the set of non‐regular boundary points, depending on whether the structure is polynomially bounded or not. This paper extends the results from the author's Ph.D. thesis [6, 7] where the problem was solved for polynomially bounded o‐minimal structures expanding the real field. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stability of two player game structures

We have extended a two player game-theoretical model proposed by V. Gurvich [To theory of multi-step games, USSR Comput. Math and Math. Phys. 13 (1973)] and H. Moulin [The Strategy of Social Choice, North Holland, Amsterdam, 1983]: All the considered game situations are framed by the same game structure. The structure determines the families of potential decisions of the two players, as well as the subsets of possible outcomes allowed by pairs of such choices. To be a solution of a game, a pair of decisions has to determine a (pure) functional equilibrium of the situational pair of payoff mappings which transforms the realized outcome into real-valued rewards of the players. Accordingly we understand that a structure is stable, if it admits functional equilibria for all possible game situations; and that it is complete, if every situation that only partitions the potential outcomes, is dominated by one of the players. We have generalized and strengthened a theorem by V. Gurvich [Equilibrium in pure strategies, Soviet Math. Dokl. 38 (1989)], proving that a proper structure is stable iff it is complete. Additional results provide game-theoretical insight that focuses the inquiry on the complexity of the stability decision problem; in particular, for coherent structures.These results also have combinatorial importance because every structure is characterized by a pair of hypergraphs [C. Berge, Graphes et Hypergraphes, Dunod, 1970] over a common ground set. The structure is dual (complete/coherent) iff the clutter of one hypergraph equals (includes/is included in) the blocker of the other one. So, for non-void coherent structures, the stability decision problem is equivalent to the much studied subexponential [M.L. Fredman, L. Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996)] hypergraph duality decision problem.     

On the existence of dual solutions for Lorentzian cost functions

The dual problem of optimal transportation in Lorentz-Finsler geometry is studied. It is shown that in general no solution exists even in the presence of an optimal coupling. Under natural assumptions dual solutions are established. It is further shown that the existence of a dual solution implies that the optimal transport is timelike on a set of full measure. In the second part the persistence of absolute continuity along an optimal transportation under obvious assumptions is proven and a solution to the relativistic Monge problem is provided.     

A note on the regularity of the free boundaries in the optimal partial transport problem

In this work we study the global regularity of the free boundaries arising in the optimal partial transport problem. Assuming the supports of both the source and the target measure to be convex, we show that the free boundaries of the active regions are globally C ^0,1/2.      

Linear groups with rank restrictions on the subgroups of infinite central dimension

The authors study linear groups of infinite central dimension and of infinite p-rank all of whose proper subgroups of infinite p-rank are of finite central dimension.     

Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two

In the paper we study the algorithmic nature of some “simple” fragments of positive theories with “few” constants for free noncyclic semigroups. Translated fromMatematicheskie Zametki, Vol. 67, No. 2, pp. 191–200, February, 2000.     

Searching for mobile intruders in circular corridors by two 1-searchers

We consider the problem of searching for a mobile intruder in a circular corridor by two mobile searchers, who hold one flashlight. A circular corridor is a polygon with one polygonal hole such that its outer and inner boundaries are mutually weakly visible. Both 1-searchers always direct their flashlights at the inner boundary. The objective is to decide whether there exists a search schedule for two 1-searchers to detect the intruder, no matter how fast he moves, and if so, generate a search schedule. We give a characterization of the circular corridors, which are searchable by two 1-searchers. Based on our characterization, an O(nlogn) time algorithm is then presented to determine the searchability of a circular corridor, where n denotes the total number of vertices of the outer and inner boundaries. Moreover, a search schedule can be reported in time linear in its size, if it exists.