Homomorphisms to oriented cycles

We discuss the existence of homomorphisms to oriented cycles and give, for a special class of cyclesC, a characterization of those digraphs that admit, a homomorphism toC. Our result can be used to prove the multiplicativity of a certain class of oriented cycles, (and thus complete the characterization of multiplicative oriented cycles), as well as to prove the membership of the corresponding decision problem in the classNPcoNP. We also mention a conjecture on the existence of homomorphisms to arbitrary oriented cycles.     

On depth first search strees inm-out digraphs

We consider depth first search (DFS for short) trees in a class of random digraphs: am-out model. Let _i be thei ^th vertex encountered by DFS andL(i, m, n) be the height of _i in the corresponding DFS tree. We show that ifi/n asn, then there exists a constanta(,m), to be defined later, such thatL(i, m, n)/n converges in probability toa(,m) asn. We also obtain results concerning the number of vertices and the number of leaves in a DFS tree.     

Second-order epi-derivatives of integral functionals

Epi-derivatives have many applications in optimization as approached through nonsmooth analysis. In particular, second-order epi-derivatives can be used to obtain optimality conditions and carry out sensitivity analysis. Therefore the existence of second-order epi-derivatives for various classes of functions is a topic of considerable interest. A broad class of composite functions on ⁿ called fully amenable functions (which include general penalty functions composed withC ² mappings, possibly under a constraint qualification) are now known to be twice epi-differentiable. Integral functionals appear widely in problems in infinite-dimensional optimization, yet to date, only integral functionals defined by convex integrands have been shown to be twice epi-differentiable, provided that the integrands are twice epi-differentiable. Here it is shown that integral functionals are twice epi-differentiable even without convexity, provided only that their defining integrands are twice epi-differentiable and satisfy a uniform lower boundedness condition. In particular, integral functionals defined by fully amenable integrands are twice epi-differentiable under mild conditions on the behavior of the integrands.This work was supported in part by the National Science Foundation under grant DMS-9200303.     

Perturbed unstable variational inequalities with unbounded operators on approximately given sets

The stability and convergence of the solutions of perturbed and regularized variational inequality to the solutions of the primary (unstable a priori) variational inequality with proper monotone operator are investigated. All the objects of inequality: the operatorA, the right-hand partf and the set of constrains are to be perturbed. At the same time no assumptions of boundedness and smoothness of the operatorA are used. The connection between the parameters of perturbations, which guarantees strong convergence of approximate solutions, is established. It is proved that the existence of the solution to the unperturbed variational inequality is necessary and sufficient condition for convergence of the regularized perturbed inequality solutions.This research was supported in part by the Ministry of Science Grant 3481-1-91 and by the Ministry of Absorption Center for Absorption in Science.     

Harmonic analysis in infinite dimension

We study the Hermite transform onL ²() where is a Gaussian measure on a Lusin locally convex spaceE. We are then lead to a Hilbert space () of analytic functions onE which is also a natural range for the Laplace transform. LetB be a convenient Hilbert-Schmidt operator on the Cameron-Martin spaceH of . There exists a natural sequence Cap _n of capacities onE associated toB. This implies the Kondratev-Yokoi theorem about positive linear forms on the Hida test-functions space.     

Computational complexity of inner and outerj-radii of polytopes in finite-dimensional normed spaces

This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of ann-dimensional convex polytope in the space ⁿ equipped with an _p norm or a polytopal norm. The polytopeP is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (-presented). The innerj-radius ofP is the radius of a largestj-ball contained inP; it isP's inradius whenj = n and half ofP's diameter whenj = 1. The outerj-radius measures how wellP can be approximated, in a minimax sense, by an (n — j)-flat; it isP's circumradius whenj = n and half ofP's width whenj = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in whichP is centrally symmetric. When the dimensionn is permitted to vary, the situation is roughly as follows: (a) for general -presented polytopes in _p spaces with 1相似文献   

Fibre cycles of holomorphic maps

This and the second part of the paper are to a great extent parts of my thesis [Si] which also appeared as preprint Mathematica Gottingensis 5/92. This work was partly supported by the S7B170 Geometrie und Analysis in Göttingen     

Modular curves and Poncelet polygons

Parts of the results and the essential techniques of this note are taken from the Erlangen thesis (1991) of the second author. They were circulated as Nr. 122 of Schriftenreihe Komplexe Mannigfaltigkeiten. Our research was supported by DFG grant Ba 423/3-3 and the European Science Project Geometry of Algebraic Varieties SCI-0398-C(A)     

Properties of compact complex manifolds carrying closed positive currents

We show that a compact complex manifold is Moishezon if and only if it carries a strictly positive, integral (1, 1)-current. We then study holomorphic line bundles carrying singular hermitian metrics with semi-positive curvature currents, and we give some cases in which these line bundles are big. We use these cases to provide sufficient conditions for a compact complex manifold to be Moishezon in terms of the existence of certain semi-positive, integral (1,1)-currents. We also show that the intersection number of two closed semi-positive currents of complementary degrees on a compact complex manifold is positive when the intersection of their singular supports is contained in a Stein domain. The first author was partially supported by National Science Foundation Grant Nos. DMS-8922760 and DMS-9204273. The second author was partially supported by National Science Foundation Grant Nos. DMS-9001365 and DMS-9204037.     

Rigidity of harmonic maps of maximum rank

Thehomotopical rank of a mapf:M →N is, by definition, min{dimg(M) ¦g homotopic tof}. We give upper bounds for this invariant whenM is compact Kähler andN is a compact discrete quotient of a classical symmetric space, e.g., the space of positive definite matrices. In many cases the upper bound is sharp and is attained by geodesic immersions of locally hermitian symmetric spaces. An example is constructed (Section 9) to show that there do, in addition, exist harmonic maps of quite a different character. A byproduct is construction of an algebraic surface with large and interesting fundamental group. Finally, a criterion for lifting harmonic maps to holomorphic ones is given, as is a factorization theorem for representations of the fundamental group of a compact Kähler manifold. The technique for the main result is a combination of harmonic map theory, algebra, and combinatorics; it follows the path pioneered by Siu in his ridigity theorem and later extended by Sampson.