A Set Partition Analog of the Erd os-Szekeres Theorem

Abstract

The monotonic subsequence problem has been studied in depth. Mathematicians and theoretical computer scientists have found and proved various results such as the Erd os-Szekeres Theorem and have studied algorithms to fi nd longest monotonic subsequences. The objective of my project is to establish the counterparts of the results mentioned above in the context of set partitions, namely the heaviest free subpartition problem. More speci cally, I introduce concepts such as "subpartition", "freeness" and other related terms to formulate the free subpartition problem. Then, I discuss various representations of the problem and evaluate the relationship between this problem and other widely studied algorithmic problems. Finally, I analyze the di fficulties we encountered and present a "greedy" algorithm that approximates the optimal solution.