Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Matroids: Matroid Intersection

In course

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many ...

Description

This lecture covers the concept of matroids, focusing on matroid intersection and the properties of subsets of a ground set. The instructor explains the definition of matroids, their intersection, and provides examples of matroids such as uniform matroids and truncated matroids. The lecture also delves into the application of matroids in bipartite matching and colorful spanning in graphs.

Instructors (3)

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Matroid

In combinatorics, a branch of mathematics, a matroid ˈmeɪtrɔɪd is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

Graphic matroid

In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid (but this should not be confused with matroids of rank 3, which generalize planar point configurations); these are exactly the graphic matroids formed from planar graphs.

Matroid rank

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks. The rank function is one of the fundamental concepts of matroid theory via which matroids may be axiomatized. Matroid rank functions form an important subclass of the submodular set functions.

Matroid representation

In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra. A linear matroid is a matroid that has a representation, and an F-linear matroid (for a field F) is a matroid that has a representation using a vector space over F.

Vámos matroid

In mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished manuscript in 1968. The Vámos matroid has eight elements, which may be thought of as the eight vertices of a cube or cuboid. The matroid has rank 4: all sets of three or fewer elements are independent, and 65 of the 70 possible sets of four elements are also independent.

Related lectures (48)

Unweighted Bipartite Matching

Introduces unweighted bipartite matching and its solution using linear programming and the simplex method.

Graph Algorithms: Ford-Fulkerson and Strongly Connected Components

Discusses the Ford-Fulkerson method and strongly connected components in graph algorithms.

Polynomial Identity Testing

Covers polynomial identity testing using oracles and random point evaluation, with applications in graph theory and algorithmic aspects.

Algorithms: Union Find and Minimum Spanning Trees

Discusses Union-Find data structures and Minimum Spanning Trees, covering algorithms and their applications in network design and optimization.

Linear Programming Duality