Bay Area Discrete Math Day, Spring 2007

San Francisco State University

Saturday, April 14, 2007





Jump to: pommersheim | ford | liu | meyers | hartke | scott


10:00 - 11:00 am.
Jamie Pommersheim, Reed College.
Combinatorial Games and Factorization in Generalized Power Series Rings.

In the 1970s, John Horton Conway introduced the surreal numbers, a number system that can be used to quantify the play of many combinatorial games. The surreal numbers form a field containing all real numbers as well as all ordinal numbers. Among the elements of this field, one finds $\omega$ (the first infinite ordinal), $\omega - 1$ , $\sqrt{\omega}$, $\frac{1}{\omega}$ (an infinitesimal) and numbers like $\frac{\omega^{\omega}}{\sqrt{\omega^2 - \pi}} + \omega^{\frac{1}{\omega}}$. Within the surreal numbers, there is also a natural generalization of the integers, called the omnific integers, denoted $\mathbb{O}\mathbb{Z}$. The first three numbers listed above are omnific integers, while the last two are not. With this new notion of integer, one can revisit many of the classical questions of number theory. Most immediately, what are the prime numbers? Can every omnific integer be factored uniquely into omnnific prime numbers? A structure theorem tells us that every surreal number can be represented as a certain generalized power series, so these questions are closely related to algebraic properties of generalized power series rings. In this talk, after introducing the surreal numbers, we'll explore some questions about primes in these rings.


11:20 - 11:50 am.
Daniel Ford, Google Inc.
Random Phylogenetic Trees.

In this talk we will look at random phylogenetic trees: rooted binary leaf-labeled trees. Phylogenetic trees are often used to represent ancestral relationships between organisms. Reconstruction algorithms often use MCMC method and so probabilities on these trees are of interest. We'll discuss some desirable properties of such probabilities and two parameterized models with these properties: the alpha and beta models. The shape of real evolutionary trees will also be discussed if there is time.


12:00 - 12:30 pm.
Fu Liu, University of California at Davis.
The volume of the Birkhoff polytope.

We provide an explicit combinatorial formula for the volume of the Birkhoff polytope. We do this by finding the multivariate generating function for the lattice points of the polytope. Our basic method is Barvinok's algorithm, which involves describing a triangulation of the dual cone to each vertex cone. We use toric ideals and Groebner bases to compute the triangulation. This is joint work with Jesus De Loera and Ruriko Yoshida.


02:00 - 02:30 pm.
Carol Meyers, Lawrence Livermore National Laboratory.
Modeling and Solving the Pup Matching Problem.

In this talk we examine the Pup Matching problem, a network flow problem arising in the trucking industry. The goal is to assign small trailers ('pups') to be paired behind caps in an optimal manner, where each cab can have either one or two pups following it. This problem is a variant of a multicommodity flow problem where two commodities traversing an arc together incur the cost of the arc only once. We propose a new integer programming formulation for the problem, as well as identifying practical problems with such formulations and how variants of the problem are related to Nash equilibria.


02:45 - 03:15 pm.
Stephen Hartke, University of Illinois at Urbana-Champaign.
Graph classes characterized both by forbidden subgraphs and degree sequences.

Given a set $\mathcal{F}$ of graphs, a graph $G$ is $\mathcal{F}$-free if $G$ does not contain any member of $\mathcal{F}$ as an induced subgraph. We say that $\mathcal{F}$ is a degree-sequence-forcing set if, for each graph $G$ in the class $\mathcal{C}$ of $\mathcal{F}$-free graphs, every realization of the degree sequence of $G$ is also in $\mathcal{C}$. We prove that for any $k$ there are finitely many minimal degree-sequence-forcing sets with cardinality $k$. We also give a complete characterization of the degree-sequence-forcing sets $\mathcal{F}$ when $\mathcal{F}$ has cardinality at most two, and partial results when $\mathcal{F}$ has cardinality three. This is joint work with M.D. Barrus and M. Kumbhat.


04:00 - 05:00 pm.
Richard Scott, Santa Clara University.
Growth series for vertex-regular cube complexes.

For any Coxeter group $W$, there is a well-known recursive formula for its growth series relative to the standard generating set. If $W$ is right-angled, there is a natural cube complex on which it acts, and the growth series for $W$ can be interpreted as a generating function for the number of vertices at a given distance to a fixed vertex. Since $W$ acts transitively on the vertices of the Davis complex, the links of the vertices are all isomorphic (as simplicial complexes), and the formula for the growth series is a rational function involving only the $f$-vector of this link. In this talk, I will describe a more general class of vertex-regular cube complexes arising from "mock reflection groups", and show that the same formula for the growth series holds.