Portland State University Discrete Mathematics Seminar

Fall 2014: Neuberger Hall 388, Mondays, 3pm-4pm (previous quarters)

October 13, 2014
(Special location: SMSU 294)

Ewan Kummel, Portland State University
Permutation structure and the "100 prisoners" problem

A basic fact from group theory is that every permutation has a unique decomposition into disjoint cycles. We will examine some basic combinatorial properties of these cycle decompositions. Then we will use cycle decompositions to find an optimal strategy to the particularly brutal "100 prisoners" problem with a surprisingly high survival rate.

October 20, 2014

Colin Weir, Simon Fraser University
Cryptography and efficient arithmetic

Digital encryption is a part of everyday life: ATMs, iClouds, and online passwords of all sorts. In this talk we will discuss the mathematical foundations of modern cryptography. This conversation will naturally lead us to look at how to preform efficient digital arithmetic. The talk will conclude with a brief overview of work in progress with D. Thompson on efficient arithmetic in finite fields.

October 27, 2014

John Caughman, Portland State University
If civilization collapses will YOU be able to calculate pi?

Perhaps you've heard of how Archimedes approximated pi, or maybe you've heard that the Indiana legislature once tried to mandate a value of pi. But, have you ever stopped and wondered how you might effectively calculate its digits for yourself by hand? Being a bit of a pi-enthusiast, I could not resist giving it a shot for myself, and I was delighted at the variety of entertaining and marvelous mathematics that quickly surfaced. Combining techniques from number theory, calculus, and geometry, we will embark on this journey together, as we before us the basic task of calculating the digits of pi.

November 10, 2014

Derek Garton, Portland State University
Pell's equation and continued fractions

In 1657, Fermat challenged European mathematicians to find solutions to Pell's equation. One year later, Fermat accepted the solutions of the Englishmen Brouckner and Wallis. I will describe the events of the intervening months and the solutions of Brouckner and Wallis (which use continued fractions).

November 17, 2014

David Sivakoff, Ohio State University
Deterministic percolation from random initial states

   slides
I will discuss two deterministic models on graphs, in which the goals are to "span" or "merge" all of the vertices in the graph. The first is bootstrap percolation, in which vertices can be either open or closed. Open vertices remain open forever, and closed vertices become open once a sufficient number of their neighbors are open. The primary goal is to describe the initial states that lead to all vertices of the graph becoming open, especially when the initial state is random. I will give an overview of this model, and possibly some of my own results. The second model is jigsaw percolation, which is a novel model for how people might combine their ideas in a social network. Despite its non-local description, this model behaves in some ways like bootstrap percolation, which I will demonstrate.

November 24, 2014

Andrew Bridy, University of Rochester
The Artin-Mazur Zeta function of a rational map in positive characteristic

The Artin-Mazur zeta function of a dynamical system is a generating function that captures information about its periodic points. In characteristic zero, the zeta function of a rational map from P1 to P1 is known to always be a rational function. In positive characteristic, the situation is much less clear. I show that, for a family of rational maps in positive characteristic that come from endomorphisms of algebraic groups, the zeta function can be understood. Somewhat surprisingly, in most cases it fails to be rational and in fact is transcendental. This talk will be accessible to students.