Doctorant F/H Types d’ordre, décomposition et complexité
Type de contrat : Fixed-term contract
Niveau de diplôme exigé : Graduate degree or equivalent
Fonction : PhD Position
Contexte et atouts du poste
L'équipe-projet INRIA Gamble fait partie de l'INRIA Nancy Grand Est ainsi que du département Algorithmes, calcul et géométrie du laboratoire LORIA de l'Université de Lorraine.
Cette thèse porte sur des questions de géométrie combinatoire et plus précisément sur les propriétés de structures discrètes induites par des ensembles finis de points du plan.
Chirotopes réalisables. À tout vecteur fini P = (p1,p2, \ldots, ) de n points de R² on peut associer une fonction, appelée chirotope de P, qui à tout triplet (i,j,k) de [n]={1, 2, ..., n} associe 1 (resp. -1, 0) si p_k est à gauche de (resp. à droite de, sur) la droite p_ip_j, orientée de p_i à p_j. Cette fonction détermine de nombreuses propriétés du vecteur P, par exemple son ensemble de points extrêmes, ou encore les graphes qu'il est possible de dessiner sans croisement par arêtes droites à sommet dans P. Les chirotopes de vecteurs de points sont dits réalisables. (Les types d'ordre mentionnés dans le titre sont des reformulations de ces chirotopes.)
Motivation. Voici quelques exemples de questions largement étudiées, et encore ouvertes, qui peuvent s'exprimer en terme de chirotopes~:
- Quel est la taille du plus grand vecteur de points du plan sans triplet aligné et sans n points en position convexe ? (Erd\"os et Szekeres ont montré que c'est au moins 2^{n-2}+1 et ont conjecturé que c'est la bonne réponse, la meilleure borne connue est essentiellement 2^{n+6n^{2/3}\log n}.)
- Quel est le nombre maximum de partitions d'un vecteur de 2n points du plan par une droite en deux parts égales ? (Les meilleures bornes connues sont ne^{\Omega(\sqrt{\log n})} et O(n^{4/3}).)
- Quels sont les nombres minimum et maximum de triangulations d'un vecteur de n points du plan sans triplet aligné ? (Tout vecteur a \Omega(2.63^n) et O(30^n) triangulations, et les exemple extrêmes connus ont O(3.47^n) et \Omega(9.08^n) triangulations.)
- Quel est le nombre minimum de croisements dans un dessin à arêtes droites du graphe complet K_n ? (Les meilleures bornes connues sont 0.3799 {n \choose 4} et 0.3805{n \choose 4}.)
Deux vecteurs de points de même chirotope sont équivalents pour chacunde ces problèmes.
Complexité. Explorer l'espace des chirotopes réalisables de taille n s'avère une question difficile informatiquement. Cela est illustré
par le problème algorithmique de la {\em réalisabilité}, qui demande, étant donnée une fonction [n]^3 \to \{-1,0,+1\}, de décider s'il existe un vecteur de points dont c'est le chirotope. Ce problème est non seulement NP-difficile, mais il est complet pour la théorie existentielle des réels et son appartenance à la classe NP est une question ouverte. Cette difficulté trouve son origine dans le théorème d'universalité de Mnëv, qui énonce que l'espace de realisation d'un chirotope peut avoir une topologie arbitrairement compliquée. Ainsi, les questions de comptage, d'énumération et de génération aléatoire restent aujourd'hui largement ouvertes.
Mission confiée
L'objectif de la thèse est d'approfondir l'étude des types d'ordre réalisables. Les angles d'approche proposés incluent en particulier :
- L'étude des arbres de décomposition modulaire de chirotopes introduits récemment par Bouvel, Feray, Goaoc et Koechlin (SoCG 2024), tant sur les aspects algorithmiques que sur l'application de ces arbres à l'étude des propriétés de chirotopes.
- L'étude des chirotopes à motifs interdits, et l'étude de généralisation du théorème de Marcus-Tardos sur les permutations à motifs exclus.
- L'étude de raffinements des types d'ordre, notamment les higher-order order types dont l'analyse a été initiée par Kalai, Matousek, Bukh, White, Por, ..., ou encore les allowable sequences de Goodman-Pollack et les sorting networks.
Principales activités
Étudier l'état de l'art, concevoir des algorithmes et analyser leur complexité, prouver de nouvelles propriétés de géométrie discrète, ...
Avantages
- Restauration subventionnée
- Transports publics remboursés partiellement
- Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d'autorisations d'absence exceptionnelle (ex : enfants malades, déménagement)
- Possibilité de télétravail (après 6 mois d'ancienneté) et aménagement du temps de travail
- Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
- Prestations sociales, culturelles et sportives (Association de gestion des œuvres sociales d'Inria)
- Accès à la formation professionnelle
- Sécurité sociale
Rémunération
2100 € brut/mois la 1ère année
Informations générales
- Thème/Domaine : Algorithmics, Computer Algebra and Cryptology
- Ville : Villers lès Nancy
- Centre Inria : Centre Inria de l'Université de Lorraine
- Date de prise de fonction souhaitée : 2024-10-01
- Durée de contrat : 3 years
- Date limite pour postuler : 2024-04-29
Attention: Les candidatures doivent être déposées en ligne sur le site Inria. Le traitement des candidatures adressées par d'autres canaux n'est pas garanti.
Consignes pour postuler
Sécurité défense :
Ce poste est susceptible d’être affecté dans une zone à régime restrictif (ZRR), telle que définie dans le décret n°2011-1425 relatif à la protection du potentiel scientifique et technique de la nation (PPST). L’autorisation d’accès à une zone est délivrée par le chef d’établissement, après avis ministériel favorable, tel que défini dans l’arrêté du 03 juillet 2012, relatif à la PPST. Un avis ministériel défavorable pour un poste affecté dans une ZRR aurait pour conséquence l’annulation du recrutement.
Politique de recrutement :
Dans le cadre de sa politique diversité, tous les postes Inria sont accessibles aux personnes en situation de handicap.
Contacts
- Équipe Inria : GAMBLE
-
Directeur de thèse :
Goaoc Xavier / xavier.goaoc@loria.fr
L'essentiel pour réussir
Goût pour le travail à l'interface entre informatique théorique et mathématiques.
A propos d'Inria
Inria est l’institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l’interface d’autres disciplines. L’institut fait appel à de nombreux talents dans plus d’une quarantaine de métiers différents. 900 personnels d’appui à la recherche et à l’innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie.