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 8 juin: à saisir
Lundi 15 juin: Nicolas Bonichon
Titre : Freeze Tag au-delà de l'analyse en pire cas
Résumé : Dans le Freeze Tag Problem (FTP), un unique robot éveillé doit réveiller tous les autres robots, initialement endormis. Dès qu'un robot est réveillé, il participe à son tour au réveil des robots restants. On cherche à minimiser le temps écoulé jusqu'au dernier réveil. L'analyse classique est celle du pire cas, où asymptotiquement, le meilleur ratio atteignable est 3 — entre la durée totale de réveil et la distance au robot le plus éloigné. Mais que se passe-t-il sur des instances typiques ?
Lundi 22 juin: Simon Barazer
Titre : Asymptotique bivariée et récurrences linéaires.
Résumé : Dans cet exposé, je parlerai des méthodes récentes développées par A. Elvey Price, W. Fang, B. Louf et M. Walner pour déterminer les comportements asymptotiques des solutions de récurrences bivariées. Ces méthodes se basent sur une approche d'abord heuristique qui permet de déterminer la forme de l'asymptotique, puis dans un second temps on utilise des arguments issus des marches aléatoires dans le quart de plan pour obtenir des équivalents. On verra comment ces méthodes peuvent s'appliquer au cas des nombres de Hurwitz monotones, que l'on a étudié avec B. Louf et si le temps le permet, aux généralisations possibles.
Lundi 29 juin: Xavier Viennot
Titre : Des permutations de Baxter aux matrices de Baxter-Knuth
Résumé : Les permutations de Baxter forment un sujet populaire, très parcouru au sein du groupe combinatoire. En Septembre 2021 Don Knuth a proposé une extension aux matrices de la notion de permutations de Baxter, extension qu’il appelle matrices de Baxter, et que je propose d’appeler matrices de Baxter-Knuth. Cette extension présente certaines analogies avec le passage de RS vers RSK (correspondance de Robinson-Schensted entre permutations et paires de tableaux de Young standards vers la correspondance de Robinson-Schensted-Knuth entre matrices et paires de tableaux de Young). Dans cet exposé nous proposons quelques idées pour accompagner cette extension.
Pour ceci nous avons besoin de revenir à la preuve bijective originale de la célèbre formule donnant le nombre de permutations de Baxter (formule de Ron Graham et co. 1978). Au passage, je raconterai quelques détails insolites de cette formule ("le dessous des cartes »). Cette preuve de la formule utilise la notion « d’histoire de Laguerre », notion provenant de la théorie des polynômes orthogonaux en analyse et de la théorie des structures de données en informatique. Ces histoires (de Laguerre!) sont en bijection avec les permutations.
Puis nous introduisons une nouvelle notion appelée « Laguerre empilements de segments », en bijection avec les permutations, notion introduite dans le cadre de la théorie des empilements de pièces. Comme l’a remarqué Bishal Deb, ces objets ne sont pas sans rappeler les « non-crossing arc diagrams », notion introduite par Nathan Reading en 2015. Les deux notions sont en bijection et apparaissent naturellement des objets dénombrés par les nombres de Baxter.
Enfin, si le temps le permet, nous terminerons cette randonnée Baxterienne en rappelant la version géométrique de la célèbre correspondance RS, puis de son extension RSK, afin de donner des idées pour une extension matricielle des "Laguerre-Baxter empilements de segments ».
L'exposé sera suivit d'un pot dans la salle du séminaire pour célébrer la fin d'éméritat de Xavier.
Lundi 6 juillet : Jean-François Marckert
Titre : Asymptotic behavior of Voronoi cells on the Erdos-Rényi graph
Résumé : The random graph G(n,p) is the graph whose set of vertices is V_n = {1, 2, ...,n} and whose set of edges E_n, is obtained by keeping each edge of the complete graph K_n, independently, with probability p. The graph distance D on G(n,p), makes of this random graph, a random metric space... and on a metric space, we can define Voronoi cells: Fix a parameter k, a positive integer, and let us call seeds the vertices 1 to k. The Voronoi cell of the seed i is defined as Cell( i, k ) = { v in V_n : D(i, v) < D(j,v), for each seed j, different from i} in words: the set of nodes in V_n closer to the seed i than to the other seeds. We can also define interfaces cells: for a subset A of the seeds set Cell (A, k ) = { v in V_n: D(i,v) is the same for all i in A, and D(i,v)< D(j,v), for all seed j not in A} in words: the set of nodes at equal distance to all seeds in A, and further to all other seeds.
The random graph G(n,p) admits a phase transition at 1+ : if p = c / n with c >1, then, if L_n is the size of the largest connect component of G(n, c / n), then L_n / n converges to a positive deterministic value L(c) (in probability), but it converges to 0, for c in [0,1]. The second largest connected component, has a sublinear size, for all value of c. Hence, for c>1, there are some (asymp.) positive probability for each cell, to belong to the giant component, in which case, those belonging to the giant component, will share this large linear territory.
In this work, we prove that, jointly for all the cells size, and for all the interface sizes, ( | Cell (A, k)| / n , A in PowerSet({1,...k}) ) converges in distribution to a random limit, with an explicit distribution (the complete statement is a bit more complex than that, however).
Joint work with Nicolas Broutin and Cécile Mailler
Vacances d'été
Lundi 14 septembre: Nathan Pagliaroli