Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Mittagsseminar Talk Information |
Date and Time: Tuesday, March 10, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Hidefumi Hiraishi (University of Tokyo)
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