UW Combinatorics Seminar

Title: The greedy algorithm, matroid polytopes and shifted simplicial complexes

Jose Samper

Wednesday May 25, 4:00pm-5:10pm
Padelford C-401

Pre-Seminar 3:30pm-3:55pm in PDL C-401

ABSTRACT

Matroid polytopes are fascinating geometric and combinatorial objects arising in optimization and algebraic geometry. They are the 01 polytopes in $\mathbb{R}^n$ whose edges are parallel to the root system of type A. Their geometry encodes a lot of information of the matroid beautifully. For example, the hyperplane description is given in terms of the rank function, the normal fan is a coarsening of the braid arrangement and the face structure enjoys deep connections with the Hopf monoid of matroids. Pure shifted simplicial complexes are a remarkable class of simplicial complexes used quite often in $f$-vector theory. They are equipped with a natural order of the groundset and satisfy a relaxed version of the well known greedy algorithm and have a rank function that is almost semimodular. This in particular suggests that the convex hull of the indicator vectors of facets of a pure shifted complex should look very similar to a matroid polytope. Using this we define two classes of ordered complexes that interpolate between shifted complexes and ordered matroids and show a lot of evidence that says we should expect geometric theory explaining this phenomenon.

In the preseminar I will talk about matroid polytopes and some of its beautiful combinatorics that I won't be able to describe during the talk.



Return to seminar home page



Sara Billey, Combinatorics Seminar, Mathematics Department, University of Washington

Page created on June 03, 2016 at 02:11 PM Copyright © 1998-2016, Sara C. Billey. All rights reserved.