Journée Charles Hermite
Complexité : Théorie des graphes
et théorie des nombres
IECL

LORIA
Institut Élie Cartan de Lorraine
(IECL, UMR CNRS 7502)

et
Laboratoire lorrain de recherche en informatique et ses applications
(LORIA, UMR CNRS 7503)


Nancy, 29 novembre 2017
UL


CNRS

Organisateurs : Manfred Madritsch, Chedy Raïssi, Jean-Sébastien Sereni et Thomas Stoll
Accès : Accès au campus et stationnement et plan du campus.
Programme
Conférenciers

Valérie Berthé (CNRS et Institut de recherche en informatique fondamentale)
Titre : Mots, fractions continues et arbres
Résumé : L’étude des mots sturmiens et de leurs systèmes dynamiques symboliques associés est intimement liée à celle des suites de Kronecker et des fractions continues usuelles. L’interaction fonctionne dans les deux directions : une approche arithmétique permet de décrire les propriétés dynamiques et symboliques de ces mots, mais inversement, l’étude des mots sturmiens permet de déduire des propriétés arithmétiques, par exemple de discrépance. Nous montrons comment étendre ces interactions via l’étude d’une famille de mots infinis qui englobe, en particulier, les sturmiens, mais aussi les codages d’échanges d’intervalles. Ces mots sont définis en termes de graphes d’extension permettant de décrire leurs langages : ces graphes sont des arbres. Nous montrons comment en déduire des développements en fractions continues généralisés et leurs propriétés arithmétiques.

Jehanne Dousse (Université de Zurich, Suisse)
Titre : Enumeration exacte et asymptotique des partitions d'entiers
Résumé : Une partition d'un entier positif n est une suite décroissante d'entiers dont la somme est n. Bien que leur définition soit très simple, les partitions sont très difficiles à compter et aucune formule simple n'est connue pour leur nombre. Cependant, il est possible d'obtenir de belles formules asymptotiques. Cette approche a été initiée par Hardy et Ramanujan avec leur méthode du cercle, qui repose sur la modularité de la série génératrice des partitions. Dans la première partie de l'exposé, j'expliquerai leur méthode ainsi qu'une généralisation aux formes de Jacobi. Une autre approche est de montrer que différents ensemble de partitions ont exactement la même cardinalité. Par exemple pour tout n, le nombre de partitions de n en parts impaires est égal au nombre de partitions de n en parts distinctes. Dans la deuxième partie de la présentation, je discuterai de ces identités -dont certaines viennent de la théorie des représentations- et je présenterai une nouvelle méthode pour les raffiner et les généraliser.

Michel Habib (Institut de recherche en informatique fondamentale)
Titre : Graph Searches on Structured Families of Graphs and Matrices
Résumé : Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS). Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings. These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance). In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.

Clemens Heuberger (Université de Klagenfurt, Autriche)
Titre : Analysis of Sequences using Transducer Automata
Résumé : This talk focusses on sequences which can be generated by transducer automata. Such sequences frequently occur in the context of digit problems, for instance in the design of efficient scalar multiplication algorithms used in elliptic curve cryptography. Existence and optimality questions can be decided by connectivity properties of the graphs underlying the corresponding transducers and precise asymptotic results can be obtained.

Florent Jouve (Université de Bordeaux)
Titre : Un crible pour les graphes de Cayley
Résumé : Dans divers contextes récents (crible pour les orbites de Bourgain-Gamburd-Sarnak, théorie de Galois probabiliste dans les groupes arithmétiques,...) des formes traditionnelles de crible (crible de Brun, grand crible) ont été utilisées pour des groupes généraux dans le but de quantifier la probabilité que certaines propriétés que l'on pense rarement vérifiées soient satisfaites. Un point commun à ces travaux est le rôle joué par certaines familles de graphes expanseurs provenant de certains quotients finis des groupes intervenant. Celles-ci fournissent en effet une propriété d'écart spectral nécessaire à la mise en oeuvre du crible. Je présenterai un travail commun avec J.-S. Sereni où l'on propose une forme de crible dans un contexte abélien assez général se basant sur le fait que certaines familles de graphes de Cayley "aléatoires" forment de bons expanseurs. On illustrera la méthode sur quelques exemples simples.

Manon Stipulanti (Université de Liège, Belgique)
Titre : Triangles de Pascal et de Sierpinski étendus aux coefficients binomiaux de mots
Résumé : Le coefficient binomial $\binom{u}{v}$ de deux mots $u$ et $v$ est défini comme le nombre de fois que $v$ apparaît comme sous-suite du mot $u$. Par exemple, $\binom{abbab}{ab}=4$. Il étend de manière naturelle le coefficient binomial de deux entiers. Ce concept a été largement étudié depuis plus d'une trentaine d'années (cf. par exemple, les travaux de Simon et Sakarovitch). Dans cet exposé, je parlerai des recherches effectuées dans le cadre de ma thèse sur une extension des triangles de Pascal et de Sierpinski à ces coefficients.

Programme
 9h00- 9h15Accueil
 9h15-10h15Valérie Berthé : Mots, fractions continues et arbres (IECL, Salle de conférences)
