Counting Argument for Discret Objects – CADO

In 2020, the principal investigator of this project introduced a proof technique with applications in many areas related to combinatorics. This proof technique relies on a counting argument and belongs to a family of techniques such as the Lovasz 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 the PI and others to 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 we can solve by utilizing these techniques.