Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Cette séance de cours couvre le théorème de Bourgain sur la coupe la plus clairsemée dans les graphes, en se concentrant sur le concept de coupe maximale et l'application de la sémimétrie. Le théorème indique que pour un ensemble donné de sommets, il existe une cartographie qui minimise la coupe. La séance de cours se penche sur la preuve du théorème, en mettant l'accent sur le rôle de la sémimétrie et la conception de la distribution. Il discute également des implications du théorème dans la théorie des graphes et les problèmes d'optimisation.