tailieunhanh - Báo cáo toán học: "On the symmetry of the distribution of k-crossings and k-nestings in graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the symmetry of the distribution of k-crossings and k-nestings in graphs. | On the symmetry of the distribution of k-crossings and k-nestings in graphs Anna de Mier Submitted Oct 11 2006 Accepted Nov 7 2006 Published Nov 23 2006 Mathematics Subject Classification 05A19 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. 1 Introduction Let G be a graph on n 1 2 . ng with multiple edges allowed but without loops or isolated vertices. We say that the edges i1 j1g . ik jkg are a k-crossing if i1 i2 ik j1 jk and that they are a k-nesting if i1 i2 ik jk j1. A graph with no k-crossing is called k--noncrossing and a graph with no k-nesting is called k-nonnesting. The largest k for which a graph G has a k-crossing respectively a k-nesting is denoted cros G resp. nest G . The left-right degree sequence of a graph on n is the sequence Zi ri 1 i n where Zj resp. Tj is the left resp. right degree of vertex i by the left resp. right degree of i we mean the number of edges that join i to a vertex j with j i resp. j i . Chen et al. 1 show that the pair cros G nest G is symmetrically distributed among the set of graphs whose degree sequence is a fixed element of 0 0 0 1 1 0 1 1 gn. Recently it has been shown see 3 that for each degree sequence D there are as many graphs with cros G k as with nest G k. The purpose of this note is to explore to which extent the result of Chen et al. can be generalized to other classes of graphs. On the positive side we show that when restricting left degrees to 0 1g there are as many Departament de Llenguatges i Sistemes Informatics .