Séminaire de l'Équipe Modèles Combinatoires

10 mars 2010 Konstantinos Panagiotou Percolation in Random Networks In the classical Erdős-Rényi model of random graphs we begin with an empty graph on n vertices, and in each round we add an edge, drawn uniformly at random from the set of all possible edges. A celebrated result states that if we parametrize n/2 rounds as a single time step, a phase transition occurs at time 1. There, a giant connected component that contains a linear in n number of vertices makes its emergence for the first time.
An important question in this context is whether the appearance of the giant can be delayed or accelerated by modifying the process slightly. One such modification is motivated by the power of choice: in each round we add an edge, which can be chosen according to some desired rule between two (or more) random edges.
In this talk I will review some results regarding such processes. Then I will show how the precise study of them can be reduced to finding solutions of certain partial differential equations, and I will reveal a connection to singularity analysis of generating functions. The talk will conclude with future perspectives and some conjectures.

31 mars 2010 Laurent Menard Etude de la quadrangulation infinie uniforme Les quadrangulations sont des plongement de graphes planaires dans la sphère pour lesquels toutes les faces sont de degré 4. Nous allons nous intéresser à la quadrangulation infinie de loi “uniforme”, pour laquelle il existe deux constructions. La première, naturelle du point de vue des cartes, consiste à prendre la limite locale de grandes quadrangulations aléatoires de loi uniforme parmi les quadrangulations de même taille. La seconde repose sur une extension de la bijection de Schaeffer: on construit dans un premier temps un arbre infini de loi uniforme, puis on transporte la loi de cet arbre sur l'ensemble des quadrangulations infinies avec la bijection. Nous détaillerons ces deux constructions et montrerons qu'elles mènent bien au même objet. Nous verrons ensuite quelques applications de ces deux points de vue.

21 avril 2010 Alice Jacquot Une bijection entre des familles de lambda-termes et de cartes Nous considérons les lambda-termes sans variable libre où chaque lambda lie exactement une variable. Nous présentons une bijection entre ces lambda-termes et les cartes triangulées pointées, basée sur la présentation en arbre enrichis d'arcs retour vers des noeuds unaires symbolisant les déclarations de variables. Cette vision alternative permet une énumeration exacte et asymptotique (ce qui est difficile à partir des équations différentielles qui décrivent la serie génératrice des lambda-termes). Ceci nous permet aussi de générer aléatoirement uniformement un lambda terme de taille n en temps linéaire. En généralisant cette bijection, nous pouvons résoudre d'autres équations différentielles par une réécriture en terme de cartes construites par recollement de demi-arêtes.

12 mai 2010 Cedric Saule énumération de structures d'ARN avec pseudo-noeuds En 2004, Anne Condon et ses co-auteurs dressèrent une classification des algorithmes exactes de prédiction de structures ARN ab initio avec pseudonoeuds basée sur le degré de généralité des structures qu'ils peuvent prédire. Ils montrèrent que ces classes sont en relation d'inclusion. Nous proposons d'évaluer le compromis entre complexité en temps et le nombre de structures prédictibles par chaqu'un de ces algorithmes. En particulier nous montrerons qu'il existe une bijection entre les structures de la classe de Lyngso et Pedersen à n arcs et les cartes planaires enracinées sans isthmes à un ou deux sommets et n arêtes. Nous montrerons aussi que ces structures peuvent être codées par des langages algébriques non ambigüs. Nous en déduisons la série génératrice et le comportement asymptotique du nombre de structures. Nous ajouterons également deux classes de structures à cette classification.
Nous présenterons également une classe d'équivalence pour les structures avec pseudonoeud et nous montrerons que ces structures sont en bijection avec les arbres ternaires.

19 mai 2010 Krajewski Thomas Une preuve combinatoire de la formule des crochets de Postnikov Au cours d'un exposé donné en juin 2004 au MIT, Alexander Postnikov a présenté une formule des crochets pour les arbres binaires plans
Cette identité est issue de calculs de volumes de permutohèdres, et à la fin de son exposé, Alexander Postnikov a proposé comme exercice d'en donner une démonstration combinatoire (voir http://www-math.mit.edu/ apost/talks/perm-slides.pdf). En utilisant des techniques de théorie perturbative des champs, nous donnerons une démonstration combinatoire d'une généralisation de l'identité où son membre de droite est remplacé par le nombre de graphes connexes et orientés avec n arêtes portant des étiquettes et m cycles indépendants.

