Graduate Student Advisory Committee (GSAC) Colloquium Schedule:

Welcome back.

This is an organizational meeting in which we'll discuss plans for upcoming events and colloquia.

Colloquium cancelled

There will be no talk this week.

Non-uniquely Ergodic Interval Exchange Transformations

Starting from rotations of the circle and flows on flat tori, I'll discuss the dynamics of interval exchange transformations and flows on flat surfaces. Rotations have the remarkable property that if a rotation has a dense orbit then every orbit is uniformly distributed. This fails for interval exchange transformations and I'll discuss some of behavior that these examples can exhibit.

Turing Machines and The Halting Problem

We will define Turing machines and explore their uses in theoretical computer science. As an application, we will describe the halting problem and sketch a proof of its undecidability. Time permitting, we may discuss P/NP.

The King Chicken Theorems

Consider a coop of chickens. In any pair of chickens, one pecks the other to assert dominance. However, there will not necessarily be a chicken who pecks every other chicken. Instead, we consider a "king chicken" to be one that, for every other chicken, either pecks that chicken or pecks a chicken that pecks that chicken. By representing each chicken as a vertex and each pecking relationship with a directed edge, we can use graph theory to determine the existence and prevalence of chicken kings. We will see every flock has a king, but this king is not necessarily unique, or even uncommon.

Colloquium cancelled

There will be no talk this week.

Pessimism Prevails: Some Integrals are Impossible

​​Since learning integration, deciding whether a "nice" form of an integral exists has likely stumped all of us at least once. While the pure math students may be content just knowing integrals exist, those in the applied camp struggle with this plight regularly. In this talk, we'll hopefully give both groups some solace and attempt to establish and prove criteria for when an elementary form of an integral is "impossible", originally proposed by Liouville while studying elliptic integrals. Along the way, we'll use some complex analysis and basic Galois theory. The classic Gaussian integral e^{-x^2} will serve as an illustrative example.

Fall break!

There will be no colloquium this week.

Does Your Vote Matter?: Weighted Voting, Game Theory, and the Shapley–Shubik Power Index

Voting comes in many forms, from presidential elections (where each citizen gets one vote), to dictatorships (where only the vote of the dictator counts), to a company's board of directors (where votes are weighted based on share ownership). In 1953, Lloyd Shapley developed a process for quantifying the worth of a person's vote. I will discuss this process (and the closely related Shapley–Shubik Power Index) and describe its applications to the Electoral College, Israeli Parliament, workers' unions, and bribery in the New York legislature.

Note: For a biomedical application, see: http://www.biomedcentral.com/1471-2105/9/361.

Monte Carlo Tree Search

Until fairly recently top Chess programs could beat top humans, but top Go programs were routinely destroyed by moderately skilled amateurs. Everyone figured this would be the case for the foreseeable future -- Go's branching factor is simply too high to solve with brute force, so it was regarded as a very difficult problem in pattern theory. In 2006 this all changed and top Go programs became nearly competitive with top human players. How the heck did they do it?!? The answer, as always, is with Monte Carlo techniques, but the algorithms are rooted in advances in solving the many-armed bandit problem, and have found uses outside board games.

Factorization Properties of Matrix Semigroups

While factorization properties of commutative semigroups have been well-studied, very little literature exists concerning factorization in the non-commutative setting. In this talk we will discuss the factorization properties of the semigroup of nxn integer-valued matrices under matrix multiplication (which is not commutative). We will determine which matrices are "irreducible" and how the uniqueness of factorization of the integers corresponds to the niceness of factorization of integer-valued matrices. Finally, we will generalize our results to study certain matrix semigroups with entries coming from some atomic domain.

A Survey of the Theory and Applications of Lie Algebra Representations

The theory of representations of Lie groups is heavily dependent on the study of representations of algebras. We will discuss how the theory of highest weights has been used to study finite dimensional Lie algebra representations, and how the universal enveloping algebra has been utilized in the study of infinite dimensional representations. Finally, we will discuss the Casimir operator as an invariant on irreducible representations and its application to particle physics.

Positively Polynomial

Suppose I have some polynomial with non-negative integer coefficients. You are tasked with guessing the polynomial; I will tell you the value of the polynomial at any integer you choose. How many integers is required for you to be certain of the polynomial? What if the polynomial has multiple variables? The solution to this problem is surprisingly simple and satisfying; we will discuss a few other interesting variations of this problem as well.

Geometric Methods for Graph Partitioning

Several geometric methods for graph partitioning have been introduced in the past few years, with wide applications in clustering, community detection, and image analysis. These methods, which I'll review, are built on graph-based analogues of total variation, motion by mean curvature, the Ginzburg-Landau functional, and Merriman-Bence-Osher threshold dynamics. In this talk, I'll also discuss a new graph partitioning method where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components.

Online Social Networks and Random Graph Generation

Graphs are a simple but effective model of Online Social Networks (OSNs) such as Facebook: vertices represent users and edges represent friendships. Such graphs exhibit special properties such as the presence of highly-connected subgraphs corresponding to, say, networks specific to single universities. In this talk, I'll describe these properties, the difficulties in building these graphs from real-world data, and recent progress towards generating random graphs with similar properties in order to test relevant algorithms.

Modeling the Flagellar Regulatory Network in Salmonella

We will discuss my current research project, which is analyzing the regulatory mechanisms in Salmonella that allow construction of flagella to occur in a trascriptional hierarchy. Experimentally, bacteria from the same population with identical genetics are divided into two distinct subpopulations, with some making flagella and others not. I will discuss the believed mechanisms for the bistability, and my current mathematical model.