Georgia Institute of Technology College of Sciences

The flow polytope associated to an acyclic graph is the set of all nonnegative flows on the edges of the graph with a fixed netflow at each vertex. We will examine flow polytopes arising from permutation matrices, alternating sign matrices and Tesler matrices. Our inspiration is the Chan-Robins-Yuen polytope (a face of the polytope of doubly-stochastic matrices), whose volume is equal to the product of the first n Catalan numbers (although there is no known combinatorial proof of this fact!). The volumes of the polytopes we study all have nice product formulas.

It is well known that periodic orbits give all the information about dynamical systems, at least for expanding maps, for which the periodic orbits are dense. This turns out to be true in dimensions 1 and 2, and false in dimension 4 or higher.We will present a proof that two $C^\infty$ expanding maps of the circle, which are topologically equivalent are $C^\infty$ conjugate if and only if the derivatives or the return map at periodic orbits are the same.

We study stable marriage where individuals strategically submit private preference information to a publicly known stable marriage algorithm. We prove that no stable marriage algorithm ensures actual stability at every Nash equilibrium when individuals are strategic. More specifically, we show that any rational marriage, stable or otherwise, can be obtained at a Nash equilibrium. Thus the set of Nash equilibria provides no predictive value nor guidance for mechanism design. We propose the following new minimal dishonesty equilibrium refinement, supported by experimental economics results: an individual will not strategically submit preference list L if there exists a more honest L' that yields as preferred an outcome. Then for all marriage algorithms satisfying monotonicity and IIA, every minimally dishonest equilibrium yields a sincerely stable marriage. This result supports the use of algorithms less biased than the (Gale-Shapley) man-optimal, which we prove yields the woman-optimal marriage in every minimally dishonest equilibrium. However, bias cannot be totally eliminated, in the sense that no monotonic IIA stable marriage algorithm is certain to yield the egalitarian-optimal marriage in a minimally dishonest equilibrium – thus answering a 28-year old open question of Gusfield and Irving's in the negative. Finally, we show that these results extend to student placement problems, where women are polygamous and honest, but not to admissions problems, where women are both polygamous and strategic. Based on joint work with Craig Tovey at Georgia Tech.

Continuing from last time, we will discuss Hilden and Montesinos' result that every smooth closed oriented three manifold is a three fold branched cover over the three sphere, and also there is a representation by bands.