Je vais vous parler de résultats variés concernant le nombre de croisements dans les graphes dessinés sur des surfaces.
Je commencerai par une introduction générale sur le nombre de croisements, en particulier je vous rappellerai la célèbre lemme de croisement et ses applications.
Ensuite, je vous présenterai des résultats récents concernant deux variantes de ce concept. Dans le cas classique, nous comptons chaque intersection entre chaque paire d’arêtes comme un croisement. Dans une variante, le nombre de croisement dégénéré, plusieurs arêtes peuvent se croiser en un seul point. Mohar a formulé la conjecture selon laquelle le nombre de croisements dégénéré dans le plan est égal au genre non orientable d’un graphe. Negami a formulé une conjecture similaire pour un autre paramètre, à savoir le nombre de croisements conjoints entre deux graphes G et H plongés dans S.
Dans sa thèse (que je codirige avec Arnaud de Mesmay), Niloufar Fuladi a découvert des résultats positifs et négatifs liés à ces conjectures en se basant sur des résultats de la biologie algorithmique. Plus précisément, elle a adapté un cas simple de l’algorithme de réarrangement génomique de Hannenhalli-Pevzner au contexte de nombre de croisement des graphes.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne