\(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams (Q950332): Difference between revisions

Let \(G\) be a graph on [\(n\)]; multiple edges and isolated vertices are allowed. A set of \(k\) edges \(i_{1}j_{1},\dots ,i_{k}j_{k}\) such that \(i_{1}<i_{2}<\dots <i_{k}<j_{1}<\dots <j_{k}\) and \(i_{1}<i_{2}<\dots <i_{k}<j_{k}<\dots <j_{1}\) is called a \(k\)-crossing and a \(k\)-nesting, respectively. In this paper a correspondence between graphs with a given degree sequence and fillings of Ferrers diagrams by nonnegative integers with prescribed row and column sums is given. This correspondence allows to show that the study of fillings of Ferrers diagrams with forbidden matrices is equivalent to the study of graphs avoiding certain subgraphs, in a given sense. In this setting, \(k\)-crossings and \(k\)-nestings of the graph become occurrences of the identity and the antiidentity matrices in the filling. This is used to prove the main result, which states that the numbers of \(k\)-noncrossing and \(k\)-nonnesting graphs with a given degree sequence are the same. Note that \textit{W. Y. C. Chen, E. Y. P. Deng, R. R. X. Du, R.P. Stanley}, and \textit{C. H. Yan} [Trans. Am. Math. Soc. 359, No. 4, 1555-1575 (2007; Zbl 1108.05012)] proved the equality of these numbers for two subclasses of graphs, namely for perfect matchings and for partition graphs, also counted by degree sequence (under a different but equivalent terminology). This extends results of \textit{M. Klazar} to \(k>2\) [Electron. J. Combin. 7, Res. paper R34 (2000; Zbl 0944.05002)]. Also, the proposed correspondence reinforces the links recently discovered by Krattenthaler between fillings of diagrams and the results of Chen et al.