Kevin Fleming

Harvey Mudd College Mathematics 2008

mugshot
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 thesis

h_distribution.cpp

h_distribution_crlf.cpp

The 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.

spherical_numbers.txt

spherical_numbers_crlf.txt

The first 25 spherical numbers (see section 5.3 for an explanation of these).