Combinatorial Enumeration and Random Generation

点击翻译按钮获取中文摘要

The study of bijections between combinatorial objectshas always remained an attractive part of Enumerativeand Algebraic Combinatorics. Despite their wideapplicability, their remains a complete lack of formalunderstanding as to which bijections are equivalent,and which one are "good" in a sense that they preservethe natural structure of the combinatorial objects.We initiate the study of asymptotic properties ofpartition bijections and claim that a large class ofwell known bijections are in fact "asymptotically stable".Using CS-style reduction ideas we propose the firstformal way to formulate that all classical Young tableaubijections are in fact linear tie equivalent. Othercombinatorial objects and several new directionsare also discussed. Since the early days of mathematics, combinatorial objectshave played an important role. These objects, whichinclude various sets of graphs, trees, partitions ofintegers, tilings of regions with smaller shapes, etc.Finding or estimating the number of such objects is afundamental problem which has been resolved in someinstances and remains open in many other case. Sometimesone is able to relate the number of such objects to thenumber of other objects by means of a direct combinatorialargument (a bijection). We propose an in-depth study ofthe nature of these bijection, as to whether (and how)they reveal not just the number, but structural resultson these combinatorial objects.