Two methods for the generation of chordal graphs

In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new results concerning the dynamic maintenance of chordality under edge insertions; the second is based on expansion/merging of maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole generation process. L. Markenzon’s research is partially supported by grant 301068/2003-8, CNPq, Brazil.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

Exploring the complexity boundary between coloring and?list-coloring

Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring. Flavia Bonomo partially supported by UBACyT Grants X606 and X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Guillermo Durán partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Javier Marenco partially supported by UBACyT Grant X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

A nonlinear programming algorithm based on non-coercive penalty functions

 We consider first the differentiable nonlinear programming problem and study the asymptotic behavior of methods based on a family of penalty functions that approximate asymptotically the usual exact penalty function. We associate two parameters to these functions: one is used to control the slope and the other controls the deviation from the exact penalty. We propose a method that does not change the slope for feasible iterates and show that for problems satisfying the Mangasarian-Fromovitz constraint qualification all iterates will remain feasible after a finite number of iterations. The same results are obtained for non-smooth convex problems under a Slater qualification condition. Received: September 2000 / Accepted: June 2002 Published online: March 21, 2003 Research partially supported by CAPES, Brazil Research partially supported by CNPq, Brazil, and CONICIT, Venezuela. Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

A strong uniqueness theorem for planar vector fields

This work establishes a strong uniqueness property for a class of planar locally integrable vector fields. A result on pointwise convergence to the boundary value is also proved for bounded solutions.Dedicated to Constantine Dafermos on his 60^th birthdayWork supported in part by CNPq, FINEP, FAPESP and a Research Incentive Fund grant of Temple University.     

Resolution of singularities of real-analytic vector fields in dimension three

Let χ be an analytic vector field defined in a real-analytic manifold of dimension three. We prove that all the singularities of χ can be made elementary by a finite number of blowing-ups in the ambient space. This work has been partially supported by the CNPq/Brasil Grant 205904/2003-5 and Fapesp Grant 02/03769-9.     

Critical point theorems and applications to a semilinear elliptic problem

The objective of this article is to establish the existence of critical points for functionals of classC ²defined on real Hilbert spaces. The argument is based on the infinite dimensional Morse theory introduced by Gromoll-Meyer [13]. The abstract results are applied to study the existence of nonzero solutions for a class of semilinear elliptic problems where the nonlinearity possesses a superlinear growth on a direction of the real line.This research was partially supported by CNPq/Brazil     

Simultaneous reduction of a family of commuting real vector fields and global hypoellipticity

In this paper we consider a family of commuting real vector fields on then-dimensional torus and show that it can be transformed into a family of constant vector fields provided that there is one of them which its transposed is globally hypoelliptic. We apply this result to prove global hypoellipticity for certain classes of sublaplacians. The author was partially supported by CNPq.     

Numerical solution of cauchy-type integral equations of index −1 by collocation methods

This paper describes a collocation method for solving constant coefficient Cauchy-type singular integral equations of index –1. A technique for reducing the set of linear equations resulting from collocation to match the number of unknows is described. The uniform convergence analysis of the resulting method is presented and convergence rates based on the smoothness of the data are given.This work was partially supported by CNPq under grant #300105/88-6(RN).     

Sub-Riemannian Geodesics on the 3-D Sphere

The unit sphere can be identified with the unitary group SU(2). Under this identification the unit sphere can be considered as a non-commutative Lie group. The commutation relations for the vector fields of the corresponding Lie algebra define a 2-step sub-Riemannian manifold. We study sub-Riemannian geodesics on this sub-Riemannian manifold making use of the Hamiltonian formalism and solving the corresponding Hamiltonian system. The first author is partially supported by a research grant from the United State Army Research Office and a Hong Kong RGC competitive earmarked research grant #600607. The second and the third authors have been supported by the grant of the Norwegian Research Council #177355/V30, and by the European Science Foundation Research Networking Programme HCAA.     

Examples of ill-behaved central paths in convex optimization

This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data.Mathematics Subject Classification (2000): 90C25, 90C51Research partially supported by CAPES, Brazil.Research partially supported by CAPES and CNPq, Brazil.     

