Santa Clara University

Mathematics and Computer Science department

SCU Mathematics/CS Colloquium Series, Fall 2008

All talks are Tuesdays at 4:00 pm in O’Connor 107, unless otherwise announced.


October 7: Valerie Peterson, University of Illinois, Urbana-Champaign

Title: The Geometry and Topology of Reconfiguration

Abstract: Suppose you run a manufacturing operation that makes use of (somewhat primitive) robotic agents that are constrained to travel along a shared track in the floor. Before beginning production you must determine whether or not the robots can accomplish their assembly task without colliding: this problem supplies our primary motivation. In this talk I will explain what is meant by “reconfiguration” and present a variety of settings in which it occurs, both applied and abstract. I will also discuss the topological, geometric, and group theoretic properties of a class of cube complexes that arise naturally in this context. All necessary definitions will be given, but I will assume a modest exposure to abstract algebra as well as a fondness for visual aids and pretty pictures.

October 14:Pat McDonald, New College of Florida

Title: Random Walks and Network Tomography

Abstract: A network is a graph with added structure associated to its edges and/or vertices. Networks occur as models for a remarkable spectrum of phenomena, with well known applications in the natural sciences and engineering. In this talk I will discuss a collection of interesting inverse problems for networks, which involve random walks on the vertices of the underlying graph. Roughly speaking, these inverse problems treat the network as a “black box” upon which we are permitted to perform (from the outside of the box) a number of experiments designed to probe the internal structure of the box. We will be interested in determining under what conditions the outcome of the experiments determine the structure of the network, and, given that the structure is determined, how we use the experimental outcomes to reconstruct the network. There will be a number of suggestions for future projects, many of which are appropriate for students. The talk will be self-contained and intended for a general scientific audience.




October 21: Walter Stromquist, Swarthmore College, Editor-Elect ofMathematics Magazine

Title:Cutting cakes and cutting pies

Abstract: Cake cutting is a mathematical metaphor for more general fair division problems. As in life, we are concerned with both efficiency and equity—how to define them, how to achieve them, and sometimes, how to choose between them. The metaphor allows us to address these issues with the rigor of theorems and proofs. In this talk we'll review the current theory of cake cutting, using methods of combinatorics, topology, and complexity theory.

A cake is cut by parallel planes into n pieces, one for each of n players whose preferences are defined by separate measures. We can show that there is always an "envy-free" division—meaning that no player prefers another player's piece to his own—and that every envy-free division is also Pareto optimal. So, for cakes, equity and efficiency go together. There are some very nice algorithms that converge to envy-free divisions, but even with just three players there is no strictly finite procedure. Even guaranteeing that each of n players gets 1/n of the cake seems to require n log n steps.

A pie is cut radially into wedges. We show that in this context, envy-free divisions are not always Pareto optimal; and in fact, for some measures, no division exists that is both envy-free and Pareto optimal. So for pies we may have to choose between equity and efficiency. We'll end with an open problem about cutting cookies.

October 28: No colloquium.  Work on your Halloween costume!

November 4: No colloquium: Election Day.

November 6 (Thursday) :  David Draper, Department of Applied Mathematics and Statistics, Universityof California, Santa Cruz

O'Connor 205  (note novel location)

Title:Bayesian statistics: a paradigm for inference, prediction and decision-making for the 21st century

Broadly speaking, statistics is the study of uncertainty—how to measure it, and how to make choices in the face of itand probability is the part of mathematics devoted to the measurement of uncertainty. Since the inception of probabilistic reasoning in the 1650s and its early development over the next 100 years, two main ways to think about the meaning of probability have survived and prospered: the frequentist approach (based on imagining repetitions of a repeatable process and monitoring the relative frequency with which interesting things would happen in the repetitions) and the Bayesian paradigm, in which probability measures the numerical weight of evidence in favor of an uncertain true-false proposition.

The Bayesian story is more general (it includes the frequentist approach as a special case), and it held sway in problems of statistical inference (reasoning backwards from data to learn about the process that generated the data) from the 1750s through the 1920s, but Bayesian calculations are more difficult in problems of realistic complexity, so the frequentist approach to inference was dominant throughout much of the 20th century.

