# Mathematics Colloquium

### Abstracts Archives 2013-14

##### Previous Abstracts

#### 2012-2013 2011-2012 2010-2011 2008-2009 2007-2008 2006-2007

# Spring 2014

## March

**3/13 Paul Cull, Computer Science, Oregon State University**

*Solving Towers of Hanoi and Related Puzzles*

We start by solving the well-known Towers of Hanoi puzzle. Then we solve a lesser known puzzle, Spin-Out. We notice that these puzzles can be described as graphs and define a family of graphs, the {\it iterated complete} graphs which generalize these puzzle graphs. Generalized Towers of Hanoi puzzles correspond to these graphs with odd dimension, and generalized Spin-Out puzzles correspond to these graphs with dimension a power of 2. By “crossing” these puzzles, we obtain combination puzzles for every natural number bigger than 1. We show that these combination puzzles can be solved in essentially the same way as Towers of Hanoi and Spin-Out. We also show how to compute the number of moves between any two configurations of these puzzles. Our iterated complete graphs have a number of remarkable properties. For example, they have Hamiltonian paths and perfect one-error-correcting codes – properties that are NP-complete for general graphs. We also discuss computational complexity and show that many calculations on our graphs. We also discuss computational complexity and show that many calculations on our graphs and puzzles can be carried out by finite state machines.

**3/7 Matt Anderson**

*A Prime Producing Polynomial*

To me, prime numbers are interesting. Although there are not as many practical applications like in statistics, physics, and engineering; there is a certain mystery and challenge in their study. My study of prime numbers has revealed many unsolved problems. For example, although it is known that many linear functions with integer coefficients and integer input variables will produce a sequence with an infinite number of prime numbers in it (Dirichlet’s Theorem), it is not known if this is the case for polynomials of degree 2 or more. This is the Bouniakowsky Conjecture. This talk will focus on a quadratic polynomial, namely x^2 + x + 41. It is my finding that many restrictions on x will yield an infinite sequence of composite numbers.

## February

**2/27 Glencora Borradaile, Oregon State University, School of Electrical Engineering & Computer Science**

*Min Cuts, Shortest Cycles and Planar Graphs, oh my!*

A min st-cut is a minimum (weight) set of edges whose removal disconnects the graph, such that the vertex s is in one component and vertex t is in another. Now suppose you want to find many min cuts in the same graph. Can you do this more efficiently than simply computing a min cut for every pair of nodes that you are interested in? It turns out that you can, and we'll see a very elegant solution to this problem, dating to the 60s. We'll also see how, if your input graph is a planar graph, you can find a particular set of min cuts very, very quickly.

**2/20 K. Tucker (a.k.a. k-TUCK)**

*Enumeration and Projection Dependence of 1-Singular Knots*

I will describe the methods of enumerating knots with a lone singularity developed during the James Madison University Knot Theory REU, methods we used to distinguish these one-singular knots, and surprising difficulties encountered along the way. These surprises include the projection dependence on the classic knots from which one-singular knots are obtained, even when the projections are both minimal in terms of crossing number. We also show that the two standard projections of (p,q)-torus knots yield different one-singular sets if p < 3q/2.

**2/20 R. Robinson (a.k.a. Ray-Robins)**

*Convergence of Sequences of Polygons *

In 1932, Martin Rosenman proposed the following problem in the American Mathematical Monthly:

Let Pi be a closed polygon in the plane with vertices z_0, z_1,...,z_{k-1}. Denote by z_0^(1), z_1^(1),...,z_{k-1}^(1) the midpoints of the sides. Using z_0^(1), z_1^(1),...,z_{k-1}^(1) as vertices, we derive a new polygon, denoted by Pi^(1). Apply the same procedure to derive the polygon Pi^(2). After n constructions, we obtain polygon Pi^(n). Show that Pi^(n) converges, as n approaches infinity to the centroid of the original points.

I will present various approaches to the solution of this and related problems.

# Fall 2013

## December

**12/5 Jordan Purdy, Mathematics Dept**

*Spatial Statistics - Logistic Regression,* *the Autologistic Model and Mountain Pine Beetle*

When information on a binary response variable is collected for many observational units, the logistic model is commonly implemented to describe the probability of “success” as a function of one or more explanatory variables. As long as the response variables are independent, such a paradigm is appropriate. However, when binary responses on a regular lattice are observed in space and/or time, spatio-temporal dependencies typically exist and the logistic model is rendered invalid. Thespatio-temporal autologistic model is an intuitive extension of the logistic model that accommodates such a lack of independence. In this talk we will review the logistic model and introduce the spatio-temporal autologistic model along with the inherent challenges associated with its implementation.

