k-noncrossing and k-nonnesting graphs and fillings of ferrers diagrams
k-noncrossing and k-nonnesting graphs and fillings of ferrers diagrams
复制标题
DOI：
10.1007/s00493-007-2297-2
复制
发表时间：
2006-02
期刊：
影响因子：
1.1
通讯作者：
A. Mier
中科院分区：
文献类型：
--
作者：
A. Mier
给出了度序列给定的图与非负整数填充Ferrers图的对应关系。在这种情况下，图的k-交叉和k-嵌套成为填充中的单位矩阵和反单位矩阵的出现。我们用它来证明具有给定度序列的k-非交叉图和k-非嵌套图的个数相等。这推广了Chen，Deng，Du，Stanley和Yan关于匹配图和划分图的类似结果，并推广了Klazar tok> 2的结果.此外，这种对应关系加强了最近发现的联系Krattenthaler之间的填充图和陈等人的结果。
We give a correspondence between graphs with a given degree sequence and fillings of Ferrers diagrams by nonnegative integers with prescribed row and column sums. In this setting,k-crossings andk-nestings of the graph become occurrences of the identity and the antiidentity matrices in the filling. We use this to show the equality of the numbers ofk-noncrossing andk-nonnesting graphs with a given degree sequence. This generalizes the analogous result for matchings and partition graphs of Chen, Deng, Du, Stanley, and Yan, and extends results of Klazar tok> 2. Moreover, this correspondence reinforces the links recently discovered by Krattenthaler between fillings of diagrams and the results of Chen et al.