Publicités

La résolution du problème de l’indépendance par la collaboration

La résolution du problème de l’indépendance par la collaboration

Un professeur de mathématiques donne à ses étudiants un problème combinatoire frustrant ; leur solution sera bientôt publiée dans une revue spécialisée.

Le professeur adjoint du MIT, Yufei Zhao (à l’extrême droite), a donné aux étudiants de premier cycle (de gauche à droite) Mehtaab Sawhney, David Stoner et Ashwin Sah un problème combinatoire particulièrement épineux. Leur théorème sur le nombre d’ensembles indépendants dans un graphique est sur le tableau derrière eux.

En 2009, alors que Yufei Zhao était étudiant au MIT, il a été intrigué par une conjecture de 2001 du mathématicien Jeff Kahn de l’Université Rutgers concernant le nombre de séries indépendantes dans un graphique. Un ensemble indépendant dans un graphique est un sous-ensemble de sommets de telle sorte qu’aucun d’entre eux ne soit relié par un bord.

« De nombreuses structures importantes peuvent être modélisées à l’aide d’ensembles indépendants « , explique Zhao. « Par exemple, si le graphique modélise une incompatibilité, alors un ensemble indépendant représente une collection mutuellement compatible. »

Zhao participait à un programme d’été d’expérience de recherche pour les étudiants de premier cycle (REU) à Duluth, Minnesota, et pendant qu’il faisait des recherches sur ce qui serait l’un de ses premiers articles de recherche en mathématiques, il a rencontré un problème combinatoire de Kahn. Le problème l’a intrigué. Une tentative de résoudre ce problème s’est approchée, comme il l’a décrit dans un article qu’il a écrit avec David Galvin en 2010 intitulé « Le nombre d’ensembles indépendants dans un graphique avec un faible degré maximum ».

Yufei Zhao a obtenu son diplôme en 2010, a obtenu son doctorat en 2015 et est maintenant professeur adjoint en développement de carrière de la promotion 1956 au MIT. Il se concentre sur la combinatoire, les mathématiques discrètes et la théorie des graphes.

Au fil des ans, cette conjecture a continué à le harceler, alors au printemps dernier, Zhao a décidé de transmettre le défi à ses élèves mathématiciens « sans peur », Ashwin Sah en deuxième année et Mehtaab Sawhney en première.

David Stoner, qui s’est lié d’amitié avec Sawhney dans le cadre du programme REU à Duluth, suit également des cours de combinatoire au MIT. Quand il a entendu parler du projet de ses amis, il a demandé à participer.

Zhao se souvient qu’au cours d’un mois, ils ont débattu de leurs idées en ligne ainsi que lors d’une session nocturne marathon dans le bâtiment 2,  » où ils ont revus les inégalités les unes après les autres « .

« À mon grand étonnement, ils sont venus me voir avec une solution de cette vieille conjecture, dit-il. « Beaucoup de mathématiciens expérimentés ont travaillé sur cette conjecture sans succès. »

Pour couronner leur succès, ils ont publié un article – « The number of independent sets in an irregular graph » – dans le Journal of Combinatorial Theory, série B, une revue leader en combinatoire.

« L’approche présentée dans le journal, bien qu’elle ne soit pas très difficile, finit par être très technique « , explique M. Sawhney. « Trouver comment gérer les différents termes qui apparaissent dans notre épreuve et les réduire sous une forme gérable joue un rôle clé. »

Stoner ajoute : « Rétrospectivement, la partie la plus difficile a probablement été la découverte d’une application particulière de l’inégalité de Holder. Cela a permis de transformer l’inégalité inductive en quelque chose de complètement local. »

Pour Sah, la partie la plus difficile a été « de trouver la bonne approche et le bon cadrage, et de comprendre le théorème de la bonne façon ».

« Une fois que nous avons cru que l’inégalité locale était vraie, elle nous a permis de voir le problème d’une manière très différente par rapport à ce qui était déjà connu, et bien qu’il y ait encore beaucoup de difficultés au-delà de cette prise de conscience, elle sous-tend certainement tout l’effort, » dit Sah.

Kahn était enthousiasmé par les résultats. « C’était formidable de voir ma vieille conjecture enfin résolue, et encore mieux de voir à quoi elle menait. Certains des problèmes réglés par Yufei et compagnie avaient été essayés par d’excellentes personnes beaucoup plus expérimentées. Bien sûr, avoir un jeune esprit frais peut aussi être un avantage. »

Zhao, pour sa part, est maintenant heureux de vérifier cette conjecture à partir de sa liste. Mais il est encore plus heureux d’avoir des étudiants comme eux dans son cours de combinatoire.

« Les élèves sont incroyables », dit-il. « Ils me posent constamment des questions et me bombardent d’idées. J’ai tellement appris d’eux. »

Les techniques qu’ils ont trouvées pour résoudre cette conjecture ont rapidement conduit à travailler sur plusieurs problèmes connexes, y compris pour leur prochain article « A Reverse Sidorenko Inequality« , lié aux colorations et aux homomorphismes des graphes. Explique Zhao : « Cet article résout plusieurs problèmes ouverts concernant les colorations de graphes et les homomorphismes, y compris l’un de mes problèmes préférés concernant la maximisation du nombre de q-colorations dans un graphique régulier en d. ».

Les trois étudiants sont prolifiques. Sawhney a écrit 12 articles jusqu’à présent, dont quatre autres avec Stoner, et un autre avec Sah, qui est l’auteur ou co-auteur de six articles au total. Stoner a huit papiers pour l’instant.

« Ils sont incroyables, dit Zhao. « La plupart des étudiants diplômés n’ont pas autant de papiers. »

Tous les trois aiment travailler ensemble. « Souvent, nous discutons des idées au téléphone ou en personne et nous avons tendance à les communiquer rapidement, même si elles ne sont qu’à moitié cuites « , dit M. Sawhney. « C’est comme s’il y avait toujours quelque chose d’autre à essayer sur un problème sur lequel on travaille. »

Ajoute Stoner : « Quand vient le temps d’exécuter ces idées en détail, nous essayons généralement de jouer sur chacune de nos forces individuelles. »

Ashwin décrit leur dynamique comme étant  » plutôt détendue « , utilisant Slack et d’autres médias en ligne pour discuter des idées et débattre des lacunes des diverses méthodes lorsqu’ils ne peuvent se rencontrer en personne. « Il y a toujours quelque chose qui se passe et quelque chose à quoi penser « , dit-il.

Sah dit que c’est l’atmosphère de collaboration qui l’a attiré au MIT.

« Je suis vraiment reconnaissant de pouvoir travailler avec ce groupe particulier de personnes sur la recherche en combinatoire « , dit-il.

MIT

Publicités

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

%d blogueurs aiment cette page :