Journée Combinatoire
3 Juillet 2018
Salle B107, Institut Galilée
Justine Falque Algèbre des orbites des groupes à profil polynomial, preuve des conjectures de Cameron et de Macpherson
Étant donné un groupe de permutation infini G, on définit la fonction qui à tout entier naturel n associe le nombre d'orbites de sous-ensembles de cardinal n, pour l'action induite de G sur les sous-ensembles d'éléments.
Cameron a conjecturé que cette fonction de comptage (le profil de G) est un quasi-polynôme dans le cas où sa croissance est polynomiale.
Une autre conjecture, plus forte, a été émise plus tard par un de ses étudiants, Macpherson. Elle concerne une certaine structure d'algèbre graduée sur les orbites
de sous-ensembles, créée par Cameron, et suppose que si le profil de G est polynomial, alors son algèbre des orbites est de type fini.
L'exposé présentera ces deux conjectures et leur contexte, ainsi que les idées de la preuve de la conjecture de Macpherson, fruit d'un travail commun avec Nicolas Thiéry (avec les conseils précieux de Peter Cameron lui-même).
Pablo Rotondo Efficient GCD computation: the continued logarithm algorithm and ergodic theory
Introduced by Gosper in 1978, the Continued Logarithm Algorithm computes the gcd of two integers efficiently, performing only shifts and subtractions. Shallit has studied its worst-case complexity in 2016, showing it to be linear. Here, we perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values, with explicit constants. Our analysis involves the dynamical system underlying the algorithm, which produces continued fraction expansions whose quotients are powers of 2. Even though studied by Chan in 2005, this system from an Ergodic Theory perspective, the presence of powers of 2 in the quotients gives a dyadic flavour which cannot be analysed only with Chan's results. Thus we introduce a dyadic component and deal with a two-component dynamical system. With this new mixed system at hand, we provide a complete average-case analysis of the algorithm.
Paulina Cecchi Dendric words and dendric subshifts
To every factor w of an infinite word x in a finite alphabet, we can associate a bipartite graph, called the extension graph of w, in which one puts edges between left and right copies of letters a, b such
that awb is a factor of x. The word x is said to be dendric if for all factor w of x, the extension graph of w is a tree. Dendric words are
therefore defined in terms of combinatorial properties of their language. Dendric subshifts are symbolic systems defined using dendric words. We will talk about some dynamical properties of dendric subshifts.
Delphin Sénizergues Degrés limites dans les arbres à attachement préférentiel affine
On introduit le modèle d'arbres suivant. On se donne une suite arbitraire de nombres réels positifs $(a_n)_{n\geq 1}$. On définit $T_1$ comme l'arbre à un seul sommet d'étiquette $1$. Si $T_n$ est déjà construit, $T_{n+1}$ est obtenu en rajoutant un sommet étiqueté $n+1$ à l'arbre $T_n$. Le nouveau sommet est un enfant du sommet $k\geq n$ avec une probabilité proportionnelle à $a_k+deg(k)$, où $deg(k)$ est le degré du sommet dans l'arbre $T_n$. On s'intéressera à l'évolution de la suite des degrés des sommets de l'arbre. Sous certaines conditions sur la suite des réels $(a_n)_{n\geq 1}$, la suite des degrés adéquatement renormalisés converge p.s. (dans $l^p$ pour p assez grand) vers une suite aléatoire, qui peut être décrite comme les accroissements successifs d'une chaîne de Markov. Pour certaines suites $(a_n)$, la loi de la chaîne de Markov est même explicite. La preuve utilise des résultats classiques sur les urnes de Pólya, que je rappellerai.