Structural properties of large random maps and lambda-terms may be gleaned by studying the limit distributions of various parameters of interest. In our work we focus on restricted classes of maps and their counterparts in the lambda-calculus, building on recent bijective connections between these two domains. In such cases, parameters in maps naturally correspond to parameters in lambda-terms and vice versa. By an interplay between lambda-terms and maps, we obtain various combinatorial specifications which allow us to access the distributions of pairs of related parameters such as: the number of bridges in rooted trivalent maps and of subterms in closed linear lambda-terms, the number of vertices of degree 1 in (1,3)-valent maps and of free variables in open linear lambda-terms etc. To analyse asymptotically these distributions, we introduce appropriate tools: a moment-pumping schema for differential equations and a composition schema inspired by Bender’s theorem.
Joint work with Olivier Bodini and Noam Zeilberger.
De Dimitry Gurevich
De James Propp
De Paul-André Melliès
De Alexandros Singh
De Sergey Yurkevich
De Cyril Banderier
De Stéphane Gaubert
De Vincel Hoang Ngoc Minh
De Lionel Pournin
De Vasudevan Srinivas
De Marc Levine
De Carlos Simpson