10h15-10h30Pause café IECL
10h30-11h30Jehanne Dousse : Enumeration exacte et asymptotique des partitions d'entiers (IECL, Salle de conférences)
11h30-12h30Florent Jouve : Un crible pour les graphes de Cayley (IECL, Salle de conférences)
12h30-14h00Buffet IECL (Salle Döblin)
14h00-15h00Michel Habib : Graph Searches on Structured Families of Graphs and Matrices (LORIA, Salle A008)
15h00-16h00Clemens Heuberger : Analysis of Sequences using Transducer Automata (LORIA, Salle A008)
16h00-16h15Pause café LORIA
16h15-17h15Manon Stipulanti : Triangles de Pascal et de Sierpinski étendus aux coefficients binomiaux de mots (LORIA, Salle A008)
Soirée au restaurant

Participants
  1. Valérie Berthé (CNRS et Institut de recherche en informatique fondamentale)
  2. Anne de Roton (Université de Lorraine)
  3. Cécile Dartyge (Université de Lorraine)
  4. Eric Domenjoud (Université de Lorraine)
  5. Jehanne Dousse (Université de Zurich, Suisse)
  6. Isabelle Dubois (Université de Lorraine)
  7. David Feutrie (Université de Lorraine)
  8. Michel Habib (Institut de recherche en informatique fondamentale)
  9. Gautier Hanna (Université de Lorraine)
  10. Clemens Heuberger (Université de Klagenfurt, Autriche)
  11. Damien Jamet (Université de Lorraine)
  12. Florent Jouve (Université de Bordeaux)
  13. Florian Lietard (Université de Lorraine)
  14. Manfred Madritsch (Université de Lorraine)
  15. Irène Marcovici (Université de Lorraine)
  16. François Pirot (Université de Lorraine et Université de Nijmegen, Pays-Bas, CSTB)
  17. Chedy Raïssi (Université de Lorraine)
  18. Robin Riblet (Université de Lorraine)
  19. Tom Riblet (Université de Lorraine)
  20. Jean-Sébastien Sereni (Université de Lorraine)
  21. André Stef (Université de Lorraine)
  22. Manon Stipulanti (Université de Liège, Belgique)
  23. Thomas Stoll (Université de Lorraine)
  24. Pierre-Adrien Tahay (Université de Lorraine)
  25. Johann Verwee (Université de Lorraine)

Inscription

Les personnes souhaitant participer à cette journée sont invitées à remplir le formulaire d'inscription ci-dessous et de l'envoyer, dans les meilleurs délais avant le 22 novembre 2017.

La participation est libre mais l'inscription avant la date limite est obligatoire pour une bonne prévision des effectifs (salle, repas, ...)

En cas de problème d'inscription avec ce formulaire, veuillez contacter directement Manfred Madritsch par courriel.



Hôtels
Grad Hôtel de la Reine ****
2, Place Stanislas
54000 NANCY
(+33) 3 83 35 03 01

Mercure Nancy Centre Stanislas ****
5 rue des Carmes
54000 NANCY
(+33) 3 83 30 92 60

Suite Novotel Nancy Centre ****
Allée du Chanoine Drioton
Stanislas Meurthe
Jardins d'eau
54000 NANCY
(+33) 3 83 32 28 80
Coeur de City Hotel Nancy Stanislas ***
61 rue Pierre Semard
54000 NANCY
(+33) 3 83 32 28 53

Hôtel de Guise ***
18 rue de Guise
54000 NANCY
(+33) 3 83 32 24 68

Hotel ibis Styles Nancy Centre Gare ***
3 rue de l Armee Patton
54000 NANCY
(+33) 3 83 40 31 24

Hotel ibis Nancy Centre Gare ***
3, rue Crampel
54000 NANCY
(+33) 3 83 32 90 16

Park Inn By Radisson Nancy Hôtel ***
11 rue Raymond Poincaré
54000 NANCY
(+33) 3 83 39 75 75

Hôtel des Prélats ***
56 place Mgr Ruch
54000 NANCY
(+33) 3 83 30 20 20

Hôtel de la résidence ***
30 Boulevard Jean-Jaurès
54000 NANCY
(+33) 3 83 40 33 56

Aparthotel Access Nancy Centre ***
31 Avenue Du XXe Corps
54000 NANCY
(+33) 3 83 15 87 80
Hôtel ibis Budget Nancy Centre **
Allée du Chanoine Drioton
54000 NANCY
(+33) 8 92 68 12 86

Hôtel Jean-Jaurès **
14 Boulevard Jean Jaurès
54000 NANCY
(+33) 3 83 27 74 14

Hôtel Revotel **
41/43 rue Raymond Poincaré
54000 NANCY
(+33) 3 83 28 02 13

Contacts
Secrétariat :
Mme Paola Schneider
IECL, Université de Lorraine, 54506 Vandouevre-lès-Nancy
Email : paola.schneider@univ-lorraine.fr
Tél : +33 (0)3 72 74 53 91
Renseignements :
Pour tout renseignement, vous pouvez contacter l'un des organisateurs : Manfred Madritsch, Chedy Raïssi, Jean-Sébastien Sereni ou Thomas Stoll