Séances de travail (doctorants)

Présentation:

  • Le groupe est animé par: Miguel Couceiro et Jean-Sébastien Sereni
  • Il est prévu toutes les 2 sémaines et il est ouvert à tous les doctorants intéressés et motivés (pour s’inscrire il faudra contacter les organisateurs)
  • Il vise la discussion de problèmes et les échanges entre les doctorants et cher- cheurs sur des thèmes très variés : mathématiques discrètes (théorie des graphes, des ensembles ordonnés, algèbre, combinatoire), mathématiques de la décision et de l’information (théorie de l’agrégation, théorie du choix social, aide à la déci- sion), la logique (modélisation, représentation et raisonnement sur des connais-sances) et l’intelligence artificielle (apprentissage artificielle, analyse de donnés, data mining, optimisation combinatoire),…

Programme:

  • 12.07.2017 de 11 à 12h, Salle B013 (LORIA): Jean-Sébastien Sereni

Méthode de déchargement dans les graphes

Nous verrons comment démontrer des propriétés structurelles sur les graphes à l’aide de l’utilisation d’une fonction de charge, à travers quelques exemples simples.

  • 10.07.2017 de 14 à 15h, Salle B013 (LORIA): Jean-Sébastien Sereni

Déplacements sur un damier

On dispose d’un damier infini : les cases sont identifiées avec les couples (x,y) d’entiers rationnels. Vous pouvez placer autant de pions que vous le souhaitez sur les cases du demi-plan inférieur : les cases (x,y) avec y ≤ 0.  Le déplacement se fait comme au solitaire (ou lorsque l’on « mange » aux dames) : par exemple si
-un pion est sur (x-1,y),
-un pion est sur (x,y), et
-la case (x+1,y) est vide,

alors on peut enlever les deux pions et en placer un sur (x+1,y). Ceci fonctionne horizontalement (dans les deux directions) et verticalement (dans les deux directions), mais pas en diagonal. De combien de pions avez-vous besoin pour placer un pion sur une case d’ordonnée y_0 ? Par exemple, si y_0 = 1, deux pions suffisent. Si y_0 = 2, alors 4 pions suffisent.  Quid si y_0 = 3 ? 4 ? 5 ? 6 ? Ce problème sera notamment pour nous l’occasion de voir une introduction aux méthodes de potentiel, ou de déchargement.

  • 24.03.2017 de 14 à 15h, Salle B013 (LORIA): Pierre Mercuriali

De combien de manières peut-on paver un échiquier avec des dominos?

Étant donné un échiquier $m\times n$ et des dominos 2×1, nous nous intéressons au nombre de différents pavages de l’échiquier avec les dominos. Après avoir reformulé le problème en termes de graphes bipartis, nous présenterons deux méthodes pour calculer le nombre de pavages. La première consiste à calculer le permanent Per(A) de la matrice d’adjacence bipartite A du graphe grille sousjacent à l’échiquier. Per(A) étant coûteux à calculer, nous donnerons une autre méthode pour déterminer le nombre de pavages possibles, basée sur l’introduction de poids (Kasteleyn signing s) sur les arêtes du graphe, et la construction d’une seconde matrice A^s dont le déterminant vérifie |Det(A^s)| = Per(A)

  • 15.12.2016 de 14 à 15h, Salle C103 (LORIA): François Pirot

Algorithme de reconnaissance des graphes planaires

Etant donné un graphe G, comment déterminer si ce graphe est planaire, c’est à dire s’il existe un plongement de ce graphe dans le plan (ou sphère) tel qu’aucune de ses arêtes ne se croisent ailleurs qu’en un sommet ? Plus simplement, on peut se contenter de rechercher une topologie garantissant la planarité d’un graphe. Nous étudierons un algorithme de Lempel, Even et Cederbaumqui permette de trouver une telle topologie, quand elle existe, en temps linéaire en la taille du graphe.

  • 9.11.2016, de 14h à 15h, Salle B011 (LORIA): Jean-Sébastien Sereni

Utilisation de la dimension d’espace-vectoriel en combinatoire
Distances impaires – Décomposition en graphe bipartis

Inverser la condition des clubs. Peut-on placer 4 points dans le plan de sorte que tout point soit à distance impaire des autres ? Décomposition du graphe complet en graphes bipartis. Lemme du tournesol et conjecture d’Erdős & Rado.

  • 17.10.2016, de 14h à 15h, Salle B013 (LORIA): Jean-Sébastien Sereni

Utilisation du rang d’une matrice en combinatoire
Inégalité de Fisher – Distances impaires

Soit F une famille de sous-ensembles d’un ensemble fini X. Si chaque élément de F a taille impaire et que l’intersection de deux éléments quelconques de F a taille paire, quelle est la taille maximale de F ? Si le nombre d’éléments communs entre deux éléments quelconques de F est exactement t, quelle est la taille maximale de F ? Nous verrons comment l’utilisation de matrices bien choisies permet de répondre simplement et rapidement à de telles questions.