组合模型理论中若干组合结构的研究

Combinatorial model theory has many applications to enumerative combinatorics. In this proposal, several combinatorial objects in the theory, such as parking functions, sandpile models and the Tutte polynomial, will be involved. In particular, parking functions on undirected graphs and digraphs will be researched by using the deletion-contraction recurrsion. To reveal the relations between parking functions and the Tutte polynomial, some new parameters will be defined on parking functions. The relations between these new paremeters and connected components of subgraphs will be also explored by using partition methods and bijection methods. To give a combinatorial interpretation for TG(-1,1), spanning trees and cotrees will be studied and it will be attempted to derive the combinatorial interpretation from the view of cotrees. To study the geometry of sandpile model, the convex hull of recurrent configurations and allowed configurations will be discussed and it will be attempted to determine the vertex set and the ridges of the convex hull. Some combinarotial structures related to parking functions on undirected graphs will be studied.

组合模型理论是计数组合学的一个重要分支, 能够以某种统一的步骤处理和解决许多不同类型的问题. 本项目研究将主要围绕组合模型理论中若干组合结构(如泊车函数、Abelian沙堆模型等)展开, 利用图的减边-缩边运算, 研究无向图和有向图上泊车函数, 在泊车函数上定义出新的参数, 揭示泊车函数与Tutte多项式的联系; 利用子图剖分和一一对应相结合的方法, 研究无向图和有向图上泊车函数新定义的参数与图的子图连通分支间的关系; 研究TG(-1,1)的组合意义; 研究无向图上Abelian沙堆模型回归构型和可允许构型凸包的几何性质;研究与图上泊车函数对应的其他组合模型及组合序列的性质.

本项目围绕组合学中的Tutte多项式，及组合学中一些重要组合结构的序列展开研究，相关研究工作均取得一些进展。具体地，我们在非奇异M-矩阵A上提出(A,r)-泊车函数的概念, 并证明了(A,r)-泊车函数的集合与r的取法无关。我们提出Proper Tutte映射的概念, 给出Tutte多项式更为系统一般的组合解释. 对于任何一般的无向图, 我们都得到Tutte多项式T(G;1,-1)的组合解释; 我们也得到T(Kn;1,-1)的组合解释; 我们提出极小泊车函数的定义, 并研究各种极小泊车函数的参数量；在弱连通Eulerian有向图上, 固定顶点v，我们定义出与v有关的sink和source多项式, 证明了定义出的多项式在sink和source下是相等的，并与v的取法无关，从而定义出的多项式深刻反映的图的本质属性; 对任何一个n元置换\pi, 我们在置换上定义了一个新的参数:cdes(\pi). 我们发现了和这个参数有关的许多有意思的公式, 并给出这些公式的代数和组合证明; 更有意思的是, 这个参数也和Callan完美匹配能够产生某种相同的递回关系, 我们也给出相应关系的组合证明. 我们研究了与Eulerian多项式有关的几个多项式的陈氏文法描述, 作为主要结果的应用, 我们获得了这几个多项式的卷积公式； 我们首先给出某种S-逆序序列与带mark排列之间的一一对应, 进而给出带mark排列与k-斯特林排列之间一一对应, 并得到相应参数之间的关系；我们重点研究2-斯特林排列上ascent-plateau多项式是gamma-正的, 得到对应的系数的组合解释, 并构造相应的Foata群作用; 我们找到Legendre-Stirling集划分上的一个编码, 进而得到Legendre-Stirling数与二项式系数之间的一个关系；我们得到Eulerian多项式等的gamma正性; 得到Stirling排列等上多项式的partial gamma正性；得到n-元对称群等上的双gamma-正性；我们证明了任何具有gamma-正性的多项式都有一个David-Barton型等式，提出semi-gamma正性概念，gamma正性是semi-gamma正性的充分条件, 证明Alternating run多项式具有semi-gamma正性，但是不具有gamma正性.