GT et PÉC de l'équipe Combinatoire et Interactions
The Combinatoire et Interactions seminar runs every Monday from 10h45 to 11h45. There is also a reserved schedule for a "mini-school" from 9h30 to 10h30. Both events happen in room 076 on the ground floor of LaBRI (building A30).
When a talk is recored it is available (live and recorded) at
https://u-bordeaux-fr.zoom.us/j/83326403471?pwd=VLapX1qCOgASs3V8OktWtKEr8dn041.1
Meeting ID: 833 2640 3471
Passcode: 1251442
Contact the secretaries (Vincent Delecroix, Oscar Fontaine and Juliette Schabanel) if you want to propose a talk or to receive announcements.
For the list of previous talks, look at the menu "GT CI" on the right side of this 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)
Lundi 25 mai: Pentecôte
Lundi 1 juin: à saisir
Lundi 8 juin: à saisir
Lundi 15 juin: à saisir
Lundi 22 juin: à saisir
Lundi 29 juin: à saisir