Symmetric Functions: Combinatorial Identities and Bijections

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

Algebraic combinatorics is the branch of mathematics that exploits the interplay between algebra and combinatorics so that the methods of proof in one area can be employed to prove theorems and conjectures in the other area. This particular project concentrates on proving combinatorial identities and bijections for symmetric functions through the exploitation of combinatorial objects such as tableaux and trees. The impetus for this work comes from problems in voting theory and it builds on my previous work. This proposal focuses on the development of a new sphere of symmetric function theory, motivated by problems in voting theory. At the very heart of this research are questions about ranking patterns. What challenging and compelling questions in symmetric function theory are inspired by ranking pattern questions? This is a distinctive approach. Instead of focusing on a technique or a type of symmetric function, this proposal targets a common origin point and asks, if we journey out from this point, what interesting symmetric function questions arise? From this central hub radiate out the various spokes of interest: Boolean product polynomials, pattern-avoiding permutation patterns, alternating trees. What are ranking patterns? These are ordered arrangements of discrete objects. Counting the number of such arrangements is not difficult: obviously, the set of all possible rankings is the set of all possible permutations; however, reality is more subtle than that and, in many applications, not all rankings occur. For example, how do you model users' rankings of candidates in an election? One popular model prioritizes certain rankings, but this leads to a new problem: how many rankings are possible in the model? Answering in general can be difficult for higher dimensional models, and mathematicians have derived answers by forging bijections to combinatorial objects. Through recent work, connections between this model and hyperplane arrangements have been made, and this has led to conjectures involving the Robinson-Schensted algorithm, alternating sign matrices, alternating trees, and pattern-avoiding permutations.  It is these conjectures I will target. Along the way I will prove results involving formal counting of combinatorial objects and the characterization of forbidden configurations. The majority of the research throughout my career has concentrated on combinatorial proofs of symmetric function identities, and to this I have added some recent results on the ramifications of truncation on ranked ballot elections. This social choice direction has cross pollinated my symmetric function research, and led to new ideas and new trajectories. While the goals of this proposal are theoretical, there is this bridge to the applied realm as well, including, the potential to show advantages and limitations in certain voting system models, and I expect the social choice community to be an important additional audience for my results.