Morse inequalities for the Koszul complex of multi-persistence

In this paper, we define the homological Morse numbers of a filtered cell complex in terms of relative homology of nested filtration pieces, and derive inequalities relating these numbers to the Betti tables of the multi-parameter persistence modules of the considered filtration. Using the Mayer-Vietoris spectral sequence we first obtain strong and weak Morse inequalities involving the above quantities, and then we improve the weak inequalities achieving a sharp lower bound for homological Morse numbers. Furthermore, we prove a sharp upper bound for homological Morse numbers, expressed again in terms of the Betti tables.     

Bending and stretching unit vector fields in Euclidean and hyperbolic 3-space

We discuss Morse inequalities for homotopic critical maps of the energy functional with a potential term. For a generic potential this gives a lower bound on the number of homotopic critical maps in terms of the Betti numbers of the moduli space of harmonic maps. Other applications include sharp existence results for maps with prescribed tension field and pseudo-harmonic maps. Our hypotheses are that the domain and target manifolds are closed and the latter has non-positive sectional curvature.      

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

ON A BI-HARMONIC EQUATION INVOLVING CRITICAL EXPONENT: EXISTENCE AND MULTIPLICITY RESULTS

In this paper, we consider the problem of existence as well as multiplicity results for a bi-harmonic equation under the Navier boundary conditions: △2 u = K(x)u p , u > 0 in Ω , △u = u = 0 on Ω , where Ω is a smooth domain in R n , n 5, and p + 1 = 2 n n 4 is the critical Sobolev exponent. We obtain highlightly a new criterion of existence, which provides existence results for a dense subset of positive functions, and generalizes Bahri-Coron type criterion in dimension six. Our argument gives also estimates on the Morse index of the obtained solutions and extends some known results. Moreover, it provides, for generic K, Morse inequalities at infinity, which delivers lower bounds for the number of solutions. As further applications of this Morse theoretical approach, we prove more existence results.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Forest covers and a polyhedral intersection theorem

Aforest cover of a graph is a spanning forest for which each component has at least two nodes. We consider the convex hull of incidence vectors of forest covers in a graph and show that this polyhedron is the intersection of the forest polytope and the cover polytope. This polytope has both the spanning tree and perfect matching polytopes as faces. Further, the forest cover polytope remains integral with the addition of the constraint requiring that, for some integerk, exactlyk edges be used in the solution.Research done while thae authors were visiting the Institut für Ökonometrie und Operations Research, Universität Bonn, West Germany.Financial support provided by the Natural Sciences and Engineering Research Council, Canada and the German Research Association (Deutsche Forschungsgemeneinschaft, SFB 303).     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

A new index for polytopes

A new index for convex polytopes is introduced. It is a vector whose length is the dimension of the linear span of the flag vectors of polytopes. The existence of this index is equivalent to the generalized Dehn-Sommerville equations. It can be computed via a shelling of the polytope. The ranks of the middle perversity intersection homology of the associated toric variety are computed from the index. This gives a proof of a result of Kalai on the relationship between the Betti numbers of a polytope and those of its dual. Margaret M. Bayer was supported in part by a National Science Foundation grant, by a Northeastern University Junior Research Fellowship, and by the Institute for Mathematics and Its Applications.     

Facets of the independent path-matching polytope

Cunningham and Geelen introduced the independent path-matching problem as a common generalization of the weighted matching problem and the weighted matroid intersection problem. Associated with an independent path-matching is an independent path-matching vector. The independent path-matching polytope of an instance of the independent path-matching problem is the convex hull of all the independent path-matching vectors. Cunningham and Geelen described a system of linear inequalities defining the independent path-matching polytope. In this paper, we characterize which inequalities in this system induce facets of the independent path-matching polytope, generalizing previous results on the matching polytope and the common independent set polytope.     

The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling Salesman polytope in Cornuéjols, Fonlupt and Naddef (1985). We show here how one can compose facet-inducing inequalities for the graphical traveling salesman polyhedron, and obtain other facet-inducing inequalities. This leads to new valid inequalities for the Symmetric Traveling Salesman polytope. This paper is the first of a series of three papers on the Symmetric Traveling Salesman polytope, the next one studies the strong relationship between that polytope and its graphical relaxation, and the last one applies all the theoretical developments of the two first papers to prove some new facet-inducing results.This work was initiated while the authors were visiting the Department of Statistics and Operations Research of New York University, and continued during several visits of the first author at IASI.     

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.     

Morse–Bott inequalities in the presence of a compact Lie group action and applications

In this paper, we obtain Morse–Bott inequalities in the presence of a compact Lie group action via Bismut–Lebeauʼs analytic localization techniques. As an application, we obtain Morse–Bott inequalities on compact manifold with nonempty boundary by applying the generalized Morse–Bott inequalities to the doubling manifold.     

Topological classification of continuous selections of five linear functions

Continuous selections of linear functions play an important role in Morse theory for piecewise C ²-functions. In this article, the topological properties of continuous selections of linear functions are investigated in detail. These are then utilized to provide a complete classification of all continuous selections of five linear functions. This is done by showing that the first four Betti numbers of a simplicial complex induced by such a function fully determine that function up to topological equivalence. The number of different topological types of continuous selections of linear functions has been known only in the case of four or less selection functions so far. The main result of this article now states that there are exactly 26 different topological types of continuous selections of five linear functions.     

Poincaré-Hopf inequalities for periodic orbits

The interplay between the dynamics of a nonsingular Morse-Smale flow on a smooth, closed, n-dimensional manifold, M, and the topology of M, was exhibited in Franks (Comment Math Helv 53(2):279?C294, 1978), Smale (Bull Am Math Soc 66:43?C49, 1960), by means of a collection of inequalities, which we refer to as Morse-Smale inequalities. These inequalities relate the number of closed orbits of each index to the Betti numbers of M. These well-known inequalities provide the necessary conditions for a given dynamical data in the form of a specified number of closed orbits of a given index to be realized as a nonsingular Morse-Smale flow on M. In this article we provide two inequalities, hereby referred to as Poincaré-Hopf inequalities for periodic orbits, which imposes constraints on the dynamics of periodic orbits without reference to the Betti numbers of the manifold M. The main theorem establishes the necessity and sufficiency of the Poincaré-Hopf inequalities in order for the Morse-Smale inequalities to hold.     

Type Numbers of Critical Points for Nonsmooth Functionals

Type numbers of critical points for Lipschitz functionals are studied. Versions of the Morse inequalities are established; it is shown that the topological index of an isolated critical point is equal to the alternated sum of its type numbers. Formulas for calculating the type numbers of the zero critical point of one functional are given.     

The equipartition polytope. II: Valid inequalities and facets

Theequipartition problem is defined as follows: given a graphG = (V, E) and edge weightsc _e , partition the setV into two sets of 1/2|V| and 1/2|V| nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized.Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we describe some facet inducing inequalities of this polytope.Partial support of NSF grants DMS 8606188 and ECS 8800281.This work was done while these two authors visited IASI, Rome, in Spring 1987.     

Isolating blocks for Morse flows

We present a constructive general procedure to build Morse flows on n-dimensional isolating blocks respecting given dynamical and homological boundary data recorded in abstract Lyapunov semi-graphs. Moreover, we prove a decomposition theorem for handles which, together with a special class of gluings, insures that this construction not only preserves the given ranks of the homology Conley indices, but it is also optimal in the sense that no other Morse flow can preserve this index with fewer singularities.