## 21st Bay Area Discrete Math Day## Saturday, October 16, 2010## Titles and Abstracts |

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

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

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

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

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

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