Linear Matroid Matching in the Oracle Model

Explore a lecture on linear matroid matching in the oracle model presented by Gyula Pap at the Hausdorff Center for Mathematics. Delve into the challenges of solving linear matroid matching problems when matrix representations are not provided, focusing on cases where the matroid is only known through an independence oracle. Discover how this approach eliminates the need for linear algebraic computation by utilizing repeated oracle-calls along alternating paths. Learn about the method's roots in Gabow and Stallmann's work and how it recovers a similar combinatorial structure. Gain insights into applications in connectivity, rigidity, and count matroids. This 44-minute talk, part of the Hausdorff Trimester Program on Combinatorial Optimization, offers a deep dive into advanced concepts in matroid theory and algorithmic problem-solving.

Gyula Pap: Linear matroid matching in the oracle model