Kevin Fleming
Harvey Mudd College Mathematics 2008
| Thesis Proposal: | Proposal |
|---|---|
| Final Report: | Boundary Cycles in Random Triangulated Surfaces |
| Thesis Advisor: | Prof. Nicholas Pippenger |
| Second Reader: | Prof. Francis Su |
Boundary Cycles in Random Triangulated Surfaces
Abstract
Random triangulated surfaces are created by taking an even number, n, of triangles and arbitrarily "gluing" together pairs of edges until every edge has been paired. The resulting surface can be described in terms of its number of boundary cycles, a random variable denoted by h. Building upon the work of Nicholas Pippenger and Kristin Schleich, and using a recent result from Alex Gamburd, we establish an improved approximation for the expectation of h for certain values of n. We use a computer simulation to exactly determine the distribution of h for small values of n, and present a method for calculating these probabilities. We also conduct an investigation into the related problem of creating one connected component out of n triangles.
Files referenced in my thesisThe C++ program I wrote and used to calculate the exact distribution of h for small values of n. You can choose the plan ASCII version or the one with CRLF line terminators; if one doesn't display or compile properly on your computer, try the other one. The two files are otherwise identical. This program uses the Class Library for Numbers, found at http://www.ginac.de/CLN/. After installing CLN, you should be able to compile it with your favorite C++ compiler (remember to link to the CLN library!). For example, g++ -O3 -lcln h_distribution.cpp ought to do it (optimization seems to make a big difference; I recommend it). When running the program, supply it one even positive integer as an argument; this will be n, the number of triangles to use. Important: you must make a subdirectory called "dists" in the directory that you run the program from. This directory will hold the output of the program (in files named things like "dist20.txt", when n = 20, and so on), and will not be created by the program. If nothing seems to happen after running it, make sure the directory exists. Finally, note that if you give the program a large value of n, it might take a long time. The largest I tried was n = 50; this took about 30 minutes on my computer, and the running time roughly doubles each time you increase n by 2 (for the actual running time, see section 5.1 of my thesis). Feel free to modify or improve the code; I'd be interested to hear about it if you do.
boundary_cycle_distributions.txt
boundary_cycle_distributions_crlf.txt
If you don't want to calculate them yourself, here are the exact distributions of h for even values of n up to 50. This file (and the following ones) also comes in both plain ASCII and CRLF versions; if one doesn't display correctly, try the other one.
boundary_cycle_distributions_one_component.txt
boundary_cycle_distributions_one_component_crlf.txt
This file contains the number of ways to identify the edges in n triangles to obtain a surface with exactly one closed component with a given Euler characteristic (called "chi" in the file). It was produced by a slightly modified version of the program above.
The first 25 spherical numbers (see section 5.3 for an explanation of these).