Partial characterizations of coordinated graphs: line graphs and complements of forests

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest. F. Bonomo, F. Soulignac, and G. Sueiro’s research partially supported by UBACyT Grant X184 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). The research of G. Durán is partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

Lineare Optimierung in halbgeordneten Vektorräumen

Summary The problem of linear programming in partially ordered vector spaces is formulated as an immediate generalization of the same problem in Euclidean spaces. Sufficient conditions for the existence of solutions of the problem and its dual are obtained. In the special case of function spaces the sufficient conditions for the solvability of the dual problem are satisfied if a certain regularity condition is assumed.

---

---

This research was supported by the Air Force Office of Scientific Research under grant AF-AFO SR-93 7-6 7     

Controlled Markov processes on the infinite planning horizon: Weighted and overtaking cost criteria

Stochastic control problems for controlled Markov processes models with an infinite planning horizon are considered, under some non-standard cost criteria. The classical discounted and average cost criteria can be viewed as complementary, in the sense that the former captures the short-time and the latter the long-time performance of the system. Thus, we study a cost criterion obtained as weighted combinations of these criteria, extending to a general state and control space framework several recent results by Feinberg and Shwartz, and by Krass et al. In addition, a functional characterization is given for overtaking optimal policies, for problems with countable state spaces and compact control spaces; our approach is based on qualitative properties of the optimality equation for problems with an average cost criterion.Research partially supported by the Engineering Foundation under grant RI-A-93-10, in part by the National Science Foundation under grant NSF-INT 9201430, and in part by a grant from the AT&T Foundation.Research partially supported by the Air Force Office of Scientific Research under Grant F49620-92-J-0045, and in part by the National Science Foundation under Grant CDR-8803012.     

Killing graphs with prescribed mean curvature

It is proved the existence and uniqueness of Killing graphs with prescribed mean curvature in a large class of Riemannian manifolds. M. Dajczer was partially supported by Procad, CNPq and Faperj. P. A. Hinojosa was partially supported by PADCT/CT-INFRA/CNPq/MCT Grant #620120/2004-5. J. H. de Lira was partially supported by CNPq and Funcap.     

Effective counting of the points of definable sets over finite fields

Given a formula in the language of fields we use Galois stratification to establish an effective algorithm to estimate the number of points over finite fields that satisfy the formula This work was partially done while all three authors were members of the Institute for Advanced Studies in Jerusalem. Parially supported by BSF grant #87-00038 and NSA grant MDA 904-91-H-0057. Partially supported by grants from the German-Israeli Foundation for Scientific Research and Development.     

Bi-Lipschitz geometry of weighted homogeneous surface singularities

We show that a weighted homogeneous complex surface singularity is metrically conical (i.e., bi-Lipschitz equivalent to a metric cone) only if its two lowest weights are equal. We also give an example of a pair of weighted homogeneous complex surface singularities that are topologically equivalent but not bi-Lipschitz equivalent. L. Birbrair was supported under CNPq grant no. 300985/93-2. A. Fernandes was supported under CNPq grant no. 300393/2005-9. W. D. Neumann was supported under NSA grant H98230-06-1-011 and NSF grant no. DMS-0206464.     

On the Circuit-cocircuit Intersection Conjecture

Oxley has conjectured that for k≥4, if a matroid M has a k-element set that is the intersection of a circuit and a cocircuit, then M has a (k−2)-element set that is the intersection of a circuit and a cocircuit. In this paper we prove a stronger version of this conjecture for regular matroids. We also show that the stronger result does not hold for binary matroids. The second author was partially supported by CNPq (grant no 302195/02-5) and the ProNEx/CNPq (grant no 664107/97-4).     

Partially monotone operators and the generic differentiability of convex-concave and biconvex mappings

By studying partially monotone operators, we are able to show among other results that convex-concave and biconvex mappings defined on Asplund spaces or dually strictly convex spaces are respectively generically Fréchet or Gateaux differentiable. Research partially supported on a N.S.E.R.C. operating grant.     

Prime ideals and radicals of centred extensions and tensor products

In this paper, we study prime ideals and radicals of centred extensions of rings. Obtained results are applied to tensor products of algebras over commutative rings. This research was partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Brazil. The second-named author was also supported by KBN grant 2 P301 035 06.