The Catalan matroid

[摘要] We show how the set of Dyck paths of length 2n naturally gives rise to a matroid, which we call the Catalan matroid C-n. We describe this matroid in detail; among several other results, we show that Q, is self-dual, it is representable over 0 but not over finite fields F, with q less than or equal to n - 2, and it has a remarkably nice Tutte polynomial. We then generalize our construction to obtain a family of matroids, which we call shifted matroids. They are precisely the matroids whose independence complex is a shifted simplicial complex. (C) 2003 Elsevier Inc. All rights reserved.

[发布日期] 2003-10-01

[关键词] Dyck path;matroid;tutte polynonual;shifted complex