Spring 2008
Tuesdays, 4:35 - 5:35 PM, JWB 335
Math 6960-001
(credit hours available!)

GSAC Home | Past Graduate Colloquia

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 15POSTPONED
Speaker: Aaron Wood
Title: Generating Gray Codes
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.

January 22
Speaker: Aaron Wood
Title: Generating Gray Codes
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.

January 29
Speaker: Dylan Zwick
Title: NP or not NP
Abstract:
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.

February 5
Speaker: Julian Chan
Title: Using Algebraic Methods to Solve Counting Problems in Chess
Abstract:
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?

February 12
Speaker:
Title:
Abstract:

February 19
Speaker:
Title:
Abstract:

February 26
Speaker: Berton Earnshaw
Title: Counting RNA structures of arbitrary pseudoknot type
Abstract:
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.

March 4
Speaker: Rex Butler
Title: Twelve Ways to Count
Abstract:
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).

March 11
Speaker:
Title:
Abstract:

March 18
Speaker:NONE
Title: Spring Break
Abstract:
Spring Break

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

April 22
Speaker: Mike Purcell and Amber Smith
Title: End of Year Party
Abstract:

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