Northfield Undergraduate Mathematics Symposium 2012
The Northfield Undergraduate Mathematics Symposium is an annual event sponsored jointly by Carleton and St. Olaf. In 2012 eight students spoke at the symposium on research they did around the country over the summer. The pictures at the right show the speakers in action, and below are the titles and abstracts of their talks, and in some cases links to their slides.
Explorations into the Lawn Mowing Problem: Specific Cases and General Trends
Hannah Burson (St. Olaf)
The general Lawn Mowing Problem has been determined to be an NP-complete problem through comparison with the Traveling Salesperson Problem. With applications to robotic routers and computer chips, the Lawn Mowing Problem has been studied in its own right with particular attention to special case algorithms. In this talk, we provide a theoretical approach to understanding the general Lawn Mowing Problem by comparing lawn mowings to unique three-dimensional paths. We then determine complete, and occasionally surprising, solutions to specific instances of the Lawn Mowing Problem.
T-segment Graphs and Variations
Christophe Dethier (Carleton)
A T-segment representation is a way of representing the key information contained in a graph using line segments intersecting in the plane. A T-segment graph is a graph which can be represented in this way. This presentation will focus on results involving T-segment graphs, as well as their variations and generalizations. It will also include a few of the most important open questions about these graphs, along with some possible methods of proof.
Labeled Oriented Intervals that are not Diagrammatically Reducible
Ashley Earls (St. Olaf)
A virtual knot, from a graph theoretic point of view, is an arbitrary (not necessarily planar) 4-regular graph. Each long virtual knot corresponds to a labeled oriented interval (LOI) whose edges encode 4-sided tiles which match the crossings of the knot. A spherical diagram is a tessellation of the surface of a sphere with these tiles and their mirror images. A spherical diagram is called reduced if no tile is adjacent to its mirror image. If a LOI has no reduced spherical diagram, it is called diagrammatically reducible (DR). In this project, we looked for similarities among LOIs which are non-DR.
Labeled Oriented Intervals Slides
Understanding Spaces of Phylogenetic Trees
Daoji Huang (Carleton)
A classical problem in computational biology is the construction of a phylogenetic tree from a sequence alignment of n species. The work by Billera, Holmes, and Vogtmann (2001) provides a construction of a space Tn of such metric trees, which is shown to have a CAT(0)-structure, enabling the computation of geodesics and centroids. Due to its conical structure, the essential combinatorial characteristics are encoded in its cross section Ln, which is a simplicial complex. We describe Ln in the language of associahedron and permutohedron, which are famous classical polytopes that encapsulate algebraic information.
An alternate phylogenetic tree space introduced by Kim (2000), known as the ``space of phylogenetic oranges'', is a more general tree space that captures forests rather than trees. Moulton and Steel (2004) proved that the space is a contractible CW-complex that admits a regular cell decomposition. We study the connection between these two important tree spaces by decomposing a quotient map into discrete folds and continuous collapses.
Betti Tables of Line Arrangements
Ben Perez (St. Olaf)
A line arrangement is simply a collection of intersecting lines in projective space. These are degenerate curves that exhibit somewhat more diverse behavior than their smooth counterparts. Despite their complex structure, however, they are easy to think about in that they can be modeled as graphs.
In algebraic geometry, curves are thought of as ideals (or systems of equations, if you like). A Betti table is a systematic way to keep track of the relations between the generators of a curves defining ideal. These are often difficult to compute by hand, and there are few theorems that allow one to go easily between ideals and Betti tables.
My talk will examine how certain properties of graphs can tell us something about the curves they represent. Furthermore, I will give equations that allow us to go directly from graphs of low genus to Betti tables, rather than getting caught up in some rather nasty homological algebra.
A Characterization of the Prime Graphs of Solvable Groups
Ben Strasser (Carleton)
For any finite group G, the prime graph of G is the graph whose vertices are the prime divisors of |G|, in which primes p and q are adjacent whenever G has an element of order pq. For example, the prime graph of a finite cyclic group is the complete graph on the set of prime divisors of its order. In this talk we characterize the prime graphs of solvable groups, and we discuss some consequences of our characterization.
Prime Graphs of Solvable Groups Slides
Linkless Embeddings of Permutation Graphs
Josh Wilson (St. Olaf)
Let G be a graph on n vertices, and let a be a permutation of the vertices of G. We define the a-permutation graph of G to be the graph formed by taking two copies of G and joining a vertex v of the first copy of G to the vertex a (v) of the second copy of G.
On a rather different note, a linkless embedding of a graph is an embedding of the graph in R3 that has no interesting links, where by interesting links we mean two circles that you can't separate from each other. In this talk we'll explore some of the intersection between permutation graphs and graphs with linkless embeddings.
Invariants of an incidence matrix related to Rota's Basis Conjecture
Adam Zweber (Carleton)
Suppose you are given n bases of an n-dimensional vector space. Additionally suppose that each basis is assigned a particular color: say the first basis is red, the second blue, etc. Then Rota's Basis Conjecture asserts that one can always repartition the multiset union of these bases into n ``rainbow bases''--that is, each new basis will contain exactly one vector of each color. This innocent-looking conjecture has been open for over twenty years. In this talk we discuss the eigenvalues and Smith normal form of a particular matrix of ones and zeros which may be useful in solving this problem.
