Obstructions locales et méthode de comptage // Local obstructions and counting method

Le Lemme Local de Lovász (LLL), introduit par Erdős et Lovász, est un outil probabiliste fondamental permettant d'établir l'existence d'objets combinatoires satisfaisant certaines propriétés en évitant des événements indésirables. Il repose sur une condition garantissant que la probabilité qu'aucun de ces événements ne se produise est non nulle.

Le LLL a de nombreuses applications en combinatoire, par exemple à la satisfiabilité des formules k-SAT, la coloration d'hypergraphes et la théorie des nombres. Ses variantes, comme le lemme asymétrique et l'algorithme de Moser-Tardos, ont conduit à des avancées notables. En physique statistique, des concepts similaires tels que le polynôme d'indépendance et l'expansion en clusters offrent des perspectives alternatives.

Matthieu Rosenfeld a récemment proposé une approche basée sur un argument de comptage, qui fournit parfois de meilleures bornes que le LLL. Cette méthode, plus simple à optimiser et à combiner avec d'autres techniques, a déjà prouvé son efficacité pour lesformules k-SAT, en coloration de graphes et en combinatoire extrémale.

L'objectif de cette thèse est d'étudier des problèmes combinatoires ouverts adaptés à cette technique. L'accent est mis sur la recherche de structures combinatoires discrètes évitant certaines obstructions locales. En plus de résoudre ces problèmes, un but secondaire est d'améliorer la compréhension de cette méthode et d'en explorer les limites.

De nombreuses familles de problèmes pourront être considérés dans cette thèse, nous donnons trois exemples particulièrement prometteurs :

Combinatoire des mots : L'argument de comptage est déjà utilisé dans ce domaine, notamment en conjonction avec les automates. Un exemple emblématique est le théorème de Thue (1906), qui affirme l'existence de mots infinis sans carrés sur un alphabet de trois lettres. Cette thèse vise à coupler la technique de comptage avec des preuves assistées par ordinateur pour obtenir des résultats plus précis sur des variantes de ce problème.

Théorie de Ramsey : Le théorème de Ramsey garantit l'existence de structures ordonnées dans des graphes suffisamment grands. Une question ouverte importante concerne l'amélioration des bornes connues sur les nombres de Ramsey, en particulier celles loin de la diagonale. La méthode de comptage a déjà été utilisée pour obtenir la meilleure borne inférieure connue sur R(k, k), et cette thèse essayera d'appliquer cette technique à d'autres paramètres.

Combinatoire extrémale : Le théorème de Turán décrit la densité minimale d'arêtes qui force une grande clique dans un graphe. On s'intéressera à des généralisations de ce résultat aux hypergraphes, où peu de densités critiques sont déterminées; par exemple l'hypergraphes 3-uniformes complets sur 4 sommets est encore ouvert.

En somme, cette thèse explore et affine une technique récente et prometteuse en combinatoire, tout en apportant des solutions à des problèmes ouverts dans plusieurs domaines connexes de la combinatoire.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The Lovász Local Lemma (LLL), introduced by Erdős and Lovász, is a fundamental probabilistic tool that establishes the existence of combinatorial objects satisfying certain properties by avoiding undesirable events. It relies on a condition ensuring that the probability of none of these events occurring is nonzero.

LLL has numerous applications in combinatorics, such as in k-SAT formula satisfiability, hypergraph coloring, and number theory. Its variants, such as the asymmetric lemma and the Moser-Tardos algorithm, have led to significant advances. It is also strongly related to concepts from statistical physics, like the independence polynomial and the cluster expansion.

Matthieu Rosenfeld recently introduced an approach based on a counting argument, which sometimes provides better bounds than LLL. This method, simpler to optimize and combine with other techniques, has already proven effective in k-SAT formula analysis, graph coloring, and extremal combinatorics.

The objective of this thesis is to study open combinatorial problems that are well-suited to this technique. The focus is on finding discrete combinatorial structures that avoid certain local obstructions. In addition to solving these problems, a secondary goal is to deepen the understanding of this method and explore its limitations.

Many families of problems can be considered in this thesis, with three particularly promising examples:

Combinatorics on Words: The counting argument is already used in this field, notably in conjunction with automata. A well-known example is Thue's theorem (1906), which states the existence of infinite square-free words over a three-letter alphabet. This thesis aims to refine the combination of counting techniques with computer-assisted proofs to obtain more precise results on variants of this problem.

Ramsey Theory: Ramsey's theorem guarantees the existence of ordered structures in sufficiently large graphs. An important open question concerns improving known bounds on Ramsey numbers, particularly those far from the diagonal. The counting method has already been used to obtain the best-known lower bound on R(k, k), and this thesis will explore applying this technique to other parameters.

Extremal Combinatorics: Turán's theorem describes the minimum edge density that forces a large clique in a graph. This thesis will study generalizations of this result to hypergraphs, where few critical densities are determined (for instance, the case of 3-uniform complete hypergraphs on 4 vertices remains open).

In summary, this thesis aims to explore and refine a recent and promising technique in combinatorics while providing solutions to different open problems from combinatorics.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2025

Contrat doctoral

Concours pour un contrat doctoral

Université de Montpellier

166 I2S - Information, Structures, Systèmes

Compétences en combinatoire, math discrète, et programmation.
Skills in combinatorics, discrete math, and programming.