Record number :
Title of article :
The Catalan matroid
Author/Authors :
Ardila، نويسنده , , Federico، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2003
Pages :
From page :
To page :
Abstract :
We show how the set of Dyck paths of length 2n naturally gives rise to a matroid, which we call the “Catalan matroid” Cn. We describe this matroid in detail; among several other results, we show that Cn is self-dual, it is representable over Q but not over finite fields Fq with q⩽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.
Keywords :
Dyck path , Matroid , Tutte polynomial , Shifted complex
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
Link To Document :