Portland State University Discrete Mathematics Seminar

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.

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.

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.

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

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.

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 P¹ to P¹ 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.