Mathématiques discrètes

Responsable : Patrice Ossona de Mendez

Propriétés asymptotiques des objets combinatoires de faible densité structurelle

L’étude de systèmes de plus en plus complexes sur lesquels sont collectés des masses de données de plus en plus importantes nécessite la conception d’algorithmes de traitement optimisés, tirant avantage au maximum des spécificités des réseaux sur lesquels ils sont appliqués.

Plusieurs constantes structurelles se dégagent des études de réseaux complexes: faible densité,  distribution des degrés fortement asymétrique et propriété de petit-monde.

Néanmoins, aucune de ces propriétés ne semble exploitable de manière algorithmique.

La théorie structurelle des graphes épars a induit la conception d’algorithmes paramétrés et d’algorithmes approchés, qui ont eu un impact fondamental en algorithmique de graphes. Ils ont notamment permis le développement de plusieurs méta-théorèmes algorithmiques, démontrant l’existence d’algorithmes efficaces adaptés à un large spectre de problèmes lorsqu’ils sont restreints aux graphes épars, telles les  classes d’expansion bornée ou, 0lus Géoéralement, les classes nulle part denses.

Ces classes admettent des algorithmes efficaces pour un grand nombre de problèmes, dont plusieurs problèmes importants spécifiques à l’étude des réseaux complexes et leurs propriétés caractéristiques se retrouvent aussi bien dans des modèles aléatoires de réseau complexes fondamentaux qu’empiriquement dans des réseaux réels d’intérêt général.

Il arrive également que les réseaux étudiés ne soient accessibles que par une représentation dérivée, et qu’ils apparaissent alors denses quoique de faible complexité structurelle. Ce point de vue, analogue aux problèmes de réduction de dimension rencontré en apprentissage profond ou à la recherche d’une approximation de faible rang en acquisition compressée, mène à la notion de classes structurellement éparses. L’étude structurelle et algorithmique de ces classes est devenu un enjeux majeur dans la recherche d’une généralisation à des classes héréditaires non éparses des méta-théorèmes obtenus pour les classes éparses.

L’étude des réseaux complexes ne se heurte pas seulement au problème de la taille et de la masse des données traitées, mais également à l’intérêt croissant pour l’étude de structures évoluant dans le temps. Comment les graphes réels évoluent-ils au fil du temps ? Quelles sont les tendances dans les réseaux sociaux, technologiques et informationnels ? Alors que de nombreuses études ont identifié des motifs typiques dans les réseaux statiques, peu d’analyses ont porté sur l’évolution des réseaux sur de longue périodes. La convergence et les limites de structures sont étudiés ici sous un point de vue unifiant les notions de limites gauches (Lovasz et al.) et de limites locales (Benjamini-Schramm), en considérant la convergence de la probabilité de satisfaction des formules du premier-ordre pour une affectation aléatoire indépendante et uniforme des variables libres. Cette étude dévoile, une fois de plus, l’existence d’un saut qualitatif à la frontière entre séquences d’objets structurellement éparses et séquences d’objets structurellement denses.

Notre point de vue est celui des mathématiques discrètes et de l’informatique théorique (complexité paramétrée, algorithmique distribuée, bases de données, etc.), bien que ses objets d’études s’étendent jusqu’à l’analyse (graphes mesurables, représentation de la convergence de structures par la convergence faible-, etc.), la théorie des modèles (structures stables ou NIP, modèles non-standards, espaces de types, jeux de Ehrenfeucht-Fraïssé, etc.), avec des incursions en théorie des probabilités, voire en algèbre.