A breakthrough in the early 1990s, in algorithms and computer speed necessary to implement them, has ushered in a revolution in statistical modeling and analysis, and the Bayesian approach to (a) inference, (b) prediction of future observable quantities, and (c) decision-making (choosing an optimal action, even though you don't have all the information you'd need to make the choice perfectly) looks set to become the dominant paradigm of the 21st century. In this talk I'll look at some of the history, contrast the two approaches, and give details on Bayesian analyses in several case studies drawn from medicine and health policy.



November 11: Eric Bahuaut, Mathematical Sciences Research Institute
Title: Asymptotically hyperbolic geometry

Abstract: The euclidean plane is an example of a surface with constant zero curvature and the unit sphere in three space is an example of a surface with constant curvature +1.  Less well known is hyperbolic space, a surface with constant curvature -1.  These three spaces form the models for constant curvature geometry.  But as everyday experience shows, interesting surfaces such as coffee cups, (American!) footballs or sailboats need not have constant curvature.  Recently there has been a great deal of interest from mathematics and physics communities in surfaces that have arbitrary shape in a bounded region but whose geometry approaches that of hyperbolic space outside that region.

In my talk I'll explain how to compute curvature in general and explore some of the unexpected facts of hyperbolic geometry.  I'll then talk a little about asymptotically hyperbolic spaces.

November 18: Alex Fink, UC Berkeley

Title: Noncrossing and nonnesting partitions

Abstract:  Given a partition of an ordered set of dots on a line, we can draw it by connecting up the successive dots in each part with arcs.  There are two natural properties of partitions we might consider in this light: perhaps no two of the arcs cross each other, so we have a noncrossing partition; or perhaps no arc is nestled completely underneath another, so we have a nonnesting partition.  It turns out that both kinds of partition are counted by the Catalan numbers.

This is all well and good.  But the real interest comes when we bring in Coxeter groups and generalise: what I've just described is the type $A$ flavour of the situation, and we can do the same for any other classical reflection group, yielding several variations on the notion of partition. We also get a generalisation of the Catalan numbers, and we've reached an active branch of combinatorial research, the Coxeter-Catalan combinatorics, dedicated to explaining the numerological coincidences by which several objects associated to Coxeter groups, including our partitions, are counted by this generalised Catalan number.

I'll talk about various aspects of the Coxeter-Catalan combinatorics, centering around my own contribution to the field, joint with Benjamin Iriarte Giraldo of the Universidad de los Andes, which was to give bijections between generalised nonnesting and noncrossing partitions in every case.  The talk should be accessible to anyone acquainted with some rudiments of algebra.

December 2: Carlo Sequin, UC Berkeley

Title: Artistic Geometry

This lecture will explore connections between Mathematics and the Arts—in particular between low-dimensional geometry and topology and abstract geometrical sculpture. In the first half of my talk I will introduce the 3- and 4-dimensional  regular polytopes and methods of finding Hamiltonian cycles on their edge graphs [1], and also show how some of these structures can be turned into artistic models. In the second half I will present some of the work of sculptor Keizo Ushio, and then generalize the key idea underlying his signature motif “Oushi Zokei”—two interlinked rings cut from a single torus—into configurations of multiple interlocked rings, torus knots, and/or Moebius spaces [2]. Small models of many of these structures have been fabricated on a Rapid Prototyping machine and will be presented at this seminar.

Related Figures:

[1] Four congruent Hamiltonian cycles in different colors on the edges of the 4-dimensional 24-Cell, see:

http://www.cs.berkeley.edu/%7Esequin/SFF/ZCORP_parts/C24_02.JPG

[2] A torus cut with a “twisting knife” to create an internals space in the shape of a Moebius band, see:

http://www.cs.berkeley.edu/%7Esequin/SCULPTS/CHS_miniSculpts/SplitKnots/MoebSpace1a.JPG

Carlo H. Séquin has been a professor of Computer Science at the University of California, Berkeley since 1977. His research interests lie in the fields of Computer Graphics, Virtual Environments, and Computer Aided Design Tools.

He has built CAD tools for the layout of integrated circuits, for the conceptual phase in architectural design, for the design of mechanical systems, and—most recently—for artists who create abstract geometrical sculptures.

There will be refreshments before the talk in O'Connor 31 starting at 3:45pm. If you have a disability and require a reasonable accommodation, please call or email Frank Farris 408-554-4430 or ffarris@scu.edu .


Printer-friendly format