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

• Matthieu Rosenfeld, principal investigator
• Daniel Gonçalves
• William Lochet
• Mickael Montassier
• Pascal Ochem
• Alexandre Pinlou
• François Pirot
• Gwenaël Richomme