Droites sur les hypergraphes

Abstract

Le Théorème de Sylvester-Gallai affirme que dans un ensemble fini S de points dans le plan, où les points ne sont pas tous sur une même droite, il y a une droite qui passe par exactement deux points de S. Chvátal [14] a étendu la notion de droites aux espaces métriques arbitraires et a fait une conjecture généralisant le Théorème de Sylvester-Gallai. Chen [10] a démontré cette conjecture qui s’appelle maintenant le Théorème de Sylvester-Chvátal. En 1943, Erdos [18] a remarqué un corollaire pour le Théorème de Sylvester-Gallai affirmant que, dans un ensemble fini V de points dans le plan, où les points ne sont pas tous sur une droite, le nombre de droites qui passent par au moins deux points de V est au moins |V |. De Bruijn et Erdos [7] ont généralisé ce corollaire, en utilisant une définition généralisée de droite (voir Chapitre 2) et ont prouvé que tout ensemble de n points, où les points ne sont pas tous sur une même droite, détermine au moins n droites distinctes. Dans le présent mémoire, nous allons étudier les théorèmes mentionnés ci-dessus. Nous allons aussi considérer le Théorème de De Bruijn-Erdos dans le cadre des hypergraphes et des espaces métriques.

The Sylvester-Gallai theorem states that in a finite set S of points in the plane, not all on the same line, there is a line passing through exactly two points of S. Chvátal [14] extended the concept of lines to arbitrary metric spaces and made a conjecture generalizing the Sylvester-Gallai theorem. Chen [10] proved this conjecture which is now called The Sylvester-Chvátal Theorem. In 1943, Erdos [18] noticed a corollary to the Sylvester-Gallai theorem stating that, in a finite set V of points in the plane, not all on a line, the number of lines that pass through at least two points of V is at least |V |. De Bruijn et Erdos [7] generalized this corollary, using a generalized definition of a line (see Chapter 2) and proved that any set of n points, not all on the same line, determines at least n distinct lines. In this master’s thesis, we will study the theorems mentioned above. We will also look at the Theorem of De Bruijn-Erdos within the framework of hypergraphs and various metric spaces.