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. [References: 18]