# Séminaires 2017 - 2018

**Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.**

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à **14h30** en **Salle C319**. Les responsables sont **Louis Esperet** et **András Sebő**, n'hésitez pas à les contacter.

9 novembre 2017 | Pierre Aboulker (G-SCOP) |
Generalizations of the geometric de Bruijn Erdős Theorem |

12 octobre 2017 | Maria Macekova (G-SCOP) |
Light subgraphs in sparse graphs |

21 septembre 2017 | Roland Grappe (LIPN) |
Principally box-integer polyhedra |

- Jeudi 9
novembre 2017
**(à 14h30)**:**Pierre Aboulker**(G-SCOP) : Generalizations of the geometric de Bruijn Erdős Theorem

A classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the euclidean plane determines at least n distinct lines. The line L(u,v) determined by two points u, v in the euclidean plane consists of all points p such that:

- dist(p, u) + dist(u, v) = dist(p, v) (i.e. u is between p and v) or

- dist(u, p) + dist(p, v) = dist(u, v) (i.e. p is between u and v) or

- dist(u, v) + dist(v, p) = dist(u, p) (i.e. v is between u and p).

With this definition of line L(u,v) in an arbitrary metric space (V, dist), Chen and Chvátal conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points.

The talk will survey results on and around this conjecture.

- Jeudi 12
octobre 2017
**(à 14h30)**:**Maria Macekova**(G-SCOP) : Light subgraphs in sparse graphs

A graph is called sparse, if its edge number is linear in the number of vertices. Sparse graphs have, compared to dense graphs, specific properties - they contain vertices of low degrees, values of different color invariants are upper bounded by constant. Within the family of sparse graphs plays an important role class of plane graphs, i.e. graphs that can be drawn in a plane without crossing of edges. In general, plane graphs with minimum vertex degree at least 2 do not have to contain any light subgraph (i.e. subgraph with vertices of bounded degrees). However, if we consider additional condition on the girth of the graph, then we can guarantee the existence of such subgraph. In this talk we will give a sumary of the results about light subgraphs in the family of plane graphs and we will mention some results for other classes of sparse graphs (e.g. 1-planar graphs, graphs with bounded average degree).

- Jeudi 21
septembre 2017
**(à 14h30)**:**Roland Grappe**(LIPN) : Principally box-integer polyhedra

A polyhedron is box-integer if its intersection with any integer box is an integer polyhedron. We introduce principally box-integer polyhedra : they are the polyhedra whose dilatations are box-integer as soon as they are integer. We will present several characterizations of principally box-integer polyhedra, which involve matrices and strong integrality properties of linear sytems. Eventually, we will discuss connexions with combinatorial optimization problems.

This is a joint work with Patrick Chervet and Louis-Hadrien Robert.