Feb 8  Ryan O'Donnell  SWM Seeking M/F's To Explore Domination (in graphs) Me: 5'8", Br/Bl, into Domination. A dominating set in a graph $G$ is a subset of the vertices $S$ such that every vertex in $G$ is at distance 1 or less from $S$. The domination number of $G$ is the size of the minimum dominating set. Together we'll prove many cute and easy theorems bounding the domination number in various kinds of graphs. Simple combinatorics and the probabilistic method will be our only tools. I will also discuss the relevance to certain problems in theoretical computer science. You: Likes to listen. M/F okay, HWP unnecessary, NS/ND/ND. The ``bondage number'' of graphs also exists, but will not be discussed. 
Feb 15  Alex Perlin  No loops, please Abstract: Given a connected graph G, a spanning tree is a connected subgraph that has no loops and includes all vertices of G. We will show how erasing loops in a random walk on G leads to a random spanning tree. As an application we will give a probabilistic proof of Cayley's theorem on the number of labeled unrooted trees on n verices. 
Feb 22  Robert David  The BanachTarski Theorem I will show a proof of the BanachTarski theorem. This theorem infamously states that a ball in 3space can be cut into a finite number of pieces which can then be rearranged to form 2 balls, each the same size as the original one. Some of the pieces must be nonmeasurable. The proof uses group theory and requires the Axiom of Choice. 
Mar 1  Mike Rosenblum  A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies Ever get laughed at for not being able to approximate the volume of convex bodies in polynomial time? Did the bully steal your lunch money, and say you could have it back as soon as you could guess the volume of the convex body he was thinking of? There is no shame in this, for no deterministic algorithm can do it well at all. I'll present a randomized algorithm of Dyer, Frieze, and Kannan that with very high probability gives a good approximation. I'll show how random walks, the ellipsoid algorithm, and ideas from differential geometry are combined to prove the algorithm works as claimed. If there is time, I will show how the randomized algorithm wriggles out of the BaranyFuredi trap that all deterministic ones fall into. 
Mar 8  Bill Bradley  Butterflies, Shuffle Graphs, and Other Computer Networks with CutesyPie Names Back in the glory days of parallel computing, people enjoyed designing supercomputers based on hypercubes. Since these are a bit hard to build when restricted to our puny threedimensional universe, they compromised. They used a host of variants on the aforementioned Butterfly and Shuffle networks (all with an outdegree of 2 and with cutesypie names). I'll talk about the basic structure of these graphs (including the hypercube itself), with an eye towards proving some permutation routing and rearrangeability results. Words such as "permutation routing" and "rearrangeability" will be defined. I'll also mention some of the more vexing open questions in this field. 
Mar 15  Etienne Rassart  Selfavoiding walks and Polyominoes You've probably heard about random walks in terms of a drunken guy trying to find his way home and making a random choice of directions at each street intersection. Now imagine a slightly less drunk walker that remembers if he's been at an intersection before and avoids it if he has. What you get then is a selfavoiding walk (SAW). An interesting problem is: given a lattice and a fixed starting point, how many lengthn SAWs are there in that lattice? This problem is interesting because after half a century of work by statistical physicists and mathematicians alike, the problem still stands open, even when considered asymptotically. I will discuss this problem and the related problem of counting polyominoes. Polyominoes are collections of little squares that are popular in recreational mathematics (think Tetris), but have turned out in deeper problems recently as well. 
Mar 22  Sergi Elizalde  Enumeration of subwords in permutations Abstract: We say that a permutation P in S_n contains another permutation Q in S_m as a subword if there exist m consecutive elements in P whose order relationships are the same as those in Q. For example, 6725341 contains 4132 as a subword (because 7253 are in the same order as 4132), but 41352 does not (even though it contains it as a subsequence, that is, in nonconsecutive positions). You probably have never wondered how many permutations in S_n do not contain a given subword. Actually, most people haven't. The general problem is unsolved. I will show you how to find the bivariate exponential generating functions counting occurrences of subwords of length 3, and also of some particular subwords of arbitrary length. The main idea is to use tree representations of permutations, so that occurrences of some subwords correspond to certain configurations in trees that can be counted more easily. Your homework will be to choose one of the following problems and solve it:

