GWU Mathematics Department Graduate Student Seminar
FALL 2008 - Seminar Presentations

Professor Valentina Harizanov, 5 December 2008.

Turing Degrees of Complexity

In 1936, Alan Turing introduced the notion of an ideal computer and gave a negative answer to Hilbert's "decision problem". Two years later in his dissertation Turing defined the notion of a Turing machine augmented with the so-called oracle which provides external information during the computation. This led Emil Post to develop in 1944 a powerful notion of Turing degree as a measure of relative algorithmic complexity of sets of natural numbers and problems they encode. There are uncountably many Turing degrees, they are partially ordered and form an upper semilattice. We will show how some familiar mathematical objects can have certain Turing degrees by encoding sets of natural numbers into them. Although the talk will be based on topics of current research interest, it will not require prior knowledge of computability theory.


Professor Robbie Robinson, 14 and 21 November 2008.

An Introduction to Mathematica Software (two part seminar)

In this pair of talks, we will present an overview of the Mathematica computing environment. Like its cousin Maple, Mathematica is one of several commercially available "Computer Algebra Systems" (CAS) (for an open source CAS, consider Sage from U. Washington). But like Maple, Mathematica is really much more than that. Mathematica is an integrated environment for doing mathematics using a computer. This is not to say that Mathematica can do all the mathematics you might want it to, and even for some problems that clearly require a computer, Mathematica may not be the ideal tool (in many such cases Matlab will be). However, Mathematica is versatile and easy to use. This makes it a quick way to perform complex calculations, to test conjectures and to visualize complex structures. For such purposes, using Mathematica is often far superior to working by hand, or to programming in C++ or Java, which have no built in mathematical knowledge.

I will start by demonstrating some basic ways Mathematica can be used for solving problems from algebra, linear algebra and calculus. Then I will show some examples of one of Mathematica's graphical capabilities-- one of its greatest strengths. Finally, I will discuss Mathematica's data structures and how to write simple Mathematica programs. It is through writing programs-- often very simple ones-- that one is able to leverage the capabilities of Mathematica to its greatest extend. And the good news is that the programming style of Mathematica is one that is very natural from the mathematician's point of view.


Professor Daniel Ullman, 31 October 2008.

The Mathematics of Elections

Presidential elections in the United States take place through the Electoral College. There have been several efforts to amend the Constitution to eliminate the Electoral College and to replace it with some sort of direct election for president. We will discuss a measure of voter power and compare (via a Monte Carlo simulation) the power of voters in various states, in an effort to discern whether our current system meets the mandate of "one person, one vote". We will then discuss possible alternatives to the Electoral College system.

A great topic for the week before an historic election!


Forest Fisher, 24 October 2008.

Hopf Algebras and Combinatorics

In abstract algebra, a "multiplication" usually refers to a binary operation, a way of combining (or "multiplying") two things to get one. If we dualize this notion, we get a "comultiplication," an operation that takes one thing and unravels it into pairs of things. This type of operation is very natural in the field of combinatorics where it is typical to talk about objects decomposing into pieces-- a graph decomposes into subgraphs, a partition splits into pairs of partitions, etc. The most ubiquitous example of such a structure is a Hopf Algebra, a vector space with both a "multiplication" and a "comultiplication" satisfying nice properties. This talk will provide an introduction to Hopf Algebras and we will discuss a number of examples appearing in combinatorics.


Hillary Einziger, 17 October 2008.

The Lattice of Non-crossing Partitions

There are many well-known properties of non-crossing partitions. This talk will describe several formulas and bijections dealing with non-crossing partitions. It will also include an introduction to some basic facts about the lattice of non-crossing partitions, and a connection to parking functions.


Mike Coleman, 10 October 2008.

Introduction to MATLAB Software & Programming

In recent decades, MATLAB has become an increasingly useful computing tool in both research and industry. Many problems whose solutions are hard (or impossible) to compute analytically can utilize the computing power of MATLAB to help arrive at a suitable numerical solution, if one exists. We'll look at some basic functions and applications of MATLAB and learn how to construct a small program using a standard interface.


Tyler White, 3 October 2008.

Representations and Arithmetic of Numbers in a Non-integer Base

It can often be beneficial to consider numbers in different bases. Given a number in base 10, it can be difficult to determine whether that number is in the Cantor set. However, if we consider the interval [0,1] in base 3, we can see the Cantor set as all the numbers in radix base 2 expansion which consist entirely of 0's and 2's. For example, 0.2220202_3 is in the Cantor set while 0.12012_3 is not. In this talk, we will consider another non-standard way to represent numbers, using non-integer bases. Such bases can be used to show that there exist dynamical systems which have entropy c for all real positive c. However, we will be mostly concerned with the theoretical aspect of these representations. In particular, which representations are computable by deterministic finite automata and algorithms in order to perform arithmetic for certain non-integer bases?


Ken Shoda, 26 September 2008.

Matroids: Introduction and Lattices of Cyclic Flats

An informal introduction to Matroid Theory will be followed by some interesting new results. The introduction will include motivations and definitions of matroids, geometric representations, cryptomorphisms, duality of matroids and lattices. The new results will include cyclic and isthmus operators and properties of the sublattice R(X) of lattices of cyclic flats.


Radmila Sazdanovic, 19 September 2008.

The Unknotting Number and Unknotting Gap

The informal introduction to knot theory (definitions, Redemeister moves, Dowker code and Conway notation) will be followed by one of the essential and difficult questions in knot theory-- determining the unknotting number of a given knot or link. We define the BJ-unlinking number and show it is an upper bound for the unknotting number. We'll also discuss an unlinking gap which measures the difference between the unlinking number of a knot and the unlinking number of its specific diagram.


Jennifer Chubb, 12 September 2008.

Model Theory and Computability

The notion of computability has its origins in the work of Alan Turing, who in 1936 made precise the notion of machine computation. In computable model theory we are interested in determining the properties of mathematical structures and their theories that are accessible to us in an effective way. A mathematical structure is computable if its domain, relations, and functions can all be described by algorithms. The computability of a structure by no means implies that everything we might want to know about it is algorithmically accessible. I will provide a brief introduction to both model theory and computability and describe some examples. Then, I will describe some of the types of questions of interest in this area, and present some results from recent research in computable model theory. This talk will be accessible to undergraduates.


This site is maintained by Mike Coleman and Tyler White of the GWU Mathematics Department. This page was last updated on Friday, 17 July 2009.

Disclaimer: The views and policies articulated in these pages are those of the authors. The contents of this page have not been reviewed or approved by George Washington University.