1 |
Counting Convex Sets on Products of Totally Ordered SetsBarnette, Brandy Amanda 01 May 2015 (has links)
The main purpose of this thesis is to find the number of convex sets on a product of two totally ordered spaces. We will give formulas to find this number for specific cases and describe a process to obtain this number for all such spaces. In the first chapter we briefly discuss the motivation behind the work presented in this thesis. Also, the definitions and notation used throughout the paper are introduced here The second chapter starts with examining the product spaces of the form {1; 2; : : : ;n} × {1; 2}. That is, we begin by analyzing a two-row by n-column space for n > N. Three separate approaches are discussed, and verified, to find the total number of convex sets on the space. A general formula is presented to obtain this total for all n. In the third chapter we take the same {1; 2; : : : ;n} × {1; 2} spaces from Chapter 2 and consider all the scenarios for adding a second disjoint convex set to the space. Adding a second convex set gives a collection of two mutually disjoint sets. Again, a general formula is presented to obtain this total number of such collections for all n. The fourth chapter takes the idea from Chapter 2 and expands it to product spaces {1; 2; : : : ;n} × {1; 2; : : : ;m} consisting of more than two rows. Here the creation of convex sets having z rows from those having z − 1 rows is exploited to obtain a model that will give the total number of z-row convex sets on any n × m space, provided the set occupies z adjacent rows. Finally, the fifth chapter describes all possible scenarios for convex sets to be placed in the {1; 2; : : : ;n}×{1; 2; : : : ;m} space. This chapter then explains the process needed to acquire a count of all convex sets on any such space as well. Chapter 5 ends by walking through this process with a concrete example, breaking it down into each scenario. We conclude by briefly summarizing the results and specifying future work we would like to further investigate, in Chapter 6.
|
Page generated in 0.017 seconds