Graph flows and partial order polytopes
Jessica Striker
Abstract: Given a finite, loopless graph, its flow polytope consists of assignments of weights to the edges satisfying certain conservation constraints. Given a finite poset, we obtain the order polytope as assignments of weights on the vertices which respect the partial order. Given a finite set of matrices, we can define a polytope as their convex hull. We find a surprising correspondence between all three perspectives on a face of the alternating sign matrix polytope and discuss the implications of this correspondence to mysterious volume questions on related polytopes. This is work in progress with Karola Meszaros and Alejandro Morales.
I got 99 problems, but Dr. Shreve's homework ain't one.
Lindsay Erickson
Abstract: This talk explores some of the favorite past problems and topics that Dr. Shreve assigned
in his courses over the last few years of his career. We will look at a problem that has a
mouse eating a block of cheese, 3-coloring the K_16
without monochromatic triangles, constructing graphs with uncountably many thick ends, along with other countable problems.
To prove some of these problems, we invoke the pigeon hole principal and favorite counting
arguments. Along the way, we will look at how Dr. Shreve's assigned problems shaped young
mathematicians in their research focus.
Reversal Ratio of Partially Ordered Sets
Mitch Keller
Abstract: A linear extension of a partially ordered set is a total order on the same ground set that respects the partial order. The linear extension graph of a partially ordered set P has as its vertex set the set of all linear extensions of P. Two vertices are adjacent in the linear extension graph if and only if the corresponding linear extensions differ in the transposition of a single pair of incomparable elements. The linear extension diameter of P is the diameter of its linear extension graph. In terms of linear extensions, the linear extension diameter is the maximum over all pairs of linear extensions L_1, L_2 of P of the
number of incomparable pairs appearing in opposite orders in L_1 and L_2. We define the reversal ratio of P to be its linear extension diameter divided by the total number of incomparable pairs.
This talk considers several extremal questions on the reversal ratio of posets. In particular, we demonstrate a family of posets with reversal ratio tending to zero as the number of points increases. We also examine bounds on the reversal ratio in terms of the dimension and width of a poset. Bounds in terms of width have proven particularly interesting and challenging, even for width 3. This is joint work with Graham Brightwell.
