Category: seminars
Treillis de framing et coordonnées cubiques
summary: Les treillis de framing sont des familles d'ordres partiels définies très récemment par [von Bell--Ceballos, 2025] et [Berggren--Serhiyenko, 2024], en lien avec les polytopes de flots. On y retrouve comme cas particulier notables l'ordre faible sur le groupe symétrique, le treillis de Tamari, le treillis booléen et ...
Compléter des colorations partielles de hom shifts
summary: On étudie les shifts ou espaces de pavages de type fini : des colorations de la grille régulière infinie qui évitent un ensemble fini de motifs interdits. Il s'agit d'un modèle étudié en particulier comme source apparemment infinie de problèmes indécidables.
Les hom shifts sont une restriction du ...
À la recherche des nombres de Schur avec des LLMs
summary: Notre but est d’améliorer les bornes inférieures des nombres de Schur. Le nombre de Schur S(k) est le plus grand entier N tel qu’il existe une façon de colorier les entiers {1, ..., N } avec k couleurs sans qu’il existe trois entiers a, b, c de ...
Skeletal posets of the Tamari lattice and beyond
summary: Given a lattice \(L\), the subposet \(\mathrm{Spine}(L)\) of \(L\) is the union of the longest maximal chains in \(L\). Dually, the subposet \(\mathrm{Spine}'(L)\) of \(L\) is the union of the shortest maximal chains in \(L\). For certain lattices, these subposets are particularly well-behaved; an example ...
Reconstruction de graphes par oracle de distance
summary: Étant donné un graphe connexe G = (V,E) où les sommets sont connus et les arêtes sont cachées, nous avons accès à un oracle capable de répondre aux requêtes suivantes : étant donné deux sommets u et v dans V, l'oracle retourne la distance d'un plus court chemin ...
Automates cellulaires surjectifs et mesures de probabilité
summary: Les automates cellulaires sont un modèle de calcul simple consistant en une coloration d'un graphe infini régulier (typiquement, une ligne infinie) sur lequel on itère une transformation locale uniforme. Ce modèle est capable de calcul universel dans un certain sens, y compris quand la configuration initiale est choisie ...
Descentes et inversions dans les permutations
summary: On peut identifier une permutation avec son ensemble d'inversions. Si deux ensembles d'inversions sont disjoints et que leur union est aussi un ensemble d'inversions, on obtient donc une nouvelle permutation. C'est un cas assez rare et intéressant et on démontre un résultat sur le nombre ...
Decision-Theoretic Approaches in Learning-Augmented Algorithms
summary: We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, as well as stochastic measures that ...
Packing many dominating sets in a graph
summary: Given a graph G, a dominating set of G is a subset of vertices S such that every vertex not in S is adjacent to at least one vertex in S. While classical studies focus on finding the smallest dominating set of G, our focus shifts to finding the ...
Mobile Agents in Adversarial Networks: Perpetual Exploration in Presence of Malicious Host
summary: Perpetual exploration is a central problem in distributed computing, requiring a team of mobile agents to repeatedly visit every node of a network indefinitely. While the problem is well understood in benign environments, its complexity increases dramatically in the presence of adversarial nodes. A particularly challenging scenario arises even ...
Page 1 / 26 »