26 mai 2010 Robert Cori Les factorisations des permutations comme produit de deux grands cycles On considérera le problème suivant qui peut s'exprimer de deux manières différentes :

Pour une permutation \(\sigma \in S_n\) donnée de combien de façons peut-on écrire \(\sigma = \alpha \beta\) ? Où \(\alpha\) est un \(n\)-cycle et \(\beta\) ou bien \(n\)-cycle ou bien un \((n-1)\)-cycle.
Si on choisit deux grands cycles au hasard dans \(S_n\) quelle est la probabilité que leur produit soit une permutation ayant \(k\) cycles ?

On reviendra sur des résultats de Boccara (1980), Stanley (1980 puis 2009) et Zagier (1995) pour en donner des preuves bijectives inspirées par des constructions combinatoires dues à A Lehman (1973), A Machi' (1992), G. Schaeffer (1998). Le lien avec des travaux très récents de V. Feray et E. Vassilieva sera aussi précisé.
Les résultats présentés font l'objet d'une communication commune de l'orateur avec M. Marcus et G. Schaeffer

2 juin 2010 Nicolas Broutin Graphes aléatoires: quelques constructions de la limite d'échelle La structure des distances dans les grandes structures aléatoires est souvent d'un intérêt majeur pour bon nombre d'applications. Malheureusement, jusqu'à maintenant, les seuls objets pour lesquels la limite d'échelle est connue précisément sont essentiellement des arbres. Un premier pas vers une généralisation consiste à considérer des graphes contenant suffisamment peu de cycles. Nous nous intéresserons au modèle des graphes aléatoires. Nous montrerons comment décrire précisément les distances dans la phase critique en utilisant l'arbre continu d'Aldous. Nous donnerons en particulier plusieurs constructions de l'espace métrique limite qui éclaire differents aspects de l'objet.
Travail en collaboration avec L. Addario-Berry et C. Goldschmidt

9 juin 2010 Eric Fusy Bijections pour les cartes planaires Nous reformulons dans un contexte dual, et en nous appuyant sur les orientations eulériennes, les bijections dues à Bouttier, Di Francesco et Guitter qui permettent de compter les cartes planaires avec controle sur la distribution des degrés des sommets. Nous en profitons pour donner une preuve simple de la formule F_{a,b}(t)=c_{a,b}R(t)^{(a+b)/2} due à Bertrand Eynard, où F_{a,b}(t) compte les cartes planaires avec 2 faces marquées de degrés a et b et toutes les autres faces de degré pair, c_{a,b} est une constante ne dépendant que de a et b, et R(t) est une série algébrique comptant une certaine famille d'arbres (ou mobiles) enracinés.

16 juin 2010 Juanjo Rue Enumération asymptotique de familles de graphes non étiquetées We present a unified general method for the asymptotic study of graphs from the so-called “subcritical” graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works both in the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number \(g_n/n!\) (resp. \(g_n\)) of labelled (resp. unlabelled) graphs on \(n\) vertices from a subcritical graph class \({\mathcal{G}}=\cup_n {\mathcal{G}_n}\) satisfies asymptotically the universal behaviour \[g_n\ \! =\ \! c\ \!n^{-5/2}\ \!\gamma^n\ \! (1+o(1))\] for computable constants \(c,\gamma\), e.g. \(\gamma\approx 9.38527\) for unlabelled series-parallel graphs, and that the number of vertices of degree \(k\) (\(k\) fixed) in a graph chosen uniformly at random from \(\mathcal{G}_n\), converges (after rescaling) to a normal law as \(n\to\infty\).
This is a joint work with Michael Drmota, Eric Fusy, Mihyun Kang and Veronika Kraus.

23 juin 2010 Alfredo Viola Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets In this talk we present the first distributional analysis of both, a parkingproblem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a \(b\alpha\)-full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size \(m\) and with \(n\) elements. We also present results related with the distribution of bucket occupancy. A key element in the analysis is the use of a new family of numbers, that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets.

