VI ALIO/EURO Workshop on Applied Combinatorial Optimization

December 15 - 17, 2008, Buenos Aires, Argentina

The Helly Property on Graphs and Hypergraphs *

Jayme L. Szwarcfiter

Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil

In this talk, we survey some of the results and consequences of the celebrated theorem by Helly on convex sets, published in 1923. We focus on graphs and hypergraphs an also present several generalizations of this theorem. Our main concern consists of algorithmic questions, we describe a few algorithms for solving problems originated from the Helly Property and also NP-hardness results. Several graphs and hypergraphs have been defined motivated by the Helly Property and some of these classes are discussed in this talk. Although our aim is not to present applications of the subject, we mention that the Helly Property has been applied in some different areas of computer science and optimization, as theory of semantics, coding, computational biology, data bases. From the theoretical point of view, the Helly Property has been playing an important role in areas as combinatorial geometry and convexity theory.

* Joint work with Mitre C. Dourado and Fábio Protti