2023-2024 / MATH0078-1

Research problems in discrete mathematics


30h Th, 10h Pr, 20h Mon. WS

Number of credits

 Master in mathematics (120 ECTS)10 crédits 
 Master in mathematics (60 ECTS)10 crédits 


Emilie Charlier, Julien Leroy, Michel Rigo


Michel Rigo

Language(s) of instruction

French language

Organisation and examination

All year long


Schedule online

Units courses prerequisite and corequisite

Prerequisite or corequisite units are presented within each program

Learning unit contents

Combinatorics is a branch of mathematics dealing with the "configurations" of a "discrete" set (in general finite). One usually looks for counting or efficiently enumerating elements of such a set, for the (possibly algebraic) structure of the set or also for its extremal properties (maximal elements, ...). Of course combinatorics on words is interested with (finite or infinite) words, i.e., sequences of symbols or letters belonging to a finite set.

Learning outcomes of the learning unit

The aim of this course is to prepare students to the study of some actual research questions in discrete mathematics or theoretical computer science. Problems arising from the representation of numbers and the recognizability (by finite automata) of the corresponding sets are used to introduce concepts from combinatorics on words. The following topics can be considered (the list is not exhaustive): integer base number systems and recognizable sets of integers (bounded gaps, syndeticity, ...), Cobham's theorems, p-automatic sequences (fiber, kernel, Prouhet's problem, ...), morphic words (i.e., sequences generated by iterated morphisms), normalization, sets definable in extended Presburger arithmetic, introduction to beta number systems (beta-shift, Bertrand-Schmidt theorem, Parry numbers, ...), linear number systems (theorems of Shallit, Hollander, Hansel, ...), Pisot numbers and associated number systems (Bertrand systems), return words, sturmian sequences and continued fractions, links with discrete geometry or ergodic theory, ...

At the end of this course, the student will be able to work autonomously, acting as a researcher in mathematics. He/she will be able to summarize an actual topic of research, to produce a corresponding document (article and/or talk) and to propose further investigations.

Prerequisite knowledge and skills

It is assumed that the student has a good background in discrete mathematics (e.g. graph theory, discrete mathematics, computability, formal language theory, combinatorics on words,  ...). In order to register for this course, the interested student must have a coherent program of study and demonstrate his/her motivation to develop a personal research activity (for instance, starting a Ph.D. or be introduced to state of the art results). The course organizers reserve the right to accept or reject a student registration. Prior to the start of the academic year, the student is invited to have an open discussion with the organizers.

Planned learning activities and teaching methods

Reading, summarizing and presenting research papers and text books, participating in seminars and reading groups, tailored courses, problem solving.

Mode of delivery (face to face, distance learning, hybrid learning)

Face-to-face course

Additional information:

This course, preparing to research, needs an active participation of the student. In order to learn the concepts independently, personal work and oral presentations given by the students will be sought. It is expected that students will mostly work alone. Appointements will also be scheduled. 

Recommended or required readings

This course mostly uses selected scientific research papers or books. As usual, scientific literature is in English. Some examples:

  • M. Lothaire, Combinatorics on words, Cambridge University Press (1997).
  • M. Lothaire, Algebraic combinatorics on words, Cambridge University Press (2002).
  • V. Berthé, M. Rigo (Eds.), Combinatorics, Automata and Number Theory, Cambridge University Press (2010).
  • V. Berthé, M. Rigo (Eds.), Combinatorics, Words, Symbolic Dynacmics, Cambridge University Press (2015).
  • J. Sakarovitch, Elements de théorie des automates, Vuibert (2003).
  • V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. (1994).
  • J.-P. Allouche, J. Shallit, Automatic sequences, Theory and applications, Cambridge University Press (2003).
  • Thomas S. Ferguson, Game Theory, UCLA.
  • J. Shallit, A second course in formal languages and automata theory, Cambridge University Press (2008).
  • E. Bach, J. Shallit, Algorithmic Number Theory, volume 1: efficient algorithms, MIT Press (1996).
  • A. de Luca, S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer (1999).

Exam(s) in session

Any session

- In-person

oral exam

Continuous assessment

Additional information:

Personal works realized all along the year (oral presentations, discussions, reports, solving exercises, ...) make the major part of the final mark. The final examination is made of a presentation (on a subject given in advance) and an oral examination on a limited part of the material presented during the year and its direct applications (student may also be asked to solve a small exercise on the blackboard).

Work placement(s)

Organisational remarks and main changes to the course


E. Charlier Institute of Mathematics (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.93.84 - E-mail : echarlier@ulg.ac.be
J. Leroy Institute of Mathematics (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.70 - E-mail : j.leroy@ulg.ac.be
M. Rigo Institute of Mathematics (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be

Association of one or more MOOCs