Matchings in Bipartite Graphs and the Generalized Permutohedra

Suho Oh (오수호)

Department of Mathematics, MIT, Cambridge, MA, USA

Department of Mathematics, MIT, Cambridge, MA, USA

2011/1/21 Fri 4PM-5PM

A transversal matroid is a collection of objects that encodes maximal matchings in a bipartite graph. Generalized permutohedra is a class of polytopes obtained by deforming the permutohedron. We introduce a nice bijection that allows one to view transversal matroids as set of lattice points inside a generalized permutohedron. As a corollary, we solve a special case of the 30-year old conjecture by Stanley on matroids and pure O-sequences. The talk will be elementary and purely combinatorial.

Tags: 오수호