arXiv Analytics

Sign in

arXiv:2009.00122 [math.CO]AbstractReferencesReviewsResources

Pattern Matching in Set Partitions is NP-Complete

Thomas Grubb

Published 2020-08-31Version 1

In this note we show that pattern matching in permutations is polynomial time reducible to pattern matching in set partitions. In particular, pattern matching in set partitions is NP-Complete.

Comments: 4 pages, comments welcome
Categories: math.CO
Subjects: 05A18, 03D15
Related articles: Most relevant | Search more
arXiv:2202.02089 [math.CO] (Published 2022-02-04)
Mahonian and Euler-Mahonian statistics for set partitions
arXiv:1806.02316 [math.CO] (Published 2018-06-06)
Set partitions without blocks of certain sizes
arXiv:1511.00192 [math.CO] (Published 2015-11-01)
Pattern avoidance for set partitions à la Klazar

Links

Toolbox