Apr 5  Peter Clifford  Picture Hanging 101 Abstract: The miniscule subfield of applied mathematics dealing with picture hanging has always been disregarded and denigrated. Practitioners have had to work behind closed doors, lest they be caught red handed striving for unappreciated perfection. Recently, however, picture hanging has become more socially acceptable, and has even breached the stronghold of prime time TV with a brief appearance on a popular animated programme. With the current popularity of mathematics in the cinema and in theatre, it can hardly be long before a biographical epic drama is created, based on a hanger and his struggle for professional recognition. We will give a survey of the field, hopefully including its ties to other areas such as knot and braid theory, geometry and combinatorics. 
Apr 12  BaoChi Nguyen  Buckling Abstract: Often things that we see, use and do in our lives involve buckling. For example, we often crumple a piece of paper before we throw it away. As a kid we learned how to make a cone from a circular sheet of paper. When we look at the drape we wonder why does it fold in a certain way. There are many technological applications which have thinsolid film deposited over substrates. As for metalcutting tools, they always have wearresistant coatings that have large compressive stresses, which leads to bucklingdriven delamination. It would be nice to understand the mechanism behind these. Crumpled paper and delamination of compressed thin films have been studied by many researchers experimentally, numerically, and theoretically . In general, when buckling occurs there are folding patterns. In order for these patterns to appear a certain amount of energy is required. To get a unique pattern one needs to minimize the energy of the system. This lead to finding developable surfaces which have zero Gaussian curvature. Locally, there are three types of developable surface: cones, cylinders and ridges. I am going to give an overview of these problems from numerical, experimental, and theoretical point of views. 
Apr 19  Rados Radoicic  Crossing Bound, kset Problem and Monotone Paths in Line Arrangements Abstract: Given a set of n points in the plane in general position, a kset is a subset of k points that can be separated with a line from the remaining points. The kset problem, one of the most challenging open problems in combinatorial and computational geometry, is to bound the maximum number of ksets of an npoint set. I am going to prove several upper bounds for the n/2problem. Proofs will elegantly follow from the bound on the crossing number of a geometric graph. I am also going to define the klevel problem, which is the dual of the kset problem. Finally, I will introduce a related problem of bounding the maximum "length" of an xmonotone path in a line arrangement. I will present the best known lower bound for this problem, due to Geza Toth and myself. I will mention several "innocentlooking" open problems. 
Apr 26  Francois Blanchette  Why you can make yogurt on a computer but not on paper Surface growth is a relatively new and absolutely exciting subject. This theory tries to describe how the interface between two "states" evolves. These states can be liquidliquid, liquidsolid or solidsolid. Looking at this from the microscopic point of view, many of those objects look like fractals. I will discuss how to classify these interfaces, simulate them and analyze the simplest models mathematically. I will assume no background in this field, some interest for it, and a strong desire to get a free dinner. 
May 3  Pedro Felzenszwalb  Computer Vision What does it mean, to see? The plain man's answer (and Aristotle's too) would be, to know what is where by looking. In other words, vision is the process of discovering from images what is present in the world, and where it is. In computer vision we study how to extract from images the various aspects of the world that are useful to us. We study the computations that make it possible to recognize familiar objects, recover 3D information of a scene, detect moving objects, etc. To solve these problems we need to bring together many fields, including signal processing, geometry, combinatorial optimization and probabilistic reasoning. I will give an overview of different problems, the mathematics that pops up in different places, and algorithms which attempt to solve some of the problems. 
May 10  Carly Klivans  Oriented Matroids Abstract: I am often asked, "What are oriented matroids anyway?". I will attempt to answer this question. 
May 17  Alberto De Sole  The Universe Abstract: I will describe the universe. Of course nobody knows how it works. This means the talk will be a little confusing. More specifically, I'll talk about quarks and elementary particles, and, as a mathematical tool, I will say a few words about representation theory of some Lie groups, mainly SU(2) and SU(3). 