Disjunctive Optimization: Critical Point Theory

In this paper, we introduce the concepts of (nondegenerate) stationary points and stationary index for disjunctive optimization problems. Two basic theorems from Morse theory, which imply the validity of the (standard) Morse relations, are proved. The first one is a deformation theorem which applies outside the stationary point set. The second one is a cell-attachment theorem which applies at nondegenerate stationary points. The dimension of the cell to be attached equals the stationary index. Here, the stationary index depends on both the restricted Hessian of the Lagrangian and the set of active inequality constraints. In standard optimization problems, the latter contribution vanishes.     

Morse theory for periodic solutions of hamiltonian systems and the maslov index

In this paper we prove Morse type inequalities for the contractible 1-periodic solutions of time dependent Hamiltonian differential equations on those compact symplectic manifolds M for which the symplectic form and the first Chern class of the tangent bundle vanish over π₂ (M). The proof is based on a version of infinite dimensional Morse theory which is due to Floer. The key point is an index theorem for the Fredholm operator which plays a central role in Floer homology. The index formula involves the Maslov index of nondegenerate contractible periodic solutions. This Maslov index plays the same role as the Morse index of a nondegenerate critical point does in finite dimensional Morse theory. We shall use this connection between Floer homology and Maslov index to establish the existence of infinitely many periodic solutions having integer periods provided that every 1-periodic solution has at least one Floquet multiplier which is not equal to 1.     

Spectral Flow,Maslov Index and Bifurcation of Semi-Riemannian Geodesics

We give a functional analytical proof of the equalitybetween the Maslov index of a semi-Riemannian geodesicand the spectral flow of the path of self-adjointFredholm operators obtained from the index form. This fact, together with recent results on the bifurcation for critical points of strongly indefinite functionals imply that each nondegenerate and nonnull conjugate (or P-focal)point along a semi-Riemannian geodesic is a bifurcation point.In particular, the semi-Riemannian exponential map is notinjective in any neighborhood of a nondegenerate conjugate point,extending a classical Riemannian result originally due to Morse and Littauer.     

Tverberg's theorem with constraints

The topological Tverberg theorem claims that for any continuous map of the (q−1)(d+1)-simplex σ(d+1)(q−1) to Rd there are q disjoint faces of σ(d+1)(q−1) such that their images have a non-empty intersection. This has been proved for affine maps, and if q is a prime power, but not in general.We extend the topological Tverberg theorem in the following way: Pairs of vertices are forced to end up in different faces. This leads to the concept of constraint graphs. In Tverberg's theorem with constraints, we come up with a list of constraints graphs for the topological Tverberg theorem.The proof is based on connectivity results of chessboard-type complexes. Moreover, Tverberg's theorem with constraints implies new lower bounds for the number of Tverberg partitions. As a consequence, we prove Sierksma's conjecture for d=2 and q=3.     

Line partitions of internal points to a conic in <Emphasis Type="Italic">PG</Emphasis>(2,<Emphasis Type="Italic">q</Emphasis>)

All sets of lines providing a partition of the set of internal points to a conic C in PG(2,q), q odd, are determined. There exist only three such linesets up to projectivities, namely the set of all non-tangent lines to C through an external point to C, the set of all non-tangent lines to C through a point in C, and, for square q, the set of all non-tangent lines to C belonging to a Baer subplane PG(2,√q) with √q+1 common points with C. This classification theorem is the analogous of a classical result by Segre and Korchmáros [9] characterizing the pencil of lines through an internal point to C as the unique set of lines, up to projectivities, which provides a partition of the set of all non-internal points to C. However, the proof is not analogous, since it does not rely on the famous Lemma of Tangents of Segre which was the main ingredient in [9]. The main tools in the present paper are certain partitions in conics of the set of all internal points to C, together with some recent combinatorial characterizations of blocking sets of non-secant lines, see [2], and of blocking sets of external lines, see [1].     

Blocking Sets Of External Lines To A Conic In PG(2,q), q ODD

