GT et PÉC de l'équipe Combinatoire et Interactions
La petite école et le séminaire de l'équipe Combinatoire et Interactions (CI) ont lieu les lundis. Les horaires sont de de 9h30 à 10h30 pour la PÉC et de 10h45 à 11h45 pour le GT. Ils ont lieu dans la salle 076 au rez-de-chaussée du LaBRI (bâtiment A30).
Lorsque l'exposé est filmé il est retransmis via zoom
https://u-bordeaux-fr.zoom.us/j/83326403471?pwd=VLapX1qCOgASs3V8OktWtKEr8dn041.1
Meeting ID: 833 2640 3471
Passcode: 1251442
Contactez les responsables (Vincent Delecroix, Oscar Fontaine et Juliette Schabanel) si vous voulez proposer un exposé. Pour recevoir les annonces de la PÉC ou du GT, envoyez un mail à sympa[at]diff.u-bordeaux.fr avec comme objet "subscribe labri.cea-gt".
Pour l'historique des exposés précédents, voir le menu "GT CI" à droite de la page.
2025-2026
Lundi 4 mai: Guillaume Lagarde (LaBRI, Bordeaux)
Exceptionnellement en salle 178 (exposé commun avec AlgoDist)
Titre: Analyzing and Leveraging the k-Sensitivity of LZ77
Résumé:
We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string can deteriorate or improve its compression. Our first result is a tight upper bound for k edits: ∀w'∈B(w,k), we have C_{LZ77}(w') ≤ 3 C_{LZ77}(w) + 4k. This result contrasts with Lempel-Ziv 78, where a single edit can significantly deteriorate compressibility, a phenomenon known as a « one-bit catastrophe ».
We further refine this bound, focusing on the coefficient 3 in front of C_{LZ77}(w), and establish a surprising trichotomy based on the compressibility of w. More precisely we prove the following bounds:
- if C_{LZ77}(w) ≲ k^{3/2} √n, the compression may increase by up to a factor of ≈3,
- if k^{3/2} √n ≲ C_{LZ77}(w) ≲ k^{1/3} n^{2.3}, this factor is at most ≈2,
- if C_{LZ77}(w) ≳ k^{1/3} n^{2.3}, the factor is at most ≈1.
Finally, we present an ε-approximation algorithm to pre-edit a word w with a budget of k modifications to improve its compression. In favorable scenarios, this approach yields a total compressed size reduction by up to a factor of ~3, accounting for both the LZ77 compression of the modified word and the cost of storing the edits, C_{LZ77}(w')+k log |w|.
Lundi 11 mai: Baptiste Louf (IMB, Bordeaux)
Petite école de Combinatoire: Comment dériver des expansions asymptotiques ?
Si on a une expansion asymptotique pour une certaine fonction dérivable f, il est tentant de dériver cette expansion terme à terme pour obtenir une expansion de f’. A priori, ça n’est pas autorisé, mais il s’avère que ça marche dans « la plupart des cas » (à une subtilité près). Le bon formalisme est celui des corps de Hardy, un concept assez simple mais méconnu, qui explique justement dans quel contexte on peut « dériver des expansions asymptotiques », et qui peut simplifier grandement certains calculs fastidieux.
puis exposé :
Titre: Nombres de Hurwitz de très grand genre et temps de mélange de la marche aléatoire sur S_n
Résumé: Les nombres de Hurwitz sont un modèle de géométrie combinatoire des surfaces (au même titre que les cartes, les surfaces hyperboliques, les surfaces de translation, etc.). On s’intéresse ici à leur asymptotique de grand genre, c’est à dire quand leur genre et leur taille tendent vers l’infini. La question générale est très difficile, mais si on contraint le genre à être beaucoup plus grand que la taille, le problème devient plus simple et on peut obtenir des résultats asymptotiques simples.
En interprétant les nombres de Hurwitz comme des factorisations de permutations, on peut s’inspirer de résultats classiques de Diaconis et Shahshahani concernant le temps de mélange de la marche aléatoire sur le groupe symétrique pour démontrer le résultat.
Travail en commun (en cours de rédaction) avec Lucas Teyssier (Nancy)
Lundi 18 mai: Dorian Perrot (LORIA, Nancy)
Titre : CP1-structure, développante et holonomie discrètes d'une surface.
Résumé : La première partie de cet exposé consistera à ajouter progressivement de la structure sur un espace topologique afin de pouvoir définir --dans le cas continu-- une CP1-structure d'une surface, application développante et son holonomie. Dans la deuxième partie, nous étudierons et construirons un pendant discret de ses objets en montrant les similarités avec les constructions continues.
Lundi 25 mai: Pentecôte
Lundi 1 juin: Yvan Le Borgne
Lundi 8 juin: à saisir
Lundi 15 juin: à saisir
Lundi 22 juin: à saisir
Lundi 29 juin: Xavier Viennot
Lundi 6 juillet : Jean-François Marckert
Vacances d'été
Lundi 14 septembre: Nathan Pagliaroli