Data on the spread of Mountain Pine Beetle in Montana will be used to motivate the generalization of the logistic model into the space-time domain.

**12/4 Samantha Reynolds, Willamette University '14
**

*College Entrance Exam Firms, Nonprofit Efficiency, and Testing Fees*

College entrance exam companies such as the College Board or the ACT claim nonprofit status. Theoretically these companies should not have high costs and considering that they aren’t profit driven, we would expect to see low testing fees. In reality this is not the case and many would claim that it stems from the inefficiency of the nonprofit. I analyzed whether high test fees could be the result of a company’s primary mission rather than inefficiency. Using the team incentive problem and the role of a budget breaker, I showed that nonprofits can induce workers to provide an effort level that minimizes costs in order to maximize net revenue. Assuming the firm has idealistic workers, the model can be extended where we still maximize net revenue without a principal playing the role of a budget breaker. The primary mission of nonprofits takes the form of a publicly valued good or service and that by maximizing revenue they can maximize the amount allocated to producing the public good. This implies that test takers may pay high fees not because the firm necessarily is inefficient but because the firm is trying to maximize how much of the public good is produced.

## November

**11/14 Professor Inga Johnson, Math Department**

*Topology, Homology, and Applications to Data
* Topology is the subfield of mathematics that is concerned with the study of shape. Mathematicians have studied topological questions for the past 250 years. In the past few years a new interdisciplinary field has blossomed bringing together topologists, statisticians, computer scientists, engineers and others, to use topological ideas to study data sets in new and exciting ways. We will discuss one of the new topological tools that has been developed called persistence homology.

This talk will be an introduction to topology and the concept of homology. We will then use homology to a look at examples of how topological ideas can be used to give new and surprising insight towards understanding data. This talk will emphasize examples and concepts. Prerequisites will be minimal.

## October

**10/31 Jeff Schreiner-McGraw and Will Agnew-Svoboda**

*Unipancyclic Matroids*

A unipancyclic (UPC) graph is a graph containing exactly one cycle of every possible size. Only a handful of these are known to exist, although searches have been performed through all graphs with 56 or fewer vertices. We generalized this problem by seeking to find and characterize UPC matroids. There are UPC matroids that are not graphic, so this does result in a larger family. In this talk, we will discuss the progress from the summer's research program.

**10/24 Nancy Ann Neudauer, Pacific University **

*What is a Matroid? Investigations of asymptotic enumeration in matroids*

In 1933, three Harvard junior-fellows tied together recurring themes in mathematics into what Gian Carlo Rota called one of the most important ideas of our day. They were finding independence everywhere they looked. Do you? We find that matroids are everywhere: Vector spaces are matroids; We can define matroids on a graph. Matroids are useful in situations that are modeled by both graphs and matrices. We consider how we can ask research questions about matroids, and look into results from a student's investigation.

Two matroids are commonly defined on a graph: the familiar cycle matroid and the more rarely-encountered bicircular matroid. The bases of the cycle matroid are the spanning trees of the associated graph; the bases of the bicircular matroid are all subgraphs of the graph, each of whose connected components contain exactly one cycle and (possibly) other edges. We enumerate the bases of the bicircular matroid for several classes of graphs. For a given graph, usually there are more bases of the bicircular matroid than of the cycle matroid. We ask when these numbers are the same. We also consider when there are more bases of the cycle matroid, and what this translates to in terms of the structure of the graph. No prior knowledge of matroids or graphs is needed!

**10/3 Yumi Li, Math Major**

*Put Your Thinking CAPS On (Exploring Finite Geometry in the Card Game SET®) *

Besides being a great card game, SET® serves as an excellent model for the ﬁnite geometry AG(n,3). Using the SET® cards as a visual representation, we will explore the structure of maximal caps and how we can manipulate them to discover new properties and substructures of AG(n,3). This work was done at the Research Experience for Undergraduates program at Lafayette College.

## September

**9/19 Ryan Wright, Janrain Inc.**

*Computing the Coming Robot Apocalypse: The math behind Artificial Intelligence and Machine Learning
* Let’s face it, it’s only a matter of time before machines rise up and take over the world. From image recognition, to Netflix recommendations, to predicting the future, Machine Learning and Artificial Intelligence are at the heart of some of the coolest technology being developed today. We give a quick introduction to how these technologies work and explain why math is how we welcome our future robot overlords.