We determine all point-sets of minimum size in PG(2,q), q odd that meet every external line to a conic in PG(2,q). The proof uses a result on the linear system of polynomials vanishing at every internal point to the conic and a corollary to the classification theorem of all subgroups of PGL(2,q). * Research supported by the Italian Ministry MURST, Strutture geometriche, combinatoria e loro applicazioni and by the Hungarian-Italian Intergovernemental project “Algebraic and Geometric Structures”.     

Morse theory for analytic functions on surfaces

In this paper we deal with analytic functions defined on a compact two dimensional Riemannian surface S whose critical points are semi degenerated (critical points having a non identically vanishing Hessian). To any element p of the set of semi degenerated critical points Q we assign an unique index which can take the values −1, 0 or 1, and prove that Q is made up of finitely many (critical) points with non zero index and embedded circles. Further, we generalize the famous Morse result by showing that the sum of the indexes of the critical points of f equals χ (S), the Euler characteristic of S. As an intermediate result we locally describe the level set of f near a point p ∈Q. We show that the level set f ⁻¹(f (p)) is either a) the set {p}, or b) the graph of a smooth curve passing through p, or c) the graphs of two smooth curves tangent at p or d) the graphs of two smooth curves building at p a cusp shape.     

q-Functions and extreme topological measures

q-Functions provide a method for constructing topological measures. We give necessary and sufficient conditions for a composition of a q-function and a topological measure to be a topological measure. Regular and extreme step q-functions are characterized by certain regions in Rn. Then extreme q-functions are used to study extreme topological measures. For example, we prove (under some assumptions on the underlying set) that given n, there are different types of extreme topological measures with values 0,1/n,…,1. In contrast, in the case of measures the only extreme points are {0,1}-valued, i.e., point masses.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

Sommets et normales concourantes des courbes convexes de largeur constante et singularités des hérissons

LetC be a convex curve of constant width and of classC ₄ ⁺ . It is known thatC has at least 6 vertices and its interior contains either a point through which infinitely many normals pass or an open set of points through each of which pass at least 6 normals. If all its vertices are nondegenerate, then: (i)C has exactly 6 vertices if, and only if, its evolute is the boundary of a topological disc through each interior point of which pass at least 6 normals; (ii) ifC has more than 6 vertices, then there exists an open set of points through each of which pass at least 10 normals. The proof: (i) expresses the number of normals passing through a point as a function of the index with respect to the evolute; (ii) relates this index to the number of singularities of the evolute (i.e. of vertices). Furthermore, we give formulas for counting singularities of generic hedgehogs in ℝ² and ℝ³.

     

Planar central configurations as fixed points

Planar central configurations can be seen as critical points of the reduced potential or solutions of a system of equations. By the homogeneity of the potential and its O(2)-invariance it is possible to see that the SO(2)- orbits of central configurations are fixed points of a map f. The purpose of the paper is to define and study this map and to derive some properties using topological fixed point theory. The generalized Moulton–Smale theorem for collinear configurations is proved, together with some estimates on the number of central configurations in the case of three bodies, using fixed point indices. Well-known results such as the compactness of the set of central configurations follow easily in this topological framework. Dedicated to Professor Albrecht Dold and Professor Edward Fadell     

A local criterion for Tverberg graphs

The topological Tverberg theorem states that for any prime power q and continuous map from a (d+1)(q−1)-simplex to ℝ ^d , there are q disjoint faces F _i of the simplex whose images intersect. It is possible to put conditions on which pairs of vertices of the simplex that are allowed to be in the same face F _i . A graph with the same vertex set as the simplex, and with two vertices adjacent if they should not be in the same F _i , is called a Tverberg graph if the topological Tverberg theorem still work.     

Tverberg’s Theorem and Graph Coloring