22 septembre 2010 Veronika Kraus The Degree Distribution in Unlabelled Subcritical Graph Families We consider the random variable \(X_n^k\), counting the number of vertices of degree \(k\) in a randomly chosen graph of size \(n\) of given families. We prove a central limit theorem for \(X_n^k\) with expected value \(E(X_n^k) \sim \mu_k n\) and variance \(V(X_n^k)\sim\sigma_k^2 n\), both asymptotically linear in \(n\), for any unlabelled subcritical family. Further, we show that a central limit theorem of the same type holds for the families of both rooted and unrooted unlabelled \(2\)-connected outerplanar or series-parallel graphs, which are subcritical families.

29 septembre 2010 Alejandro Morales q-analogues of derangements and fixed point free involutions and relations to q-rook numbers One q-analogue of permutations as bijections is the set of invertible matrices over a finite field. We study the general problem of counting matrices over finite fields with certain rank and whose support avoids a set for the entries. It is known that for general sets the answer will not be a polynomial in q. We give polynomial q-analogues of derangements (counting invertible matrices with zero diagonal) and of fixed point free involutions (counting invertible symmetric matrices with zero diagonal in odd char). We then survey a relation between the general counting problem and Garsia and Remmel's q-rook numbers that, thanks to a result from Kerov, suggests a connection to unicellular maps.
The first part of the talk is joint work with Joel Lewis, Ricky Liu, Greta Panova, Steven Sam, and Yan Zhang.

