Séances de travail (doctorants)

Présentation:

  • Le groupe est animé par: M. Couceiro, J.-S. Sereni et A. Bazin
  • Il est prévu toutes les 2 semaines 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:

  • 26.04.2019 de 11 à 12h, Salle A006 (LORIA): Jessie Carbonnel et Giacomo Kahn

From formal concept analysis to relational concept analysis

We will start by introducing formal concept analysis and some of its foundations. We will give an example of some applications in software engineering. After that, we will try to inject some relations into our data and see where it leads us.

  • 22.03.2019 de 11 à 12h, Salle B011 (LORIA): Alexandre Bazin

Rules in binary data: why they are more interesting in the multidimensional case

Association rules and their exact variants, implications, are a good way to represent the regularities in binary datasets. However, their number makes them hard to use. Most works on the subject aim at reducing this number either with or without loss of information. While both options are well understood in the classic bidimensional case, they are less so in the multidimensional one. We will talk about how it is traditionally done and how those results can be generalized to n-ary relations.

  • 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.