T
- Marie Théret (Modal’X),
Comportement au 1er ordre de la constante de temps dans un modèle de percolation de premier passage de Bernoulli.
31/03/2022
Dans le modèle de percolation de premier passage sur $\mathbb{Z}^d$, on associe aux arêtes du graphe une famille de variables i.i.d. positives, représentant le temps aléatoire nécessaire pour traverser chaque arête. Il s’agit d’un modèle jouet pour étudier des phénomènes de propagation sur un réseau. La vitesse asymptotique moyenne de propagation dans une direction $v$ est donnée par l’inverse d'une constante $\mu(v)$ (qui dépend de la direction $v$, de la dimension $d$ et de la loi des temps de traversée d’arête) qu’on appelle constante de temps. Les théorèmes ergodiques sous-additifs nous assurent l’existence d’une telle vitesse asymptotique moyenne, mais ne nous permettent pas de calculer sa valeur. Pour des lois de temps de traversées d’arêtes générales, on ne sait en fait que très peu de choses sur la valeur de $\mu(v)$.
Dans cet exposé, nous nous intéressons à une famille de lois très simples pour les temps de traversée d’arête : une loi de Bernoulli de paramètre $1-\epsilon$. Pour $\epsilon=0$, $\mu_\epsilon (v) = \|v\|_1$. Nous étudions le comportement au premier ordre de $\epsilon \mapsto \mu_\epsilon (v)$ quand $\epsilon$ tend vers $0$.
Il s’agit d’un travail en collaboration avec Anne-Laure Basdevant et Jean-Baptiste Gouéré.
- Jean-Yves Thibon (LIGM, Marne-la-Vallée),
Réalisations polynomiales d’algèbres de Hopf combinatoires.
27/01/2012.
Transparents. Synthèse.
L'idée d'utiliser des algèbres de Hopf en combinatoire n'est pas très récente, elle remonte au moins à Rota dans les années 1970. Toutefois, c'est seulement depuis une quinzaine d'années qu'on a vu apparaître de nombreux exemples nouveaux. Ces algèbres de Hopf combinatoires (AHC) sont formées de combinaisons linéaires formelles d'objets combinatoires classiques, et leurs opérations (produit et coproduit) s'expriment en termes d'algorithmes de composition ou de décomposition de tels objets. Ces exemples sont souvent reliés (par des homomorphismes) aux fonctions symétriques ou quasi-symétriques. Or, ces dernières sont définies au moyen de variables auxiliaires, et leurs opérations sont induites par le produit ordinaire des polynômes, et une opération simple de dédoublement des variables. Il est donc tentant de rechercher des variables auxiliaires permettant une description similaire des autres AHC. Lorsque cela est possible, on parle de réalisation polynomiale de l'algèbre. On obtient alors en général une simplification importante de la théorie, ainsi que de nouvelles bases qui semblent paver la voie vers une théorie des fonctions spéciales non-commutatives.
- Nicolas Thiéry (LRI, Université Paris 11),
Nombre moyen de tresses dans les mots réduits et tableaux justifiés à droite.
2/06/2016.
Transparents.
En 2005, Vic Reiner a démontré que, en moyenne, l'on peut appliquer exactement une relation de tresse non triviale à un mot réduit de l'élément le plus long du groupe symétrique. Nous donnons une preuve bijective du résultat analogue lorsque l'on se restreint à la classe de commutation du mot réduit lexicographiquement minimal. Cette bijection fait intervenir, via les empilements de pièces de Viennot, un énoncé équivalent sur les tableaux standards justifiés à droite, et les opérateurs de promotion sur ceux-ci.
Travail commun avec Anne Schilling, Graham White et Nathan William.
- Béatrice de Tillière (Laboratoire de Probabilités et Modèles Aléatoires, UPMC),
Le Laplacien Z-invariant massique sur les graphes isoradiaux.
4/06/2015.
Transparents.
Après avoir expliqué la notion de Z-invariance pour les modèles de mécanique statistique, nous introduisons une famille à un paramètre (dépendant du module elliptique) de Laplaciens massiques Z-invariants définis sur les graphes isoradiaux. Nous démontrons une formule explicite pour son inverse, la fonction de Green massique, qui a la propriété remarquable de ne dépendre que de la géométrie locale du graphe. Nous expliquerons les conséquences de ce résultat pour le modèle des forêts couvrantes, en particulier la preuve d'une transition de phase d'ordre 2 avec le modèle des arbre couvrants critiques sur les graphes isoradiaux, introduit par Kenyon. Finalement, nous considérons la courbe spectrale de ce Laplacien massique et montrons qu'il s'agit d'une courbe de Harnack de genre 1.
Il s'agit d'un travail en collaboration avec Cédric Boutillier et Kilian Raschel.
- Christophe Tollu (LIPN, Villetaneuse),
Nombres de Littlewood-Richardson : modèles combinatoires, calcul et complexité.
29/03/2012.
Transparents.
Les nombres de Littlewood-Richardson sont des entiers naturels paramétrés par trois partitions d'entiers, qui énumèrent des points entiers dans des polytopes à sommets rationnels. Ils apparaissent dans l'étude des représentations des groupes généraux linéaires. L'exposé présentera quelques propriétés importantes de ces nombres, connues de longue date ou plus récemment découvertes, puis traitera de la complexité de leur calcul et du test de leur non-nullité, ce qui permettra de faire le lien avec la théorie géométrique de la complexité, un programme d'approche du problème P vs. NP à travers la théorie des invariants et la théorie des représentations, lancé il y a quelques années par K. Mulmuley et M. Sohoni.
- Cristina Toninelli (CNRS, Université Paris Dauphine),
Bootstrap percolation and kinetically constrained spin models: critical time scales.
30/01/2020.
Recent years have seen a great deal of progress in understanding the behavior of bootstrap percolation models, a particular class of monotone cellular automata. In the two dimensional lattice there is now a quite complete understanding of their evolution starting from a random initial condition, with a universality picture for their critical behavior. Much less is known for their non-monotone stochastic counterpart, namely kinetically constrained models (KCM). In KCM each vertex is resampled (independently) at rate one by tossing a p-coin iff it can be infected in the next step by the bootstrap model. In particular infection can also heal, hence the non-monotonicity. Besides the connection with bootstrap percolation, KCM have an interest in their own : when $p \to 0$ they display some of the most striking features of the liquid/glass transition, a major and still largely open problem in condensed matter physics. I will discuss some recent results on the characteristic time scales of KCM as $p \to 0$ and the connection with the critical behavior of the corresponding bootstrap models.
V
- Brigitte Vallée (GREYC-Caen),
Théorie de l’information : Sources, Séries de Dirichlet, Analyse réaliste d’algorithmes.
3/01/2011.
Transparents.
En algorithmique, on manipule très souvent des mots, notamment dans l'algorithmique du texte ; plus souvent encore, on manipule ce qu'on appelle communément des clés, notamment dans les algorithmes de tri ou de recherche, ou dans les bases de données. Une clé, comme un mot, est une suite finie de symboles sur un alphabet. En algorithmique du texte, on étudie les propriétés fines des mots, et leur influence sur l'efficacité des algorithmes. C'est alors le nombre de comparaisons entre symboles qui va être la bonne mesure de coût. La manière dont les mots sont produits, les corrélations possibles entre symboles vont jouer alors un rôle essentiel; cependant, on se limite le plus souvent à des modèles simples, qui conduisent donc à des analyses peu réalistes. En algorithmique générale, la structure d'une clé est "transparente" et n'est pas prise en compte dans l'analyse : on compte pour un coût unitaire la comparaison entre deux clés. Cela conduit à des énoncés classique du type "la complexité moyenne de l'algorithme QuickSort est en $O(n \log n)$, celle de QuickSelect est en $O(n)$". Cette mesure de coût est souvent peu réaliste, dès que les clés ont une structure complexe, dans le contexte des bases de données ou de la langue naturelle, par exemple.
Pour effectuer une analyse plus réaliste, il faut d'abord prendre en compte la structure d'une clé, et la considérer vraiment comme un mot. On remplace alors le coût unitaire d'une comparaison entre deux clés par le coût de la comparaison entre deux mots, égal au nombre de symboles comparés. L'algorithmique générale devient alors ... de l'algorithmique du texte. Ensuite, il faut définir un cadre adapté qui modélise la "source"qui "produit" le mot. Notre programme, décrit dans l'exposé, est donc le suivant (a) Donner un sens à ce qu'on appelle une "source générale", opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques. (b) Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet. (c) Utiliser les propriétés analytiques des séries génératrices des sources pour obtenir l'asymptotique des principales structures ou algorithmes construits sur les mots de la source : arbres binaires de recherche, arbres digitaux, et algorithmes QuickSort et QuickSelect.
- Brigitte Vallée (CNRS, Université de Caen),
The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace.
4/10/2019.
Transparents.
The Depoissonisation process is central in various analyses of the AofA domain. I first recall the two possible paths that may be used in this process, namely the Depoissonisation path and the Rice path. The two paths are rarely described (for themselves) in the literature, and general methodological results are often difficult to isolate amongst particular results that are more directed towards various applications.
The main results for the Depoissonisation path are scattered in at least five papers, with a chronological order which does not correspond to the logical order of the method. The Rice path is also almost always presented with a strong focus towards possible applications. It is often very easy to apply, but it needs a tameness condition, which appears a priori to be quite restrictive, and is not deeply studied in the literature. This explains why the Rice path is very often undervalued.
Second, the two paths are not precisely compared, and the situation creates various "feelings": some people see the tools that are used in the two paths as quite different, and strongly prefer one of the two paths; some others think the two paths are almost the same, with just a change of vocabulary. It is thus useful to compare the two paths and the tools they use. I also "follow" this comparison on a precise problem, related to the analysis of tries.
The talk also exhibits a new framework, of practical use, where the tameness condition of Rice path is proven to hold. This approach, perhaps of independent interest, deals with the inverse Laplace transform, which does not seem of classical use in this context. It performs very simple computations. This adds a new method to the Depoissonisation context and explains the title of the talk
I then conclude that the Rice path is both of easy and practical use : even though (much?) less general than the Depoissonisation path, it is easier to apply.
- Bruno Vallette (Université Paris 13),
La diagonale de l’associaèdre.
15/2/2018.
Les associaèdres forment une famille de polytopes convexes qui sont les réalisations géométriques du treillis des arbres de Tamari. Ils ont de nombreuses propriétés algébriques, combinatoires, topologiques et géométriques remarquables et ils jouent un rôle crucial dans la reconnaissance des espaces de lacets itérés, en lien avec la notion d’algèbre associative à homotopie près et en géométrie algébrique via les variétés toriques par exemple. Dans cet exposé, nous expliquerons ce qu’est le problème de la diagonale de l'associaèdre à la fois algébriquement avec le calcul opéradique et combinatoirement avec la décomposition cellulaire de ces derniers. Nous montrerons aussi pourquoi ce problème est crucial : sa résolution permet de considérer le produit de A_infini-catégories de Fukaya en topologique sympléctique, le produit tensoriel en théorie des cordes ou de faire des calculs des groupes d’homologie d’espaces fibrés. L’exposé tachera de rester le plus élémentaire possible et inclura des dessins significatifs.
- Michèle Vergne (Institut de Mathématiques de Jussieu),
Continuation analytique de polytopes.
6/12/2012.
Transparents. Synthèse.
Soit $P(b)$ un polytope défini par $N$ inéquations linéaires $(\mu_1, x) \leq b_1$, $(\mu_2, x) \leq b_2 ,\ldots, (\mu_N, x) \leq b_N$. Lorsque le paramètre $b$ varie dans un petit voisinage du paramètre initial $b^0$, le polytope $P(b)$ garde la même forme. En particulier, son volume $vol(b)$ est donné par une fonction polynomiale de $b$, lorque $b$ est proche de la valeur $b^0$. Ce polynôme change lorsque $b$ passe un mur. Varchenko a défini une "continuation analytique" $AP(b)$ de $P(b)$ : une réunion signée de polytopes $Q_i(b)$, de diverses dimensions. Si $b$ est proche de $b^0$, $AP(b) = P(b)$, mais $AP(b)$ est "analytique" en $b$. Par exemple le volume de $AP(b)$ (une somme signée de volumes) est un polynôme en $b$ pour tout $b\in \mathbb{R}^{N}$. Nous avons donné une formule de saut pour $AP(b)$. Cette étude est une version ensembliste de la variation en fonction du fibré en lignes $L$ du support du module $\sum_i (-1)^i H_i(M,O(L))$ lorsque $M$ est une variété torique. En particulier, on retrouve les formules de saut de Paradan pour le nombre de points entiers dans le polytope $P(b)$, lorsque le paramètre $b$ passe un mur.
Travail commun avec Nicole Berline.
- Laurent Viennot (INRIA & IRIF),
A trip through hub labeling in graphs,.
03/12/2020.
Hub labeling is a simple method for coding distances in a graph. It work surprisingly well in road networks where it offers a very compact representation of travel times between any two points and thus allows very fast computation of shortest paths. We will see a graph property called skeleton dimension that explains such efficiency and that seems to fit with road networks. This method has been shown to work well also on various practical graphs. An intriguing problem in distributed computing resides in building such compact representation for sparse graphs in general. We will see that a family of sparse graphs requires almost quadratic space for any hub labeling. These graphs are connected to the Rusza-Szemerédi function counting induced matchings in dense graphs. We also relate the problem of finding more general distance labels for these graphs to the sum index problem in communication complexity, a second hint that representing distances with sub-quadratic space seems hard even in sparse graphs.
- Xavier Viennot (Labri-Bordeaux),
Algèbres quadratiques, Robinson-Schensted, matrices à signes alternants et au-delà.
26/05/2011.
Transparents.
La plus simple algèbre de Weyl-Heisenberg, bien connue en physique, est définie par les opérateurs $U$ et $D$ (création et suppression de particules) avec la relation de commutation $UD=DU+Id$. Un des derniers articles de P. Flajolet (avec P. Blasiak) donne des modèles combinatoires pour la réduction sous "forme normale" de polynômes dans une telle algèbre quadratique. Nous introduisons un autre modèle combinatoire, initialisé par S.Fomin, et permettant de retrouver à partir de cette algèbre quadratique, la très classique correspondance de Robinson-Schensted entre les permutations et les paires de tableaux de Young de même forme. Partant de cet exemple fondamental, nous esquisserons une théorie générale, l' "Ansatz cellulaire", permettant d'associer à certaines algèbres quadratiques Q des objets combinatoires (les Q-tableaux) , ainsi que des constructions "semi-automatiques" de bijections, comprenant en particulier la correspondance de Robinson-Schensted et les célèbres matrices à signes alternants. Une approche équivalente est basée sur la nouvelle notion d'"automate planaire".
W
- Lauren K. Williams (Department of Mathematics, University of California, Berkeley),
Combinatorics of positroids.
16/10/2014.
Positroids are a class of matroids which were studied extensively by Postnikov, in connection with the positive Grassmannian. In joint work with Federico Ardila and Felipe Rincon, we prove a structure theorem for positroids: each positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected positroid on each of the blocks. This allows us to make a link with free probability. We also prove da Silva's 1987 conjecture that any positively oriented matroid is a positroid; that is, it can be realized by a set of vectors in a real vector space. It follows from this and an earlier topological result of the speaker that the positive matroid Grassmannian (or positive MacPhersonian) is homeomorphic to a closed ball.
- Lauren Williams (Harvard)
Bruhat interval polytopes and their friends.
Transparents.
24/10/2022.
Given two permutations u and v, with u<=v in Bruhat order, the Bruhat interval polytope P_{u,v} is the convex hull of all permutation vectors (z(1),...,z(n)) with u<=z<=v.Bruhat interval polytopes include the permutohedron, and are a subset of generalized permutohedra. I'll give an introduction to Bruhat interval polytopes (BIPs) and survey some of their nice properties; for example, each face of a BIP is again a BIP. I'll also explain how these polytopes are connected to tropical geometry and to flag matroids. If time permits, I'll mention some open problems, and indicate how these objects can be generalized to other Lie types and to other partial flag varieties.
Based on joint works with Kodama, Tsukerman, and Boretsky-Eur.
Z
- Lenka Zdeborova (Institut de Physique Theorique, CEA/SACLAY),
Clustering of sparse graphs: From phase transitions to optimal algorithms.
2/06/2016.
Transparents.
A central problem in analyzing networks or graphs is partitioning them into modules or communities, i.e. groups with a statistically homogeneous pattern of connections to each other or to the rest of the network. A principled approach to address this problem is to fit the network on a stochastic block model, this task is, however, belongs to the class of very hard algorithmic problems. Still it can be reformulated as the equilibrium statistical mechanics of a particular mean field spin glass model. We apply the cavity method that is standard in studies of spin glasses and structural glasses and compute the associated phase diagram of the problem. We describe consequences of this result for algorithmic tractability of the clustering problem. Further, we take advantage of the insight gained by the analysis to introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. We show that the algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit.
- Jiang Zeng (Institut Camille Jordan),
Combinatoire des permutations de Genocchi, positivité gamma et J-fractions.
3/02/2022.
Récemment, Hetyei, Lazar et Wachs, dans leurs études d’arrangement d’hyperplans, ont trouvé de nouvelles classes de permutations dont les cardinaux sont les nombres de Genocchi et Genocchi médians.
L’un de ces modèles est l’ensemble des permutations dont chaque descente est formée de nombres pair et impair. Eu et al. ont montré que le polynôme de descentes de ces permutations admet une décomposition gamma avec des coefficients positifs. Dans cet exposé nous considérons une généralisation du polynôme de descentes avec huit variables. En particulier nous montrons que la fonction génératrice de ces polynômes a un développement explicit en J-fraction. En spécialisant les paramètres, nous établissons des liens avec les polynômes généralisés de Dumont-Foata, ce qui nous permet de démontrer une conjecture de Lazar-Wachs sur les nombres de Genocchi médians, ainsi qu’un (p,q)-analogue de la formula de gamma-positivité avec une propriété de factorisation. La dernière est similaire à une ex-conjecture de Branden sur un (p,q)-analogue de polynômes Eulériens.
Référence: Cycles of even-odd drop permutations and continued fractions of Genocchi numbers, Q Pan, J Zeng arXiv preprint arXiv:2108.03200.
- Paul Zinn-Justin (Laboratoire de Physique Théorique et Hautes Energies – LPTHE, CNRS),
Des fibrés conormaux des variétés de Schubert au modèle de boucles de Brauer.
3/02/2014.
Dans ce travail en collaboration avec A. Knutson, nous investiguons la correspondance entre géometrie algébrique et systemes intégrables quantiques, sous l'angle des dégénerescences de Gröbner. Ce dernier point de vue a l'avantage d'être très combinatoire et de s'appliquer à
la fois en cohomologie et en K-théorie.
Suivant Knutson et Miller, je rappellerai le cadre le plus simple dans lequel on peut développer cette approche, qui est celui des variétés (matricielles) de Schubert et des polynômes de Schubert et de Grothendieck. Ensuite je formulerai plusieurs variations et extensions successives de cette approche, qui nous amèneront naturellement aux modèles de boucles sur réseaux: d'abord de boucles non-croisantes (modèle de Temperley--Lieb), puis si le temps le permet, de boucles croisantes (modèle de Brauer).
