4 papers · 1 filter
Set Partition Patterns and the Dimension Index
Thomas Grubb, Frederick Rajasekaran
The notion of containment and avoidance provides a natural partial ordering on set partitions. Work of Sagan and of Goyt has led to enumerative results in avoidance classes of set…
Pattern Matching in Set Partitions is NP-Complete
Thomas Grubb
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…
Threshold Progressions in a Variety of Covering and Packing Contexts
Anant Godbole, Thomas Grubb, Kyutae Han +1
Using standard methods (due to Janson, Stein-Chen, and Talagrand) from probabilistic combinatorics, we explore the following general theme: As one progresses from each member of a…
Restricted growth function patterns and statistics
Lindsey R. Campbell, Samantha Dahlberg, Robert Dorward +4
A restricted growth function (RGF) of length n is a sequence w = w_1 w_2 ... w_n of positive integers such that w_1 = 1 and w_i is at most 1 + max{w_1,..., w_{i-1}} for i at least…