21st Bay Area Discrete Math Day

Saturday, October 16, 2010

Titles and Abstracts

Goran Konjevod.   Some combinatorial and algorithmic results on origami
Lawrence Livermore Lab / Arizona State University

I'll review some recent combinatorial and algorithmic results on origami. One of these is a new construction for folding an n by n checkerboard from an uncut square or rectangular sheet. The two sides of the sheet have different colors and this is used to create a grid of squares alternating in color. The construction is asymptotically the best known and, in particular, beats a long-conjectured lower bound.
Results presented include joint work with Erik and Martin Demaine and Robert Lang.

Tristram Bogart.   Mapping polytopes of polygons
MSRI / San Francisco State University

Given full-dimensional polytopes P in R^p and Q in R^q, Ziegler defines the mapping polytope H(P,Q) to be the set of affine maps L from R^p to R^q such that L(P) is contained in Q. It is not difficult to give a complete facet description of H(P,Q), but little else is known. Unlike the facets, the number of vertices and other lower-dimensional faces depend on the geometry of P and Q, rather than only on their combinatorial types. In joint work with Mark Contois and Joseph Gubeladze, we investigate the case that P and Q are both polygons, which makes H(P,Q) a 6-polytope. If P and Q are generic, we show that all of the vertices of H(P,Q) that correspond to full-rank affine maps are simple. Combined with enumeration of the remaining vertices, this yields rough bounds on the f-vector.

Tim Roughgarden.   Potential Functions and the Inefficiency of Equilibria
Stanford University

We survey one area of algorithmic game theory: the use of approximation measures to quantify the inefficiency of game-theoretic equilibria. Potential functions, which enable the application of optimization theory to the study of equilibria, have been a versatile and powerful tool in this area. We also discuss recent results on the "intrinsic robustness" of such approximation bounds.

Alexander Engström.   Polytopes from Exponential Random Graph Models
University of California, Berkeley

Exponential random graph models are used by statisticians to understand local and global behaviour of large networks. This is applied to model for example how people interact in societies. Recently Feinberg, Rinaldo and Zhou introduced a class of polytopes to describe how statistical tools as maximum likelihood estimation behaves in this context.
The explicit description of some small low-dimensional examples of these polytopes correspond to classical graph enumeration problems initially studied by Bollobas, Erdos, Lovasz and coauthors. I will explain how these polytopes are constructed and report on work with Patrik Noren about their geometry.

Megan Owen.   Shortest Paths in Cubical Complexes
University of California, Berkeley

A cubical complex is a polyhedral complex in which all the cells are unit cubes. By giving each cube the Euclidean L^2 metric, we get a natural metric on the whole complex. These complexes arise in such areas as geometric group theory, reconfigurable systems, and phylogenetics. If a cubical complex is non-positively curved, then there is a unique shortest path between any two points in the complex. We present algorithms for finding this path. This is joint work with Federico Ardila and Seth Sullivant.

Matthias Beck.   10 Years BADGeometry: Progress and Open Problems in Ehrhart Theory
San Francisco State University

Given a lattice polytope $P$ (the convex hull of finitely many integer points in ${\bf R}^d$), a famous theorem of E. Ehrhart asserts that the counting function $\# (tP \cap {\bf Z}^d)$ is a polynomial in the (positive integer) variable $t$. Ehrhart polynomials appear in a wealth of areas in mathematics and beyond, in part because polytopes can be described by a system of linear equalities and inequalities. In honor of the 10-year anniversary of the BADMath Day, we will exhibit various advances in Ehrhart theory of the last decade, many of which involve BADMathematicians. Along the way we will mention several open problems centered around Ehrhart polynomials.