On the Symmetry of the Distribution of $k$-Crossings and $k$-Nestings in Graphs

Abstract

This note contains two results on the distribution of $k$-crossings and $k$-nestings in graphs. On the positive side, we exhibit a class of graphs for which there are as many $k$-noncrossing $2$-nonnesting graphs as $k$-nonnesting $2$-noncrossing graphs. This class consists of the graphs on $[n]$ where each vertex $x$ is joined to at most one vertex $y$ with $y < x$. On the negative side, we show that this is not the case if we consider arbitrary graphs. The counterexample is given in terms of fillings of Ferrers diagrams and solves a problem of Krattenthaler.