Thumbnail Image
Publication

A Set Partition Analog of the Erd os-Szekeres Theorem

Liu, Rui
Citations
Altmetric:
Contributor
Photographer
Author
Liu, Rui
Artist
Editor
Advisor
Keywords
Text, Honors papers, Student research, Mathematics and Computer Science, Department of
Local ID
Collections
Honors Papers
Show all metadata
Files
Thumbnail Image
Liu_Rui_Honors_2013.pdf
Adobe PDF, 341.67 KB
URI
http://hdl.handle.net/10267/16556
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.
Description
Permission to publish this work was granted by the author. The paper was submitted to the Archives on CD.