DIMACS REU 2011

Project Description

"Given a user query, search engines generally return a very sizeable collection of possible answers. Clustering has been proposed as a tool to partition the possible answer set into more manageable subsets of related results. There is no current agreement on the preferred mode of presentation of these clusters. Currently, most search engines display the set of results on almost a pure textual form. However, relatively recently we have witnessed some timid attempts to use some graphical representations. This study is a first step to elucidate when and why text appears to outperform graphics for certain fundamental clustering related tasks. To this end we designed three interfaces to display flat clusters of user queries. The interfaces are enhanced with mechanisms by which users provide feedback about the relevance of a cluster for a pre-specified input query. Subsequently, users are asked to provide a name for a given cluster that best describes the cluster contents." My task focuses more on the mathematical basis of constructing these new, efficient search engines. Utilizing maximal chains of permutations, I am attempting to identify the smallest matrix that does not create a proper polygon.

Weekly Project Log

Preliminaries: I met with Dr. Abello well before the commencement of the program to discuss my project. I proceeded to learn more about affine transformations, non-degenerate staircase configurations of polygons and geometric orientation of points under his guidance.

Week 1: I began my experience by attending Dr. Abello's graph theory lectures M-TH while learning more about maximal chains of permutations. Using these permutations, I attempted to create different matrices and the appropriate visibility graphs.

Week 2: In order to organize my ideas, I catalogued every possible matrix from n = 1...7. While doing so, I constructed various conjectures that may explain why certain patterns arise.

Week 3: I began converting the matrices and into proper polygons. During this process, I realized that each vertex of a polygon created a "line of visibility" with another vertex and consequently created regions in which another point can be placed. With this information, I began computing and proving the possible orderings of 0's and 1's in each row of G.

Week 4: Using what I had done so far, I wrote down a rough draft of the proof. Furthermore, I realized that persistent matrices M_n+1 can be decomposed into two matrices M_n and a single tile with value 0 or 1. This discovery helped me deduce the general pattern to these matrices.

Week 5: I attempted to combine all my findings in Week 4 into one concrete proof. While doing so, I continued to validate my findings using my catalogue of matrices.

Week 6: After speaking with Dr. Abello, I decided to approach my proof in a different manner. While doing so, I discovered that there might be more general cases than the one I had found earlier. I had also given my final talk on Thursday.

Week 7: I prepared write-ups for Cases 1 and 2 while modifying Case 1 to a much more general case. I then tested my theory for these two cases by first appending a Case 1 row to n = 6 and then appending a Case 2 row to the new matrix (n = 7). I repeated the process again but this time in the reverse permutation.

Week 8: I revised the proof(s) for Cases 1 and 2 from the previous week. While doing so, I discovered another special case for persistent matrices - one with an initial string of 1's in row n + 1 and an initial string of 0's in column 1.