Patrick Chen


Student: Patrick Chen
Office: CORE 450
School: Rutgers University, New Brunswick
E-mail: patrick dot p dot chen at rutgers dot edu
Project: Visualization of Time-Varying Graphs

Week 1

Began researching visibility graphs and southeast paths (for more information, see presentation slides below).
Worked on presentation. slides

Week 2

Read about the relationship between maximal chains in weak Bruhat order of Sn and balanced tableaux, the application of the skeleton function on a tabula to generate a 0-1 matrix.
Problem Statement: Given a balanced tableaux T, can we always find a southeast polygon whose visibility is skeleton(T)?

Week 3

Realized that southeast polygons can be segmented into contiguous concave and convex parts.
Began looking at 2-patterns (polygons with two segments, viz., concave-concave, concave-convex, convex-concave, convex-convex). Advised that these may be the "fundamental building blocks" for analyzing more complex southeast polygons. Identified some basic attributes of concave-convex and convex-concave 2-patterns.
Wrote (python) code in Jupyter to generate and visualize random southeast polygons given a specificed sequence of concave/convex segments and each segment's length.*
Verified some basic relationships between southeast polygons, visibility, the ordering of slopes between two points, and the outcome of a balanced tabula.

* Unfortunately, the "random" generation algorithm produced trivial results far too often for much use. Advised to focus on other tools, such as those that can analyze the slopes and visibilities within southeast polygons.

Week 4

Attempted to formalize the attributes of all 2-patterns by proving said attributes from the ground up.
Helped me crystallize a lot of the intuition I was taking for granted.
Spent most of my time working on the relationships between slopes, visibility, and concave/convex segments.

Week 5

Formalized proofs for concave-convex and convex-concave 2-patterns.
Began formalizing ideas for convex-convex and concave-concave 2-patterns.
Advised to generate more visualizations and examples; as such, went back to the random-polygon code and tried to tweak it to more frequently produce nontrivial cases. Better, but not completely satisfactory.
Wrote code to produce colored diagrams for visualizing 2-patterns.

Week 6

Found an oversight within my explanation of concave-concave patterns.
Many interesting consequences; perhaps this pattern should not be treated as a "fundamental" one?
Generated large polygons to re-examine this pattern.

Special Thanks

James Abello - Advisor
NSF - funding
Érik Amorim - REU Coordinator
Martin Böhm - REU Coordinator
Lazaros Gallos - REU Director

Last updated: July 10, 2016