The SPAMS Schedule - Spring 2001

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.

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.

I will show a proof of the Banach-Tarski theorem. This theorem infamously states that a ball in 3-space 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.

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 Barany-Furedi trap that all deterministic ones fall into.

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 three-dimensional universe, they compromised. They used a host of variants on the aforementioned Butterfly and Shuffle networks (all with an out-degree of 2 and with cutesy-pie 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.

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 self-avoiding walk (SAW). An interesting problem is: given a lattice and a fixed starting point, how many length-n 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.

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 non-consecutive 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:

• How many permutations in S_n do not contain 1324 as a subword? (Hint: I don't know.)
• How many days remain for the Spring Break? (Hint: It can be counted without using tree representations.)

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.

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 thin-solid film deposited over substrates. As for metal-cutting tools, they always have wear-resistant coatings that have large compressive stresses, which leads to buckling-driven 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.

Abstract: Given a set of n points in the plane in general position, a k-set is a subset of k points that can be separated with a line from the remaining points. The k-set problem, one of the most challenging open problems in combinatorial and computational geometry, is to bound the maximum number of k-sets of an n-point set. I am going to prove several upper bounds for the n/2-problem. Proofs will elegantly follow from the bound on the crossing number of a geometric graph. I am also going to define the k-level problem, which is the dual of the k-set problem. Finally, I will introduce a related problem of bounding the maximum "length" of an x-monotone 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 "innocent-looking" open problems.

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 liquid-liquid, liquid-solid or solid-solid. 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.

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.

Abstract: I am often asked, "What are oriented matroids anyway?". I will attempt to answer this question.

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