首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Grid classes and partial well order
Authors:Robert Brignall
Institution:Department of Mathematics and Statistics, The Open University, Milton Keynes, UK
Abstract:We prove necessary and sufficient conditions on a family of (generalised) gridding matrices to determine when the corresponding permutation classes are partially well-ordered. One direction requires an application of Higman?s Theorem and relies on there being only finitely many simple permutations in the only non-monotone cell of each component of the matrix. The other direction is proved by a more general result that allows the construction of infinite antichains in any grid class of a matrix whose graph has a component containing two or more non-monotone-griddable cells. The construction uses a generalisation of pin sequences to grid classes, together with a number of symmetry operations on the rows and columns of a gridding.
Keywords:Permutation classes  Grid classes  Partial well-order  Infinite antichains
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号