Symmetric Functions: Combinatorial Identities and Bijections

代数组合学是数学的一个分支，它利用代数和组合学之间的相互作用，使得一个领域的证明方法可以用来证明另一个领域的定理和猜想。这个特殊的项目集中于通过开发组合对象如表和树来证明对称函数的组合恒等式和双射。这项工作的动力来自于投票理论中的问题，它建立在我之前的工作基础上。这项建议的重点是发展对称函数理论的新领域，其动机是投票理论中的问题。这项研究的核心是关于排名模式的问题。在对称函数理论中，排名模式问题启发了哪些具有挑战性和说服力的问题？这是一种独特的方法。这项建议没有关注一种技术或一种对称函数，而是针对一个共同的原点，并问道，如果我们从这一点出发，会产生哪些有趣的对称函数问题？从这个中心中心辐射出各种感兴趣的轮辐：布尔积多项式、避免模式的排列模式、交替的树。排名模式是什么？这些是离散对象的有序排列。计算这种排列的数量并不困难：显然，所有可能的排名的集合就是所有可能的排列的集合；然而，现实要比这更微妙，在许多应用中，并不是所有的排名都会发生。例如，您如何模拟用户在选举中对候选人的排名？一种流行的模型对某些排名进行了优先排序，但这导致了一个新的问题：该模型中可能有多少个排名？一般来说，对于高维模型来说，答案可能很难回答，数学家们已经通过伪造组合对象的双射来推导出答案。通过最近的工作，已经在这个模型和超平面排列之间建立了联系，这导致了涉及Robinson-Schensted算法、交替符号矩阵、交替树和模式避免排列的猜想。我将针对这些猜想。在此过程中，我将证明涉及组合对象的形式计数和禁止配置的表征的结果。在我的职业生涯中，大部分研究都集中在对称函数恒等式的组合证明上，在此基础上，我还添加了一些关于截断在分级选票选举中的分支的最新结果。这种社会选择方向给我的对称函数研究带来了异花授粉，并导致了新的想法和新的轨迹。虽然这项提议的目标是理论上的，但也有这座通往应用领域的桥梁，包括在某些投票系统模式中展示优势和局限性的潜力，我预计社会选择社区将成为我的结果的重要额外受众。

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.