Graduate Colloquium: Spring 2008

Spring 2008

Tuesdays, 4:35 - 5:35 PM, JWB 335

Math 6960-001

The goal of this Colloquium is to encourage interaction among graduate
students, specifically between graduate students who are actively researching
a problem and those who have not yet started their research. Speakers will
discuss their research or a related introductory topic on a level which
should be accessible to nonspecialists. The discussions will be geared
toward graduate students in the beginning of their program, but all are
invited to attend. This invitation explicitly includes undergraduate students.

**January 15**POSTPONED

**Speaker: **Aaron Wood

**Title:** Generating Gray Codes

**Abstract:**

**January 22**

**Speaker: ** Aaron Wood

**Title:** Generating Gray Codes

**Abstract:**

**January 29**

**Speaker: ** Dylan Zwick

**Title:** NP or not NP

**Abstract:**

**February 5**

**Speaker: ** Julian Chan

**Title:** Using Algebraic Methods to Solve Counting Problems in Chess

**Abstract:**

**February 12**

**Speaker: **

**Title:**

**Abstract:**

*
*

**February 19**

**Speaker:**

**Title:**

**Abstract:**

*
*

**February 26**

**Speaker:** Berton Earnshaw

**Title:** Counting RNA structures of arbitrary pseudoknot type

**Abstract:**

**March 4**

**Speaker: **Rex Butler

**Title:** Twelve Ways to Count

**Abstract:**

**March 11**

**Speaker: **

**Title:**

**Abstract:**

*
*

**March 18**

**Speaker:**NONE

**Title:** Spring Break

**Abstract:**

**March 25**

**Speaker: ** Will Malone

**Title:** Geometrize Now

**Abstract:**

*
In 1904, after developing the fundamental group, Henry Poincare conjectured that the
only simply connected
closed 3-manifold was in fact the three sphere. After this paper little progress was made until
Bill Thurston
announced a major result and a conjecture extending his result that if true would imply the
Poincare conjecture.
This conjecture of Thurston has become known as the Geometrization Conjecture which was recently
proved to be true by Grigori
Perelman. In this talk we will endeavor to explain the statement of the Geometrization
Conjecture through
examples.
*

**March 31 - Special Recruitment**

**Speaker: ** Matthew Reimherr - Statistics/Probability

**Speaker:** Casey Johnson - Representation Theory

**Speaker:** Yael Algom-Kfir - Geo. Group Theory/Topology

*
*

**April 1**

**Speaker: **

**Title:**

**Abstract:**

*
*

**April 8**

**Speaker: ** Davar Khoshnevisan

**Title:**

**Abstract:**

*
*

**April 15**

**Speaker: ** Sarah Kitchen

**Title:**Reimann-Hilbert Problem

**Abstract:**

**April 22**

**Speaker: ** Mike Purcell and Amber Smith

**Title:** End of Year Party

**Abstract:**

*
*

The term combinatorial Gray code is used to describe an ordering of
combinatorial objects so that successive objects differ in a pre-specified
way.
One example is an ordering of the strings of digits from the set {1,...,R},
called an R-ary Gray code. In 1947, Frank Gray developed an ordering of
binary
n-strings, called the binary reflected Gray code, that was used in encoding
analog signals into strings of binary digits. We will discuss methods of
generating many other binary Gray codes.

The term combinatorial Gray code is used to describe an ordering of
combinatorial objects so that successive objects differ in a pre-specified
way.
One example is an ordering of the strings of digits from the set {1,...,R},
called an R-ary Gray code. In 1947, Frank Gray developed an ordering of
binary
n-strings, called the binary reflected Gray code, that was used in encoding
analog signals into strings of binary digits. We will discuss methods of
generating many other binary Gray codes.

NP or not NP? That's a million dollar question. In this talk I'll introduce
the concept of algorithmic complexity and give some examples. We'll then
examine two classes of problems, P and NP, and discuss some ideas about them
such as NP completeness. We'll end with a statement of one of the seven
millennium problems, that by the end of the talk you should understand.

We'll discuss how one can solve the following problems:

(1) On an n by n chess board after placing k queens on the board how many squares are left unattacked?

(2) How many ways can we place k queens on an n by n board and have EXACTLY u unattcked squares?

(3) On an infinite chess board how many squares can a knight reach in d moves?

(4) How many squares can be reached in d moves and NO LESS by a knight?

In this talk I will review some recent results of Christian Reidys
(2008) on counting the number of secondary structures that an abstract
single-strand of RNA can obtain ("abstract" means we do not specify an
underlying base sequence for the RNA strand). These results rely on the
recent observation of Chen et al. (2007) that k-noncrossing partitions of
the set {1,...,n} are in one-to-one correspondence with all random walks of
length n which remain in the Weyl chamber of dimension k-1 [i.e., the set of
all points (x_1,...,x_{k-1}) in Z^{k-1} such that x_1 > ... > x_{k-1} > 0]
and that start and end at (k-1,k-2,...,1). The construction of this
bijection and, ultimately, the RNA structure counting formula rely on such
ideas as vascillating Young tableaux, the RSK algorithm, finite reflection
(or Weyl) groups, the reflection principle of Gessel and Zeilberger (1992),
and an amazing formula for the exponential generating function of the walks
mentioned above due to Grabiner and Magyar (1993). This talk should be
self-contained; however, I will only motivate the proofs of the main results
through examples, figures, etc., and will not provide details.

In this talk, using as many visuals as possible, I will present twelve
ways to count the ways to allocate a finite set A of balls into a finite
set B of boxes. To begin, one such way is simply to count the total
number of functions from A to B. This corresponds to the arbitrary
allocation of labeled balls into labeled boxes.
The other options arise as follows. First, we count all allocations,
allocations where each box gets at most one ball, or allocations where
each box gets at least one ball. Second, we optionally equate allocations
which differ only by a relabeling of the balls, or the the boxes, or both.
This makes the balls and/or boxes unlabeled and 'indistinguishable' with
respect to the enumeration.
The resulting table provides an easy summary of a nice portion of
elementary combinatorics, and includes the binomial, partition, and
Sterling numbers (of the second kind).

Spring Break

Analytic continuation of solutions to a system of m first order
differential equations in m complex-valued functions of one complex variable
induces a linear transformation on the space of solutions. If we analytically
continue along a closed path, then these linear transformations determine a
representation of a certain fundamental group, called the monodromy of the
system. In 1857, Riemann asked the converse problem: given a faithful
representation of a certain fundamental group, find all systems with that
monodromy. Hilbert generalized this problem in 1900 when he stated his 21st
problem, which asks the same question for systems of differential equations on
arbitrary Riemann surfaces. In this talk, we will state the problem more
precisely, examine the history and solution, and outline a generalization to
higher dimensions.

155 South 1400 East, Room 233, Salt Lake City, UT 84112-0090, T:+1 801 581 6851, F:+1 801 581 4148