Thèse Marco CAODURO

Problèmes de géométrie en optimisation combinatoire :
packing, transversaux, et coloration de rectangles

Résumé

Les graphes d’intersection géométriques sont des graphes qui proviennent de familles d’objets géométriques dans le plan (et, plus généralement, dans R d ). Cette classe a attiré l’attention de nombreux chercheurs car elle est riche en questions théoriques et en applications pratiques. Dans ce manuscrit, nous nous limitons aux propriétés combinatoires des rectangles, segments et carrés dans le plan, parallèles aux axes ou non. De nombreuses questions fondamentales sur ces objets ont été soulevées dans les années 60. Ces travaux se sont concentrés sur la relation entre le nombre transversal (nombre minimum de points nécessaires pour intersecter tous les objets de la famille) et le nombre de packing (nombre maximum d’objets disjoint 2 à 2), ainsi qu’entre le nombre chromatique (nombre minimum de couleurs telles que toutes paires d’objects s’intersecant ont des couleurs distinctes) et le nombre de clique (nombre maximum d’objets que s’intersectant 2 à 2).
La première partie de la thèse traite de la célèbre conjecture de Wegner. Cette conjecture, proposée par Gerd Wegner en 1965, stipule que pour toute famille de rectangles parallèles aux axes dans le plan, le nombre transversal de la famille est au plus deux fois son nombre de packing moins un. Nous présentons l’état de l’art sur ce problème avec plusieurs résultats partiels, en nous concentrant principalement sur des cas particuliers, tels que les familles avec un graphe d’intersection sans triangle et les familles sans rectangles croisés. De même, nous explorons le problème de la borne du nombre chromatique en fonction du nombre de clique. Ensuite, nous traitons le cas particulier des segments parallèles aux axes. Nous prouvons que non seulement la constante de la conjecture de Wegner est valide pour cette classe dégénérée de rectangles, mais, qu’étonnamment, elle est aussi optimale.
Dans la deuxième partie du manuscrit, nous abandonnons l’hypothèse de parallélisme des axes et étudions les propriétés combinatoires des rectangles qui ne vérifient pas nécessairement cette propriété. Lorsque la rotation des rectangles est également autorisée, ni le nombre transversal ni le nombre chromatique ne peuvent être bornés respectivement par le nombre de packing ou le nombre de clique. Pour cette raison, nous portons notre attention sur les carrés et les rectangles dont le rapport de forme, c’est-à-dire le rapport entre la longueur de ses côtés les plus longs et les plus courts, est borné. Le rapport entre les nombres transversal et de packing ainsi que celui entre les nombres chromatique et de clique sont également des questions ouvertes pour les objets naturels tels que les disques et les carrés. Nous réduisons ces écarts en établissant des bornes linéaires avec des constantes raisonnablement petites pour les carrés et en généralisant ces résultats pour les rectangles dont le rapport de forme est borné.
Ces questions nous amènent à nous interroger sur la boxicité d’un graphe, c’est-à-dire la dimension minimale d telle que le graphe soit le graphe d’intersection d’une famille de boîtes alignées sur l’axe dans R d . Ce paramètre, introduit par Roberts en 1969, est bien étudié dans plusieurs classes de graphes, comme les graphes planaires, les graphes triangulés et les line graphs. Dans la troisième et dernière partie de la thèse, nous développons des techniques pour calculer la boxicité d’un graphe en se basant sur les sous-graphes induits interdits des graphes d’intervalles et sur des propriétés spécifiques des ordres d’intervalles. Ces techniques visent à explorer la classe des graphes ayant des paramètres d’intérêt pour les conjectures de transversal et de coloration discutées dans la première partie. Ainsi, nous prouvons que certains des graphes parmi les plus célèbres en Théorie des graphes, tels que le graphe de Grötzsch, le graphe de Chvátal, le graphe de Petersen, et certains des plus petits graphes de Ramsey, ne sont pas des graphes d’intersection de rectangles parallèles aux axes dans le plan, alors qu’ils peuvent être représentés par des boîtes parallèles aux axes dans R 3 . Notre méthode s’étend également aux dimensions supérieures et nous permet de calculer exactement la boxicité du complément du line graph de Kn pour n ≥ 5 (ce qui correspond au graphe de Kneser KG(n, 2)).