The topological Tverberg theorem has been generalized in several directions by setting extra restrictions on the Tverberg partitions. Restricted Tverberg partitions, defined by the idea that certain points cannot be in the same part, are encoded with graphs. When two points are adjacent in the graph, they are not in the same part. If the restrictions are too harsh, then the topological Tverberg theorem fails. The colored Tverberg theorem corresponds to graphs constructed as disjoint unions of small complete graphs. Hell studied the case of paths and cycles. In graph theory these partitions are usually viewed as graph colorings. As explored by Aharoni, Haxell, Meshulam and others there are fundamental connections between several notions of graph colorings and topological combinatorics. For ordinary graph colorings it is enough to require that the number of colors q satisfy q>Δ, where Δ is the maximal degree of the graph. It was proven by the first author using equivariant topology that if q>Δ ² then the topological Tverberg theorem still works. It is conjectured that q>KΔ is also enough for some constant K, and in this paper we prove a fixed-parameter version of that conjecture. The required topological connectivity results are proven with shellability, which also strengthens some previous partial results where the topological connectivity was proven with the nerve lemma.     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Generalized bochner theorems and the spectrum of complete manifolds

Bochner's theorem that a compact Riemannian manifold with positive Ricci curvature has vanishing first cohomology group has various extensions to complete noncompact manifolds with Ricci possibly negative. One still has a vanishing theorem for L ² harmonic one-forms if the infimum of the spectrum of the Laplacian on functions is greater than minus the infimum of the Ricci curvature. This result and its analogues for p-forms yield vanishing results for certain infinite volume hyperbolic manifolds. This spectral condition also imposes topological restrictions on the ends of the manifold. More refined results are obtained by taking a certain Brownian motion average of the Ricci curvature; if this average is positive, one has a vanishing theorem for the first cohomology group with compact supports on the universal cover of a compact manifold. There are corresponding results for L ² harmonic spinors on spin manifolds.     

Directional maximal operators with smooth densities

We study directional maximal operators on ?ⁿ with smooth densities. We prove that if the classical directional maximal operator in a given set of directions is weak type (1, 1), then the corresponding smooth‐density maximal operator in that set of directions will be bounded on L^q for q suitably large, depending on the order of the stationary points of the density function. In contrast to the classical case, if q is too small, the smooth density operator need not be bounded on L^q. Improving upon previously known results, we also establish that if the density function has only finitely many extreme points, each of finite order, then any maximal operator in a finite sum of diadic directions is bounded on all L^q for q > 1 (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A sampling theorem for multivariate stationary processes

The notion of sampling for second-order q-variate processes is defined. It is shown that if the components of a q-variate process (not necessarily stationary) admits a sampling theorem with some sample spacing, then the process itself admits a sampling theorem with the same sample spacing. A sampling theorem for q-variate stationary processes, under a periodicity condition on the range of the spectral measure of the process, is proved in the spirit of Lloy's work. This sampling theorem is used to show that if a q-variate stationary process admits a sampling theorem, then each of its components will admit a sampling theorem too.     

A filtration of -Catalan numbers

The operator of F. Bergeron, Garsia, Haiman and Tesler [F. Bergeron, A. Garsia, M. Haiman, G. Tesler, Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions, Methods Appl. Anal. 6 (1999) 363–420] acting on the k-Schur functions [L. Lapointe, A. Lascoux, J. Morse, Tableaux atoms and a new Macdonald positivity conjecture, Duke Math. J. 116 (2003) 103–146; L. Lapointe, J. Morse, Schur functions analogs for a filtration of the symmetric functions space, J. Combin. Theory Ser. A 101 (2003) 191–224; L. Lapointe, J. Morse, Tableaux on k+1-cores, reduced words for affine permutations and k-Schur expansion, J. Combin. Theory Ser. A 112 (2005) 44–81] indexed by a single column has a coefficient in the expansion which is an analogue of the (q,t)-Catalan number with a level k. When k divides n we conjecture a representation theoretical model in this case such that the graded dimensions of the module are the coefficients of the (q,t)-Catalan polynomials of level k. When the parameter t is set to 1, the Catalan numbers of level k are shown to count the number of Dyck paths that lie below a certain Dyck path with q counting the area of the path.     

A relative morse index for the symplectic action

The notion of a Morse index of a function on a finite-dimensional manifold cannot be generalized directly to the symplectic action function a on the loop space of a manifold. In this paper, we define for any pair of critical points of a a relative Morse index, which corresponds to the difference of the two Morse indices in finite dimensions. It is based on the spectral flow of the Hessian of a and can be identified with a topological invariant recently defined by Viterbo, and with the dimension of the space of trajectories between the two critical points.