CADO: Counting Argument for Discret Objects

Abstract

In 2020, a new proof technique relying on a counting argument emerged. This technique belongs to a family of techniques including Lovász Local Lemma and Entropy Compression. These techniques are instrumental in proving the existence of combinatorial objects under specific constraints. They have found numerous applications in combinatorics on words, graph theory, tilings, group theory, and many other related areas.

The most basic version of the counting argument yields bounds identical to one of the versions of entropy compression. Moreover, the proofs are considerably simpler, relying on elementary combinatorial arguments such as inductions and bijections. This simplicity has enabled different authors to easily push this argument further to solve open problems that resisted other known techniques. The objective of the project is to study the counting argument and some related techniques to improve their applications. The success of this project will be measured by the new problems that we can solve by utilizing these techniques. We will also improve our understanding of these techniques and of the way they relate to each other.

Members

Publications

TBD

Post-doc position in Montpellier

A 1-year postdoctoral position in combinatorics and discrete mathematics is available at LIRMM (Montpellier, France). The successful candidate will work with me and join the CADO project (Counting Arguments and Discrete Objects). The project explores probabilistic and combinatorial proof techniques, such as entropy compression and the Lovász Local Lemma, in connection with counting approaches.

The postdoc will work within the general themes of the project, with particular interest in applications to combinatorics and related areas (including combinatorics on words, graph theory, tilings, etc.). Candidates whose research interests broadly overlap mine, but who are not familiar with the approaches considered in the project, are also very welcome to apply. The position comes with no teaching duties.

The planned start date is Autumn 2026, with some flexibility.

Application deadline: March 31, 2026

Applications should be submitted by email to matthieu.rosenfeld@lirmm.fr and should consist of:

  • a curriculum vitae with a list of publications,
  • a short "cover letter" (a few paragraphs in the email suffice).

Informal inquiries are welcome and should be addressed to matthieu.rosenfeld@lirmm.fr.