6 octobre 2010 Juanjo Rue Dynamic programming for graphs on surfaces In this paper we provide a general framework to bound the size of the tables of dynamic programming algorithms over branch decompositions of graphs on surfaces. The existing \emph{fast} algorithms for non-local subgraph problems on bounded-genus graphs are based on the following strategy: given a graph embedded in a surface, repeatedly remove handles (cutting along non-contractible nooses) to reduce the bounded-genus graph down to a planar graph, where Catalan structures arguments are possible.
Our approach is essentially different: instead of reducing ourselves to the planar case, we exploit directly the combinatorial structure of the topological surface. Namely, we count the number of non-crossing partitions on a generic surface with boundaries using two powerful tools from combinatorics: we apply \emph{singularity analysis} over expressions obtained by the \emph{symbolic method}. To do so, we first construct an appropriate branch decomposition of the input graph with nice topological properties, which we call \emph{surface cut decomposition}. At that point the machinery of the symbolic method and singularity analysis comes into play, giving a precise asymptotic enumeration of the number of non-crossing partitions on a surface with boundaries.
When applied to design subexponential exact algorithms, our methodology allows us to improve previous running times for some classical graph-theoretical problems. For instance, given a graph on \(n\) vertices embedded in a surface of Euler genus \(g\), the algorithm for solving \textsc{Hamiltonian Cycle} runs in time \(2^{\mathcal{O}(g\sqrt{g \cdots})} \cdot n^{\mathcal{O}(g^2)}\). Applying our techniques, the running time becomes \(2^{\mathcal{O}(\sqrt{g \cdot n})} \cdot n^{\mathcal{O}(g)}\cdot 2^{\mathcal{O}(g \log g)}
This is a joint work with Ignasi Sau (CNRS) and Dimitrios Thilikos (Kapodistrian University of Athens)
A preliminary version of this work was presented in July at ICALP'10, and an extended version (not definitive yet) can be found here http://hal.archives-ouvertes.fr/inria-00443582/fr/

3 novembre 2010 Gwendal Collet Cartes avec un nombre fixé de trous Dans une carte en genre quelconque, un trou est une face munie d'un coin marqué. Dans des travaux récents, Bertrand Eynard développe une méthode analytique permettant de compter les cartes avec des trous de longueur fixée en genre pour les séries génératrices dans le cas quasi-biparti (i.e., les faces non-marquées sont de degré pair) planaire avec 2 et 3 trous.
L'objet de cet exposé sera de donner une interprétation à ces cas simples, mettant au jour la structure combinatoire sous-jacente. On exploitera en particulier la bijection de Bouttier-Di Francesco-Guitter avec les mobiles afin de décomposer ces cartes. L'étude de cartes avec un petit nombre de trous nous permettra, de plus, de conjecturer puis vérifier une formule générale très simple pour la série génératrice dans le cas biparti avec nombre arbitraire de trous et le cas quasi-biparti avec deux trous de taille impaire (cela couvre donc les cas quasi-bipartis à 2 trous et 3 trous).
Il s'agit d'un travail effectué en collaboration avec Éric Fusy.

24 novembre 2010 Louis-Francois Préville-Ratelle (UQAM, Montreal) Structures combinatoires et statistiques associées aux espaces coinvariants du groupe symétrique Nous commencerons par donner les définitions de base des espaces coinvariants du groupe symétrique. Nous parlerons des objets combinatoires (conjectures) associés aux espaces coinvariants du groupe symétrique à un, deux et trois jeux de variables. Nous présenterons des statistiques sur ces objets. Plus particulièrement, nous discuterons d'une extension de la formule de Cayley aux triangulations. Cet exposé est accessible à tous.

1 decembre 2010 Marc Sage (ENS) Asymptotique des nombres de Hurwitz ayant un nombre quelconque de partitions Nous donnons l’asymptotique générale des nombres de Hurwitz à plusieurs partitions, s’appuyant sur un théorème de Maxim Kazarian (issu du cadre intégral de la formule ELSV) pour le cas d’une partition et s’inspirant d’une récurrence menée par Dimitri Zvonkine (pour montrer un résultat général sur les séries génératrices des nombres de Hurwitz). En substance, l’asymptotique pour plusieurs partitions est la même que celle à une partition obtenue en concaténant les partitions.

8 decembre 2010 Katya Vassilieva Enumeration de certaines factorisations d'un long cycle Nous étudions le nombre de permutations sigma de [N] avec m cycles telles que \((1 2 ... N)*sigma\) a un seul cycle. Ces nombres apparaissent en tant que coefficients des monômes linéaires des polynômes de Kerov et de Stanley. Récemment, (arXiv:0901.2008), à l’aide de méthodes algébriques, R. Stanley a trouvé une connexion inattendue avec les nombres de Stirling de taille N+1. Nous présentons ici la première preuve combinatoire de son résultat, en introduisant une nouvelle bijection entre des cartes partitionnées et des arbres épineux. De plus, nous obtenons un résultat plus fin, prenant en compte le type des permutations.

15 decembre 2010 Pierre Nicodeme Bounded discrete walks We consider i.i.d. integers increments \(X_i \in [-c,+d]\), the partial sums \(S_j=\sum_{1\leq i\leq j}X_i\), and the discrete walks \(((j,S_j))_{1\leq j\leq n}\). Late conditionning by a return of the walk to zero at time \(n\) provides discrete bridges that we note \((B_j)_{1\leq j\leq n}\). We provide the asymptotic law in the central domain of the height (\(\max_{1\leq j\leq n}B_j\)) of the bridges. As expected, this law converges to the Rayleigh law which is the law of the maximum of a standard Brownian bridge. In the case where \(c=1\) (only one negative jump), we provide a full expansion of the asymptotic limit; this applies in particular for the case where \(X_i\in \{-1,+d\}\), in which case the expansion is expressible as a function of \(n\), \(d\) and of the height of the bridge. This last result can be applied heuristically to statistical analysis of DNA-arrays.

15 decembre 2010 Jérémy Barbay Instance Optimality and Order Adaptivity for Convex Hulls and Related Problems Adaptive analysis is a well known technique in algorithm design, which refines the traditional worst case analysis over all instances of fixed input size by taking into account some other parameters, such as the size of the output in the case of output sensitive analysis. We present some adaptive techniques for the computation of the convex hull in two and three dimensions, and related problems
The main analysis technique is unordered instance optimality, based on the structural entropy of the instance, and yields results on the computational complexity of planar convex hull in two and three dimensions, through a generalization of output sensitivity and a more precise analysis of the complexity of Kirkpatrick and Seidel's algorithm, which yields algorithms which are instance optimal among all algorithms in the multilinear decision tree model with worst or random input order.
We will describe complementary analysis techniques based on the input order, which improve results on the computation of convex hulls in two and three dimensions, and yield new results on for the adaptive computation of Voronoi and Delaunay diagrams, through the entropy of a partition of the input in easier instances.