Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, March 10, 2015, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Hidefumi Hiraishi (University of Tokyo)

Excluded Minors of Rank 3 for Orientable and Representable Matroids

In graph theory, graph minor theorem by Robertson and Seymour is a monumental result which states that any minor-closed class of graphs has just a finite number of excluded minors, i.e. forbidden patterns minimal with respect to minor operations. This implies that excluded minors play a crucial role to characterize graph classes.
Matroid is a combinatorial abstraction of graphs, point configurations and so on. While minor operation can be naturally extendable from graphs to matroids, characterization by a finite list of excluded minors is not always possible even for fundamental classes. In this talk, we focus on two fundamental classes known to have infinitely many excluded minors: orientable matroids and matroids representable over an infinite field. A matroid is orientable, if it can be extended to an oriented matroids. For a field $\mathbb{F}$, a matroid is $\mathbb{F}$-representable, if some point configuration on the projective space over $\mathbb{F}$ has the matroid as an underlying structure. We investigate whether the number of excluded minors becomes finite or remains infinite under taking unions and intersections, and then obtain the following result: for an infinite field $\mathbb{F}$, there exist infinitely many excluded minors of rank 3 for both the unions and the intersections of orientable matroids and $\mathbb{F}$-representable matroids. This shows that, even restricting the rank, the characterization by excluded minors is difficult.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login