Geodesic diameter of sets defined by few quadratic equations and inequalities

We prove a bound for the geodesic diameter of a subset of the unit ball in ${\mathbb{R}^n}$ described by a fixed number of quadratic equations and inequalities, which is polynomial in n, whereas the known bound for general degree is exponential in n. Our proof uses methods borrowed from D’Acunto and Kurdyka (to deal with the geodesic diameter) and from Barvinok (to take advantage of the quadratic nature).     

On the stability of sets defined by a finite number of equalities and inequalities

Let a set be defined by a finite number of equalities and inequalities. For smooth data, the condition of Mangasarian and Fromovitz is known to be equivalent to the local stability—in a strong sense—of the set. We study here weaker forms of stability. Namely, we state a condition generalizing the one of Mangasarian and Fromovitz that, for some weak form of stability, is necessary. If the gradients of the equality constraints are linearly independent or if there is no equality constraint, this condition is also sufficient.     

On the topology of semi-algebraic functions on closed semi-algebraic sets

We consider a closed semi-algebraic set ${X \subset \mathbb{R}^n}$ and a C ² semi-algebraic function ${f : \mathbb{R}^n \rightarrow\mathbb{R}}$ such that ${f_{\vert X}}$ has a finite number of critical points. We relate the topology of X to the topology of the sets ${X \cap \{ f * \alpha \}}$ , where ${* \in \{\le,=,\ge \}}$ and ${\alpha \in \mathbb{R}}$ , and the indices of the critical points of ${f_{\vert X}}$ and ${-f_{\vert X}}$ . We also relate the topology of X to the topology of the links at infinity of the sets ${X \cap \{ f * \alpha\}}$ and the indices of these critical points. We give applications when ${X=\mathbb{R}^n}$ and when f is a generic linear function.     

On the number of homotopy types of fibres of a definable map

In this paper we prove a single exponential upper bound on thenumber of possible homotopy types of the fibres of a Pfaffianmap in terms of the format of its graph. In particular, we showthat if a semi-algebraic set SR^m+n, where R is a real closedfield, is defined by a Boolean formula with s polynomials ofdegree less than d, and : R^m+nRⁿ is the projection on a subspace,then the number of different homotopy types of fibres of doesnot exceed s^2(m+1)n(2^m nd)^O(nm). As applications of our mainresults we prove single exponential bounds on the number ofhomotopy types of semi-algebraic sets defined by fewnomials,and by polynomials with bounded additive complexity. We alsoprove single exponential upper bounds on the radii of ballsguaranteeing local contractibility for semi-algebraic sets definedby polynomials with integer coefficients.     

Matrix problems and stable homotopy types of polyhedra

This is a survey of the results on stable homotopy types of polyhedra of small dimensions, mainly obtained by H.-J. Baues and the author [3, 5, 6]. The proofs are based on the technique of matrix problems (bimodule categories). Dedicated to C. M. Ringel.     

Computing roadmaps of semi-algebraic sets on a variety

We consider a semi-algebraic set defined by polynomials in variables which is contained in an algebraic variety . The variety is assumed to have real dimension the polynomial and the polynomials defining have degree at most . We present an algorithm which constructs a roadmap on . The complexity of this algorithm is . We also present an algorithm which, given a point of defined by polynomials of degree at most , constructs a path joining this point to the roadmap. The complexity of this algorithm is These algorithms easily yield an algorithm which, given two points of defined by polynomials of degree at most , decides whether or not these two points of lie in the same semi-algebraically connected component of and if they do computes a semi-algebraic path in connecting the two points.

     

Variable metric gradient projection processes in convex feasible sets defined by nonlinear inequalities

A capture-convergence rate theorem is proved for variable metric gradient projection processes near nonsingular local minimizers in convex feasible sets defined by nonlinear inequalities in a real Hilbert spaceX. The minimizers in question satisfy standard Kuhn-Tucker second-order sufficient conditions for local optimality.Investigation partially supported by National Science Foundation Research Grant No. DMS-85-03746.     

Bounding the number of circuits of a graph

Letc(G) denote the number of circuits of a graphG. In this paper, we characterize those minor-closed classesG of graphs for which there is a polynomial functionp(.) such thatc(G)p(|E(G)|) for all graphsG inG.     

Bounding the number of bases of a matroid

Letb(M) andc(M), respectively, be the number of bases and circuits of a matroidM. For any given minor closed class? of matroids, the following two questions, are investigated in this paper. (1) When is there a polynomial functionp(x) such thatb(M)≤p(c(m)|E(M)|) for every matroidM in?? (2) When is there a polynomial functionp(x) such thatb(M)≤p(|E(M)|) for every matroidM in?? Let us denote byM _Mn the direct sum ofn copies ofU _1,2. We prove that the answer to the first question is affirmative if and only if someM _Mn is not in?. Furthermore, if all the members of? are representable over a fixed finite field, then we prove that the answer to the second question is affirmative if and only if, also, someM _Mn is not in?.     

Bounding the vertex cover number of a hypergraph

For a hypergraphH, we denote by

1. τ(H) the minimumk such that some set ofk vertices meets all the edges,
2. ν(H) the maximumk such that somek edges are pairwise disjoint, and
3. λ(H) the maximumk≥2 such that the incidence matrix ofH has as a submatrix the transpose of the incidence matrix of the complete graphK _k .

We show that τ(H) is bounded above by a function of ν(H) and λ(H), and indeed that if λ(H) is bounded by a constant then τ(H) is at most a polynomial function of ν(H).